Q: Explain Bubble Sort, Selection Sort, and Insertion Sort with their complexities.

### Bubble Sort Repeatedly swaps adjacent elements if out of order. Optimised with early exit if no swaps occurred in a pass. - **Best**: $O(N)$ (already sorted, with flag), **Worst/Average**: $O(N^2)$. ### Selection Sort Finds the minimum in the unsorted portion and swaps it to the correct position. Always $O(N^2)$ regardless of input. - **Pro**: Minimises number of swaps ($O(N)$ swaps vs $O(N^2)$ for Bubble). ### Insertion Sort Builds a sorted sub-array from left to right, inserting each element into its correct position. - **Best**: $O(N)$ (nearly sorted input), **Worst/Average**: $O(N^2)$. - **When to use**: Excellent for small arrays ($N < 20$) or nearly sorted data — used as the base case inside Timsort. Key Takeaway: Insertion Sort is the best O(N²) algorithm for nearly-sorted data. All three have O(1) space. Prefer Merge/Quick sort for large N.

Q: What is the Two-Pointer Technique?

The **Two-Pointer Technique** uses two indices that typically start at opposite ends (or same end) of an array and converge, reducing nested loop $O(N^2)$ problems to $O(N)$. ### When to Apply: - Array/string is **sorted** or the problem involves comparing elements from both ends. - Finding pairs that sum to a target. - Checking palindromes, removing duplicates in-place. - Sliding window variants (fast + slow pointers). Key Takeaway: Two-pointers reduce O(N²) pair-search problems to O(N) by exploiting sorted order or symmetry. Master this before interviews.

Q: What is the Sliding Window Technique?

The **Sliding Window** technique maintains a window (contiguous sub-array/sub-string) and slides it across the input, avoiding redundant recomputation. ### Fixed Window (size K): Slide the window by adding the next element and removing the oldest one. - Time: $O(N)$, Space: $O(1)$. ### Variable Window: Expand the right pointer; shrink the left pointer when a constraint is violated. - Used for: Longest substring without repeating characters, smallest subarray with sum ≥ target. Key Takeaway: Sliding Window converts O(N²) brute-force subarray problems into O(N) by maintaining a running computation as the window moves.

Q: What is Recursion and how do you identify the Base Case?

**Recursion** is when a function calls itself with a smaller or simpler sub-problem until it reaches a **base case** that returns a known value without further recursion. ### Key Components: 1. **Base Case**: The termination condition that stops recursion (e.g., `n === 0`). 2. **Recursive Case**: The function calling itself with a *smaller* input toward the base case. 3. **Call Stack**: Each recursive call pushes a frame; too many calls without a base case → **Stack Overflow**. ### Recursion vs Iteration: - Recursion is elegant but uses $O(N)$ call stack space (can cause stack overflow for large $N$). - Most recursive solutions can be converted to iterative using an explicit stack. Key Takeaway: Always define a clear base case to prevent infinite recursion. Use memoization to eliminate redundant recursive calls from O(2^N) to O(N).

Q: What is a Binary Tree and what are its key properties?

A **Binary Tree** is a hierarchical data structure where each node has at most **two children** (left and right). ### Key Terms: - **Height**: Longest path from root to a leaf node. - **Depth**: Distance from the root to a given node. - **Full Binary Tree**: Every node has 0 or 2 children. - **Complete Binary Tree**: All levels are filled except possibly the last, filled left-to-right. - **Perfect Binary Tree**: All internal nodes have 2 children; all leaves at the same depth. - **Balanced**: Height difference between left and right subtrees ≤ 1 at every node (AVL, Red-Black Trees). ### Traversal Types: | Traversal | Order | Use Case | |---|---|---| | Inorder | Left → Root → Right | BST sorted output | | Preorder | Root → Left → Right | Tree serialisation | | Postorder | Left → Right → Root | Directory size calc | | Level Order | BFS level by level | Shortest path | Key Takeaway: Master all four traversal types (inorder, preorder, postorder, level-order) — they underpin most tree interview problems.

Question 1

What is the difference between an Array and a Linked List?

Accepted Answer

**Arrays** store elements in contiguous memory blocks; **Linked Lists** store elements in nodes scattered in memory, connected via pointers.

### Time Complexity Comparison:
| Operation | Array | Linked List |
|---|---|---|
| **Access by index** | $O(1)$ | $O(N)$ |
| **Search** | $O(N)$ | $O(N)$ |
| **Insert at head** | $O(N)$ (shift) | $O(1)$ |
| **Insert at tail** | $O(1)$ amortized | $O(N)$ (singly) / $O(1)$ (doubly with tail ptr) |
| **Delete at head** | $O(N)$ (shift) | $O(1)$ |

### When to Use:
- **Array**: Random index access is frequent; cache locality matters; fixed or slowly growing data.
- **Linked List**: Frequent insertions/deletions at the head/middle; size is highly dynamic.

Key Takeaway: Arrays provide O(1) random access; Linked Lists provide O(1) head insertions. Choose based on the dominant operation in your algorithm.

Question 2

What is Big-O Notation and why is it important?

Accepted Answer

**Big-O Notation** describes the *worst-case* upper bound on how an algorithm's runtime or memory usage grows relative to the input size $N$.

### Common Complexity Classes (Best → Worst):
| Notation | Name | Example |
|---|---|---|
| $O(1)$ | Constant | Hash map lookup |
| $O(\log N)$ | Logarithmic | Binary search |
| $O(N)$ | Linear | Array scan |
| $O(N \log N)$ | Linearithmic | Merge sort |
| $O(N^2)$ | Quadratic | Bubble sort |
| $O(2^N)$ | Exponential | Subsets generation |
| $O(N!)$ | Factorial | Permutation generation |

### Analysis Rules:
- **Drop constants**: $O(2N) = O(N)$.
- **Drop non-dominant terms**: $O(N^2 + N) = O(N^2)$.
- **Space complexity** counts auxiliary memory (excluding the input itself).

Key Takeaway: Big-O is the universal language for comparing algorithm efficiency. Always analyse both time and space complexity when designing solutions.

Question 3

What are Stack and Queue data structures and where are they used?

Accepted Answer

**Stack** follows **LIFO** (Last-In, First-Out) — the most recently added element is removed first.
**Queue** follows **FIFO** (First-In, First-Out) — the oldest element is removed first.

### Operations (both $O(1)$):
| Structure | Add | Remove | Peek |
|---|---|---|---|
| Stack | `push` | `pop` | `peek/top` |
| Queue | `enqueue` | `dequeue` | `front` |

### Real-World Use Cases:
- **Stack**: Browser back/forward history, call stack (recursion), undo/redo, balanced parenthesis checking, DFS traversal.
- **Queue**: CPU/disk task scheduling, BFS traversal, print spoolers, request queues in web servers.

Key Takeaway: Stacks model LIFO access (DFS, recursion); Queues model FIFO access (BFS, scheduling). Both offer O(1) push/pop/enqueue/dequeue with proper implementations.

Question 4

How does Binary Search work and what are its prerequisites?

Accepted Answer

**Binary Search** repeatedly halves the search space by comparing the target to the middle element of a **sorted** array, achieving $O(\log N)$ time complexity.

### Prerequisites:
1. The collection **must be sorted**.
2. Random access (O(1) index lookup) — works best on arrays.

### Algorithm:
1. Set `low = 0`, `high = n - 1`.
2. While `low <= high`: compute `mid = low + Math.floor((high - low) / 2)`.
3. If `arr[mid] === target` → found.
4. If `arr[mid] < target` → search right half (`low = mid + 1`).
5. If `arr[mid] > target` → search left half (`high = mid - 1`).

