Data Structures and System Design Interview Prep Notes

Data Structures and Algorithms Notes

Important Concepts

Graph 

1. DFS - Max Area of Island - LeetCode

2. BFS - Rotting Oranges - LeetCode

3. Detect cycle in undirected graph Graph Valid Tree - LeetCode

4. Topological Sort + Detect cycle in DAG Course Schedule II - LeetCode 

5. Union Find Algorithm 

1. No of Connected Components Number of Connected Components in an Undirected Graph - LeetCode

2. Redundant Connection - LeetCode 

3. Accounts Merge
   

6. Dijkstra's Network Delay Time - LeetCode (BFS + Priority Queue)

7. Prims and Kruskal's algorithm Min Cost to Connect All Points - LeetCode (BFS + Priority Queue) and Union Find Algorithm.

Sliding Window Algorithm

usual pattern is

while expanding window

        process right element

        try to shrink window

        update the answer based on the current window

1. Fixed Length Window - Permutations in String 
2. Variable Length Window - Minimum Window Substring
3. Sliding window with Deque - Sliding window maximum

Stack

1. Monotonic Stack - Largest Rectangle in Histogram
2. Revise - Car Fleet

Binary Search

1. Binary Search in 2d Matrix - Search a 2D matrix
2. Binary search the answer - Koko Eating Bananas
3. Search in sorted rotate array Search in sorted rotated array
4. Find Peak Element - LeetCode  Good binary search problem.

LinkedList

1. Reorder List  Combination of finding middle element of linkedlist + reversing linked list + merging two linekdlist
2. Remove Nth Node from LinkedList 
3. Copy List with random pointer
4. Linked List Cycle
5. Find duplicate number in array Duplicate number in array [Tortoise hare problem]

Trees

1. Subtree of another tree Teaches following concepts - Recursion, String Matching, TreeHash
2. LCA of binary search tree
3. Validate BST Teaches you how to maintain a range for tree node and also an interesting property of inorder traversal with binary search tree.
4. Kth Smallest Element in BST . Also think about kth largest element in BST.
5. Construct binary tree from inorder and preorder traversal 
6. Diameter of binary tree  Teaches you how to maintain max and what to return in recursion function call
7. Max path sum in binary tree Max path sum binary tree Teaches you how to maintain max and what to return in recursion function call
8. Serialize and Deserialize a binary tree Teaches you how to reconstruct a tree.
9. Delete Nodes And Return Forest - LeetCode Makes you think what traversal order will work and then what to return as value in each recursion.
10. All Nodes Distance K in Binary Tree Teaches you how to convert a tree to adjlist map and then operate like a graph
    
11. Vertical Order Traversal of a Binary Tree - LeetCode Teaches you verical order traversal of the graph + some custom sorting in the language. Problem statement is also tricky. 

Trie

1. Design add and search word data structure 
2. Trie with backtracking word search 2

1-D DP

1. Palindromic substrings - Teaches you how to cleverly check if a string is palindrome or not.
2. Decode Ways Recursion with memorization with some edge cases.
3. House Robber 2 Trick related to handling circular array with some dp.

Geometry

1. Minimum Area Rectangle - LeetCode Some interesting usage of diagonals in rectangle.

Prefix Sum

1. https://leetcode.com/problems/subarray-sum-equals-k/
2. https://leetcode.com/problems/continuous-subarray-sum/description/

Parentheses

1. https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
2. https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/