프로그래밍 면접 문제

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

 

프로그래밍 면접 문제 전체 목록입니다. 총 28개의 문제가 있고, 28은 완벽한 숫자(도널드 커누스가 언급했듯이)이기 때문에 여기에서 멈추는 것이 좋을 것 같습니다.

1. Array Pair Sum
정수 배열이 주어지면, 두 수를 더한 결과가 k가 되는 모든 숫자 쌍을 구하는 문제입니다.

2. Matrix Region Sum
정수형 행렬과 행렬 내 사각형 영역을 나타내는 좌표가 주어지면, 이 사각형 영역 안의 수를 모두 더한 값을 구하는 문제입니다. 프로그램은 동일한 행렬의 다른 사각형 영역에 대해서 여러번 실행됩니다.

3. Largest Continuous Sum
주어진 정수형 배열(양수, 음수 모두 포함)에서 가장 큰 연속 합계를 구하는 문제입니다.

4. Find Missing Element
음수가 아닌 정수로 채워진 배열이 있습니다. 첫 번째 배열 요소들을 이동시키고, 랜덤으로 특정 요소를 하나 삭제한 다음 두 번째 배열을 만듭니다. 이렇게 두 배열이 주어지면, 두 번째 배열에서 누락된 요소를 찾는 문제입니다.

5. Linked List Remove Nodes
정수를 저장하는 연결리스트와 정수 값이 주어지면, 연결 리스트에서 주어진 정수 값을 저장하고 있는 모든 노드를 삭제하는 문제입니다.

6. Combine Two Strings
3개의 문자열 str1, str2, str3이 있습니다. str3은 str1과 str2 문자열의 각 문자를 결합해서 만드는데, str1, str2 각 문자열의 왼쪽부터 오른쪽 순서로 각 문자의 순서는 유지시키면서 문자를 결합합니다. 예를 들어, str1=”abc”이고 str2=”def”일때, str3=”dabecf”인 경우, str3은 str1과 str2의 각 문자 순서를 유지한 상태에서 문자를 결합시켰기 때문에 유효한 문자열입니다. 따라서, 주어지는 3개의 문자열에 대해서 str3 문자열이 str1과 str2를 유효하게 조합해서 만든 문자열인지 확인하는 함수를 작성하는 것이 이번 문제입니다.

7. Binary Search Tree Check
주어진 이진 트리가 이진 탐색 트리(binary search tree)인지 확인하는 문제입니다.

8. Transform Word
원본 단어, 목표 단어 그리고 영어 사전이 주어지면, 원본 단어를 한번에 한 문자씩 변경/추가/제거를 통해서 목표 단어로 변환합니다. 단어를 변환하는 과정에서 나오는 중간 단어(intermediate word)는 모두 유효한 영어 단어여야 합니다. 중간 단어의 수가 가장 적은 변환 체인(transform chain)을 반환합니다.

9. Convert Array
배열 [a1, a2, …, aN, b1, b2, …, bN, c1, c2, …, cN]이 주어지면 이 배열을 일정한 크기의 추가 공간만 사용해서 [a1, b1, c1, a2, b2, c2, …, aN, bN, cN]와 같이 변환하는 문제입니다.

10. Kth Largest Element in Array
정수 배열이 주어지면 정렬 된 순서로 k 번째 요소를 찾습니다 (서로 구별되는 요소 중 k 번째 요소가 아닙니다). 따라서 배열이 [3, 1, 2, 1, 4]이고 k가 3인 경우, 정렬 된 순서의 세 번째 요소는 2입니다 (그러나 구별되는 요소 중 세 번째 요소는 3입니다).

 

 

11. All Permutations of String
문자열이 주어지면 그 문자열의 모든 순열을 생성하는 문제입니다.

12. Reverse Words in a String
문자열이 입력으로 주어지면, 모든 단어를 뒤집는 문제입니다. 좀 더 명확하게 예를 들어보겠습니다. 입력이 다음과 같을때: “Interviews are awesome!” 출력은 다음과 같습니다: “awesome! are Interviews”. 또한 문자열 맨 앞과 맨 뒤의 공백은 모두 제거합니다. 따라서, ”   CS degree”, “CS    degree”, “CS degree   “, or ”   CS   degree   ”의 결과는 모두 공백을 제거하면 degree CS”가 됩니다.

13. Median of Integer Stream
정렬되지 않은 정수의 스트림(stream)이 주어지면 주어진 시간에 정렬 된 순서로 중간 요소를 찾습니다. 무작위 순서로 연속적인 숫자의 배열이 주어지며 배열의 길이는 미리 알 수 없습니다. 이 상황에서 주어진 수 들의 중간 값을 효율적으로 찾는 함수를 작성해야 합니다. 중간 값을 여러 번 찾아야 할 수도 있습니다. 다시 상기시켜보면, 메디안은 홀수 길이의 정렬된 배열에서는 중간 요소이며, 배열의 길이가 짝수인 경우에는 중간 요소의 평균을 의미합니다.

