### Data Structures and System Design Interview Prep Notes

## Data Structures and Algorithms Notes

### Important Concepts

### Graph

Detect cycle in undirected graph Graph Valid Tree - LeetCode

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

Union Find Algorithm

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

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

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

- Fixed Length Window - Permutations in String
- Variable Length Window - Minimum Window Substring
- Sliding window with Deque - Sliding window maximum

### Stack

- Monotonic Stack - Largest Rectangle in Histogram
- Revise - Car Fleet

### Binary Search

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

### LinkedList

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

### Trees

- Subtree of another tree Teaches following concepts - Recursion, String Matching, TreeHash
- LCA of binary search tree
- Validate BST Teaches you how to maintain a range for tree node and also an interesting property of inorder traversal with binary search tree.
- Kth Smallest Element in BST . Also think about kth largest element in BST.
- Construct binary tree from inorder and preorder traversal
- Diameter of binary tree Teaches you how to maintain max and what to return in recursion function call
- 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
- Serialize and Deserialize a binary tree Teaches you how to reconstruct a tree.
- Delete Nodes And Return Forest - LeetCode Makes you think what traversal order will work and then what to return as value in each recursion.
- All Nodes Distance K in Binary Tree Teaches you how to convert a tree to adjlist map and then operate like a graph
- 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

- Design add and search word data structure
- Trie with backtracking word search 2

**1-D DP**

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

**Geometry**

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

#### Prefix Sum

### Parentheses

## Comments

## Post a Comment