시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"두 개의 연결된 목록의 교차점을 가져 오는 함수 작성"문제는 두 개의 연결된 목록이 제공된다는 것을 나타냅니다. 그러나 그들은 독립적 인 연결 목록이 아닙니다. 그들은 어느 시점에서 연결됩니다. 이제이 두 목록의 교차점을 찾아야합니다.
예
1 -> 2 \ 5 -> 6 / 3 -> 4
Point of intersection: 5
설명 : 입력에는 1, 2, 5, 6 및 3, 4, 5, 6의 두 개의 연결 목록이 표시됩니다. 둘 다 값이 5 인 노드에서 병합됩니다. 따라서 출력은 5입니다.
접근
문제는 설명하기 간단합니다. 두 가지가있다 연결 목록 그러나 그들은 어느 시점에서 결합되거나 상호 연결됩니다. 결합 지점 이전에는 두 연결 목록이 서로 다른 노드를 가지며 결합 노드 이후에 있습니다. 단일 목록으로 표시됩니다. 그렇다면 문제는 그러한 노드 (또는 포인트)를 어떻게 찾을 수 있는가입니다. 문제에 대한 가능한 답변 / 해결 방법이 많이있을 수 있습니다. 그러나 가장 간단한 방법은 연결 목록의 길이를 찾는 것입니다. 솔루션이 간단 할 때마다 시간 제한을 통과하는 것은 효율적이지 않습니다. 그러나 여기서는 그렇지 않습니다. 이 솔루션은 효율적이고 간단합니다.
설명
이 솔루션에서는 두 연결 목록의 길이를 찾을 것입니다. 그리고 더 긴 연결 목록의 머리 부분을 (레나 - 렌비) 노드. 여기 레나 및 렌비 연결 목록 A와 B의 길이를 각각 나타냅니다. 그러나 우리는 왜 이것을 했습니까?
공통 연결 목록의 길이는 z이고 더 긴 목록의 길이는 x + z 더 짧은 연결 목록은 y + z. 그래서 지금까지 우리는 lenA – lenB 더 긴 연결 목록 위에. 그건 (x + z – (y + z)) = x – y. 이것은 우리가 현재 서있는 노드가 길이를 가질 때까지 더 긴 연결 목록 위로 이동했음을 의미합니다. y 더 짧은 연결 목록의 헤드의 결합 노드에서. 그런 다음 두 연결 목록에서 동시에 이동하고 현재 노드가 모두 같은지 확인합니다. 그렇다면 교차점을 찾은 것입니다. 그러나 연결 목록이 끝날 때까지 그러한 지점을 찾지 못하면. 그러면 교차점이 없음을 나타냅니다.
이것이 두 개의 연결된 목록의 교차점을 얻는 함수를 작성하는 방법입니다.
암호
두 연결 목록의 교차점을 찾는 C ++ 코드
#include <bits/stdc++.h> using namespace std; struct ListNode{ int data; ListNode *next; }; ListNode* create(int data){ ListNode* tmp = new ListNode(); tmp->data = data; tmp->next = NULL; return tmp; } int length(ListNode *tmp){ int cnt = 0; while(tmp != NULL){ cnt++; tmp = tmp->next; } return cnt; } ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA = length(headA); int lenB = length(headB); if(lenA > lenB){ int cnt = lenA - lenB; while(cnt--) headA = headA->next; } else { int cnt = lenB - lenA; while(cnt--) headB = headB->next; } while(headA != NULL && headB != NULL){ if(headA == headB) return headA; headA = headA->next; headB = headB->next; } return NULL; } int main(){ ListNode *headA = create(1); headA->next = create(2); ListNode *headB = create(3); headB->next = create(4); headA->next->next = headB->next->next = create(5); headA->next->next->next = headB->next->next->next = create(6); cout<<"Intersection at node: "; cout<<getIntersectionNode(headA, headB)->data<<endl; }
Intersection at node: 5
두 연결 목록의 교차점을 찾는 Java 코드
import java.util.*; class ListNode{ int data; ListNode next; } class Main{ static ListNode create(int data){ ListNode tmp = new ListNode(); tmp.data = data; tmp.next = null; return tmp; } static int length(ListNode tmp){ int cnt = 0; while(tmp != null){ cnt++; tmp = tmp.next; } return cnt; } public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = length(headA); int lenB = length(headB); if(lenA > lenB){ int cnt = lenA - lenB; while(cnt-- > 0) headA = headA.next; } else { int cnt = lenB - lenA; while(cnt-- > 0) headB = headB.next; } while(headA != null && headB != null){ if(headA == headB) return headA; headA = headA.next; headB = headB.next; } return null; } public static void main(String[] args){ ListNode headA = create(1); headA.next = create(2); ListNode headB = create(3); headB.next = create(4); headA.next.next = headB.next.next = create(5); headA.next.next.next = headB.next.next.next = create(6); System.out.print("Intersection at node: "); System.out.print(getIntersectionNode(headA, headB).data); } }
Intersection at node: 5
복잡성 분석
시간 복잡성
의 위에), 연결 목록의 각 노드를 정확히 한 번 실행했기 때문입니다. 교차점이있는 경우 해당 노드에 도달하면이를 반환합니다. 그렇지 않으면 각 노드가 한 번만 순회됩니다. 이것은 시간 복잡성이 선형임을 증명합니다.
공간 복잡성
O (1), 우리가 저장 한 유일한 것은이 알고리즘이 일정한 공간만을 차지하게하는 연결 목록의 길이입니다.
