Bağlı Siyahıda bir döngə aşkar edin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Facebook Goldman Sachs google microsoft
Bağlı siyahı Əlaqəli siyahıBaxılıb 983

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

"Bağlı siyahıda bir dövrü aşkar et" problemində a əlaqəli siyahı. Döngünün olub olmadığını tapın. Bağlı siyahıda bir döngə varsa, əlaqəli siyahıdakı bəzi qovşaqlar eyni əlaqəli siyahıda əvvəlki qovşaqlardan birini göstərəcəkdir.

misal

1 2 3 4 5
1 2 3 4 5

Bağlı Siyahıda bir döngə aşkar edinPin

Yanaşma

Biz istifadə edəcəyik Tısbağa və Hare bu problemi həll etmək üçün iki göstəricinin saxlandığı yanaşma.

  1. Yavaş göstərici ( tısbağa) // Hər dəfə yalnız 1 addım köçürür
  2. Sürətli Göstərici (dovşan) // Hər dəfə 2 addım köçürür

Hər təkrarda göstəricilərdən birini iki addım, digəri isə bir addım hərəkət etdiririk. Yəni iki göstərici tısbağa və dovşan var.

Bu alqoritmə əsasən iki hal yaranır:

  1. Dovşan əlaqəli siyahının (null) sonuna çatacaq, bu da onda heç bir dövr olmadığı anlamına gəlir.
  2. Dovşan tısbağa ilə qarşılaşacaq, yəni əlaqəli siyahıda bir dövrə var.

Hər addımda tısbağa 1 düyün, dovşan 2 düyün gəzir. Tısbağa 1 məsafə vahidi ilə uzaqlaşır, sonra dovşan 2 məsafə vahidi yaxınlığında olur. sanki hər addımda tısbağa hərəkətsiz qalır və dovşan 1 addım irəliləyir.

sübut

Bağlı Siyahıda bir döngə aşkar edinPin

Döngə uzunluğu, n = y + z

SlowPointer tərəfindən qət edilən məsafə (tısbağa) görüşmədən əvvəl = x + c1 * n + y

FastPointer tərəfindən qət edilən məsafə (dovşan) görüşmədən əvvəl = x + c2 * n + y

C1 və c2 sabitləri olduğu yerlərdə. FastPointer olduğundan (dovşan) yavaş göstəricinin iki qat sürəti ilə hərəkət edir (tısbağa), görüşmə nöqtəsinə çatdıqda isə hər ikisi üçün zaman sabitdir. Belə ki,

2 (x + c1 * n + y) = x + c2 * n

=> x + y = (2 * c1 - c2) * n => x + y = K * n (K sabitdir) => x = K * n - y => x = z

Beləliklə, yavaş bir göstəricini əlaqəli bir siyahının başlanğıcı üçün hərəkətə gətirərək və həm yavaş, həm də sürətli göstəricini bir anda bir nodu hərəkət etdirərək, ikisi də əlaqəli siyahıda döngənin başladığı nöqtəyə çatacaq.

Həyata keçirilməsi

Bağlı Siyahıda bir döngəni aşkar etmək üçün C ++ Proqramı

#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;
    }
    
    bool hasCycle() {
        ListNode *slow=head,*fast=head;
        
        while(fast && fast->next) {
            
            slow = slow->next;               
            fast = fast->next->next;        
            
            if(slow==fast) 
                return true;
        }
        
        return false; 
    }

    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);

    cout<<list->hasCycle();
}

Bağlı Siyahıda bir döngəni aşkar 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);
    System.out.println(obj.hasCycle());
    
  }
  
  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 boolean hasCycle() {
          if(head==null || head.next==null) return false;
          Node fast=head,slow=head;
          while(fast!=null && fast.next!=null){
              fast=fast.next.next;
              slow=slow.next;
              if(fast==slow) return true;
          }
          return false;
      }

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

Bağlı Siyahıda bir döngəni aşkar 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 əlaqəli siyahıdan keçirik və xətti vaxt aparan döngəni yoxlayırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

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