DSA interview questions and answers

DFS with a legal (low, high) window: left child must be < node and stay > low, right must be > node and stay < high.

Inorder traversal visits keys in order

Walk from the root: go left if both keys are smaller, right if both are larger

Always pick the middle element as root and recurse on left and right halves so subtree sizes differ by at most one.

Count frequencies in a hash map, then push (freq, value) into a min-heap of size k.

Keep a max-heap of size k by squared distance so the farthest of the closest k sits at the top.

Count frequencies, reject if the max count exceeds (n+1)/2, then always place the current most frequent remaining character from a max-heap, holding the previous one out for a turn.

Push the first column (or first row) into a min-heap of (value, r, c) and pop k times, pushing the next item in that row each pop.

Scan cells

Hash original node to clone.

Build a directed graph and detect a cycle: Kahn's algorithm peels indegree-zero nodes, or DFS colors nodes gray/black.

Start DFS from every cell matching the first letter, marking visited in-path and backtracking.

Reverse the thinking: BFS/DFS from Pacific border cells and from Atlantic border cells uphill, then intersect the two reachable sets.

Multi-source BFS from all zeros at once, spreading to ones with increasing distance.

dp[i] is the best of skipping i (dp[i-1]) or taking nums[i] plus dp[i-2].

dp[r][c] = dp[r-1][c] + dp[r][c-1], with first row/column as 1.

dp[x] is 1 plus the min of dp[x-coin] over coins that fit, with dp[0]=0 and others inf.

O(n^2) DP: dp[i] = 1 + max dp[j] for j < i and nums[j] < nums[i].

dp[w] is the best value using capacity w

dp[i] adds dp[i-1] if the last digit is 1-9 and dp[i-2] if the last two digits are 10-26.