Key Takeaway: Binary Search achieves O(log N) by halving the search space each step. Always use `low + (high - low) / 2` to prevent integer overflow.

Question 5

How does a Hash Table work internally?

Accepted Answer

A **Hash Table** maps keys to values using a **hash function** that converts a key into a bucket index. It provides amortised $O(1)$ average-time lookup, insertion, and deletion.

### Collision Resolution:
- **Separate Chaining**: Each bucket holds a linked list of entries that hash to the same index. Lookup: $O(1 + \alpha)$ where $\alpha$ = load factor.
- **Open Addressing (Linear/Quadratic Probing)**: On collision, probe adjacent buckets until an empty slot is found.

### Load Factor & Rehashing:
When the load factor ($\alpha = n / m$, entries/buckets) exceeds a threshold (typically $0.75$), the table **rehashes** — doubles capacity and reinserts all keys — an $O(N)$ operation amortised to $O(1)$.

Key Takeaway: Hash Tables achieve O(1) average-case operations via hash functions. Manage load factor < 0.75 to keep collision chains short.

Question 6

Explain Bubble Sort, Selection Sort, and Insertion Sort with their complexities.

Accepted Answer

### Bubble Sort
Repeatedly swaps adjacent elements if out of order. Optimised with early exit if no swaps occurred in a pass.
- **Best**: $O(N)$ (already sorted, with flag), **Worst/Average**: $O(N^2)$.

### Selection Sort
Finds the minimum in the unsorted portion and swaps it to the correct position. Always $O(N^2)$ regardless of input.
- **Pro**: Minimises number of swaps ($O(N)$ swaps vs $O(N^2)$ for Bubble).

### Insertion Sort
Builds a sorted sub-array from left to right, inserting each element into its correct position.
- **Best**: $O(N)$ (nearly sorted input), **Worst/Average**: $O(N^2)$.
- **When to use**: Excellent for small arrays ($N < 20$) or nearly sorted data — used as the base case inside Timsort.

Key Takeaway: Insertion Sort is the best O(N²) algorithm for nearly-sorted data. All three have O(1) space. Prefer Merge/Quick sort for large N.

Question 7

What is the Two-Pointer Technique?

Accepted Answer

The **Two-Pointer Technique** uses two indices that typically start at opposite ends (or same end) of an array and converge, reducing nested loop $O(N^2)$ problems to $O(N)$.

### When to Apply:
- Array/string is **sorted** or the problem involves comparing elements from both ends.
- Finding pairs that sum to a target.
- Checking palindromes, removing duplicates in-place.
- Sliding window variants (fast + slow pointers).

Key Takeaway: Two-pointers reduce O(N²) pair-search problems to O(N) by exploiting sorted order or symmetry. Master this before interviews.

Question 8

What is the Sliding Window Technique?

Accepted Answer

The **Sliding Window** technique maintains a window (contiguous sub-array/sub-string) and slides it across the input, avoiding redundant recomputation.

### Fixed Window (size K):
Slide the window by adding the next element and removing the oldest one.
- Time: $O(N)$, Space: $O(1)$.

### Variable Window:
Expand the right pointer; shrink the left pointer when a constraint is violated.
- Used for: Longest substring without repeating characters, smallest subarray with sum ≥ target.

Key Takeaway: Sliding Window converts O(N²) brute-force subarray problems into O(N) by maintaining a running computation as the window moves.

Question 9

What is Recursion and how do you identify the Base Case?

Accepted Answer

**Recursion** is when a function calls itself with a smaller or simpler sub-problem until it reaches a **base case** that returns a known value without further recursion.

### Key Components:
1. **Base Case**: The termination condition that stops recursion (e.g., `n === 0`).
2. **Recursive Case**: The function calling itself with a *smaller* input toward the base case.
3. **Call Stack**: Each recursive call pushes a frame; too many calls without a base case → **Stack Overflow**.

### Recursion vs Iteration:
- Recursion is elegant but uses $O(N)$ call stack space (can cause stack overflow for large $N$).
- Most recursive solutions can be converted to iterative using an explicit stack.

Key Takeaway: Always define a clear base case to prevent infinite recursion. Use memoization to eliminate redundant recursive calls from O(2^N) to O(N).

Question 10

What is a Binary Tree and what are its key properties?

Accepted Answer

A **Binary Tree** is a hierarchical data structure where each node has at most **two children** (left and right).

### Key Terms:
- **Height**: Longest path from root to a leaf node.
- **Depth**: Distance from the root to a given node.
- **Full Binary Tree**: Every node has 0 or 2 children.
- **Complete Binary Tree**: All levels are filled except possibly the last, filled left-to-right.
- **Perfect Binary Tree**: All internal nodes have 2 children; all leaves at the same depth.
- **Balanced**: Height difference between left and right subtrees ≤ 1 at every node (AVL, Red-Black Trees).

### Traversal Types:
| Traversal | Order | Use Case |
|---|---|---|
| Inorder | Left → Root → Right | BST sorted output |
| Preorder | Root → Left → Right | Tree serialisation |
| Postorder | Left → Right → Root | Directory size calc |
| Level Order | BFS level by level | Shortest path |

Key Takeaway: Master all four traversal types (inorder, preorder, postorder, level-order) — they underpin most tree interview problems.

Question 11

What is a Binary Search Tree (BST) and how do Search, Insert, and Delete work?

Accepted Answer

A **Binary Search Tree (BST)** maintains the **BST invariant**: for every node, all values in its left subtree are **less than** the node, and all values in its right subtree are **greater than** the node.

### Operations:
- **Search**: Compare target to current node; go left if smaller, right if larger. $O(H)$ where $H$ = height.
- **Insert**: Traverse to the correct position and add the node. $O(H)$.
- **Delete**: Three cases:
  1. Leaf → simply remove.
  2. One child → replace node with child.
  3. Two children → replace with **in-order successor** (smallest in right subtree) and delete successor.
- **Average case**: $O(\log N)$ for balanced BST. **Worst case**: $O(N)$ for skewed (sorted insertion).

Key Takeaway: BST gives O(log N) average-case operations. Always consider balanced BST variants (AVL, Red-Black) for guaranteed O(log N) in production.

Question 12

How do you implement a Queue using two Stacks?

Accepted Answer

**Idea**: Use two stacks — `inbox` and `outbox`.
- **Enqueue**: Always push onto `inbox`. $O(1)$.
- **Dequeue**: If `outbox` is empty, pop ALL from `inbox` into `outbox` (reverses order). Pop from `outbox`. Amortised $O(1)$ — each element moves at most once.

This is a classic problem demonstrating amortised analysis. Each element is pushed and popped exactly twice across both stacks.

Key Takeaway: Two-stack queue is a classic amortised O(1) design. Interviewers use it to test understanding of amortised analysis and data structure composition.

Question 13

How does Merge Sort work and why is it preferred for stable sorting?

Accepted Answer

**Merge Sort** is a **divide-and-conquer** sorting algorithm:
1. **Divide**: Split array into two halves recursively until each sub-array has 1 element.
2. **Conquer**: Merge adjacent sorted sub-arrays back together in sorted order.

### Complexity:
- **Time**: $O(N \log N)$ at all cases (best, average, worst).
- **Space**: $O(N)$ auxiliary space for the merge step.
- **Stable**: Equal elements preserve their relative input order.

### When to Use:
- Sorting **linked lists** (preferred over Quicksort — no random access needed).
- **External sorting** of data too large for RAM (merge sorted file chunks).
- Any scenario requiring **stable sort** with guaranteed $O(N \log N)$.

