미국 개발자 FAANG 취업 후기 - 2. 코딩 테스트 준비

 

미국의 대부분 테크 회사들의 경우 프로그래밍 실력을 굉장히 중시한다. 개인적으로 충격적이었던 건 전체 프로세스에서 코딩 인터뷰의 비중이 꽤 크다는 것이다. 가장 덜 중요한 것은 소위 인성면접인 Behavioral Interview이다. 개인적으로는 인성은 어떻더라도 코딩만 잘하면 된다는 인상을 받았다. 회사마다 다르겠지만 내가 준비했던 메타의 경우 전체 프로세스에서 최소 6개의 코딩 문제를 받게 된다. Pre-screening에서 2개, Onsite에서 4개를 받는데 이 라운드들은 모두 해당 면접자를 hire / no hire (채용할 것이냐, 아니냐) 를 가르게 되는 중요한 단계이다. 메타에서는 아무리 다른 라운드의 면접을 잘 보더라도 코딩 문제를 하나 이상 못풀게 되면 합격하기 어려우며 최소 채용 조건이라고 말한다.

 

그럼 이 중요한 프로세스를 어떻게 준비하느냐. 어려운 것은 코딩 인터뷰는 단기간에 준비한다고 완성되는 것이 아니다. 시간을 들여야한다. 그리고 이해를 요한다. 지금 글을 작성하는 시점에서 돌이켜보면 문제를 많이 푸는 것보다는 유형을 완벽하게 이해하고 파악할 수 있는 능력이 훨씬 중요하다. 그 다음 약간의 tactic/테크닉들을 갖추게 되면 인터뷰할 준비가 되어있을 것이다.

 

미국으로의 이민이 결정되고 난 이후 나는 코딩테스트를 준비하기 시작했는데, 당시에는 어떻게 접근해야할지 모르겠어서 단순히 Leetcode만을 많이 풀었다. 소위 Leetcode Top 150, Blind 75와 같이 문제 리스트를 순회하면서 풀어나갔다. 처음에는 어떻게 접근해야할지 모르겠어서 Easy 레벨 문제들도 푸는데 오래걸렸다. 이 때의 나에겐 "코딩테스트적인" 사고방식이 갖춰져있지 않았다. 시간을 들여서 고민해보다가도 모르겠다면 답안을 보고 외우는 방식으로 접근했다. 그렇게 문제 리스트를 반복해서 풀기를 여러번, 이제 암기가 된 문제들은 5-10분만에 정답 코드를 작성해나갔다.

 

단순히 많은 문제들을 반복해서 풀기만 했던 시절

그래도 뭔가 부족한 느낌이 계속 있었다. 나는 목표가 뚜렷하게 보이면 달리는 편인데, 퇴근 후에 짬짬이 문제들을 계속 풀기를 반복했으나 무언가 비어있는 느낌이 계속 들었다. 그래서 유투브로 다시 빅테크 회사들의 면접에 합격했던 사람들의 후기를 찾아보기 시작했다. 공통의 조언은 문제를 풀고 풀이를 간단하게 적어보라는 것이더라. 그래서 또 다시 반복해서 풀면서 풀이를 옮겨적기 시작했다. 이 때서야 비로소 유형별로 묶을 수 있었던 것 같다.

문제별 카테고리와 풀이에 대해 간단히 적어나가보던 시절

이쯤되니 내가 준비가 된 것 같았다. 뭔가 유형들도 그려지는 것 같았고, 중요하다고 하는 문제들을 모두 풀어봤으니 자신감이 있었다. 이 정도로 마무리했을 때가 내가 미국에 막 도착해서 지원서를 써볼까 고민하던 시기였다. 그리고 이 때가 롱디를 마무리하고 남편과 함께 신혼집에 머물면서 저녁 시간에 mock interview를 시작해볼 시기였다.

 

