コーディング面接対策のために解きたいLeetCode 60問
2019/04/25
自分がコーディング面接対策のために解いてよかった LeetCode の問題をコンセプトごとにまとめました。カバーするコンセプトは
- LinkedList
- Stack
- Heap, PriorityQueue
- HashMap
- Graph, BFS, DFS
- Tree, BT, BST
- Sort
- Dynamic Programming
- Binary search
- Recursion
- Sliding window
- Greedy + Backtracking
です。 これらの問題が 30 分以内に実装できれば面接の準備は整ったと言っていいと思います。Easy と Medium で問題は構成されてます。進捗を管理するためにGoogle Spreadsheetを用意しました。コピペしてご自由にお使いください。
これらの問題は、LeetCode のリスト機能でも公開されています。クローンすれば自分がすでにどの問題を解いているかがわかります。
解説動画を YouTube にあげていってます。(▶)をクリックすると該当の動画に飛びます。解説してほしい問題やわからないところをコメントで教えていただけると嬉しいです。
LinkedList
- Linked List Cycle (▶)
- Linked List Cycle II (▶)
- Remove Duplicates from Sorted List (▶)
- Remove Duplicates from Sorted List II (▶)
- Add Two Numbers (▶)
Stack
Heap, PriorityQueue
HashMap
- Two Sum
- Group Anagrams
- Intersection of Two Arrays
- Unique Email Addresses
- First Unique Character in a String
- Subarray Sum Equals K
Graph, BFS, DFS
- Number of Islands
- Max Area of Island
- Number of Connected Components in an Undirected Graph
- Word Ladder
Tree, BT, BST
- Maximum Depth of Binary Tree
- Minimum Depth of Binary Tree
- Merge Two Binary Trees
- Convert Sorted Array to Binary Search Tree
- Path Sum
- Binary Tree Level Order Traversal
- Binary Tree Zigzag Level Order Traversal
- Validate Binary Search Tree
- Construct Binary Tree from Preorder and Inorder Traversal
Sort
Sorting Algorithms Animationsが参考になります。挿入ソートや基数ソートがどういうデータセットのときに、NLogN のソートと比べて優れているかを確認しましょう。それぞれのアルゴリズムの特徴を把握するとよいです。
Dynamic Programming
- Paint Fence
- Longest Increasing Subsequence
- Maximum Subarray
- Unique Paths
- Unique Paths II
- House Robber
- House Robber II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Word Break
- Coin Change
Binary Search
- Search Insert Position
- Find Minimum in Rotated Sorted Array
- Search in Rotated Sorted Array
- Capacity To Ship Packages Within D Days
Recursion
Sliding Window
Greedy + Backtracking
その他
これらの問題は総合的に考えて実装する問題です。
- Move Zeroes
- Meeting Rooms
- Meeting Rooms II
- Is Subsequence
- Next Permutation
- String to Integer (atoi)
- ZigZag Conversion
まとめ
いかがだったでしょうか？これらの問題がすばやく解けるようになったら、@yangshun によるAlgorithm Questionsもやってみるといいです。この記事と同じように、コンセプトごとに LeetCode の問題やコーナーケースがまとめられています。
Algorithm Question もやりつくしてしまったら、友人が書いてるAlgorithms and Coding Interviewsをおすすめします。分野ごとに説明/コードが記載されており、この記事もこの本を参考にしています。
競技プログラミングなどをやったことない人にとって、これらの問題は馴染みがないかもしれません。ですが、準備をすればコーディング面接は確実に突破できます。筆者は 200 問ほど解き、Google からオファーをもらいました。
実際の面接対策にはPrampがおすすめです。これは、コーディング面接の準備をしている人同士をマッチングさせるプラットフォームです。英語でしか使えないことに注意してください。オンサイト面接の経験を積みたければ、TripleByte をおすすめしています。アメリカで OPT が 2 年間できるという制約がありますが、オンサイト面接に慣れます。
