Preparing the Swift Coding Interview — [Index] Algorithm and Data Structure
Published in
2 min readApr 5, 2018
- Big-O and 7-Steps of Thinking
1. 1. Big-O
1. 2. 7-Steps of Thinking - List-Based Collections
2. 1. Array
2. 2. Linked List
2. 3. Stack
2. 4. Queue/Dequeue
2. 5. Priority Queue - Trees 1
3. 1. Heap
3. 2. Max Heap / Min Heap
3. 3. Segment Tree
3. 4. Binary Index Tree
3. 5. Red Black Tree
3. 6. Treap
3. 7. Binary Search Tree - Mathematics 1
4. 1. Permutation
4. 2. Combination
4. 3. Prime Number
4. 4. Eratostheneen seula
4. 5. GCD Euclideon Algorithm - Recursion
- Sorting
6. 1. Bubble Sort
6. 2. Insertion Sort
6. 3. Selection Sort
6. 4. Quick Sort
6. 5. Merge Sort
6. 6. Heap Sort
6. 7. Radix Sort - Searching
7. 1. Backtracking
7. 2. Brute-Force
7. 3. Jump Search
7. 4. Linear Search
7. 5. Power Set
7. 6. Optimization Problem - Divide & Conquer
8.1. Binary Search - Greedy Algoritm
- Bitmask
- String
11. 1. Palindrome
11. 2. Manacher’s Algorithm
11. 3. Trie
11. 4. Suffix Tree - Maps
- Disjoint Set (Union/Find)
- Minimum Spanning Tree (MST)
14. 1. Kruskal’s Algorithm
14. 2. Prim’s Algorithm - Shortest Path
15. 1. Dijkstra’s Algorithm (O(n²))
15. 2. Bellman-Ford Algorithm
15. 3. Flyod-Warshall Algorithm (O(n³))
15. 4. Shortest Path Faster Algorithm - Graphs 1
16. 1. Graph Modeling
16. 2. Topological Sort
- 정점의 차수를 이용한 위상 정렬 (O(n³))
- DFS를 이용한 위상 정렬 (O(n²)) - Mathematics 2
17. 1. Binomial Coefficient
17. 2. Pascal’s Triangle
17. 3. Catalan Number
17. 4. Euler’s phi function
17. 5. Fermat’s little theorem
17. 6. Gaussian elimination
17. 8. Modular Arithmetic
17. 9. Discrete Mathmatics
17. 10. The Pigeonhole Priciple
17. 11. Stirling numbers of the second kind - Tree 2
18. 1. Lowest Common Ancestor
(Using Preorder DFS & Segment Tree / Using Sparse Table) - Graph 2
19. 1. Maximum Flow
19. 2. Ford-Fulkerson
19. 3. Edmond-Karp
19. 4. Dinic’s Algorithm
19. 5. Minimum Cut Maximum Flow
19. 6. Minimum Cost Maximum Flow
(Using Bellman-Ford Algorithm of SPFA / Hungarian Method)
19. 7. Bipartite Matching (Hopcroft-Karp Algorithm) - Hashing
- Complexity
- Huffman Coding
- Dynamic Programming
23. 1. 0–1 Knapsack Problem
23. 2. LCS, LIS
23. 3. Subset
23. 4. DP Optimization
23. 5. Knuth Optimization
23. 6. Divide & Conquer Optimization
23. 7. Convex Hull Optimization - Geometric Algorithm