남편과 Mock Interview를 시작하니 뭔가 단단히 잘못되었음을 깨달았다. 내가 선택한 알고리즘, 작성한 코드에 대해 설명하려다 보니 내가 정말 이를 이해하고 있는 것이 맞나라는 의구심이 생겼다. 그리고 남편이 문제풀이에 대해 해설하며 했던 말들이 나에게는 너무 생소했다. 예를 들어 그래프 문제를 푼다고 했을 때, 그래프란 무엇이며 왜 사람들이 그래프를 사용하는지, 그리고 왜 탐색 알고리즘이 필요한지에 대한 답을 하지 못했다. 남편은 간단하게 "세상의 대부분의 문제들은 그래프로 표현될 수 있어. 학부시절 이론적으로는 SNS 네트워크, 의사결정 모형 등에 대해서만 알려주지만 더 다양하게 활용될 수 있고, 보통 굉장히 고차원이라 사람들이 직관적으로 이해할 수 없는 경우가 대다수야. 그래서 우리가 그래프를 이해하려면 그래프 전체를 탐색하게 될 수 밖에 없어. 그건 굉장히 비효율적이기 때문에 여러 알고리즘들이 나온거야. 가장 단순하게는 이웃한 모든 노드와 엣지를 방문하는 BFS, DFS가 있어. 하지만 엣지에 weight가 생기면 이제 더 이상 동일한(equivalent) 엣지가 아니기 때문에 우선순위를 두면서 방문해볼 수 밖에 없어. 그래서 weight가 있는 경우 Dijkstra 알고리즘을 사용하는거야. 우선순위를 파악하기 위해 Priority Queue를 두고 다음에 방문할 엣지를 결정하는거야"라고 말했다.

 

그렇다. 코딩 인터뷰를 진행하게 되면 내가 선택한 알고리즘이 왜 optimal한 선택이며 다른 알고리즘에 비해 어떠한 Trade-off가 있는지를 설명해야한다. 그리고 그 알고리즘이 어떤 목적임을 분명히 알고있어야한다. 내가 문제를 푸는 것과 누군가에게 설명할 줄 안다는 것은 전혀 다른 레벨의 이야기이기 때문이다.

 

얼빠졌던 나에게 남편은 책을 하나 추천해주고 갔다. <Introduction to Algorithms> 이라는 책이며 처음부터 끝까지 모두 정독할 필요는 없지만 아래 챕터들은 충분히 읽을 만 하다.

• Advanced Design and Analysis Techniques
• Graph Algorithms

 

* 한 가지 참고해야할 것은 회사마다 중점으로 두는 알고리즘들이 다르다. 이건 Leetcode premium을 결제하게 되면 문제마다 회사가 tagging이 되어있는데 준비하고자 하는 회사가 tag된 문제들을 보면 대충 유형을 뽑을 수 있다. 내가 준비했던 메타는 Binary Search, Graph 중에서도 특히 Tree 관련 문제를 좋아했다. 내가 알고있는 바로는 웬만한 회사들은 Graph문제들을 좋아하는 편이다.

 

책을 보면서 내가 했던 것은 정리 노트를 만드는 것이었다. 예를 들어 그래프에 대해 공부한다고 치면, 아래와 같은 Tablel of Contents를 뽑아낼 수 있다:

1. Graph
   1. Traversal - DFS, BFS
   2. Single-Source Shortest Path
      1. BFS
      2. Dijkstra's
      3. Bellman-Ford
   3. All-Pairs Shortest Path
   4. Topological Sort ~ DAG
   5. Strongly Connected Components (SCC)
   6. Minimum Spanning Tree

책을 보게 되면 이 알고리즘이 왜 이러한 approach를 취했는지에 대한 설명이 있다. 예를 들어 MST를 찾는 문제에서 Kruskal과 Prim 알고리즘 두 개로 나뉜다고 해보자. Kruskal은 edge 중심의 접근방식이며 Prim은 vertex 중심이다. Kruskal은 disjoint set으로 MST를 구현하는데 edge를 weight에 따라 우선 정렬하며 가중치가 낮은 edge부터 disjoint set (=MST)에 추가하며 다음으로 큰 weight의 edge를 구성하는 vertex의 양끝 노드가 이미 MST에 존재하면 cycle을 구성하는 것이기 때문에 skip한다. Prim은 vertex로 MST를 그려나가는데 BFS같은 방식으로 priority queue를 두고 visited set으로 cycle이 생기는 것을 방지한다. 이렇게 두 알고리즘의 접근방식이 다르다는 것을 이해하면 알고리즘들의 디테일들을 억지로 외우지 않더라도 이해할 수 있게 된다. 앞서 disjoint set으로 Kruskal을 구현한다고 하면 cycle이 있는지 확인하기 위해서는 union 함수의 결과가 False가 아니어야한다는 등..

 

