시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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), 우리가 저장 한 유일한 것은이 알고리즘이 일정한 공간만을 차지하게하는 연결 목록의 길이입니다.
