Giải mã cuộc phỏng vấn mã hóa, ấn bản lần thứ 6, 2.8

Question

Báo cáo vấn đề: Được cung cấp danh sách liên kết vòng tròn, triển khai thực hiện một bản ngã trả về nút ở đầu vòng lặp.

Phím trả lời đưa ra giải pháp phức tạp hơn những gì tôi đề xuất. Có gì sai với tôi ?:

public static Node loopDetection(Node n1) { 
    ArrayList<Node> nodeStorage = new ArrayList<Node>(); 

    while (n1.next != null) { 
     nodeStorage.add(n1); 
     if (nodeStorage.contains(n1.next)) { 
      return n1; 
     } 
     else { 
      n1 = n1.next; 
     } 
    } 

    return null; 
} 

Answer 1

giải pháp của bạn là O(n^2) thời gian (mỗi trong ArrayList là O(n) thời gian) và O(n) không gian (để lưu trữ nodeStorage), trong khi các giải pháp "phức tạp hơn" là O(n) thời gian và O(1) không gian.

Cuốn sách này cung cấp các giải pháp sau đây, để bất cứ ai quan tâm, đó là O(n) thời gian và O(1) không gian:

Nếu chúng ta di chuyển hai con trỏ, một với tốc độ 1 và khác với tốc độ 2, họ sẽ kết thúc lập cuộc họp nếu danh sách được liên kết có vòng lặp. Tại sao? Hãy suy nghĩ về hai chiếc xe đang lái xe trên đường đua — xe hơi nhanh hơn sẽ luôn vượt qua tốc độ chậm hơn! Phần phức tạp ở đây là tìm sự bắt đầu của vòng lặp. Hãy tưởng tượng, giống như một sự tương tự, hai người chạy đua vòng quanh một đường đua, một đường chạy số nhanh gấp hai lần đường còn lại. Nếu họ bắt đầu ở cùng một địa điểm, khi họ sẽ gặp nhau lần sau, ? Họ sẽ gặp nhau vào lúc bắt đầu vòng tiếp theo. Bây giờ, giả sử Fast Runner có khởi đầu là k mét trên n vòng đua . Khi nào họ sẽ gặp nhau? Họ sẽ gặp k mét trước khi bắt đầu vòng đua tiếp theo . Fast Runner sẽ thực hiện các bước k + 2 (n - k) , bao gồm cả khởi đầu, và Slow Runner sẽ thực hiện các bước n - k . Cả hai bước này sẽ là k bước trước khi bắt đầu vòng lặp.) , quay trở lại vấn đề, khi Fast Runner (n2) và Slow Runner (n1) là di chuyển quanh danh sách liên kết vòng tròn của chúng tôi, n2 sẽ có một khởi đầu trên vòng lặp khi n1 đi vào. Cụ thể, nó sẽ có khởi đầu bằng k, trong đó k là số nút trước vòng lặp. Vì n2 có đầu bắt đầu của các nút k, n1 và n2 sẽ gặp các nút k trước khi bắt đầu vòng lặp . Vì vậy, bây giờ chúng ta biết những điều sau đây: 1. Đầu là nút k từ LoopStart (theo định nghĩa). 2. MeetingPoint cho n1 và n2 là k nodes từ LoopStart (như được hiển thị ở trên). Vì vậy, nếu chúng ta di chuyển n1 trở lại Head và giữ n2 tại MeetingPoint, và di chuyển chúng ở cùng một tốc độ, chúng sẽ gặp nhau tại LoopStart.

LinkedListNode FindBeginning(LinkedListNode head) { 
    LinkedListNode n1 = head; 
    LinkedListNode n2 = head; 

    // Find meeting point 
    while (n2.next != null) { 
     n1 = n1.next; 
     n2 = n2.next.next; 
     if (n1 == n2) { 
     break; 
     } 
    } 
// Error check - there is no meeting point, and therefore no loop 
    if (n2.next == null) { 
     return null; 
    } 
    /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps 
    /* from the Loop Start. If they move at the same pace, they must 
    * meet at Loop Start. */ 
    n1 = head; 
    while (n1 != n2) { 
     n1 = n1.next; 
     n2 = n2.next; 
    } 
    // Now n2 points to the start of the loop. 
    return n2; 
    } 

Answer 2

Có giải pháp được đưa ra bởi amit. Vấn đề là bạn có biết hay không, nhưng bạn sẽ không thể tìm ra nó trong một cuộc phỏng vấn. Vì tôi có không bao giờ cần phải tìm một chu kỳ trong danh sách được liên kết, việc biết nó là vô nghĩa, ngoại trừ việc phỏng vấn qua. Vì vậy, đối với một người phỏng vấn, nói điều này như một câu hỏi phỏng vấn, và mong đợi câu trả lời của amir (đó là tốt đẹp bởi vì nó có thời gian tuyến tính và không gian thêm không), là khá ngu ngốc.

Vì vậy, giải pháp của bạn là tốt, ngoại trừ việc bạn nên sử dụng bảng băm và bạn phải đảm bảo rằng băm bảng băm tham chiếu đến các nút chứ không phải nút. Giả sử bạn có một nút chứa chuỗi và con trỏ "tiếp theo" và hàm băm sẽ băm chuỗi và so sánh các nút bằng nhau nếu các chuỗi bằng nhau. Trong trường hợp đó, bạn sẽ tìm thấy nút đầu tiên với một chuỗi trùng lặp, và không phải là nút ở đầu vòng lặp, trừ khi bạn cẩn thận.

(giải pháp của amir có vấn đề rất giống với ngôn ngữ mà == so sánh các đối tượng chứ không phải tham chiếu. Ví dụ trong Swift, bạn phải sử dụng === (so sánh tham chiếu) chứ không phải == (so sánh các đối tượng)).