DSAは絶対コーディングやドメイン知識面接に聞かれます。世の中にはたくさんのDSAがあるがアルゴリズムのエンジニア的なロールを応募していない限りここでカバーしているものは十分だと思います。InterviewCatではトピックスごとにLeetCodeから問題を選んできています。最後の技術質問にドメイン知識面接よく聞かれる質問もまとめたので復習用としてオススメです。
また注意点ですが、問題数を数多くこなしたい方はコーディング面接の対策についてに書かれているLeetCodeの問題集（Blind75、NeetCode150）やPrampなどでモックインタビューを行う必要があります。ここでは最も重要な問題のみをピックアップしています。
また現在Coding InterviewCatというコーディングテストやコーディング面接に特化した教材を開発しています。コーティング面接に必要なPythonの学習、基本的なデータ構造とアルゴリズム、LeetCodeでの効率的な学習を手助けする教材となっているのでご期待ください。
Big O Notation
ビッグオー表記法は、アルゴリズムが入力サイズに対してどのようにスケーリングするかを説明するものです。これは、アルゴリズムの最悪のケースシナリオを表現するために使われます。また、アルゴリズムを比較し、どのアルゴリズムがより優れているかを判断するためにも使用されます。例: O(n)
Data structure & Algorithm
データ構造はテクニカル面接の中で最も大事な武器になります。leetcodeには2000問以上の問題（2023/4時点で2654問）があるがArray、String、Hash Tableに熟練できればほとんどの問題と向き合うことができます。もちろんそれぞれのデータ構造には各自のアルゴリズムがあるので簡単ではないです。
Array
🚦 Important
Operation | Average Time Complexity |
Search | O(n) |
Search (sorted array) | O(log(n)) |
Insert | O(n) |
Insert (at the end) | O(1) |
Remove | O(n) |
Remove (at the end) | O(1) |
練習
String
🚦 Important
Operation | Average Time Complexity |
Access | O(1) |
Search | O(n) |
Insert | O(n) |
Remove | O(n) |
練習
Hash Table
🚦 Important
Operation | Average Time Complexity |
Search | O(1) |
Insert | O(1) |
Remove | O(1) |
練習
Sort & Search
🚦 Important
Algorithm | Average Time Complexity | Worst Time Complexity | Worst Space Complexity |
Bubble sort | O(n^2) | O(n^2) | O(1) |
Insertion sort | O(n^2) | O(n^2) | O(1) |
Selection sort | O(n^2) | O(n^2) | O(1) |
Quicksort | O(n log(n)) | O(n^2) | O(log(n)) |
Mergesort | O(n log(n)) | O(n log(n)) | O(n) |
Heap sort | O(n log(n)) | O(n log(n)) | O(1) |
Bucket sort | O(n+k) | O(n^2) | O(n + k) |
Radix sort | O(nk) | O(nk) | O(n+k) |
練習
- 適当な配列を
- Mergesortで実装してみる
- Quicksortで実装してみる
Recursion/Backtracking
練習
Binary search
練習
Linked Lists
Operation | Average Time Complexity |
Access | O(n) |
Search | O(n) |
Insert | O(1) |
Remove | O(1) |
練習
Stack
Operation | Average Time Complexity |
Top/Peek | O(1) |
Push | O(1) |
Pop | O(1) |
練習
Queue
Operation | Average Time Complexity |
Enqueue/Offer | O(1) |
Dequeue/Poll | O(1) |
練習
Balanced binary tree
🚦 Important
Operation | Average Time Complexity |
Access | O(log(n)) |
Search | O(log(n)) |
Insert | O(log(n)) |
Remove | O(log(n)) |
練習
