내가 코딩을 직업으로 가진지 10년이 넘었는데도 코딩 인터뷰를 못 봐서 어쩔 수 없이 코딩 인터뷰를 준비하게 되었다. 내 실력을 평가받는 것은 고통스러운 일이다. 잘 하면 모르겠는데 못하면 참 괴롭다. 못하면 못하는대로 열심히 노력해서 조금 덜 못하게 해야 한다.
이건 마치 코딩 고시 같다. 최근 몇 년 들어 코딩 인터뷰의 형식이 정형화되어서, 대부분의 기업들이 80-90%는 비슷하게 보게 되었다. 이 형식에 정확히 맞게 잘 하면 된다. 여기서 추가적으로 아주 반짝이는 천재성을 더 보여주면 좋겠지만, 나는 아무래도 천재는 아닌 것 같아 그냥 준비를 철저히 한 모습을 보여주는 것을 목표로 삼는다.
목표: leetcode의 medium, hard 2문제를 말로 설명하며 각각 15분, 총 30분 안에 2문제를 푼다. 중간에 문제를 살짝 비틀어도 당황하지 말고 코드를 유연하게 바꿔가며 대응한다. 구글의 인터뷰 예제 영상을 참고한다.
방법: leetcode > Explore > Top Interview questions > Medium, Hard를 평소에 풀면서 연습하다가, 특정 기업 인터뷰가 시작하기 직전에 해당 기업의 문제를 푼다. 일단 타이머를 켜고 15분 안에 풀도록 하고, 막히면 중단하고 solution을 보고 다시 풀어본다. 막히면 어차피 내가 아이디어가 없거나 그 아이디어를 구현하는 실력이 부족한 것이므로 쓸데없이 시간을 낭비하는 것이다. 빨리 끊고 앞으로 나아가야 한다.
푸는 방법이 여러가지이면 다 해본다. 처음에는 태블릿 펜으로 원노트에 쓰면서 녹화하고 다시 봤는데, 요즘은 coderpad.io 를 쓰기 때문에 손으로 쓰는 연습이 필요가 없다.
풀면서 외워야 하는 부분, 아이디어를 떠올리는 recipe가 필요한 부분, 내가 잘 안 되는 부분들은 적어놨다가 1장짜리 cheat sheet로 만든다. 이것은 온라인으로 볼 때는 옆에다가 놓고 보고, 오프라인이라면 직전에 달달 외워서 간다.
코드는 최대한 짧게 쓰도록 연습한다. 최적화가 필요하거나 edge case를 감안해야 할 경우, interviewer에게 물어봐서 요구할 경우에만 추가한다. 이거 다 하다간 15분 안에 못 푼다. 물론 interviewer가 요구하면 다 해야 하는데, 그러면 15분에 2문제가 아니라 30분에 1문제를 풀겠다는 얘기다. 이러면 문제를 푸는 아이디어보다는 온갖 이상한 input에도 에러 없이 돌아가는 robust한 코드를 보겠다는 얘기다.
변수명이나 function 이름도 최대한 짧게 만든다. 일단은 15분 안에 풀어야 한다. 이름이 잘 생각나지 않으면 integer는 i, j, k, l로 순서대로 대충 짓고, String은 s,t,u,v로 순서대로 대충 짓고, array는 arr, List는 list, Map은 map, function은 helper()로 대충 짓고 넘어간다. 풀다가 더 좋은 이름이 떠오르면 그때 고친다. 이름을 고치는 건 빨리 할 수 있으니까.
Facebook의 경우 library 펑션을 구현하는 문제를 내는데, 이건 솔직히 boilerplate 코드를 빨리 짜는 걸 보는 거다. 마치 타자연습을 하는 것처럼, 영화에 나오는 해커처럼, 키보드를 타닥타닥 빠르게 쳐야 15분 안에 풀 수 있다. 좋은 키보드, 좋은 마우스, 눈높이에 맞는 화면 등 코딩에 편안한 환경을 만들면 한 1분은 단축할 수 있다.
코딩을 하기 전에 미리 test case를 몇 개 만들어놓고, 그걸 보면서 코딩한다. 그리고 코딩을 다 하면 그 test case들을 가지고 손으로 디버깅을 한다. 물론 하나하나 다 짚다간 시간이 너무 오래 걸리므로 빠르게 훑어간다. 그러면 꼭 뭘 하나씩 빼먹은게 나오는데, 그러면 뭐가 잘못됐는지 설명하고 고친다. 보통 3개 정도는 틀린게 나온다. 절대 적당히 넘기면 안된다. 고통스러워도 참고 꼼꼼히 돌려본다.
코드를 자꾸 지웠다 썼다 하지 말고, 한번에 깔끔한 코드를 순서대로 적어야 한다. 중간에 말이 끊기거나 코딩이 멈추지 않도록 한다. 정 막히면 내가 왜 막히는지 말로 설명한다. 보통 막히는 경우는 내가 틀려서다. 왜 틀렸는지를 설명하고, 어떻게 고치면 될지를 말한다. 시간을 허비한 것이 아까워도 어쩔 수 없다. 늦는다면 늦는대로 계속 하는 수 밖에 없다. 만회할 수 없더라도 마지막까지 최선을 다 한다.
매일 일을 끝내고 컴퓨터 앞에 앉아 코딩 인터뷰 문제를 풀다가 잔다. 자기 직전에 오늘 풀었던 문제들을 떠올려본다. 내가 어떻게 풀었고, 어디서 막혔고, 어떻게 풀었는지, 뭐가 문제였는지, 어떻게 하면 좋을지를 짧게 생각한다. 어쩌면 꿈에서도 생각할지 모른다. 그것도 좋다.
아내 앞에서 가상 인터뷰를 본다. 무엇을 어떻게 질문할지를 알려주고, 아내가 내 준 문제를 아내 앞에서 푼다. 이것을 녹화해서 다시 보고, 마음에 들 때까지 반복한다. 내가 혼자 풀 때랑 남 앞에서 풀 때랑 꽤 차이가 난다. 연습은 되는데 내가 잘 못하면 부부 사이가 안 좋아진다. 아니면 다른 사람과 하면 되는데 내 주위에 인터뷰를 준비하는 사람이 없어서 어쩔 수 없다.
다음은 내가 잘 못 풀어서 떨어졌던 문제들의 회고다.
Implement Queue using Stacks
https://leetcode.com/problems/implement-queue-using-stacks/
Java의 경우 Stack은 그냥 Stack<Integer> stack = new Stack<>(); 을 쓰고, Queue라면 Queue<Integer> q = new LinkedList<>(); 를 쓴다. 아이디어는 하노이의 탑처럼 stack 2개를 옮겨가면서 넣다 뺐다 하는 건데, 이게 어디로 넣고 어디로 빼는지를 헷갈려서 한참을 헤맸다. 그리고 가진게 없을 경우에 poll()을 하면 어떻게 예외처리를 할지를 또 헤맸다. 무려 나는 throw Exception()을 했다… 세상에. 이것은 내가 매일 일을 하는 방식이었지만 코딩 인터뷰의 conversion에는 어긋나는 것이었다. 보통 이러면 0이나 -1을 return거나, Integer라면 null을 return한다.
아이디어가 잘 생각이 안 나면 일단 가장 순진한 방법으로 생각해봐야 한다. 스택의 땅을 다 파서 옆에다가 쌓아놨다가, 맨 밑에 새 걸 깔고 다시 옆에 쌓아놨던 걸 덮으면 된다. 이러면 O(n)이 걸린다.
여기서 좀 더 생각해보면 offer() 할때까지는 아무것도 안 해도 된다. 나중에 poll() 할때 그 때 가서 하면 된다. lazy loading이다. 나는 이것을 설거지를 잔뜩 쌓아놨다가 그릇이 필요할 때가 다 되서야 설거지를 하는 거라고 생각한다. 그러면 poll()은 늦겠지만 offer()는 빨라진다.
다만 이렇게 하면 넣는 스택, 빼는 스택 2개를 써야 하는데, 뺄 때 넣는 스택 전체를 빼는 스택으로 옮긴 다음에 빼는 스택 맨 위에 있는 것을 return해야 한다. 근데 그 다음에 넣는 스택에 넣다가 뺄 때, 빼는 스택이 남아있는데 그 위에다가 쌓으면 순서가 엉키므로, 빼는 스택을 다 쓴 다음에 넣는 스택에 있는 걸 다시 빼는 스택에 부어줘야 한다.
여기에 시간이 남을 경우 추가로 물어볼만한 것으로 get(index)를 추가하는 것이다. 이러면 lazy loading의 경우 복잡해지는데, 넣는 스택과 빼는 스택의 순서를 잘 따져서 찾으면 된다.
Number of Islands
https://leetcode.com/problems/number-of-islands/
grid가 나오길래 DP 문제일 줄 알았는데, 의외로 DP로 안 풀린다. 몇 몇 예외만 잘 처리해주면 될 줄 알았는데, snake case로 islands가 뱀처럼 모든 방향으로 꼬인 경우에는 어떻게 해도 안 된다. 시간이 다 되갈 즈음에야 겨우 union-find를 생각해냈는데, 구현하다가 버벅여서 잘 안 됐다.
일단 union-find를 쉽게 하려면 2d 좌표를 1d로 바꿔야 한다. 이것은 물론 overflow가 없다는 가정 아래서다. overflow를 막으려면 2d는 2d 그대로 풀어야 하고, parent를 찾을 수 있도록 (i,j) 둘 다 각각 저장해야 한다. 이렇게 여러개의 값을 저장하려면 array를 갯수만큼 더 쓰거나, array를 한 단계 더 깊이 들어가서 …[0] …[1] 이렇게 쓰거나, 아니면 간단히 클래스를 하나 만들어서 쓰면 된다. 나는 평소 업무하던 대로 클래스를 만들어 쓰는 편인데, 잘못하면 시간을 엄청 잡아먹으므로 웬만하면 간단하게 가야 한다. 여기에 hashCode(), equals() 까지 구현해서 두 클래스가 같은지 검사까지 하면 시간 다 간다. 물론 문제에 따라서는 이렇게 푸는게 더 간단한 경우도 있지만 여기선 아니다.
union-find를 할 때 좋은 점은 {-1,0}, {0,-1} 2개만 합치면 된다는 것이다. dfs로 모든 경로를 돌 경우에는 {-1,0}, {0,-1}, {1,0}, {0,1} 4개를 다 돌아야 한다. 물론 union-find건 dfs건 둘 다 시간복잡도는 O(nm)으로 같다. visited 처리를 할 경우 말이다. 아 참 여기서 grid를 덮어쓸 수 있다면 visitied 배열을 별도로 안 만들어도 된다.
