DSA interview questions and answers

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.

Track the farthest reachable index while scanning left to right

If total gas is less than total cost, no start works.

Sort by end time and keep an interval if it starts after or at the last kept end

Sort items by value/weight and take whole items then a fraction of the next, which is optimal for the fractional version.

Slide a min-heap of size k+1: push the next element and pop the min into the result.

There are n!

A geometric resize (double the capacity) copies O(n) elements only occasionally.

Backtrack: at each index either include nums[i] or skip it, recording a copy when i reaches n.

Backtrack by swapping the next position with each remaining candidate, or by choosing unused indices with a used array.

XOR everything