DSA interview questions and answers

Preorder with explicit null markers (or BFS with nulls) encodes structure uniquely

DFS returns the best downward gain through one child (or zero if negative).

The first preorder value is the root

BFS with (node, column), incrementing column on right and decrementing on left, collecting into a map from column to list.

Reverse postorder: flatten right, flatten left, then splice the old right onto the tail of the left and null the left.

Inorder should be sorted

Push the left spine onto a stack.

Postorder return (is_bst, min, max, size) for each subtree.

Keep a max-heap of the lower half and a min-heap of the upper half, rebalancing so sizes differ by at most one.

Min-heap of the current head of each array with (value, array_id, index).

Greedy with a max-heap of frequencies and a cooldown queue of length k-1.

BFS on the word graph where edges are one-letter differences

Compare adjacent words to extract letter-precedence edges, then topological sort.

A min-heap of (distance, node) always settles the closest unsettled vertex and relaxes its edges.

Kahn: queue all zero-indegree courses, append them to the order, and decrement neighbors.

Tarjan DFS with discovery time and low-link: an edge u-v is a bridge if v cannot reach an ancestor of u, i.e., low[v] > disc[u].

Kruskal sorts edges by weight and adds an edge if Union-Find says the ends are in different components: O(E log E).

Bellman-Ford style relaxation for k+1 rounds, or BFS/Dijkstra on a state (city, stops).

dp[i][j] is the min of replace, delete, or insert to turn word1[:i] into word2[:j], with a free diagonal copy when characters match.

dp[i][j] = dp[i-1][j-1]+1 on a match, else max of skip either character.