Practice questions and answer explanations
Try an answer before reading the explanation. These are practice examples; adapt them to your own experience and expect different questions in an actual interview.
How would you solve Two Sum and explain the trade-off?
First clarify whether the answer should contain indices or values and whether a solution is guaranteed. For indices, scan the array while storing earlier values and their indices in a hash map. Before inserting the current value, check whether its complement is already present so you do not reuse the same element. This takes expected O(n) time and O(n) extra space, compared with O(n²) time for checking every pair.
Try this next: How does your solution handle [3, 3] with target 6, and what should it return when no pair exists?
How do you avoid infinite loops in binary search?
Choose one interval convention and maintain it throughout. For an inclusive interval [low, high], continue while low <= high, compute a midpoint, and move to mid + 1 or mid - 1 when the midpoint cannot be the answer. State the sorted-input requirement and the invariant that any remaining answer lies inside the interval. Each step shrinks the interval, giving O(log n) time and O(1) extra space for an iterative implementation.
Try this next: How would you change the search to return the first occurrence when duplicate values are present?
When does BFS find a shortest path?
Breadth-first search finds a path with the fewest edges in an unweighted graph by exploring vertices in distance layers. Use a queue and mark a vertex visited when it is enqueued to avoid repeated work. Store each vertex’s parent if you need the actual path. With adjacency lists, traversal takes O(V + E) time and O(V) additional space. Unequal edge weights require a different shortest-path strategy.
Try this next: What should your function return if the destination is unreachable or the start and destination are the same?
How would you validate balanced brackets?
Push opening brackets onto a stack. For each closing bracket, reject the input if the stack is empty or its top has the wrong opening type; otherwise pop the matching opener. Accept only if the stack is empty at the end. A single counter cannot handle mixed types such as ([)]. The scan takes O(n) time and O(n) space in the worst case. Agree on whether non-bracket characters should be ignored or rejected.
Try this next: Walk through an empty string, a lone closing bracket, and ([)] before writing the implementation.
Vriona