Dr. Woo's epigram

오랫만에 남경 출장기를 이어서 쓴다.
명현릉 구경도 잘 했고, 저녁밥도 든든하게 먹었고, 이제 호텔로 돌아왔다.

출장을 오기 전에도 말은 좀 했었지만, 면접을 위한 기술적인 문제를 좀 준비하기로 했다.
나는 면접에 참고하기 위해서 예전에 열심히 공부했었던 Programming Pearls 를 가져갔는데, 거기에 나온 문제 들 중 두 개를 골랐다. 홍책임도 구글 면접 문제로 유명한 문제를 하나 골라왔다. 그리고 프로그래밍 스타일을 파악하기 위한 문제도 하나 준비했는데, 이건 기억이 잘 나지 않는다.

일단 이 날 우리가 준비한 문제들 중 기억에 나는 것들을 여기 적어둔다.

[1] Bean Problem
(Precondition) 검정콩과 흰 콩들이 섞여서 들어 있는 컵이 하나 있고, 검은콩이 무한대로 들어 있는 자루가 있다.
(Task) 컵에서 두 개의 콩을 꺼내서 두 콩의 색이 같으면 둘 다 버린 후, 검은 콩을 자루에서 하나 꺼내서 컵에 넣는다. 컵에서 꺼낸 두 콩의 색이 다르면 검은콩은 버리고 흰콩은 다시 컵에 넣는다.
(Question 1) 다음과 같은 작업들을 계속 반복한다면 어떻게 될 것인가?
(Question 2) 처음 컵에 흰 콩이 M개, 검은 콩이 N개 담겨 있었다면 마지막 콩의 색깔은 어떻게 결정되는가?

[2] Graph Problem
X 축 [0..1] 구간에 y = a*x + b 와 같은 직선들이 (예를 들어) 1,000개 쯤 있다.
a와 b는 각각 실수이며(음수, 양수, 0 모두 가능), 1,000개의 직선들은 x축 [0..1] 구간에서 절대로 서로 교차하지 않는다.

1,000개의 직선들이 (a, b)의 쌍 1,000개로서 주어졌을 때, 어떤 점 P = (Px, Py)는 주어진 1,000개의 직선들 중 두 개의 직선 및 x=0, x=1 으로 이루어진 사각형 내에 포함된다고 하자. 이럴 때 입력으로 주어진 1,000개의 직선들 중 P를 둘러싼 두 개의 직선을 찾아내는 알고리즘을 기술하라.

(미리 소팅이 가능한 경우와 미리 소팅이 가능하지 않은 경우의 답이 다르다)

[3] Card Shuffling
N개의 숫자들이 오름차순으로 가지런히 정렬되어 있다.
rand() 함수를 사용하여 N개의 숫자들을 ramdomized order로 재구성하되, O(N)의 complexity를 가지도록 재구성하는 방법은?

대강 이런 문제들이었다.

저녁밥을 먹고 와서부터 홍책임 방으로 내려가서 계속 같이 작업을 했는데, 밤 11시쯤이 되니까 각 문제에 대한 채점 기준 같은 것들도 세부적으로 정할 수 있었다. 사실 준비한 문제들이 많지 않아서 좀 걱정이 되긴 하였다. 면접자들이 서로 문제에 대한 해답을 주고받으면 그 효용성이 크게 떨어지기 대문이다. 그렇지만 채점 기준들까지 정해두고 나니 뭔가 면접을 위해서 나름 기본은 지키려고 애를 쓴 것 같아서 서로 뿌듯하였다.

그 다음 코스는 다음날 면접을 위해서 쿨쿨 잠~
물론 같이 잔 것은 아니다 :)