메모
면접 문제
4.7 순서 정하기
- 프로젝트의 리스트와 프로젝트들 간의 종속 관계(즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두 번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻)가 주어졌을 때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다.
4.8 첫 번째 공통 조상
- 이진 트리에서 노드 두 개가 주어졌을 때 이 두 노드의 첫 번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안 된다. 반드시 이진 탐색 트리일 필요는 없다.
4.9 BST 수열
- 배열의 원소를 왼쪽에서부터 차례로 트리에 삽임함으로써 이진 탐색 트리를 생성할 수 있다. 이진 탐색 트리 안에서 원소가 중복되지 않는다고 할 때, 해당 트리를 만들어 낼 수 있는 모든 가능한 배열을 출력하라.
4.10 하위 트리 확인
- 두 개의 커다란 이진 트리 T1과 T2가 있다고 하자. T1이 T2보다 훨씬 크다고 했을 때, T2가 T1의 하위 트리(subtree)인지 판별하는 알고리즘을 만들라. T1 안에 있는 노드 n의 하위 트리가 T2와 동일하면, T2는 T1의 하위 트리다. 다시 말해, T1에서 노드 n의 아래쪽을 끊어 냈을 때 그 결과가 T2와 동일해야 한다.
4.11 임의의 노드
- 이진 트리 클래스를 바닥부터 구현하려고 한다. 노드의 삽입, 검색, 삭제뿐만 아니라 임의의 노드를 반환하는 getRandomNode() 메서드도 구현한다. 모든 노드를 같은 확률로 선택해주는 getRandomNode 메서드를 설계하고 구현하라. 또한 나머지 메서드는 어떻게 구현할지 설명하라.
4.12 합의 경로
- 각 노드의 값이 정수(음수 및 양수)인 이진 트리가 있다. 이때 정수의 합이 특정 값이 되도록 하는 경로의 개수를 세려고 한다. 경로가 꼭 루트에서 시작해서 말단 노드에서 끝날 필요는 없지만 반드시 아래로 내려가야 한다. 즉, 부모노드에서 자식 노드로만 움직일 수 있다. 알고리즘을 어떻게 설계할 것인가?
댓글