Sıralanmış Bağlı Siyahıya Node əlavə edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur alma microsoft
Bağlı siyahı Əlaqəli siyahı çeşidləyiciBaxılıb 436

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"Sıralanmış əlaqəli siyahıda qovşaq əlavə edin" problemində a əlaqəli siyahı. Sıralanmış əlaqəli siyahıya sıralanmış bir şəkildə yeni bir qovşaq daxil edin. Sıralanmış bağlı siyahıya bir qovşaq əlavə etdikdən sonra son əlaqəli siyahı sıralanmış əlaqəli siyahı olmalıdır.

misal

4 7 10 
3 5 15
3 4 5 7 10 15

Yanaşma

Sıralanmış bağlantılı siyahıya bir qovşaq əlavə etməliyik ki, bağlı siyahıya qovşaq əlavə etdikdən sonra sıralanmış qalacaq. Düyünü düzgün vəziyyətdə yerləşdirməliyik. 

Bağlı siyahıya daxil etmək istədiyimiz dəyərlə yeni bir qovşaq yaratmalıyıq. Doğru mövqeyi tapmaq üçün əlaqələndirilənləri təkrarlayın. Bağlı siyahıda qovşaqların dəyəri əlaqəli siyahıya daxil etmək istədiyimizdən az olana qədər əlaqəli siyahıdan təkrar edirik. Daxil etməli olduğumuz yeni düyünün dəyərindən az bir dəyəri olan əvvəlki bir qovluğu da saxlayırıq. Yeni qovşaq dəyərindən böyük bir dəyərə sahib olan əyri düyünü tapdıqdan sonra.

Sonra new_node-a növbəti göstərici curr nodu göstərir. Curr node dəyəri new_node'dan böyük olduğundan. Əgər əvvəlki qovşaq boşdursa, deməli new_node ən kiçik qovşaqdır, o zaman əlaqəli siyahının əvvəlində yerləşdirilməlidir. Beləliklə başı bu düyünə yönəldirik. Əvvəlcədən sıfır deyilsə, əvvəlkini new_node-un yanına bağlayırıq.

Alqoritm

  1. Bağlı siyahıya daxil etmək istədiyimiz dəyər ilə bir qovşaq yaradın.
  2. İki göstərici düzəldin və əvvəlcədən düzəldin, baş qovşağına yönəldin və əvvəlcə boşdur.
  3. Bağlı siyahını qovşaqlarda yeni_düyün dəyərindən az dəyərə qədər təkrarlayın.
  4. Cur_ node yanında yeni_düyünü göstərir,
  5. Ön düyün boşdursa, baş düyün bu düyünü göstərir, əks halda əvvəlcədən new_node olur.

Izahat

C ++ proqramı, Sıralanmış Bağlı Siyahıya Node əlavə etmək

#include<bits/stdc++.h>
using namespace std;

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        int val;
        ListNode(int a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    void sortedInsert(int val){
        ListNode* node = new ListNode(val);
        ListNode* pre = NULL;
        ListNode *curr = head;

        while(curr!=NULL && val>curr->val){
            pre = curr;
            curr = curr->next;
        }

        node->next = curr;
        if(pre==NULL){
            head = node;
        }else{
            pre->next = node;
        }
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};


int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(10);
  list->addAtHead(7);
  list->addAtHead(4);
  list->print_list();
    list->sortedInsert(5);
    list->sortedInsert(3);
    list->sortedInsert(15);

    list->print_list();
}

Sıralanmış Bağlı Siyahıya Node əlavə etmək üçün Java Proqramı

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(10);
    obj.addAtHead(7);
    obj.addAtHead(4);
    obj.printList();
    
    obj.sortedInsert(2);
    obj.sortedInsert(5);
    obj.sortedInsert(15);
    obj.printList();
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      public Node getNodeAt(int index){
          Node curr = head;
          while(index-- > 0){
              curr = curr.next;
          }
          
          return curr;
      }
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
      public void sortedInsert(int val) {
          Node newNode = new Node(val);
          Node previous = null;
          Node current = head;
  
          while (current != null && val > current.val) {
              previous = current;
              current = current.next;
          }
  
          newNode.next = current;
      if (previous == null)
          head = newNode;
      else
          previous.next = newNode;
  
      }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
4 6 7
2 5
2 4 5 6 7

Sıralanmış əlaqəli siyahıya nodu əlavə etmək üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n əlaqəli siyahıda mövcud olan qovşaqların sayıdır. Burada sadəcə başlanğıcdan əlaqəli siyahıdan keçirik və düyünü düzgün vəziyyətinə əlavə edirik.

Kosmik Mürəkkəblik

O (1) çünki heç bir köməkçi yer yaratmırıq. Burada əlavə bir yer istifadə etmədən istədiyi yerə bir qovşaq əlavə edirik.

Crack Sistemi Dizayn Müsahibələri
Translate »