Interview Prep Panel

DSA Interview Defense Q&A

Master complex algorithmic conceptual transitions. Learn how to explain trade-offs, identify structural bottlenecks, and defend your designs in systems/FAANG interviews.

Filter by Category

Showing 105 Questions

DSA Interview Defense Q&A

Why does a HashMap lookup run in O(1) average time, and when can it degrade to O(N)?

How does CPU cache memory access patterns make Arrays faster than Linked Lists for sequential scans?

Explain the amortized O(1) complexity of inserting items into a dynamic array (e.g. ArrayList).

Compare Chaining versus Open Addressing collision resolution strategies in hash tables.

Why is a HashMap combined with a Min-Heap preferred over sorting for finding Top K elements?

How is a HashSet typically implemented internally under the hood?

How does prefix sum matching optimize subarray searches from O(N^2) to O(N)?

Compare inward-moving pointers to fast/slow pointer speed variations.

How does sorting reduce the complexity of the 3Sum problem from O(N^3) to O(N^2)?

Explain the greedy choice of moving the pointer pointing to the shorter bar in Container With Most Water.

How do you mathematically prove that Fast and Slow pointers will always meet if a Linked List cycle exists?

How are pointers used to merge overlapping intervals in O(N log N) time?

Explain the read-pointer and write-pointer roles in Remove Duplicates from Sorted Array.

Explain the Dutch National Flag 3-pointer partition mechanism used in Sort Colors.

What is the key difference between fixed-size and variable-size sliding windows?

Why does Minimum Window Substring require a character frequency map, and how do we check match status in O(1)?

How does a Monotonic Deque help find the maximum of all sliding windows in O(N) time?

Why do we track maxFrequency in Longest Repeating Character Replacement, and does it need to decrease on shrink?

How do we find all anagrams of a string using a fixed sliding window?

Explain why the dynamic sliding window works for Minimum Size Subarray Sum but not if there are negative numbers.

Explain the execution transition of Permutation in String.

Why is mid calculated as left + (right - left) / 2 instead of (left + right) / 2?

Explain how we find an element in a sorted rotated array in O(log N) time.

What does 'Binary Search on Answer Space' mean, and what is the monotonicity requirement?

How do we locate the first and last position of an element in a sorted array containing duplicates?

How do we treat a 2D matrix as a sorted 1D array to search it in O(log(M * N))?

Why can we use binary search to find a peak element in an unsorted array?

Explain the partition strategy used to find the median of two sorted arrays in O(log(min(M, N))).

Why do we use a Dummy Node in Linked List deletions or merges?

Explain in-place pointer reversal in a Singly Linked List.

How do you find and remove the Nth node from the end of a Linked List in a single pass?

How do you copy a Linked List containing random pointer links in O(N) time and O(1) auxiliary space?

Why does resetting one pointer to head and moving both at equal speed find the cycle start node after collision?

How do you reorder a list (L0 -> Ln -> L1 -> Ln-1) in O(N) time and O(1) space?

Why does LRU Cache require a Doubly Linked List instead of Singly Linked List?

Compare Stack (LIFO) and Queue (FIFO) operations and memory allocations.

How do you implement a Queue using two Stacks, and what is the amortized cost of operations?

Explain how a monotonic stack processes Next Greater Element queries in O(N) time.

How do you design a Min Stack that retrieves the minimum element in O(1) time?

Explain how a stack parses and evaluates Reverse Polish Notation (Postfix expressions).

How does a Circular Queue implement fixed-capacity ring buffers without moving elements on dequeue?

Explain the stack transition logic in Largest Rectangle in Histogram.

Explain the Binary Search Tree (BST) property and search runtime cost.

Compare Pre-order, In-order, and Post-order DFS traversals.

Explain the recursion logic of Lowest Common Ancestor (LCA) in a Binary Tree.

How do you calculate the Maximum Path Sum in a Binary Tree where paths can start and end anywhere?

How do you serialize and deserialize a binary tree using pre-order traversal?

How do preorder and inorder traversal lists reconstruct a unique binary tree?

How do you verify if a binary tree is height-balanced in O(N) time?

Compare BFS and DFS search patterns and queue/stack allocations.

How do you detect a cycle in a Directed Graph versus an Undirected Graph?

Compare Dijkstra's and Bellman-Ford algorithms for shortest paths.

Explain Kahn's Algorithm for Topological Sort using in-degrees.

How do Path Compression and Union-by-Rank optimize Union-Find operations to O(alpha(N))?

How do you verify if a graph is Bipartite (2-colorable)?

Explain the dual DFS passes logic of Kosaraju's Algorithm for Strongly Connected Components.

How does a Binary Heap map to a 1D array list, and how do we calculate children indices?

Why is building a heap (heapify) O(N) complexity while inserting N elements is O(N log N)?

Explain the two-heaps design pattern for finding the median of dynamic streams.

How does Priority Queue optimize Dijkstra's relaxation step?

Explain the K-Way merge pattern using heaps.

Explain bubble-up (sift-up) and bubble-down (sift-down) algorithms.

How does a Max-Heap optimize task scheduling under cooldown limits?

What is backtracking, and how does it differ from pure DFS traversal?

Explain constraint pruning in backtracking using N-Queens as an example.

How do you generate permutations of a list containing duplicate elements without generating duplicate permutations?

How does a Sudoku Solver track constraints to run cells checks in O(1) time?

Explain the recursion tree of Letter Combinations of a Phone Number.

How does Word Search prevent reusing the same grid cell in a single word path?

Why does Expression Add Operators require passing the prevOp value to handle multiplication?

What are the two core criteria required to apply Dynamic Programming?

Explain the transition recurrence relation for the Coin Change problem.

How can 2D DP tables be space-optimized to 1D arrays?

Explain how to solve Longest Increasing Subsequence (LIS) in O(N log N) using patience sorting.

Explain the transition transitions in Longest Common Subsequence.

Why does 0/1 Knapsack require Dynamic Programming while Fractional Knapsack can be solved greedily?

Explain Interval DP transitions using Burst Balloons.

What is a Greedy algorithm, and when is it safe to use?

Why sorting by finish times yields optimal interval scheduling outputs?