반응형

[코딩 인터뷰 모음] 자료구조

반응형

1. What method would you use to look up a word in a dictionary? 

(사전 단어를 찾을 때 어떤 방법을 쓸것인가? )


=>해쉬를 쓰거나, 리스트로 저장되어 있을 경우 바이너리 서치


2. Imagine you have a closet full of shirts. What can you do to organize your shirts for easy retrieval? 

(옷장에 셔츠들이 꽉 차있다고 생각하자. 쉽게 셔츠를 고르기 위해서 어떻게 구성하면 되는가?)


=>색깔대로 혹은 종류대로 정렬하고 바이너리 서치


3. Write a function to find the middle node of a singly-linked list.

(싱글 링크드 리스트에서 정중앙의 노드를 찾는 함수를 구현하라.)


=> Two Pointer 방식으로 한 Pointer는 두 스텝 씩 뛰고 나머지 하나는 한 스텝 씩 뛰고 두 스텝 씩 뛰는 Pointer가 맨 끝에 다다를 경우 한 스텝씩 뛴 Pointer의 위치가 정중앙

public Node findMiddle(Node root){
Node oneStep = root;
Node twoStep = root;

while(twoStep.next != null){
twoStep = twoStep.next;
if(twoStep != null)
twoStep = twoStep.next;

oneStep = oneStep.next;
}

return oneStep;
}


4. Write a function to compare whether two binary trees are identical. Identical trees have the same key value at each position and the same structure.

(두 개의 이진 트리가 같다는 함수를 작성하라. 같은 트리는 각각의 위치에 같은 키값과 같은 구조를 가지고 있다.)


=> Recursive하게 구현 

public boolean compare(Node root1, Node root2){
if(root1 == null && root2 == null)
return true;
if(root1 != null && root2 != null){
return root1.val == root2.val &&
compare(root1.left, root2.left) &&
compare(root1.right, root2.right);
}
else
return false;
}


5. Write a program to convert a binary search tree into a linked list.

(이진 탐색 트리를 링크드 리스트로 변환하는 프로그램을 작성하라.)


=> 현 이진 탐색 트리는 작은 부분이 왼쪽 서브 트리, 큰 부분이 오른쪽 서브 트리에 있다고 가정하자. 다음 이진 탐색 트리 왼쪽을 중위 순회하는 함수를 작성하고 Node 값에 접근했을 때 링크드 리스트에 넣는다.


여기서 중요한 포인트는 이진 탐색 트리의 가장 오른족 부분이 트리의 중앙 부분에 연결되게 하는 것이다. pushToLinkedList를 쓰는 이유를 눈여겨 봐야한다. 

public void pushToLinkedList(Node prev, Node next){
if(prev.right != null)
pushToLinkedList(prev.right, next);
else
prev.right = next;
}

public Node binaryToLinkedList(Node binaryNode){
Node left = null, right = null;
if(binaryNode.left != null){
left = binaryToLinkedList(binaryNode.left);
binaryNode.left = null;
}
if(binaryNode.right != null){
right = binaryToLinkedList(binaryNode.right);
binaryNode.right = null;
}
if(left != null)
pushToLinkedList(left, binaryNode);
else
left = binaryNode;
if(right != null)
pushToLinkedList(left, right);
return left;
}


6. Implement an algorithm to reverse a linked list. Now do it without recursion.

(링크드 리스트를 뒤집는 알고리즘을 구현하시오. 재귀를 쓰지 않고 구현해야 하라.)


=> 3개의 변수를 이용해서 reverse를 구현한다.

