Data Structures & Algorithms

Don’t recall. You won’t remember it. Reason. Then you might.

Focus Areas

Linked-List, Bit-Manipulation, Stacks & Queues, Binary Search, Heaps, Greedy Algorithms, Dynamic Programming, Vectors/ArrayLists, Big O Time and Space, Sorting, Two Pointers, Sliding Window, Union-Find, String Manipulations, Trees and Graphs, BFS/DFS, Recursion, Back-Tracking, Hashing, Trie, Segment Trees & Binary Indexed Trees.

Core Porblem Solving Tricks

Attention

  • Binary Search

  • Prefix Sum

  • Two Pointers

  • Sliding Window

  • Divide & Conquer

  • Recursion & DP

  • Priority Queue

  • DFS/BFS

Core Algorithms & Data Structures

  1. Binary Search: [Basic] Find Key, Bisect Left, Bisect Right, Both Ends, [Rotated] Find Min (distinct), Find Key (distinct), Find Key (not distinct)

  2. Two pointers/Bookkeeping: Any Two Sum Pairs, All Two Sum Pairs, All Three Sum Triplets, 2 Way Partition (Quicksort), 3 Way Partition (Dutch National Flag)

  3. Sort: Heap Sort, Merge Sort, Count Inversions

  4. Stack: Using Queue

  5. Queue: Circular, Using Stack, Circular Deque

  6. Linked List: Cycle Detection, Reverse, Design

  7. Tree: Binary Traversal (Preorder, Inorder, Postorder, Level-order, Vertical/Unordered, Vertical/Ordered), N-Ary Traversal (Preorder, Postorder, Level-order), LCA, Path Sum, Serialize (Binary Tree, N-Ary Tree) Reconstruct (Preorder and Inorder, Inorder and Postorder, Preorder and Postorder, Preorder, Descriptions, Number of Ways), Encode N-Ary to Binary

  8. Binary Search Tree: Search, Insert, Delete, Balance, Threaded Binary Tree, Inorder Iterator, Validate BST, Serialize, LCA, Reconstruct (Preorder, Sorted List), Merge

  9. DSU: TODO

  10. Range Query Trees: Binary Indexed Tree/Fenwick Tree, Segment Tree, Cartesian Tree, Interval Tree

  11. Monotonic Stack: Next Greater, Previous Greater, Both Ends (Rectangle in Histogram), All Subarray Mins)

  12. Graph: BFS, Bidirectional BFS, Multi Source BFS, DFS, Cycle Detection (Undirected, Directed) Edge Classification, MST, SSSP, TSort, Articulation Vertices & Bridges, SCC

  13. DP - Sequence: Counting Path 2 2D Array, LCS, LIS, LPS, 0-1 Knapsack: Bounded (Target Sum, Equal Sum Partition), Unbounded (Min Items Count, All Combination Count), Edit Distance, Maximal Square, Rod Cutting

  14. Backtracking: Permutations, Permutation with Repetition, Combinations, Paranthesis, Subsets, Subsets with Repetition, Combination Sum Unbounded, Combination Sum Bounded

  15. String: Hashing, Rolling Hash, Trie, Trie DFS, Trie Application

Resources

Fundamentals

Attention

Problem Patterns

Note

Code Patterns

Note