Key Takeaway: Merge Sort guarantees O(N log N) for all cases with O(N) space. Prefer it for linked lists and when stability matters.

Question 14

How do you reverse a string and check if two strings are anagrams?

Accepted Answer

### String Reversal:
- Swap characters using two pointers from both ends: $O(N)$ time, $O(1)$ extra space (in-place on a char array).

### Anagram Check:
Two strings are anagrams if they contain the same characters with the same frequencies.
- **Sort approach**: Sort both strings and compare — $O(N \log N)$.
- **Frequency map**: Count character frequencies — $O(N)$ time, $O(1)$ space (bounded by 26 alphabets).

Key Takeaway: String problems often reduce to frequency counting or two-pointer traversal. Always clarify character set constraints (ASCII vs Unicode).

Question 15

What is the Prefix Sum technique and when is it useful?

Accepted Answer

A **Prefix Sum** array `prefix[i]` stores the sum of elements from index `0` to `i`.

### Construction: $O(N)$
`prefix[i] = prefix[i-1] + arr[i]`

### Range Sum Query: $O(1)$
Sum of `arr[l..r]` = `prefix[r] - prefix[l-1]` (or `prefix[r] - prefix[l] + arr[l]`).

### Use Cases:
- Range sum queries (subarray sum equals K).
- Finding equilibrium index.
- 2D prefix sums for rectangle sums in image processing.
- Difference arrays for range updates.

Key Takeaway: Prefix Sums preprocess an array in O(N) to answer range sum queries in O(1). Essential for problems involving subarray sums.

Question 16

