시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
"두 개의 노드가 트리에서 동일한 경로에 있는지 확인"문제는 n 항 트리 (directed acyclic graph) 뿌리 뿌리 노드 단방향 정점 사이의 가장자리. 또한 쿼리 목록이 제공됩니다. q.
- 목록 q의 각 쿼리는 두 개의 꼭지점 u 및 v로 구성됩니다.
- “예”if 노드 u와 v는 같은 길을 따라 누워 유래 뿌리 꼭지점.
- Else print“아니”if 노드 u & v는 다른 길을 따라 누워 유래 뿌리 꼭지점.
예
두 노드가 트리에서 동일한 경로에 있는지 확인하는 방법
아이디어는 수행하는 것입니다 DFS 에 뿌리 마디. 이 DFS 순회는 먼저 마지막 깊이까지 루트의 각 하위 트리를 방문합니다. 즉, 마지막 리프 정점까지 각 고유 선형 경로를 방문한 다음 다음 선형 경로로 이동합니다.
중히 여기다,
제 시간에 – 노드의 intime은 루트 노드에서 시작하여 DFS 순회를 수행하는 동안 처음 방문한 시간입니다. 입장 시간 DFS 순회 중 노드의.
외출 – 노드의 아웃 타임은 모든 자식이 방문한 후 방문한 시간입니다. 이것은 루트 노드로 향하는 경로를 따라 돌아 오는 동안 발생합니다. 종료 시간 DFS 순회 중 노드의.
노드 u & v가 동일한 경로를 따라있는 경우 :
- u가 v의 부모라고 가정하면 intime of u <intime of v & u의 아웃 타임> v의 아웃 타임.
- 또는 v가 u의 부모라고 가정하면 v의 intime <u의 intime & v의 outtime> u의 outtime.
- 일반적으로, 두 노드가 같은 경로에있을 때 하나는 부모이고 다른 하나는 자식. 이 경우 DFS 순회 후 :
- 부모의 시간 <자식의 시간
- 부모의 외출> 자녀의 외출
1. Perform DFS traversal from the given root node and for each node calculate entry time and exit time using intime[ ] and outtime[ ] arrays. 2. So after the DFS traversal is complete. Process the query list q. Each query in q consists of two values u and v. 3. If intime[u] < intime[v] and also outtime[u] > outtime[v], print "YES". 4. Or if intime[v] < intime[u] and also outtume[v] > outtime[u], print "YES". 5. If conditions 3 and 4 are false, then print "NO". 6. If conditions 3 and 4 are true, this signifies that u & v lie along the same path originating from the root. 7. If condition 5 is true, then it signifies that u & v do not lie along the same path originating from the root.
알고리즘은 다음과 같습니다.
암호
트리에서 두 노드가 동일한 경로에 있는지 확인하는 C ++ 프로그램
#include <iostream> #include <bits/stdc++.h> using namespace std; /* variable to keep track of intime and outtime values for each vertex */ int times = 0; /* function to perform DFS from root nodes to all the leaves & calculate entry time (intime) & exit time (outtime) for each vertex */ void DFS(int root,vector <int> graph[],vector <int> &intime,vector<int> &outtime) { intime[root] = ++times; for(auto i : graph[root]) DFS(i,graph,intime,outtime); outtime[root] = ++times; return; } /* function that returns true if nodes u and v lie along the same path else return false */ bool query(int u,int v,vector <int> intime,vector <int> outtime) { return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || (intime[v] < intime[u] && outtime[v] > outtime[u])); } int main() { /* Define 1.number of vertices 2.root vertex 3.edges */ int V = 9; int root = 0; vector<vector<int>> Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}}; /* construct the graph */ vector <int> graph[V]; for(auto edge : Edges) graph[edge[0]].push_back(edge[1]); /* Define vectors that store entry time(intime) & exit time(outtime) for each vertex of the tree */ vector <int> intime(V,0); vector <int> outtime(V,0); /* perform DFS traversal to fill intime & outtime vectors */ DFS(root,graph,intime,outtime); /* Define query vertices */ vector<vector<int>> q = {{0,5},{2,7},{1,8}}; for(auto i : q) { if(query(i[0],i[1],intime,outtime)) cout<<"YES"; else cout<<"NO"; cout<<endl; } return 0; }
YES YES NO
찾을 Java 코드 두 노드가 트리에서 동일한 경로에 있는지 확인
import java.io.*; import java.util.*; class TutorialCup { /* variable to keep track of intime and outtime values for each vertex */ static int times = 0; /* function to perform DFS from root nodes to all the leaves & calculate entry time (intime) & exit time (outtime) for each vertex */ static void DFS(int root,ArrayList<ArrayList<Integer>> graph,int [] intime,int [] outtime) { intime[root] = ++times; Iterator itr = graph.get(root).iterator(); while(itr.hasNext()) { int i = (Integer)itr.next(); DFS(i,graph,intime,outtime); } outtime[root] = ++times; return; } /* function that returns true if nodes u and v lie along the same path else return false */ static boolean query(int u,int v,int [] intime,int [] outtime) { return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || (intime[v] < intime[u] && outtime[v] > outtime[u])); } public static void main (String[] args) { /* Define 1.number of vertices 2.root vertex 3.edges */ int V = 9; int root = 0; int [][] Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}}; /* construct the graph */ ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>(); for(int i=0;i<V;i++) graph.add(new ArrayList<Integer>()); for(int i=0; i<Edges.length; i++) graph.get(Edges[i][0]).add(Edges[i][1]); /* Define vectors that store entry time(intime) & exit time(outtime) for each vertex of the tree */ int [] intime = new int[V]; int [] outtime = new int[V]; /* perform DFS traversal to fill intime & outtime vectors */ DFS(root,graph,intime,outtime); /* Define query vertices */ int [][] q = {{0,5},{2,7},{1,8}}; for(int i=0; i<q.length; i++) { if(query(q[i][0],q[i][1],intime,outtime)) System.out.println("YES"); else System.out.println("NO"); } } }
YES YES NO
복잡성 분석
시간 복잡성
T (n) = O (n), n = 노드 수. 트리의 노드를 가로 지르는 DFS를 사용했기 때문입니다. 따라서 시간 복잡도는 선형입니다.
공간 복잡성
A (n) = O (n), intime [] 및 outtime [] 배열 사용. 이 두 어레이의 크기는 노드 수에 따라 다릅니다. 따라서 공간 복잡성도 선형입니다.
