실리콘 밸리 주니어 취업기
인터뷰 준비(중) - 데이터 구조 / 알고리즘 리뷰
해당 글은 실리콘 밸리 주니어 개발자 취업기 중 4번째 글입니다.
1. 해외 취업을 결심하기 전에 체크해야 할 것들
2. 자신에게 맞는 가능한 취업 경로 파악하기
3. 인터뷰 준비(상) - 지원 시기 정하기, 이력서 작성하기
4. 인터뷰 준비(중) - 데이터 구조 / 알고리즘 리뷰 (현재 글)
5. 인터뷰 준비(하) - 실제 인터뷰 준비하기
6. 오퍼를 받았다면? 연봉 협상, 비교 하기
7. 베이 지역 정착 준비
8. 기타 정보들(계속 업데이트 예정)
이번 포스팅은 본격적인 인터뷰 준비에 관한 글이다.
인터뷰 준비 (중)
베이 지역의 표준 면접 문제의 기본은 알고리즘 문제다. 소프트웨어 엔지니어링의 가장 기초가 되는 데이터 구조로부터 시작하여 여러 기술적인 문제를 해결하는 데 필요한 알고리즘을 고안할 수 있는 가에 대한 상식적인 부분을 물어본다. 이 포스팅에서는 이러한 문제들을 '알고리즘 문제'라고 부르기로 하자. 또 다른 하나의 표준 면접 문제는 시스템 디자인 문제다. 요구 조건과 리소스 사항들을 설명해주고 이러한 역할을 하는 컴퓨터 시스템을 어떻게 효율적으로 그리고 동시에 Scalable 하도록 디자인하는지에 대한 디스커션 문제이다. 보통은 답이 정해지지 않은 Open-ended 문제이지만 면접관들은 충분한 요구사항에 대한 토론을 통하여 시스템의 요구 조건을 분석하고 거기에 맞는 Trade-off를 통해 특정 형태의 데이터 구조나 디자인을 미리 예상하고 문제를 내기도 한다. 이러한 문제를 '디자인 문제'라고 부르자. 두 문제 다 보통은 1시간 정도의 면접 시간이 주어지고 면접관과 1:1로 면접을 보게 된다. 앞장에서 잠깐 언급하였듯이 자기소개와 이력서나 회사에 관하여 얘기를 하다 보면 실제 면접 시간은 45분 정도 된다. 따라서 실제로 45분 안에 풀 수 있는 난이도의 문제가 주어진다. 그럼 해당 면접에 필요한 데이터 구조와 알고리즘에 대해 알아보자.
준비하기 - 데이터 구조
데이터 구조는 소프트웨어 엔지니어링의 기본이 되는 지식이기 때문에 굉장히 중요하다. 그래서 가장 기본적인 데이터 구조인 Array(Vector), Linked list, Queue, Stack, Binary (Search) Tree, Trie, Heap, Hash map 등의 개념은 알아둬야 한다. 또 해당 구조가 자신이 쓰는 언어의 표준 라이브러리에서 어떤 것과 맵핑이 되고 (예를 들어 C++이면 Array는 std::vector, Binary Search Tree는 std::map, Hash Map은 std::unordered_map라는 식으로) 그 라이브러리를 비교적 자유롭게 쓸 수 있으면 좋다. 또 직접 Implementation을 할 필요는 없지만 내부적으로 어떻게 구현되어 돌아가는지에 대한 rough 한 idea가 있으면 좋다. 그렇지만 std::stack이 push을 사용해서 넣는지 insert를 사용해서 넣는지는 그다지 중요하지 않다. 매일매일 쓰는 데이터 구조가 아니라면 API의 정확한 이름을 틀리거나 인자의 순서를 헷갈리는 것은 아무도 신경 쓰지 않는다.
고급 데이터 구조, 이를 테면 AVL Tree나 Binary Indexed Tree 같은 구조를 정확히 이해하고 사용할 수 있는지는 잘 물어보지 않는다. 빈도수로 치면 인터뷰를 20번 보면 한번 나올까 말까이고 그것도 빈도가 점점 줄어들고 있다. (밑의 트렌드에서 더 설명하겠다.) 다만 해당 구조의 원리에서 착안한 알고리즘 문제를 물어볼 수는 있다. 이 경우에는 해당 구조를 모른다고 가정하고 그냥 그 원리를 이용한 알고리즘을 고안할 수 있는 가를 물어보는 것이다. 물론 이 문제는 어려우므로 온갖 힌트와 디스커션을 적절히 따라가며 생각하기를 기대한다. 따라서 시간이 많다면 고급 데이터 구조도 리뷰할 수 있고 시간이 없다면 스킵해도 된다고 생각한다.
만약 나에게 가장 중요한 데이터 구조 두 개를 꼽으라고 한다면 Binary Tree와 Hash Map을 꼽겠다. Hash Map은 메모리에 데이터를 저장하고 Constant Time안에 그 데이터에 접근할 수 있다는 점에서 범용성이 높다. Hash Map을 바로 사용하지 않아도 종종 문제에서 Hash Map안에 데이터 값을 저장함으로서 Time-Memory Trade Off를 통한 최적화가 가능한 경우가 있다. Binary Tree는 그 재귀적 특성 때문에 백트래킹에 대한 아이디어를 생각할 수 있는가에 대한 문제들, 또 Binary Search Tree의 특성과 결합하여 여러 문제를 출제하기에 좋기 때문이다. 특히 다양한 Tree Traversal의 방법과 그 알고리즘들은 리뷰하는 것이 좋다.
기본적인 데이터 구조 수업을 들었다는 가정하에 데이터 구조를 리뷰하기에 좋은 사이트는 여럿 있지만 나는 인터뷰를 보기 전에 주로 http://www.geeksforgeeks.org/data-structures/를 통해 개념을 리뷰하였다.
준비하기 - 알고리즘
위 데이터 구조를 리뷰했으면 이제는 해당 데이터 구조를 어떻게 잘 사용할지에 대해 리뷰할 차례이다. 우리가 대학교에서 배우는 알고리즘 수업과 크게 다르지 않는데 가장 중요한 부분은 Asymptotic Analysis를 이용한 알고리즘의 Time/Space Complexity 분석과 패턴이 어느 정도 정형화된 알고리즘 (Greedy, Backtracking & DP, Divide and Conquer, Graph Traverse - Basic DFS/BFS + Shortest Path and Union Found) 등이다. 이 컨셉을 교과서를 찾아서 공부해도 되고 개념을 한번 리뷰하고 문제를 직접 풀면서 연습해도 상관없다. 특히 Backtracking이나 DP 같은 많이 출제되는 형태는 딱히 미리 리뷰를 하지 않아도 워낙 문제가 많은 탓에 많이 연습할 수 있다.
다만 알고리즘 책의 후반부에 나오는 NP-Complete에 관한 이론은 그렇게 깊게 리뷰할 필요가 없다. 소프트웨어 엔지니어링과 아직까지는 크게 관계가 없기 때문이다. 또 앞에서 살짝 언급했지만 고급 알고리즘, 예를 들면 레드 블랙 트리나 AVL 트리 또는 A* Search 같은 알고리즘은 시간이 없으면 리뷰하지 않아도 된다. 다만 AVL Tree가 Self-balancing 되는 BST라는 것 정도는 알아두면 좋다. 패턴 매칭에서 자주 쓰이는 KMP Algorithm이나 Rabin-Karp Hashing의 경우에는 알아두면 좋은 경우도 있지만 인터뷰어도 이 모든 것을 알고 있다고 생각하지는 않는다. 예를 들어 KMP 알고리즘은 한 번에 구현하기가 너무 어렵기 때문에 패턴 매칭이 나왔을 때 KMP 스러운 알고리즘을 한 번에 사용하기를 기대하지 않고 Rabin-Karp 스타일의 단순한 해쉬 함수로 Brute force 스타일의 패턴 매칭만 개선해도 좋은 점수를 받을 수 있다.
물론 이렇게 계속 언급을 하면 어떤 부분을 커버해야 되고 어떤 부분을 스킵해도 되는지에 대한 토론을 끝없이 할 수 있을 것이다. General Rule은 45분 안에 일반 소프트웨어 엔지니어가 풀 수 있을 만한 문제를 물어본다는 것이다. 해당 부분을 평가하긴 상당히 애매하긴 하지만 인터뷰 출제자 입장에서 생각을 하는 것이 도움이 될 수가 있다. 인터뷰어가 평가할 덕목은 알고리즘 대회 우승자를 뽑는 게 아니고 같이 일할 소프트웨어 엔지니어를 뽑는 것이다. 얼마나 많은 숫자의 소프트웨어 엔지니어가 배운 지 5년이 넘은 알고리즘 책에 나오는 AVL Tree를 사용하여 45분 만에 구현을 하고 문제를 풀 수 있을까. 만약에 어떤 엔지니어가 45분 안에 문제를 해결했다면 그 엔지니어를 좋은 엔지니어라고 부를 수 있을까. 이런 질문들은 어떤 부분을 공부해야 할 것인가에 대한 힌트가 될 수 있다.
알고리즘 문제도 마찬가지로 같은 사이트의 알고리즘 파트를 리뷰해도 되고 공부하는 스타일에 따라 요즘 가장 유명한 Leetcode나 HackerRank 같은 사이트에서 문제를 풀면서 연습해도 된다. 책으로 공부하는 것이 편한 분들은 가장 많이 읽는 바이블 격의 Cracking the Coding Interview (한글 버전 링크)나 Elements of Programming Interviews도 괜찮다.
또 많이들 추천하는 책 중에 알고리즘 문제 해결 전략이라는 책 도 있는데 만약 시간이 많고 논리적으로 생각하는 방법을 배우려면 괜찮을 선택일 수 있다. (나는 이 책으로 조금 공부하고 Leetcode로 연습했다.) 모든 부분을 다 할 필요는 없고 특히 Recursion과 DP가 이 책에서 굉장히 설명히 잘 되어 있다. 다만 이 책에서 난이도 '하'로 표시된 문제들이 실제 인터뷰 문제 중 상당히 어려운 편 이므로 개념 설명 부분을 잘 읽고 너무 높은 난이도의 문제를 푸는 데 시간을 쓰지 않아도 된다.
문제 푸는 연습하기
아무리 본인이 데이터 구조와 알고리즘을 잘 알고 있다 하더라도 문제 푸는 연습은 어느 정도 필요하다. 왜냐하면 45분 정도의 짧은 시간에 문제를 어떻게 풀 지 생각하고 그 생각을 완벽히 코드로 옮기고 테스트하고 버그를 수정하는 것이 쉬운 작업이 아니기 때문이다. 내 개인적인 경험으로, 이 문제 푸는 연습이 어떤 과정을 거쳤는지 단계로 간단히 나타내 보면 다음과 같다. 그리고 아래 섹션이 분리되어 있긴 하지만 그냥 알고리즘/데이터 구조 연습과 문제 푸는 연습을 병행하면서 자신이 부족한 부분을 찾고 그 부분을 보강하는 식으로 준비하는 것이 효율적일 수 있다.
1단계 - 메모장 코딩에 익숙해지기 (일단 돌아가는 코드를 만들자.)
나는 처음에 Visual Studio 같은 고급 IDE에 익숙했기 때문에 Intellisense가 없는 코딩이 상당히 불편했다. 표준 라이브러리의 컨테이너가 어떤 함수를 제공하는지 Intellisense가 다 알려줬기 때문에 그런 부분을 제대로 짤 수도 없었고 오타나 마침표 실수, bracket/brace 실수 등이 많았다. 따라서 우선은 가장 쉬운 문제 (예: Reverse the string)를 버그 없이 돌아가게 만드는 것이 첫 단계였다. 이 단계에서 여러 라이브러리들을 어떻게 활용하고 오타를 줄이며 깔끔한 코드를 짜는 것을 연습했다. 또 본인의 Indent/Padding 스타일이 일관되지 않다면 그 부분도 같이 고치는 연습을 하는 것이 좋다.
2단계 - 쉬운 난이도의 여러 유형의 문제 풀어보기
에디터 도움 없이 스스로 돌아가는 코드를 짤 수 있게 된 다음에는 여러 유형의 쉬운 문제를 풀었다. 내가 이용한 사이트는 Leetcode 였는데 난이도 별로 정리가 되어 있었으므로 주로 Easy 난이도의 문제를 Tag 별로 분류해서 풀었다. 문제를 풀다가 모르는 알고리즘이나 이론이 나오면 그때그때 정리하면서 풀었고 Easy 문제만 풀었으므로 문제 푸는 속도도 매우 빠르고 점점 많은 문제를 풀게 됨에 따라 자신감도 붙었다. 이 단계에서 대부분의 라이브러리 사용이 굉장히 빨라졌다. 예를 들어 예전에는 std::map의 find의 인터페이스가 어떻고, 어떤 값들을 리턴하는지 일일이 찾아봐야 했다면 이런 부분들이 기계적으로 빨라졌다. 자주 쓰는 라이브러리는 습관처럼 쓰게 되니까 이 부분들을 특별히 신경 쓰지 않아도 자연스럽게 취득하게 된다.
3단계 - 여러 문제를 풀어보고 본인이 취약한 부분 찾기
쉬운 문제를 풀면서 어느 정도 자신감이 붙은 뒤에는 중간 난이도의 문제와 (좋은) 어려운 난이도의 문제를 풀면서 실제 문제 연습을 하고 내가 어떤 부분에 약한지를 찾고 그 부분의 컨셉을 더 공부하거나 문제 푸는 연습을 했다. 어려운 문제는 '좋은' 문제만 풀기를 추천하는데 Solution이 너무 Specific하지 않고 Brain-teaser가 아니면서 Memory나 Design trade off를 위한 더 좋은 솔루션을 찾을 수 있는 문제가 좋은 문제이다.
보통 중간 정도의 난이도 문제는 'Brute Force' (무식하게 풀기) 방법을 사용하여 풀 수 있지만 문제 조건을 잘 이용하면 Pruning/Memory Reusage 등을 통하여 좀 더 빨리 풀 수 있다. 여기서 "빨리" 푼다는 말은 Time Complexity를 줄이는 것을 뜻한다. 무식하게 푸는 방법에서 발상의 전환을 통하여 더 좋게 푸는 방식을 체득하는 것이 이 단계의 핵심이었다.
나는 이러한 중간 난이도의 문제를 풀 때 String/Recursion/DP와 관련된 문제는 잘 풀었지만 Tree와 관련된 문제는 굉장히 못 풀었다. 그렇기 때문에 Tree 문제들은 그림을 그려가며 처음부터 끝까지 공부하고 다시 풀고 하면서 많은 연습을 했었다. 이 부분들은 사람마다 다를 것이지만 본인이 취약한 부분이 발견되면 그 부분은 집중적으로 연습하는 것이 좋다. 특정 카테고리의 문제를 풀 때 그 코어 아이디어가 다 비슷하기 때문에 한번 그쪽으로 생각의 길을 밝힐 수 있게 되면 그때부터는 해당 문제들은 풀기가 쉬워지는 것을 느꼈다.
중간 정도의 문제를 어느 정도 풀게 되면 대부분의 인터뷰 문제를 핸들링할 수 있게 된다. 다만 인터뷰는 인터뷰어와 함께 문제를 토론하고 같이 풀어가는 과정이므로 혼자 문제를 잘 푼다고 좋은 점수를 받을 수 있는 것은 아니다. 실제 인터뷰에서는 문제를 얼마나 잘 정의하며(Clarification) 얼마나 자신의 생각과 그 흐름을(Thought Process) 말로 잘 표현하고 같이 토론해가며 풀어갈 수 있는지를 측정하므로 인터뷰하는 방법 자체에 대한 연습도 필요하다. 이 부분은 또 긴 내용이 될 것이므로 다음 장에서 이어서 쓸 예정이다.
현재 인터뷰 문제와 그 트렌드에 관해
현재 베이 지역의 스탠다드 인터뷰 스타일은 원래 구글 인터뷰에서 시작되었다. 10년 전 기사를 읽어보면 알 수 있듯이 그때에는 인터뷰 라운드도 많았고 "계란 두 개를 가지고 계란이 깨지는 건물 높이를 찾으시오."나 "코끼리를 냉장고에 어떻게 넣을 것인가" 같은 황당한 Brain-teasor 문제들을 내는 경우도 있었다. 하지만 시간이 갈수록 이러한 문제들을 잘 푼 사람들과 그 사람들의 실제 퍼포먼스 관의 상관관계는 거의 없다는 것을 밝혀내게 되었고 엔지니어링 실력만이 중요하다는 것을 알게 되었다. 그래서 이렇게 45분 만에 풀 수 있는 인터뷰 문제들을 출제하고 그 문제를 같이 풀어가며 사람을 검증하는 것이 표준화가 되어갔다.
하지만 그 후에 CareerCup 이나 GlassDoor같은 회사 인터뷰 문제 후기를 공유하는 곳이 생겨나기 시작하고, 운 좋게 인터뷰 문제를 미리 풀어본 실력 없는 엔지니어들을 합격시키거나 해당 문제를 못 푼다는 이유 만으로 잘하는 소프트웨어 엔지니어를 불합격시키는 등의 일들이 일어나면서 이 45분짜리 코딩 인터뷰가 과연 좋은 사람을 검증할 수 있는가에 대한 회의도 생겨나기 시작했다. 심지어 몇 년 전에 혜성처럼 등장한 Leetcode라는 사이트는 깔끔한 인터페이스와 회사 인터뷰 문제를 잘 정리해서 공유함으로써 대부분 테크 회사 인터뷰 문제들의 문제 풀을 체계적으로 관리하여 공개하게 되었고 누구나 많은 문제만 풀기 시작하면 대부분의 테크 회사에 들어갈 수 있는 환경이 주어졌다. 더욱이 구글 하이어링 팀 통계에 따르면 인터뷰에서 좋은 성적을 거둔 사람과 일을 잘하는 사람들 관의 Correlation이 거의 없었다고 한다.
이 때문에 어떤 식으로 사람을 검증할 것인가에 대한 새로운 실험과 토론을 지금도 계속하고 있지만 그럼에도 불구하고 차악의 방법은 여전히 코딩 인터뷰로 사람을 검증하는 것이라고 한다. (한국 기업 임원 면접에서 할아버지들이 물어보는 꼰대 같은 질문이나 마케팅이나 영업을 하는 사람한테 공간 지각력 검증 도형 문제를 풀게 하는 인적성 시험보다는 낫지 않은가.) 따라서 2017년 현재의 코딩 인터뷰 트렌드는 대부분 다음과 같은 룰을 따라 이동하고 있다. 다만 모든 문제 출제는 일반 엔지니어 인터뷰어가 하는 것이고 대부분의 엔지니어에게 인터뷰는 상당히 귀찮은 일(...) 이므로 그냥 맨날 내는 출제 문제를 아무 생각 없이 물어보는 경우도 많다.
너무 어려운 문제를 물어보지 않는다. 너무 어려운 문제를 물어보면 훌륭한 엔지니어를 놓치거나 답을 미리 공부해 온 사람들만 풀 수 있다. (False Negative와 False Positive가 많아진다.) 마찬가지로 풀이 방법이 한 가지로 정해진 문제도 지양한다.
LeetCode 같은 온라인 Judge 풀에서 나온 문제를 그대로 묻지 않는다. 마찬가지로 False Positive 문제가 있다. LeetCode 문제를 물어보더라도, 조건을 다르게 주거나, 문제를 섞거나, Design Discussion을 도입한다. 예를 들어 Tree를 Traverse 하는 문제를 내고 해당 Tree를 Thread-safe 하게 하려면 어떻게 해야 하냐고 묻거나 여기서 Insert가 많이 일어나게 하려면 어떤 캐시 구조를 함께 쓰는 게 좋은지 등을 묻는다.
문제 답안을 적절하게 도출하는 것도 중요하지만 그에 못지않게 과정이 중요하다. 커뮤니케이션은 어떻게 하는지, 어떤 과정 때문에 이러한 생각/방법을 도출하게 되었는지 물어본다. (또는 그렇게 설명하기를 기대한다.)
Design Discussion의 빈도를 늘린다. 옛날에는 순수하게 코딩 인터뷰 문제만을 물어보는 것이 추세였다면 점점 더 해당 문제를 풀 때 다른 조건/가정을 한 뒤에 다른 방식으로 푸는 것이 왜 좋은지/나쁜지에 대한 Tradeoff Discussion을 많이 한다.
이 밖에도 좀 더 좋은 방향으로 사람을 검증할 수 있다면 그쪽으로 계속 이동해가는 추세이다. 하지만 모든 회사에서 이런 움직임을 보이고 있는 것은 아니며 인터뷰 인력이 항상 부족하기 때문에 취업한 지 몇 달 되지 않은 신입 엔지니어들도 인터뷰에 투입되는 경우도 많이 있어서 모든 인터뷰 문제가 좋은 것은 아니다. 따라서 인터뷰는 운도 굉장히 중요하고 많이 볼 수 있는 기회를 만드는 것도 중요하다. 하지만 일반적인 대세는 좀 더 상식적인 문제를 물어보고 그 사람이 진짜 문제를 이해하고 있는지에 대해 도출하려고 노력하니 그런 부분을 연습하면 대부분의 면접 문제는 풀만하다고 느낄 수 있을 것이다.
인터뷰 준비는 특별한 방법이나 편법은 없지만 꾸준히 연습하면 충분히 준비할 수 있는 부분이다. ACM ICPC 같은 대회 문제를 준비하는 것이 아니기 때문에 상식적인 수준에서만 공부하고 연습하면 기본 컴퓨터 구조와 알고리즘을 알고 있다는 가정 하에 대부분의 문제를 핸들링할 수 있다고 생각한다. 면접 보는 방식에 대한 대비는 이 알고리즘 문제를 푸는 것과는 전혀 다른 이야기이기 때문에 영어로 말하는 법이나 생각을 표현하는 방식 등에 대한 연습이 필요하며 이 경험은 다음장에서 공유하려고 한다.
