조금 지난 일이지만 구글 코리아 소프트웨어 엔지니어 포지션에 지원해서 최종 합격을 했다. 쉽지 않은 과정이었고, 특히 도움을 받을 곳이나 구체적인 로드맵이 없어서 내가 제대로 준비하고 있는지 확신이 없던 시간이었다. 누군가는 나와 비슷한 상황에 있지 않을까 싶어 알고리즘 인터뷰 준비 과정을 글로 남겨보려 한다.
시작하기 전에
구글 인터뷰 준비 전의 알고리즘 실력은 국내 IT 대기업 코딩 테스트를 통과할 정도였다 (카카오 신입 1차 코테 점수가 4.5/7 이었다). 학부 자료구조와 알고리즘 수업을 열심히 들었고, 백준에서 단계별로 풀어보기와 수업에서 다뤘던 알고리즘 문제들을 풀어봤다.
국내 IT 기업 코테 문제들은 어떤 알고리즘을 물어보고 싶은 건지 어렵지 않게 파악할 수 있었던 반면, 구글 기출문제라고 떠도는 문제들은 어떻게 접근해야 할지 감이 안 잡혔다. 여기저기서 모은 자료들을 바탕으로 나름의 계획을 세웠는데 결과적으로 그런대로 괜찮은 계획이지 않았나 싶다.
면접을 준비하는 과정에서 NORANG 블로그와 Jeina, De'vLog 블로그, Ries 마법의 슈퍼마리오 블로그에서 큰 도움을 받았고 블라인드에 '구글 면접', '구글 인터뷰' 등의 키워드로 검색해서 나온 글에서도 도움을 받았다. 이 자리를 빌어 좋은 글을 남겨주신 분들께 감사하다는 말을 전해본다. 글을 쓰는 시점에 한 번 더 검색해보니 친절한외노자 블로그와 gomjellie.log 블로그의 글도 많은 도움이 될 것 같다.
기초 다지기
어디선가 구글 알고리즘 인터뷰에서는 time/space complexity를 짚고 넘어가는 게 중요하다는 얘기를 들었다. 알고리즘을 빠르고 정확하게 구현하는 게 중요하다는 얘기도 들었다. 좋은 공부 자료를 찾다가 Ries 마법의 슈퍼마리오 블로그에 있는 대회알고리즘 카테고리를 활용하기로 했다.
알고리즘별로 complexity가 어떻게 되는지와 왜 그렇게 되는지를 익힌 다음에 추천 문제를 모두 풀었다. 당연히 힌트는 보지 않았고, 어떤 알고리즘을 써야 할지 아는 상황이기 때문에 시간에 구애받지 않고 끝까지 풀기 위해 노력했다. 문제를 풀 때에는 어떤 문제를 풀 때 이 알고리즘을 쓰는 게 효율적인지와 어떻게 구현해야 실수 없이 빠르게 코딩할 수 있을지를 신경썼다.
전자는 유명한 Maximal Rectangle 문제를 예로 들 수 있다. 0, 1로 구성된 matrix에서 가장 넓은 직사각형을 찾는 문제인데, 각 column을 prefix sum array로 바꾸면 Largest Rectangle in Histogram 문제가 된다. 그리고 라이님 블로그의 스택 문제를 풀어봤다면 이 문제는 스택을 써서 효율적으로 풀 수 있다는 걸 알 수 있다. 어떤 문제를 어떤 알고리즘으로 풀 수 있는지 안다면 복잡한 문제를 잘 아는 쉬운 문제로 바꿔서 풀 수 있지 않을까 싶었다.
후자는 라이님의 Dijkstra 코드를 예로 들어본다. 이 코드는 전체 흐름이 마음에 들어서 거의 그대로 썼지만 2중 while문 대신 while-continue를 쓰는 게 더 편해 아래처럼 바꿔서 사용했다. 손에 맞는 코딩 스타일을 익혀놓으면 인터뷰 현장에서 실수가 덜하지 않을까 싶었다 (다른 언어를 쓴다면 그 언어에 맞는 자신만의 스타일을 찾으면 되지 않을까 싶다).
while (!pq.empty()) {
const int curr = pq.top().second;
pq.pop();
if (visited[curr]) {
continue;
}
// 이하 생략
}대회알고리즘 카테고리를 모두 풀기엔 글이 너무 많아서 <코딩 인터뷰 완전 분석> 책을 참고하여 공부 범위를 조정했다. 가장 오래된 글부터 위상정렬까지 풀었고 (벨만 포드, 플로이드 와샬 제외) 추가로 트라이를 더 풀었다.
Complexity는 제대로 공부하려면 전공 교재를 보는 게 가장 확실했겠지만 라이님 블로그와 함께 위의 책으로 비슷하게 준비할 수 있을 것 같아서 교재 정독은 스킵했다.
책 <코딩 인터뷰 완전 분석>
라이님 블로그를 보고 나니 웬만한 알고리즘 문제는 다 풀 수 있을 것 같은 느낌이 들었다. 하지만 리트코드 미디엄 정도에서도 처음 보는 유형의 문제는 접근법조차 떠오르지 않는 상황을 겪게 되었다. 문제를 최대한 많이 풀어서 가능한 모든 경우를 준비해야 하는 건가 싶었다. 그러다 비슷한 시기에 코딩 인터뷰 완전 분석 (이하 CtCI) 책을 보기 시작했고 큰 도움이 될 것 같다는 생각을 하게 됐다.
이 책은 특이하게 답안지가 매우 두껍다. 전체의 2/3 정도였던 것 같다. 알고리즘 문제의 핵심인 중복되는 작업을 줄여나가는 과정을 답안지에 모두 담으려고 하다보니 책이 두꺼워졌다는 말을 어디선가 읽어서, 중복 작업 제거에 초점을 맞춰서 문제를 풀기로 했다. 중복을 제거한다는 건 아래와 같은 방식으로 문제를 풀어가는 것을 뜻한다.
정수 수열에서 구간합이 0인 구간의 개수를 구하는 문제가 있다고 해보자. Lower bound가
Ω(N)인 건 쉽게 알 수 있지만O(N)알고리즘을 바로 떠올리는 건 쉽지 않다. 이때 brute force부터 시작해서 중복 작업을 줄여나가는 접근이 도움이 된다.Brute force는
N(N+1)/2개의 모든 구간에 대해 각 구간의 원소를 순회하면서 합을 구하는 방법으로O(N^3)이다. 이 과정을 잘 들여다보면 동일한 구간의 합을 반복적으로 구한다는 걸 알 수 있다 (ex.a[0]~a[3]의 합을 구할 때 사용한 결과를a[1]~a[3]의 합을 구할 때 다시 사용하지 않는다). 구간합을 빠르게 구하게 도와주는 prefix sum을 사용하면 각 구간합을O(1)에 구할 수 있어 전체 complexity는O(N^2)로 줄어든다.하지만 여전히 중복 작업이 남아 있다. 특정 원소에서 끝나는 구간의 개수를 찾기 위해서는 그 앞에 나오는 같은 prefix sum 값의 개수만 알면 되는데도 전체 배열을 중복해서 순회하고 있다. Hash table을 써서 각 값의 출현 횟수를 저장한다면 특정 원소에서 끝나는 구간의 개수를
O(1)에 알 수 있다. 이때 prefix sum을 만드는 작업과 hash table을 만들고 사용하는 작업 모두O(N)이므로O(N)에 문제를 풀 수 있다.
CtCI의 단점은 문제를 온라인으로 풀 수 있는 플랫폼이 없다는 점이다 (사실 있을 수도 있는데 적극적으로 찾아보지 않았다). 코드에 대한 피드백을 빠르게 받을 수 없어서 구현을 스킵하는 대신 위의 예시처럼 최적 알고리즘을 찾는 과정을 종이에 적고 답안지와 비교하는 방식으로 공부했다. 물론 어렵지 않은 문제는 바로 최적해를 적었다. 문제를 머리로만 풀면 나중에 직접 코딩을 할 때 버벅이지 않을까 걱정이 됐지만 리트코드에서 문제를 많이 풀면 커버될 거라 믿었다 (좀 더 정확히 말하면 리트코드와 이 책을 병행했다).
리트코드
리트코드를 몇 문제나 풀고 인터뷰를 통과했는지는 사람마다 다르겠지만 나는 400문제를 넘기면서 슬슬 감이 잡히는 느낌이었다. '감이 잡힌다'는 건 오답노트에 정리해뒀던 문제를 다시 풀면 거의 다 맞고 처음 보는 하드 문제를 50% 이상의 확률로 푸는 정도를 뜻한다. 프로필을 확인해보니 총 500문제 가량을 이지:미디엄:하드 = 3:5:2 로 풀었다.
알고리즘 문제는 frequency 순으로 정렬해서 풀었고, 전체 리스트를 먼저 풀다가 문제 스타일에 익숙해질 즈음 Problems 탭의 우측 하단에 있는 Google 태그가 붙은 문제로 넘어갔다. Top Google Questions에 있는 문제들도 풀어봤다.
리트코드를 풀면서는 네 가지 원칙을 세웠었다. 문제 조건들 (ex. 배열의 최대 크기) 꼼꼼하게 체크하기, 면접관에게 설명하는 것처럼 complexity와 풀이 방향을 주석으로 적은 다음에 구현 시작하기, 다 푼 다음에 discussion에서 최적해와 비교해보기, 45분이 지나면 깔끔하게 손 떼기.
이 중 최적해와 비교해보는 건 면접에서 제시한 풀이가 최적해가 아니면 더 나은 방법이 없는지 물어본다는 얘기를 들어서 추가했고, 문제당 45분만 쓰기는 면접 시간과 비슷하게 리듬을 가져가면 좋지 않을까 싶어 추가했다. 다만 리트코드를 풀기 시작한 초반에는 시간 제한을 넉넉하게 뒀다가 어느 정도 익숙해졌다 싶을 때 45분으로 줄였고, 실제 면접에서는 후속 질문이 나온다는 점을 감안해서 막판에는 미디엄 문제들은 25분 안에 풀려고 했다.
영어 인터뷰
온사이트 인터뷰에서는 4개의 기술 인터뷰 중 2개를 영어로 봐야 했다. 외국에 혼자 여행가서 그럭저럭 다닐 정도로 영어를 할 수 있어서, 면접 준비 과정에서는 기술적인 부분을 영어로 설명하는 것과 영어로 된 피드백을 듣고 이해하는 데에 주로 신경을 썼다.
처음에는 테크 유튜버의 영상을 자주 들으면 듣기 실력도 향상되고 내 발음과 억양도 좋아지고 기술적인 표현에도 익숙해지지 않을까 싶었다. 적절한 테크 유튜버를 찾아보다가 말이 너무 빠르지 않으면서 발음도 어느 정도 따라할 수 있을 것 같은 TechLead의 영상을 많이 봤다. 익숙해진 이후에는 리스닝 실력을 조금 더 키우기 위해 말이 더 빠른 Clément Mihailescu의 영상을 봤다.
인터뷰가 얼마 남지 않은 시점부터는 실제 면접을 보는 것처럼 문제를 처음 읽는 순간부터 구현을 마칠 때까지 혼자 영어로 계속 설명하면서 문제를 풀었다. 말하다가 막히는 부분이 생기면 적절한 표현을 찾아보고 외우려 했다. 덕분에 말로 설명하면서 코딩하는 것에 익숙해질 수 있었다.
다만 이게 좋은 방법인지는 잘 모르겠다. 영어는 지금도 손에 잡히지 않는 신기루 같다.
마치며
지난 알고리즘 인터뷰 준비 과정을 돌이켜보면, 필요 이상으로 과하게 준비했던 걸까 싶은 생각과 함께 어쩌면 운이 좋아서 조금만 준비하고도 붙은 건 아닐까 하는 생각이 든다. 더 효율적인 준비 방법이 있지 않았을까 싶기도 하다. 인터뷰를 통과한 많은 사람들 중 그저 한 명의 이야기일 뿐이라는 점을 감안하고 읽어주셨으면 하는 바람이다.
인터뷰 준비하시는 분들 모두 노력한 만큼 좋은 결과가 있으면 좋겠다.