# 1. Data Structures & Algorithms

## Coding Challenges

Do all the Leetcode problems from the "[Google Problems](https://heapclub.gitbook.io/heapclub-algorithms/google-problems)" section. Don't worry if you're not applying to Google. And don't be a cry baby. Just do them all and you'll be in a better shape.

## Data Structures

### Essentials - You're screwed if you don't know these.

Be able to implement any of these from scratch

1. [Dynamic Array](https://github.com/jwasham/coding-interview-university#arrays) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#arrays))
2. [Linked List](https://github.com/jwasham/coding-interview-university#linked-lists) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#linked-lists))
3. [Stack & Queue](https://github.com/jwasham/coding-interview-university#stack) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#stacks-and-queues))
4. [Hash Tables](https://github.com/jwasham/coding-interview-university#hash-table) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#hash-tables))
5. [Binary Search Tree](https://github.com/jwasham/coding-interview-university#binary-search-trees-bsts) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#binary-search-trees))
6. [BinaryHeaps](https://github.com/jwasham/coding-interview-university#heap--priority-queue--binary-heap) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#heap))
7. [Graphs](https://github.com/jwasham/coding-interview-university#graphs) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#graphs))
8. [Trie](https://github.com/raywenderlich/swift-algorithm-club/tree/master/Trie) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#trie-prefix-tree))
9. [Priority Queue](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#priority-queues)

### Advanced - Ignore if you don't have time.

1. [Red-Black Tree](https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#balanced-bst))
2. [AVL Tree](https://medium.com/basecs/the-little-avl-tree-that-could-86a3cae410c7) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#balanced-bst))
3. [Splay Tree](https://www.cs.cornell.edu/courses/cs3110/2009fa/recitations/rec-splay.html) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#balanced-bst))
4. [Radix trees](https://medium.com/basecs/compressing-radix-trees-without-too-many-tears-a2e658adb9a0) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#radix-tree))
5. [Suffix Tree](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#suffix-tree)
6. [B-Tree](https://medium.com/basecs/busying-oneself-with-b-trees-78bbf10522e7) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#b-tree))
7. [Fibonacci Heap](https://en.wikipedia.org/wiki/Fibonacci_heap) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/data-structures.md#fibonacci-heap))
8. [Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree)

## Algorithms

### Essentials - You're screwed if you don't know these.

Try implementing these.

1. [Bit Manipulation](https://github.com/jwasham/coding-interview-university#bitwise-operations) & [Numbers](https://github.com/jwasham/coding-interview-university/blob/master/extras/cheat%20sheets/bits-cheat-cheet.pdf) ([Notes](https://www.geeksforgeeks.org/bits-manipulation-important-tactics/)) - Unsigned vs signed numbers. Negative and positive number representation. Know how add and subtract works.
2. [Stability in Sorting](https://github.com/jwasham/coding-interview-university#sorting)
3. [Mergesort](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#mergesort)
4. [Quicksort](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#quicksort)
5. [Heapsort](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#heapsort) - Sort it in-place to get O(1) space
6. [Binary Search](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#binary-search)
7. [Selections - Kth Smallest Elements (Sort, QuickSelect, Mediums of Mediums)](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#selection-k-th-smallest-element) - Implement all three ways
8. [Permutations](https://leetcode.com/problems/permutations/description/) ([Notes](https://github.com/raywenderlich/swift-algorithm-club/tree/master/Combinatorics))
9. [Subsets](https://leetcode.com/problems/subsets/description/)
10. [BFS Graph](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#bfs-graph-traversal)
11. [DFS Graph](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#dfs-graph-traversal)
12. [Dijkstra's Algorithm](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#shortest-paths)
13. [Tree Traversals](https://github.com/jwasham/coding-interview-university#trees) - BFS, DFS (in-order, pre-order, post-order): Implement Recursive and Iterative
14. [External Sort](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#external-sort) - No implementation
15. [NP-Complete](https://github.com/jwasham/coding-interview-university#np-np-complete-and-approximation-algorithms) ([Video](https://www.youtube.com/watch?v=e0tGC6ZQdQE\&list=PLFDnELG9dpVxQCxuD-9BSy2E7BWY3t5Sm\&index=16)) - just know the concept
16. [Topological Sort](https://medium.com/basecs/spinning-around-in-cycles-with-directed-acyclic-graphs-a233496d4688)
17. Detect cycle in an undirected graph
18. Detect cycle in a directed graph
19. Count connected components in graph
20. Find strongly connected components in graph

### Advanced - Ignore if you don't have time.

1. [Bellman Ford](https://www.programiz.com/dsa/bellman-ford-algorithm)
2. [Floyd Warshall](https://www.google.com/search?q=floyd+warshall\&rlz=1C5CHFA_enUS779US779\&oq=floyd+warshall\&aqs=chrome..69i57j69i60.2758j0j1\&sourceid=chrome\&ie=UTF-8)
3. [Ford Fulkerson](https://www.google.com/search?q=ford+feoukerson\&rlz=1C5CHFA_enUS779US779\&oq=ford+feoukerson\&aqs=chrome..69i57.1045j0j1\&sourceid=chrome\&ie=UTF-8)
4. Disjoint Set
5. What is a Spanning tree?
6. Minimum Spanning Tree (Kruskal and Prim)
7. [A\*](https://en.wikipedia.org/wiki/A*_search_algorithm)
8. [Radix Sort](https://medium.com/basecs/getting-to-the-root-of-sorting-with-radix-sort-f8e9240d4224) —— Didn’t cover in class
9. [General Sorting Algorithms](https://github.com/jwasham/coding-interview-university#sorting) ([Notes](https://github.com/orrsella/soft-eng-interview-prep/blob/master/topics/algorithms.md#sorting)) - Bubble sort, insertion sort, etc.
10. Explain bipartite graph (how do you check if graph is bipartite?)
11. Do Traveling Salesperson and other NP problems