# 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://heapclub.gitbook.io/heapclub-algorithms/interview-preparation/important-topics.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.