왜 이러한 방식으로 공부하는 것이 중요한지를 언급하기 위해 또 다른 예시를 들어보겠다. Dijkstra 알고리즘을 공부한다고 쳐보자. 일단 dijkstra를 구현하는 template 코드가 있다. 이 코드를 보면 과거의 나는 일단 디테일들을 외웠다. 1) Priority Queue를 둔다. 2) 음수일 땐 사용할 수 없다. 하지만 Dijkstra를 이해하면 그 디테일들을 암기할 필요가 없다. 다시 Dijkstra알고리즘이 어떤 것인지를 생각해보자. 노드 주변의 최단 경로만을 선택하는 그리디 알고리즘이다. 가중치가 음수일 때 사용할 수 없는 이유는 당연하다. 매 순간 지금까지의 최소 경로는 모두 방문해봤다는 가정인 알고리즘인데 음수인 edge를 만나게 되면 그 가정이 깨지기 때문이다. 그리디 알고리즘이 그리디하지 않다는 모순이 생기게 된다. 이렇게 이해하게 되면 그 알고리즘의 구현 방식도 자연스럽게 머릿 속에 그려지게 된다.

 

이렇게 알고리즘들에 대해 익숙해진 다음 우리가 해야할 일은 어떤 순간에 어떤 알고리즘을 선택해야하는지를 아는 것이다. 이건 어떻게 보면 문제를 많이 풀수록 익혀지는 감이기도 하다. 하지만 문제를 많이 풀어야한다는 건 시간을 그만큼 투자해야한다는 것이기에 이를 단축하기 위해 이 사이트에서는 알고리즘들의 접근 방향을 flow chart로 그렸다.

Algomonster의 알고리즘 decision tree

지금까지가 어떤 기업이든 코딩테스트를 준비하기 위한 이상적인 단계들을 설명이었다. 이제는 좀 더 인터뷰하고자 하는 기업에 특화된 이야기를 다루려고 한다. 앞서 간단하게 언급했다시피 회사마다 인터뷰에서 자주 물어보는 알고리즘 유형들이 어느 정도 정해져있다. 이에 대한 정보는 검색을 해보는 수밖에 없다. LeetCode 혹은 Blind를 검색해보면 회사별로 좋아하는 알고리즘 문제들에 대한 정보가 나와있다. 검색이 어렵다면 LeetCode에서 돈주고 Premium을 끊은 뒤 준비하는 회사 tag 문제들을 보면 된다. 이 알고리즘들에 대해 빠삭하게 이해하고 있는 것이 가장 첫 준비 단계이다.

 

그 다음으로 해야할 일은 회사마다 다른데, 만약 회사가 자주 출제되는 문제가 반복적으로 있다면 (내부 interview question bank가 있고 거기서 반복적으로 출제한다면) 이 출제 문제들을 긁어모으는 것이다. LeetCode에는 문제은행 외에 강력한 다른 feature가 있는데 바로 <커뮤니티>이다. Discuss 메뉴를 들어가도 조회할 수 있고, 회사 tag된 문제 리스트에서도 회사 특정 discussion 채널이 따로 있다.

 

 

 

 

이 정보의 가장 큰! 막강한! 장점은 최신 기출문제를 볼 수 있다는 것이다. 그리고 기출문제별 인터뷰어가 어떤 것을 중점적으로 보는지를 확인할 수 있다. 동일한 문제도 space optimal하게 푸는 방법, time optimal하게 푸는 방법이 접근방식이 다르다. 회사마다, 인터뷰어마다 어떤 접근을 선호하는지에 대한 정보가 이 커뮤니티에서 얻을 수 있다. 메타는 Meta-tagged Top 100 만 풀어도 준비할 수 있는 것으로 유명한 회사인데, 사실 LeetCode 문제를 그대로 출제한다기보단 말을 바꾸거나, 살짝 꼬아서 다른 것을 물어보기도 한다. 그러한 variant 문제들을 확인할 수 있는 것도 이 LeetCode discussion이다. 만약 당신이 메타를 준비한다면 이 유투브 채널도 추천한다.

 

인터뷰 일정이 잡히고서 나의 주된 준비방법은 이러했다:

• Meta tagged Top 100 Question 반복 풀기
  • Variant 함께 풀기
  • Opitmal solution 확인하기 - Time/Space complexity 체크
• Discussion 채널에서 최신 기출문제 1달치 뽑아 풀기

 

인터뷰 직전까지도 코딩인터뷰는 준비된 듯 하면서도 준비되지 않은 것 같은 느낌이 든다. 지금 글을 쓰는 순간의 나 역시도 가장 자신없는 파트이기도 하다. 코딩인터뷰는 전체 프로세스 중에서도 가장 긴 싸움이 될 것이다. 때문에 지금 글을 읽고 있는 당신에게 응원의 힘을 보낸다! 노력은 빛을 발하기 마련이고 최선을 다하는 것이 최고의 전략이다.