public static Node reverseList(Node list){
Node next = null;
Node curr = list;
Node prev = list;

if(curr.next == null)
return list;

curr = curr.next;
if(curr.next == null){
curr.next = prev;
prev.next = null;
return curr;
}
while(curr.next != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

curr.next = prev;
list.next = null;

return curr;
}


7. What is the best data structure for maintaining URLs that have been visited by a Web crawler? Give an algorithm to test whether a given URL has already been visited, optimizing both space and time.

(웹 클로러가 방문한 사이트의 URL을 관리하기 위한 가장 좋은 자료 구조는 무엇인가? 주어진 URL이 이미 방문한 사이트인지 아닌지를 테스트하는 알고리즘을 제시하고 시간 및 공간복잡도를 최적화 하라.)


=> URL 문자열 리스트를 정렬하여 이진 탐색을 할 수 있다. 이 경우 m이 문자열의 최대 길이, n이 URL 문자열 개수라고 하면 O(m·logn)의 시간복잡도를 가진다. 공간복잡도는 O(m*n)이다. 


하지만 여기서 트라이 자료구조를 쓰면 시간 시간복잡도는 O(m)이다. 공간복잡도는 URL간 겹치는 부분이 많을 때 더 효율적으로 최적화되지만 최악의 경우 O(m*n)이다.


8. Reverse the words in a sentence—i.e., “My name is Chris” becomes “Chris is name My.” Optimize for time and space.

(문장에 있는 단어들을 뒤집어라, 예로들어 "My name is Chris"를 "Chris is name My"로 바꾸는 것이 그 예이다. 시간과 공간복잡도를 최적화하라)


=> 1. 전체 sentence를 한 번 뒤집는다. 2. 다음 각 단어들의 순서를 뒤집는다.

https://www.geeksforgeeks.org/reverse-words-in-a-given-string/


9. Determine whether a linked list contains a loop as quickly as possible without using any extra storage. Also, identify the location of the loop.

(추가적인 변수, 메모리를 쓰지 말고 링크드 리스트가 루프가 있는 지 판별하라. 또한 루프의 위치도 찾아라)


=> Two Pointers를 만들고 한 포인터는 slow pointer, 다른 포인터는 fast pointer로 지정한다. slow 포인터는 1step 씩 이동하며 fast 포인터는 2step 씩 이동한다. 만일 fast pointer가 링크드 리스트가 끝에 다다르면 루프가 없는 것이고 만일 slow pointer와 어느 한 점에서 만나면 루프가 존재하는 것이다.


만일 루프가 존재하여 slow pointer와 faster pointer가 한 점에서 만나면 slow pointer를 링크드 리스트 header에 위치시키고 같은 속도로 움직일 때 두 pointer가 만나는 지점이 바로 loop가 시작하는 곳이다. 자세한 내용은 아래 참조.

https://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/



10. You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi.  You may not use division. You can use extra memory. 

(순서가 정해지지 않은 n개의 정수를 가진 배열 X가 있다. n개의 요소들이 있는 배열 M을 구하라. 배열 M의 요소 Mi는 X 배열에서 Xi 요소만 뺀 나머지 요소들의 프로덕트다. ( 곱셈 ). 나눗셈을 사용하면 안되며 추가적인 메모리는 사용 가능하다.)


=> 1. 누적 프로덕션 P와 Q 구하기

P0=1,Pk=XkPk1=ki=1xi
Qn=1,Qk=XkQk+1=ni=kxi

2. M을 구하기
Mk=Pk1Qk+1,k[1,n]

public class Multiplication {
public static int[] product(int[] x) {
int[] M = new int[x.length];

for (int i = 0; i < x.length; i++) {
M[i] = product(x, M, i + 1, x.length);
}

return M;
}

private static int product(int[] x, int[] y, int i, int length) {
if (i == length)
return productLeft(x, i - 2, length);

return x[i] * productLeft(x, i - 2, length) * productRight(x, i + 1, length);
}

private static int productLeft(int[] x, int i, int length) {
if (i < 0)
return 1;

return x[i] * productLeft(x, i - 1, length);
}

private static int productRight(int[] x, int i, int length) {
if (i >= length)
return 1;

return x[i] * productRight(x, i + 1, length);
}
}


11. Give an algorithm for finding an ordered word pair (e.g., “New York”) occurring

with the greatest frequency in a given webpage. Which data structures would you

use? Optimize both time and space.

(주어진 웹사이트에서 가장 많은 빈도로 발생하는 순서 있는 단어쌍을 찾는 알고리즘을 제시하라. 어떤 자료구조를 쓸 것인가? 시간 및 공간복잡도를 최적화하라)


=> 해쉬 테이블 혹은 트라이를 쓰면 된다.

반응형

이 글을 공유하기

댓글

Designed by JB FACTORY