第五章 Data Structures & Algorithms (DSA)
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で実装してみる
- https://leetcode.com/problems/kth-largest-element-in-an-array/
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)) |
練習
この続きは、購入者向けの内容です。
非表示コンテンツ 📝 11,492文字
続きは購入後に閲覧できます。
この教材を購入 ↗