14. Check Balanced Parentheses
열린 괄호와 닫힌 괄호로 이루어진 문자열이 주어지면, 해당 괄호가 균형을 이루는지 확인하는 문제입니다. 괄호의 유형은 다음과 같이 총 3가지 입니다: 소괄호(), 대괄호 [], 중괄호{}. 주어지는 문자열에는 이 괄호 외에 문자나 숫자, 공백 등 다른 문자가 포함되지 않는다고 가정합니다. 균형을 이루는 괄호는, 열린 괄호의 역순으로 닫힌 괄호가 나열되야 합니다. 예를 들어, ‘([])’는 균형을 이루지만, ‘([)]’는 균형을 이루지 않습니다.

15. First Non Repeated Character in String
주어진 문자열에서 처음으로 반복되지 않는 (고유한) 문자를 찾는 문제입니다.

16. Anagram Strings
주어진 두 개의 문자열이 Anagram인지 확인합니다. 두 문자열이 공백, 구두점 및 대소문자를 무시한 상태에서 서로 동일한 문자를 사용하면 Anagram입니다.  두 문자열에서 모두 같은 수의 문자가 존재해야 합니다. 예를 들어, ‘Eleven plus two’ and ‘Twelve plus one’은 서로 의미있는 Anagram입니다.

17. Search Unknown Length Array
길이를 모르는 정렬된 배열과 찾아야 하는 숫자가 주어지면 배열에서 해당 숫자의 인덱스(index)를 반환하는 기능을 구현하는 문제입니다. 범위를 벗어난 요소에 접근하면 예외를 발생시킵니다. 찾는 숫자가 여러 개 존재하는 경우, 여러 인덱스 중 아무 인덱스나 반환합니다. 찾는 숫자가 배열에 존재하지 않으면 -1을 반환합니다.

18. Find Even Occurring Element
나머지 모든 요소들은 홀수번 발생하고 하나의 요소만 짝수번 발생하는 정수 배열이 주어집니다. 이 배열에서 짝수번 발생하는 요소를 찾는 문제입니다.

19. Find Next Palindrome Number
주어진 숫자보다 큰 수들 중에서 가장 작은 대칭수(Palindrome Number)를 찾는 문제입니다. 예를 들어 125가 주어졌을 때, 이 수보다 크지만 가장작은 대칭수는 131입니다.

20. Tree Level Order Print
정수를 값으로 갖는 이진 트리가 주어지면, 계층 순서대로 출력하는 문제입니다. 동일한 계층에 있는 숫자들 사이에는 공백을 포함하고, 다른 계층 사이에는 줄을 바꿔 출력합니다.

 

 

21. Tree Reverse Level Order Print
이 문제는 이전에 포스팅한 level order print와 매우 유사합니다. 트리를 계층 순서대로 다시 출력하지만, 이번에는 아래부터 시작해서 루트(root) 계층으로 출력합니다.

22. Find Odd Occurring Element
정수 배열이 주어지면, 나머지 요소들은 모두 짝수번 존재하는데 하나의 요소만 홀수번 존재합니다. 여기에서 홀수번 존재하는 요소를 찾습니다.

23. Find Word Positions in Text
텍스트 파일과 단어가 주어지면, 주어진 파일에서 주어진 단어의 위치를 찾는 문제입니다. 같은 파일 내 여러 단어의 위치를 찾으라는 요청을 받을 수 있습니다.

24. Find Next Higher Number With Same Digits
숫자가 주어지면 주어진 숫자만 사용해서 다음으로 높은 수를 찾는 문제입니다. 예를 들어 주어진 숫자가 1234인 경우 각 자리의 수를 이용해서 다음으로 높은 숫자를 만들면 1243입니다.

25. Remove Duplicate Characters in String
주어진 문자열에서 첫번째 나타난 문자는 유지하고 나머지 중첩된 문자는 제거하는 문제입니다. 예를 들어, ‘tree traversal’이 입력 문자열인 경우 출력 결과는 ‘tre avsl’입니다.

26. Trim Binary Search Tree
이진 탐색 트리의 루트(root)와 최소, 최대 2개의 숫자가 주어지면, 모든 값이주어진 최소 값과 최대 값 사이의(최소, 최대 값을 포함) 값으로 새로운 트리를 만드는 문제입니다. 결과로 생성된 트리 역시 유효한 이진 탐색 트리여야 합니다.

27. Squareroot of a Number
sqrt 함수를 사용하지 않고, 주어진 숫자를 반내림(rounded down)해서 제곱근을 구합니다. 예를 들어, [9, 15] 사이 숫자는 3을 반환하고 [16, 24] 사이의 숫자는 4를 반환해야 합니다.

28. Longest Compound Word
정렬된 단어 목록이 주어지면, 이 목록에 있는 단어들을 연결해 가장 긴 합성어를 찾는 문제입니다. 예를 들어, 입력된 단어 목록이 [‘cat’, ‘cats’, ‘catsdogcats’, ‘catxdogcatsrat’, ‘dog’, ‘dogcatsdog’, ‘hippopotamuses’, ‘rat’, ‘ratcat’, ‘ratcatdog’, ‘ratcatdogcat’]인 경우, 가장 긴 합성어는 12자의 길이를 가진 ‘ratcatdogcat’입니다. 가장 긴 개별 단어는 14자의 ‘catxdogcatsrat’ 그리고‘hippopotamuses’ 이지만, 목록의 다른 단어로 완전하게 구성되지 않았습니다. ‘catxdogcatsrat’에는 ‘x’ 문자가 있고, ‘hippopotamuses’는 합성어가 아닌 개별 단어입니다.