How do you detect a cycle in a Linked List (Floyd's Algorithm)?

Accepted Answer

**Floyd's Cycle Detection** (Tortoise and Hare) uses two pointers:
- **Slow pointer**: Moves 1 step at a time.
- **Fast pointer**: Moves 2 steps at a time.

If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle.
- **Time**: $O(N)$, **Space**: $O(1)$.

### Finding Cycle Entry Point:
After detection, reset one pointer to the head and advance both one step at a time. They meet at the cycle's entry node.

Key Takeaway: Floyd's algorithm detects cycles in O(N) / O(1) without extra memory. A hashtable approach would use O(N) space.

Question 17

How do you validate balanced parentheses using a Stack?

Accepted Answer

**Algorithm**:
1. Iterate each character in the string.
2. If it is an **opening bracket** (`(`, `[`, `{`), **push** it onto the stack.
3. If it is a **closing bracket**, check if the stack's top matches the expected opener:
   - If yes → **pop** the stack.
   - If no or stack is empty → **invalid** (return false).
4. After iterating, the string is valid only if the stack is **empty**.

- **Time**: $O(N)$, **Space**: $O(N)$.

Key Takeaway: A stack is the natural data structure for matching nested/balanced structures. This pattern extends to HTML/XML tag validation.

Question 18

What is the difference between Memoization (Top-Down DP) and Tabulation (Bottom-Up DP)?

Accepted Answer

Both techniques optimise **overlapping sub-problems** from $O(2^N)$ recursive brute-force to $O(N)$.

### Memoization (Top-Down):
- Recursive approach + caching computed results in a memo table.
- Computes only the sub-problems actually needed.
- $O(N)$ time, $O(N)$ space (memo table + call stack).

### Tabulation (Bottom-Up):
- Iteratively fills a table starting from the smallest sub-problems.
- No recursion → no stack overflow risk.
- $O(N)$ time, $O(N)$ space (reducible to $O(1)$ by keeping only the last 2 values).

Key Takeaway: Memoization is easier to implement from recursive solutions. Tabulation avoids stack overhead and can often reduce space from O(N) to O(1).

Question 19

What is the difference between BFS and DFS graph traversal?

Accepted Answer

Both BFS and DFS traverse all reachable vertices in $O(V + E)$ time.

| Property | BFS | DFS |
|---|---|---|
| **Data Structure** | Queue | Stack (or recursion) |
| **Space** | $O(W)$ max width | $O(H)$ max height |
| **Order** | Level-by-level | Deep path first |
| **Shortest Path** | ✅ (unweighted) | ❌ |
| **Cycle Detection** | ✅ | ✅ |
| **Topological Sort** | ❌ | ✅ |
| **Connected Components** | ✅ | ✅ |

### When to Use:
- **BFS**: Shortest path (unweighted), social network proximity levels, word ladder.
- **DFS**: Maze/puzzle solving, topological sort, strongly connected components.

Key Takeaway: BFS uses a queue and finds shortest paths in unweighted graphs. DFS uses a stack and is ideal for topological sorting and cycle detection.

Question 20

How does Quick Sort work and what makes it fast in practice?

Accepted Answer

**Quick Sort** is a divide-and-conquer algorithm:
1. **Choose a pivot** (e.g., last element, median-of-3).
2. **Partition**: Rearrange array so elements < pivot are left, elements > pivot are right.
3. **Recursively sort** left and right partitions.

### Complexity:
- **Average**: $O(N \log N)$ (random or median pivot).
- **Worst**: $O(N^2)$ (sorted input with last-element pivot — always smallest partition).
- **Space**: $O(\log N)$ call stack average, $O(N)$ worst.

### Why Faster in Practice:
- Excellent **cache locality** (in-place partitioning).
- Small constant factors vs Merge Sort's $O(N)$ auxiliary allocation.
- **Randomised pivot** eliminates worst case for most inputs.

Key Takeaway: Quick Sort is the fastest practical sort due to cache efficiency. Use randomised pivot or median-of-3 to avoid O(N²) worst case.

Question 21

How do you traverse a 2D matrix (row-major, spiral, diagonal)?

Accepted Answer

### Row-Major Traversal: $O(M 	imes N)$
Access each row left-to-right, top-to-bottom. Maximises CPU cache efficiency since 2D arrays are stored in row-major order in memory.

### Spiral Order Traversal:
Maintain four boundaries — `top`, `bottom`, `left`, `right` — and peel off the outer layer in each pass (right → down → left → up), shrinking boundaries inward.

Key Takeaway: Matrix problems often require boundary pointers. Spiral order is a classic interview question testing careful index management.

Question 22

What are Counting Sort and Radix Sort and when do they beat O(N log N)?

Accepted Answer

### Counting Sort: $O(N + K)$ where $K$ = range of values
- Count frequency of each value → compute cumulative counts → place elements.
- **Constraint**: Only works with **non-negative integer** keys in a bounded range $[0, K]$.
- Ideal when $K = O(N)$ (e.g., sorting ages 0–120, exam scores 0–100).

### Radix Sort: $O(N 	imes d)$ where $d$ = number of digits
- Sort digit by digit from least significant to most significant using a **stable** sub-sort (Counting Sort).
- Works on integers or fixed-length strings.
- Beats $O(N \log N)$ when $d \ll \log N$ and $K = O(N)$.

Key Takeaway: Counting/Radix Sort break the O(N log N) comparison barrier when input values are integers in a bounded range.

Question 23

How do you find the maximum and minimum in an array with fewest comparisons?

Accepted Answer

### Naive Approach: 2N − 2 comparisons (two separate scans).

### Tournament Method: ~3N/2 comparisons (optimal).
- Process elements in **pairs**: compare the pair with each other first (1 comparison).
- Compare the **larger** with the current max (1 comparison).
- Compare the **smaller** with the current min (1 comparison).
- Total: 3 comparisons per 2 elements = **3N/2 − 2** total.

This is the information-theoretically optimal minimum number of comparisons for this problem.

Key Takeaway: The tournament method finds min+max using only 3N/2 comparisons vs 2N for naive separate scans — a classic optimisation problem.

Question 24

How do you check if a number is a Power of Two using bit manipulation?

Accepted Answer

**Key Insight**: A power of two in binary has exactly **one set bit**.
- $1 = 0001$, $2 = 0010$, $4 = 0100$, $8 = 1000$.

**Trick**: $N$ & $(N - 1)$ clears the lowest set bit of $N$.
- For a power of two, this equals $0$ (only one bit → cleared completely).
- For non-powers (e.g., $6 = 0110$): $6$ & $5 = 0110$ & $0101 = 0100 
eq 0$.

`isPowerOfTwo(N) = N > 0 && (N & (N-1)) === 0`

Key Takeaway: n & (n-1) is a fundamental bit trick that clears the lowest set bit. Powers of two have exactly one set bit, making the result 0.

Question 25

How do you find the first non-repeating character in a string?

Accepted Answer

**Two-Pass Approach**: $O(N)$ time, $O(1)$ space (26 characters max):
1. **First pass**: Count frequency of every character.
2. **Second pass**: Return the first character with frequency = 1.

Alternatively, use a **LinkedHashMap** to maintain insertion order while tracking frequencies (required if you need the actual character, not just its index).

Key Takeaway: A fixed-size frequency array (26 for lowercase letters) gives O(1) space vs O(N) for a HashMap. Always clarify the character set.

Question 26

How do you reverse a Singly Linked List iteratively and recursively?

Accepted Answer

### Iterative (O(1) space — preferred):
Maintain three pointers: `prev`, `curr`, `next`. Redirect each node's `.next` to `prev`, then advance all three pointers.

### Recursive (O(N) call stack):
Recurse to the tail, then re-link pointers on the way back up.

Key Takeaway: Prefer iterative reversal for O(1) space. The three-pointer (prev, curr, next) pattern is fundamental for in-place linked list manipulation.

Question 27

What is the space-optimised Fibonacci solution?

Accepted Answer

Standard bottom-up Fibonacci DP creates an $O(N)$ table. But since $F(N) = F(N-1) + F(N-2)$, we only need the **last two values** at any time.

By using two rolling variables we reduce space to $O(1)$ while keeping time at $O(N)$.

Key Takeaway: Space optimisation by rolling variables is a key DP technique. Whenever the recurrence only references the last K states, you can reduce space from O(N) to O(K).

Question 28

How does Kadane's Algorithm find the Maximum Subarray Sum in O(N)?

Accepted Answer

**Kadane's Algorithm** solves Maximum Subarray Sum in $O(N)$ time and $O(1)$ space.

**Core Decision at each element**:
At each position $i$, choose the maximum of:
- **Extend** existing subarray: `currentMax + arr[i]`
- **Start fresh** from current element: `arr[i]`

Track the global maximum across all positions.

The key insight: if the current running sum becomes negative, it can only hurt future elements — so we reset it.

Key Takeaway: Kadane's Algorithm is the canonical O(N) solution for maximum subarray. It illustrates the "extend vs restart" DP decision pattern.

Question 29

What is a Heap (Min-Heap / Max-Heap) and how is it used as a Priority Queue?

Accepted Answer

A **Heap** is a complete binary tree stored as an array satisfying the **heap property**:
- **Max-Heap**: Parent ≥ children (root = maximum element).
- **Min-Heap**: Parent ≤ children (root = minimum element).

### Key Operations:
| Operation | Time |
|---|---|
| Insert (sift-up) | $O(\log N)$ |
| Remove root (sift-down) | $O(\log N)$ |
| Peek (root) | $O(1)$ |
| Build heap (heapify) | $O(N)$ |

### Parent/Child Index in Array (0-indexed):
- Parent of $i$: `Math.floor((i - 1) / 2)`
- Left child: `2i + 1`, Right child: `2i + 2`

Key Takeaway: Use a Min-Heap of size K for K-largest problems. Heap sort achieves O(N log N) with O(1) space — an in-place advantage over Merge Sort.

Question 30

How do you find a Missing Number using XOR or Gauss's formula?

Accepted Answer

Given array of $N$ distinct integers in range $[0, N]$ with one missing:

### Approach 1: Gauss Formula — $O(N)$ time, $O(1)$ space
Expected sum $= N(N+1)/2$. Missing = expected − actual sum.

### Approach 2: XOR — $O(N)$ time, $O(1)$ space
XOR all numbers $0..N$ with all array elements. Paired duplicates cancel ($x \oplus x = 0$); remaining value = missing number.
- XOR approach avoids potential integer overflow with large $N$ (though JavaScript uses BigInt or 64-bit float).

Key Takeaway: XOR cancellation (a⊕a=0, a⊕0=a) is an O(1) space trick for finding unique/missing elements. Know both XOR and sum approaches.

Question 31

How does Backtracking work and how do you generate all Subsets?

Accepted Answer

**Backtracking** is a recursive algorithmic technique that incrementally builds candidates for solutions and **abandons** (backtracks) a path as soon as it violates constraints.

### Template:
```
backtrack(choices, current_state):
  if is_solution(current_state): record_solution(); return
  for choice in choices:
    make_choice()
    backtrack(remaining_choices, updated_state)
    undo_choice()  // BACKTRACK
```

### Subsets (Power Set): $O(N 	imes 2^N)$
At each index, choose to **include** or **exclude** the element.

Key Takeaway: Backtracking = DFS + undo. The "make choice → recurse → undo choice" template applies to subsets, permutations, combinations, Sudoku, and N-Queens.

Question 32

What is Topological Sorting and how does Kahn's Algorithm work?

Accepted Answer

**Topological Sort** produces a linear ordering of vertices in a **Directed Acyclic Graph (DAG)** such that every edge $u 	o v$ places $u$ before $v$.

### Kahn's Algorithm (BFS-based):
1. Compute **in-degree** of every vertex (number of incoming edges).
2. Enqueue all vertices with in-degree = 0 (no dependencies).
3. While queue is non-empty:
   - Dequeue vertex $u$; add to result.
   - For each neighbour $v$ of $u$: decrement in-degree of $v$. If it becomes 0 → enqueue $v$.
4. If result contains all $V$ vertices → valid topological order. Else → **cycle exists**.

- **Time**: $O(V + E)$, **Space**: $O(V)$.

Key Takeaway: Topological sort only works on DAGs. Use Kahn's for BFS-style (detects cycles naturally) or DFS postorder for recursive solutions.

Question 33

How does Dijkstra's Algorithm find the Shortest Path in a weighted graph?

Accepted Answer

**Dijkstra's Algorithm** finds shortest paths from a source vertex to all other vertices in a graph with **non-negative edge weights**.

### Steps:
1. Initialise distance array: `dist[source] = 0`, all others = $\infty$.
2. Use a **min-priority queue** (min-heap) ordered by distance.
3. While heap is non-empty:
   - Extract vertex $u$ with minimum distance.
   - For each neighbour $v$ with edge weight $w$:
     - If `dist[u] + w < dist[v]` → **relax** the edge: update `dist[v]` and push $v$ to heap.
4. Result: `dist[]` = shortest distances from source.

- **Complexity**: $O((V + E) \log V)$ with binary min-heap.
- **Constraint**: Fails with **negative edge weights** → use Bellman-Ford instead.

Key Takeaway: Dijkstra's O((V+E)log V) requires non-negative weights. For negative weights use Bellman-Ford O(VE). For all-pairs use Floyd-Warshall O(V³).

Question 34

How do you solve the Coin Change problem with Dynamic Programming?

Accepted Answer

### Problem: Given coin denominations and a target amount, find the minimum number of coins to reach the target.

### DP Formulation:
- **State**: `dp[i]` = minimum coins needed to make amount `i`.
- **Base case**: `dp[0] = 0`.
- **Recurrence**: `dp[i] = 1 + min(dp[i - coin])` for each coin ≤ i.
- **Time**: $O(	ext{amount} 	imes 	ext{coins})$, **Space**: $O(	ext{amount})$.

Key Takeaway: Coin Change is the archetypal unbounded knapsack DP. The recurrence dp[i] = 1 + min(dp[i - coin]) models "use 1 coin + optimal remaining".

Question 35

How do you compute the Longest Common Subsequence (LCS)?

Accepted Answer

### LCS vs LCS (Substring):
- **Subsequence**: Characters need not be contiguous (e.g., "ACE" is a subsequence of "ABCDE").
- **Substring**: Characters must be contiguous.

### DP Recurrence:
Let `dp[i][j]` = LCS of `s1[0..i-1]` and `s2[0..j-1]`.
```
if s1[i-1] === s2[j-1]:  dp[i][j] = 1 + dp[i-1][j-1]
else:                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
- **Time**: $O(M 	imes N)$, **Space**: $O(M 	imes N)$ (reducible to $O(\min(M,N))$).

Key Takeaway: LCS is a foundational DP problem powering diff tools (git diff), spell checkers, and DNA sequence alignment. Master the 2D table and recurrence.

Question 36

How do you solve the 0/1 Knapsack problem with Dynamic Programming?

Accepted Answer

### Problem: Given $N$ items each with weight $w_i$ and value $v_i$, maximise value without exceeding capacity $W$. Each item can be taken **0 or 1** times.

### DP State:
`dp[i][c]` = max value using items $[0..i-1]$ with capacity $c$.
```
dp[i][c] = max(dp[i-1][c],                    // skip item i
               dp[i-1][c - w[i]] + v[i])      // take item i (if w[i] <= c)
```
### 1D Space Optimisation:
Iterate capacity **right-to-left** to prevent reusing the same item (0/1 constraint). Left-to-right would give unbounded knapsack.

Key Takeaway: Reverse capacity traversal in 1D Knapsack enforces the 0/1 constraint. Forward traversal (unbounded knapsack) allows infinite reuse of items.

Question 37

What is a Trie (Prefix Tree) and what are its advantages over a hash map for strings?

Accepted Answer

A **Trie** (retrieval tree / prefix tree) is a tree where each node represents a character, and paths from root to leaf nodes spell out keys.

### Operations: $O(L)$ where $L$ = key length
- **Insert/Search**: Traverse one character at a time from root.
- **Prefix Query**: Check if any word starts with a given prefix in $O(P)$ where $P$ = prefix length.

### Advantages over Hash Map:
- Efficient **prefix searches** and **autocomplete** — hash maps can't answer "all words starting with 'un'" efficiently.
- Shared prefix storage saves space for large dictionaries.
- Lexicographic order inherently supported.

Key Takeaway: Tries provide O(L) prefix queries — perfect for autocomplete, spell checkers, and IP routing tables. Hash maps lack prefix semantics.

Question 38

What is Union-Find (Disjoint Set Union) and how do Path Compression and Union by Rank work?

Accepted Answer

**Union-Find (DSU)** maintains a collection of disjoint sets and supports:
- **Find(x)**: Returns the **root/representative** of x's set.
- **Union(x, y)**: Merges the sets containing x and y.

### Optimisations:
- **Path Compression**: During Find, redirect every node directly to the root, flattening the tree.
- **Union by Rank**: Attach the shorter tree under the taller one to keep height logarithmic.

### Complexity with both optimisations: $O(\alpha(N))$ amortised ≈ $O(1)$ practically.

### Use Cases: Cycle detection, Kruskal's MST, connected components, social network grouping.

Key Takeaway: Union-Find with path compression + union by rank achieves O(α(N)) amortised — nearly O(1). Essential for Kruskal's MST and cycle detection.

Question 39

What is a Segment Tree and when is it better than a Prefix Sum?

Accepted Answer

A **Segment Tree** is a binary tree where each node stores aggregate information (sum, min, max) of a range of the original array.

### Complexity:
| Operation | Prefix Sum | Segment Tree |
|---|---|---|
| Build | $O(N)$ | $O(N)$ |
| Range Query | $O(1)$ | $O(\log N)$ |
| Point Update | $O(N)$ rebuild | $O(\log N)$ |

### When to Use Segment Tree:
- **Dynamic arrays** with frequent updates + queries — prefix sum requires $O(N)$ rebuild on update.
- Range min/max queries (prefix sum only handles sums).
- Lazy propagation for **range updates** in $O(\log N)$.

Key Takeaway: Use Segment Trees when both range queries AND point updates are frequent. Prefix sums give O(1) query but O(N) update.

Question 40

What is an AVL Tree and how do rotations maintain balance?

Accepted Answer

An **AVL Tree** is a self-balancing BST where the **balance factor** of every node = height(left) − height(right) ∈ {−1, 0, 1}.

### Rotations to Restore Balance:
| Case | Imbalance | Fix |
|---|---|---|
| **LL** (Left-Left) | Node is right-heavy after left child insertion | Right Rotation |
| **RR** (Right-Right) | Node is left-heavy after right child insertion | Left Rotation |
| **LR** (Left-Right) | Left child's right subtree is heavy | Left Rotate child → Right Rotate node |
| **RL** (Right-Left) | Right child's left subtree is heavy | Right Rotate child → Left Rotate node |

AVL trees guarantee $O(\log N)$ height at all times, ensuring $O(\log N)$ search, insert, delete.

Key Takeaway: AVL Trees guarantee O(log N) at the cost of rotation overhead on insertions. Red-Black Trees (used in Java TreeMap, C++ std::map) have lighter balancing.

Question 41

How do you detect a cycle in an undirected and directed graph?

Accepted Answer

### Undirected Graph — DFS with Parent Tracking:
During DFS, if we visit a neighbour that is already visited AND is not the parent of the current node → **cycle detected**.

### Directed Graph — DFS with Recursion Stack (Coloring):
Use 3 colors:
- **0 (White)**: Not visited.
- **1 (Gray)**: Currently in the recursion stack (being explored).
- **2 (Black)**: Fully processed.

If we reach a **Gray** neighbour → **back edge → cycle**!

Key Takeaway: Undirected cycle: DFS + parent check. Directed cycle: DFS + recursion stack (gray color). Both O(V+E).

Question 42

What is a Monotonic Stack and how does it solve Next Greater Element?

Accepted Answer

A **Monotonic Stack** maintains elements in strictly increasing or decreasing order. When a new element violates the order, it **pops** all elements it is greater (or smaller) than, resolving those elements' answers.

### Next Greater Element: $O(N)$
Maintain a **decreasing stack** of indices. When element $A[i]$ is greater than `stack.top`, pop the top — $A[i]$ is its next greater element!

Key Takeaway: Monotonic stacks solve "next greater/smaller" patterns in O(N). Each element is pushed and popped at most once. Used in stock span, histogram, trap rain water.

Question 43

How do you solve the Trapping Rain Water problem optimally?

Accepted Answer

**Observation**: Water trapped at position $i$ = $\min(	ext{maxLeft}[i], 	ext{maxRight}[i]) - 	ext{height}[i]$.

### O(N) / O(1) Two-Pointer Approach:
Maintain `left`, `right` pointers and `maxLeft`, `maxRight`.
- Process the pointer with the **smaller max**: the water at that position is determined by the smaller side.
- This avoids the $O(N)$ prefix/suffix max arrays (reduces space from $O(N)$ to $O(1)$).

Key Takeaway: Two-pointer rain water reduces O(N) space (prefix arrays) to O(1) by processing the smaller-max side first. Classic interview difficulty: Hard.

Question 44

How do you merge K sorted linked lists efficiently?

Accepted Answer

### Naive: Merge one by one → $O(NK)$ total.
### Optimal: Min-Heap of size $K$ → $O(N \log K)$

**Algorithm**:
1. Push the **head** of each of the $K$ lists into a min-heap (ordered by node value).
2. Pop the minimum node → append to result list.
3. Push the popped node's **next** node (if exists) into the heap.
4. Repeat until heap is empty.

- **Time**: $O(N \log K)$ where $N$ = total nodes, $K$ = number of lists.
- **Space**: $O(K)$ for the heap.

Key Takeaway: Min-Heap merge is O(N log K) vs O(NK) for sequential merge. This pattern appears in external sort, streaming merges, and database merge joins.

Question 45

How do you find the Longest Increasing Subsequence (LIS)?

Accepted Answer

### O(N²) DP:
`dp[i]` = LIS ending at index `i`.
`dp[i] = 1 + max(dp[j])` for all `j < i` where `nums[j] < nums[i]`.

### O(N log N) — Patience Sorting / Binary Search:
Maintain a `tails` array where `tails[i]` = smallest tail element of all increasing subsequences of length `i + 1`.
- For each `num`:
  - If `num > tails.last` → extend by 1 (append).
  - Else → binary search for the **leftmost tail ≥ num** and replace it.
- LIS length = `tails.length`.

Key Takeaway: LIS has a classic O(N²) DP and an elegant O(N log N) solution via binary search on a maintained tails array. Know both for interviews.

Question 46

How do you solve the Word Search problem on a 2D grid using Backtracking?

Accepted Answer

**Approach**: For each cell matching `word[0]`, initiate a DFS exploring all 4 directions. Mark cells as **visited** before recursing and **unmark** (backtrack) when returning.

- **Time**: $O(M 	imes N 	imes 4^L)$ where $L$ = word length.
- **Space**: $O(L)$ recursion stack.

**Key**: Modify the grid in-place to mark visits (set to `'#'`), avoiding an extra visited matrix.

Key Takeaway: Word Search exemplifies backtracking with in-place state modification. Backtrack by restoring the cell value after each DFS branch.

Question 47

How do you implement an LRU Cache in O(1) time?

Accepted Answer

**LRU Cache**: Evicts the least recently used item when at capacity.

### Data Structures:
- **Hash Map** (key → node): $O(1)$ lookup.
- **Doubly Linked List** (ordered by recency): $O(1)$ insertion and deletion from both ends.
  - Head = most recently used (MRU).
  - Tail = least recently used (LRU).

### Operations:
- **Get(key)**: Move node to head. Return value.
- **Put(key, val)**: Insert at head. If at capacity → evict tail.

Key Takeaway: LRU Cache = HashMap (O(1) lookup) + Doubly Linked List (O(1) eviction order). This exact design is used in CPU caches, CDNs, and OS page tables.

Question 48

How do you count the Number of Islands in a 2D grid?

Accepted Answer

**Approach**: Iterate every cell. When a `'1'` (land) is found, increment island count and run **DFS/BFS** to flood-fill (mark) all connected land cells as `'0'` (visited) to prevent recounting.

- **Time**: $O(M 	imes N)$ — each cell is visited at most once.
- **Space**: $O(M 	imes N)$ worst case (recursion stack for DFS on a grid full of '1').

Key Takeaway: Number of Islands is a classic connected-component counting problem. The DFS/BFS flood-fill pattern extends to: clone graph, Pacific Atlantic water flow, and word search.

Question 49

What is a Fenwick Tree (Binary Indexed Tree) and how does it work?

Accepted Answer

A **Fenwick Tree (BIT)** provides $O(\log N)$ prefix sum queries and point updates, with $O(N)$ space — simpler to implement than a Segment Tree.

### Core Idea: Lowbit Trick
Each index $i$ is responsible for a range of length equal to its **lowest set bit** (`i & (-i)`).
- **Update**: Add delta to index $i$ and propagate to all ancestors: `i += i & (-i)`.
- **Query (prefix sum 1..i)**: Sum contributions while moving to parent: `i -= i & (-i)`.

Key Takeaway: Fenwick Tree is simpler to code than a Segment Tree but limited to associative-invertible operations (sum, XOR). Not suitable for range min/max without modifications.

Question 50

How do you find the shortest path in an unweighted grid using BFS?

Accepted Answer

**BFS Level-by-Level** guarantees the shortest path in **unweighted** grids/graphs because it explores all cells at distance $d$ before distance $d + 1$.

### Algorithm:
1. Enqueue the start cell with distance 0.
2. For each cell dequeued: explore all 8 directions (or 4 for Manhattan).
3. Enqueue valid unvisited open cells with `distance + 1`.
4. Return distance when reaching the target.

Key Takeaway: BFS is the correct algorithm for shortest path in unweighted graphs/grids. Dijkstra would also work but is overkill — BFS is O(V+E) vs O((V+E) log V).

Question 51

How do you find the Kth Largest Element in an array efficiently?

Accepted Answer

### Approach 1: Sort — $O(N \log N)$
Sort descending; return index K−1. Too slow when called frequently.

### Approach 2: Min-Heap of size K — $O(N \log K)$
Maintain a heap of the K largest seen. Pop the minimum when size exceeds K. Root = Kth largest.

### Approach 3: QuickSelect — $O(N)$ average, $O(N^2)$ worst
Partial Quick Sort: partition around a pivot; only recurse into the partition containing index `N−K`. Randomised pivot gives $O(N)$ expected.

Key Takeaway: QuickSelect is O(N) average for Kth element. Min-Heap O(N log K) is better for streaming data. Know both — interviewers test all three approaches.

Question 52

How do you compute the Edit Distance (Levenshtein Distance) between two strings?

Accepted Answer

**Edit Distance** = minimum operations (insert, delete, replace) to transform string $s1$ into $s2$.

### Recurrence:
`dp[i][j]` = edit distance between `s1[0..i-1]` and `s2[0..j-1]`.
```
if s1[i-1] === s2[j-1]:  dp[i][j] = dp[i-1][j-1]       (no op needed)
else:  dp[i][j] = 1 + min(
  dp[i-1][j],   // delete from s1
  dp[i][j-1],   // insert into s1
  dp[i-1][j-1]  // replace
)
```
- **Time**: $O(M 	imes N)$, **Space**: $O(M 	imes N)$ (reducible to $O(\min(M,N))$).

Key Takeaway: Edit Distance underlies spell checkers, DNA alignment, and diff tools (git diff). The 3-way min recurrence (insert, delete, replace) is the key insight.

Question 53

Explain the K-way Merge pattern and its applications.

Accepted Answer

**K-way Merge** uses a **min-heap** to efficiently merge $K$ sorted sequences:
1. Push the first element of each sequence into the heap.
2. Pop the global minimum → add to output.
3. Push the next element from that sequence.
4. Repeat until heap is empty.

- **Time**: $O(N \log K)$, **Space**: $O(K)$.

### Applications:
1. **Merge K sorted linked lists** (LeetCode Hard).
2. **External Sort**: Merge sorted file chunks that don't fit in RAM.
3. **Median from data stream**: Combine results from multiple sorted partitions.
4. **Smallest range covering K lists**: Extended K-way merge with range tracking.

Key Takeaway: K-way merge is a fundamental pattern in distributed systems (merge shards) and external sorting. Always use a min-heap, not repeated binary merges.

Question 54

How do Kruskal's and Prim's algorithms find the Minimum Spanning Tree?

Accepted Answer

A **Minimum Spanning Tree (MST)** connects all $V$ vertices with $V−1$ edges of minimum total weight, with no cycles.

### Kruskal's Algorithm — $O(E \log E)$:
- Sort all edges by weight.
- Add edge to MST if it doesn't form a cycle (Union-Find check).
- Best for **sparse graphs**.

### Prim's Algorithm — $O(E \log V)$ with min-heap:
- Start from any vertex; greedily add the minimum-weight edge connecting the MST to a new vertex.
- Best for **dense graphs**.

Both produce the same MST (weight), though the tree structure may differ.

Key Takeaway: Kruskal's is edge-based (sort + Union-Find) — great for sparse graphs. Prim's is vertex-based (greedy + min-heap) — better for dense graphs.

Question 55

How does the Dutch National Flag algorithm sort an array of 0s, 1s, and 2s in O(N)?

Accepted Answer

**Dutch National Flag** (Dijkstra) partitions an array into three sections in a single pass using three pointers.

### Pointers:
- `lo`: boundary of 0s (left section ends here).
- `mid`: current element being processed.
- `hi`: boundary of 2s (right section starts here).

### Invariants:
- `arr[0..lo-1]` = all 0s.
- `arr[lo..mid-1]` = all 1s.
- `arr[mid..hi]` = unknown.
- `arr[hi+1..n-1]` = all 2s.

Key Takeaway: Dutch National Flag is a 3-way partition running in O(N)/O(1). Key: when swapping with hi, don't advance mid — the swapped element is unprocessed.

Question 56

How does Bellman-Ford detect negative cycles in a weighted graph?

Accepted Answer

**Bellman-Ford** relaxes all edges $V - 1$ times. Since the shortest path in a graph with $V$ vertices has at most $V - 1$ edges, $V - 1$ relaxation rounds are sufficient.

### Negative Cycle Detection:
Perform one **additional** (Vth) relaxation pass. If any distance still decreases → a **negative cycle** exists (paths can spiral to $-\infty$).

### vs Dijkstra:
| | Dijkstra | Bellman-Ford |
|---|---|---|
| Negative weights | ❌ | ✅ |
| Time | $O((V+E)\log V)$ | $O(V 	imes E)$ |
| Negative cycle detect | ❌ | ✅ |

Key Takeaway: Bellman-Ford handles negative weights and detects negative cycles. Use it when Dijkstra's non-negative weight constraint cannot be guaranteed.

Question 57

How does Floyd-Warshall solve All-Pairs Shortest Paths?

Accepted Answer

**Floyd-Warshall** computes shortest paths between **all pairs** of vertices in $O(V^3)$ time.

### Key Recurrence:
`dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`

Iterating intermediate vertex $k$ from $0$ to $V - 1$: for each pair $(i, j)$, check if routing through $k$ improves the path.

### Negative Cycle Detection:
If `dist[i][i] < 0` after the algorithm → vertex $i$ lies on a negative cycle.

### Applications:
- Network routing (all-to-all latency matrix).
- Transitive closure (reachability).
- Detecting arbitrage in currency exchange graphs.

Key Takeaway: Floyd-Warshall finds all-pairs shortest paths in O(V³). Use it for dense graphs or when you need all-to-all distances. Negative diagonal = negative cycle.

Question 58

How does Kosaraju's Algorithm find Strongly Connected Components?

Accepted Answer

A **Strongly Connected Component (SCC)** is a maximal set of vertices where every vertex is reachable from every other.

### Kosaraju's Algorithm (Two-Pass DFS):
1. **Pass 1**: DFS on original graph. Push vertices to a stack in **finish order** (postorder).
2. **Reverse the graph** (transpose all edges).
3. **Pass 2**: Process vertices from the stack. Each DFS from an unvisited vertex on the reversed graph discovers one SCC.

- **Time**: $O(V + E)$, **Space**: $O(V + E)$.

Key Takeaway: Kosaraju's SCC uses two DFS passes and a graph transpose. SCCs compress a directed graph into a DAG — essential for circuit analysis and dependency resolution.

Question 59

What is a Suffix Array and how is it used for pattern matching?

Accepted Answer

A **Suffix Array** is a sorted array of all suffixes of a string, storing their starting indices.

### Why Suffix Arrays?
- $O(N \log N)$ construction (prefix doubling / SA-IS $O(N)$).
- Pattern search: Binary search on sorted suffixes → $O(P \log N)$ vs Suffix Trie's $O(P)$.
- Space: $O(N)$ integers vs $O(N^2)$ for suffix trie.

### Coupled with LCP (Longest Common Prefix) Array:
- Enables many string queries in $O(N)$ post-preprocessing: count distinct substrings, longest repeated substring.

Key Takeaway: Suffix Arrays power competitive-programming string problems and real-world systems like full-text search indexes (Lucene), genome aligners, and file diff tools.

Question 60

What are the properties of a Red-Black Tree and why is it preferred over AVL?

Accepted Answer

A **Red-Black Tree** is a self-balancing BST with these invariants:
1. Every node is **Red** or **Black**.
2. Root is **Black**.
3. Every leaf (NIL) is **Black**.
4. Red nodes have **Black children** (no two consecutive reds).
5. Every path from root to NIL has the **same number of Black nodes** (Black-height).

### Red-Black vs AVL:
| | AVL | Red-Black |
|---|---|---|
| Balance | Stricter (|BF| ≤ 1) | Looser (2× height ratio) |
| Rotations per insert/delete | More | Fewer (~2 max per operation) |
| Read-heavy | Slightly faster lookups | Slightly slower |
| Write-heavy | Slower | Faster |

**Usage**: C++ `std::map`, Java `TreeMap`, Linux kernel's CFS scheduler.

Key Takeaway: Red-Black Trees tolerate looser balance than AVL but perform fewer rotations on insert/delete. Preferred in write-heavy production systems (databases, OS schedulers).

Question 61

How do KMP and Z-Algorithm achieve O(N+M) pattern matching?

Accepted Answer

### Naive Pattern Matching: $O(NM)$
For each position in text, compare all $M$ characters of the pattern.

### KMP (Knuth-Morris-Pratt): $O(N + M)$
Precompute the **LPS (Longest Proper Prefix which is also Suffix)** array for the pattern in $O(M)$. On mismatch, use LPS to skip characters already matched — never moving the text pointer backwards!

### Z-Algorithm: $O(N + M)$
Build the Z-array for the concatenated string `pattern + '#' + text`. `Z[i]` = length of the longest substring starting at `i` that matches a prefix of the string. Pattern found where `Z[i] === M`.

Key Takeaway: KMP and Z-Algorithm are O(N+M) pattern matchers vs O(NM) naive. KMP uses the LPS (failure function); Z uses the Z-array. Both avoid redundant comparisons.

Question 62

What is Heavy-Light Decomposition (HLD) and what problems does it solve?

Accepted Answer

**Heavy-Light Decomposition** decomposes a tree into a set of **chains** such that any root-to-leaf path crosses at most $O(\log N)$ chains.

### Concept:
- **Heavy Edge**: For each non-leaf node, the edge to the child with the **largest subtree size** is the heavy edge.
- **Chain**: Maximal path of consecutive heavy edges.
- Any path between two nodes crosses $O(\log N)$ chains.

### Usage:
Combine HLD with a Segment Tree on flattened chain arrays to:
- Answer path sum/min/max queries in $O(\log^2 N)$.
- Handle point/range updates on paths in $O(\log^2 N)$.

Applications: Competitive programming, interval tree queries on hierarchical data.

Key Takeaway: HLD reduces tree path queries to segment tree range queries by guaranteeing O(log N) chain crossings per path. Essential for O(log²N) tree path problems.

Question 63

What is a Persistent Segment Tree and when is it necessary?

Accepted Answer

**Persistent Data Structures** preserve all historical versions of a data structure after updates.

### Persistent Segment Tree:
When updating a leaf in a segment tree, instead of overwriting nodes, create **new nodes only along the root-to-leaf path** ($O(\log N)$ new nodes per update). Each version shares unchanged subtrees with previous versions.

### Use Case — Range Kth Smallest in O(log N):
Build a persistent segment tree over sorted array values. For queries, take the difference between versions $r$ and $l - 1$ to simulate a virtual segment tree for the subarray `[l, r]`.

Key Takeaway: Persistent Segment Trees store O(N log N) nodes for N versions. Path copying creates O(log N) new nodes per update. Essential for offline range Kth queries.

Question 64

How does Ford-Fulkerson compute Maximum Flow in a network?

Accepted Answer

**Maximum Flow** finds the maximum amount of "flow" from source $s$ to sink $t$ in a directed capacity graph.

### Ford-Fulkerson Method:
1. Initialise all flows to 0.
2. While there exists an **augmenting path** (source → sink with residual capacity) in the **residual graph**:
   - Find the bottleneck capacity $c$ of the path.
   - Add $c$ to flow along forward edges; subtract $c$ from backward (reverse) edges.
3. When no augmenting path exists → **maximum flow found**.

### Edmonds-Karp: $O(VE^2)$
Uses BFS (shortest path by hops) to find augmenting paths, giving polynomial time guarantee.

### Max-Flow Min-Cut Theorem:
Max flow = weight of minimum cut separating source from sink.

Key Takeaway: Max-Flow = Min-Cut (fundamental theorem). Edmonds-Karp gives O(VE²). Applications: bipartite matching, network reliability, airline scheduling.

Take Data Structures & Algorithms Skill Assessment Quiz

Showing 85 Questions

1. What is the difference between an Array and a Linked List?

Time Complexity Comparison:

When to Use:

2. What is Big-O Notation and why is it important?

3. What are Stack and Queue data structures and where are they used?

4. How does Binary Search work and what are its prerequisites?

5. How does a Hash Table work internally?

6. Explain Bubble Sort, Selection Sort, and Insertion Sort with their complexities.

7. What is the Two-Pointer Technique?

8. What is the Sliding Window Technique?

9. What is Recursion and how do you identify the Base Case?

10. What is a Binary Tree and what are its key properties?

11. What is a Binary Search Tree (BST) and how do Search, Insert, and Delete work?

12. How do you implement a Queue using two Stacks?

13. How does Merge Sort work and why is it preferred for stable sorting?

14. How do you reverse a string and check if two strings are anagrams?

15. What is the Prefix Sum technique and when is it useful?

16. How do you detect a cycle in a Linked List (Floyd's Algorithm)?

17. How do you validate balanced parentheses using a Stack?

18. What is the difference between Memoization (Top-Down DP) and Tabulation (Bottom-Up DP)?

19. What is the difference between BFS and DFS graph traversal?

20. How does Quick Sort work and what makes it fast in practice?

21. How do you traverse a 2D matrix (row-major, spiral, diagonal)?

22. What are Counting Sort and Radix Sort and when do they beat O(N log N)?

23. How do you find the maximum and minimum in an array with fewest comparisons?

24. How do you check if a number is a Power of Two using bit manipulation?

25. How do you find the first non-repeating character in a string?

26. How do you reverse a Singly Linked List iteratively and recursively?

27. What is the space-optimised Fibonacci solution?

28. How does Kadane's Algorithm find the Maximum Subarray Sum in O(N)?

29. What is a Heap (Min-Heap / Max-Heap) and how is it used as a Priority Queue?

30. How do you find a Missing Number using XOR or Gauss's formula?

31. How does Backtracking work and how do you generate all Subsets?

32. What is Topological Sorting and how does Kahn's Algorithm work?

33. How does Dijkstra's Algorithm find the Shortest Path in a weighted graph?

34. How do you solve the Coin Change problem with Dynamic Programming?

35. How do you compute the Longest Common Subsequence (LCS)?

36. How do you solve the 0/1 Knapsack problem with Dynamic Programming?

37. What is a Trie (Prefix Tree) and what are its advantages over a hash map for strings?

38. What is Union-Find (Disjoint Set Union) and how do Path Compression and Union by Rank work?

39. What is a Segment Tree and when is it better than a Prefix Sum?

40. What is an AVL Tree and how do rotations maintain balance?

41. How do you detect a cycle in an undirected and directed graph?

42. What is a Monotonic Stack and how does it solve Next Greater Element?

43. How do you solve the Trapping Rain Water problem optimally?

44. How do you merge K sorted linked lists efficiently?

45. How do you find the Longest Increasing Subsequence (LIS)?

46. How do you solve the Word Search problem on a 2D grid using Backtracking?

47. How do you implement an LRU Cache in O(1) time?

48. How do you count the Number of Islands in a 2D grid?

49. What is a Fenwick Tree (Binary Indexed Tree) and how does it work?

50. How do you find the shortest path in an unweighted grid using BFS?

51. How do you find the Kth Largest Element in an array efficiently?

52. How do you compute the Edit Distance (Levenshtein Distance) between two strings?

53. Explain the K-way Merge pattern and its applications.

54. How do Kruskal's and Prim's algorithms find the Minimum Spanning Tree?

55. How does the Dutch National Flag algorithm sort an array of 0s, 1s, and 2s in O(N)?

56. How does Bellman-Ford detect negative cycles in a weighted graph?

57. How does Floyd-Warshall solve All-Pairs Shortest Paths?

58. How does Kosaraju's Algorithm find Strongly Connected Components?

59. What is a Suffix Array and how is it used for pattern matching?

60. What are the properties of a Red-Black Tree and why is it preferred over AVL?

61. How do KMP and Z-Algorithm achieve O(N+M) pattern matching?

62. What is Heavy-Light Decomposition (HLD) and what problems does it solve?

63. What is a Persistent Segment Tree and when is it necessary?

64. How does Ford-Fulkerson compute Maximum Flow in a network?

65. How do you solve Matrix Chain Multiplication using Dynamic Programming?

66. How do you find Articulation Points and Bridges in a graph?

67. How does Graham Scan compute the Convex Hull in O(N log N)?

68. What is Bitmask Dynamic Programming and how does it solve the Travelling Salesman Problem?

69. What is Mo's Algorithm for offline range queries?

70. How does Binary Lifting solve Lowest Common Ancestor (LCA) queries in O(log N)?

71. How does the Aho-Corasick Algorithm enable multi-pattern string matching?

72. What is Reservoir Sampling and how does it select K items uniformly from a stream?

73. What is a Skip List and how does it achieve O(log N) operations probabilistically?

74. What is a Treap (Tree + Heap) and how does it maintain expected O(log N) height?

75. What is Square Root Decomposition and when is it used?

76. Explain Amortised Analysis with Aggregate, Accounting, and Potential methods.