Coding Interview Questions With Worked Answers and Code

Coding interview questions test more than whether you can produce working code. You need to clarify the prompt, select a defensible algorithm, explain why it works, test it, and state its complexity.

This question bank organizes common coding problems for interviews by pattern. The goal is not to memorize implementations. It is to build a repeatable way to reason out loud.

What Coding Interview Questions Are Actually Testing#

A strong answer combines correct code with a clear account of how you reached it.

Interviewers commonly evaluate five things:

1. Problem clarification. You identify ambiguous inputs, outputs, constraints, and guarantees.
2. Algorithm selection. You compare a baseline approach with a better one when optimization matters.
3. Code quality. You choose useful names, keep state manageable, and avoid unnecessary abstraction.
4. Testing. You cover ordinary inputs, boundaries, duplicates, and invalid cases allowed by the prompt.
5. Complexity analysis. You explain which operations dominate time and what additional memory you use.

Solving the problem silently is not the same as presenting a defensible solution. The interviewer cannot infer your reasoning from the final loop. State the invariant that makes the loop correct.

Use this structure for coding interview questions and answers:

• Clarify: Restate the input, output, and important guarantees.
• Baseline: Give the simplest correct approach and its complexity.
• Optimize: Identify repeated work and choose a data structure that removes it.
• Implement: Explain the state you maintain while writing code.
• Test: Trace a normal case and at least one boundary case.
• Analyze: State time and auxiliary space complexity.

This structure also helps with broader software engineering interview questions. It shows how you handle incomplete requirements and defend implementation choices.

Array and Hash Map Questions#

Array questions often become hash map questions when repeated scanning is the bottleneck.

Two Sum#

Core pattern: Store previously seen values by value.

For each number, compute the complement required to reach the target. If that complement is already in the map, return the two indices. Otherwise, record the current value and index.

Watch for duplicate values, negative numbers, and rules about returning indices rather than values. The one-pass solution takes O(n) time and O(n) space.

Contains Duplicate#

Core pattern: Use a set for membership.

Scan the array. Return true when a value is already present. Otherwise, add it to the set.

An empty array and a one-element array contain no duplicate. Repeated negative values need no special handling. Time is O(n) and space is O(n).

Group Anagrams#

Core pattern: Map a canonical signature to a list of strings.

A sorted string can serve as the key. For a restricted alphabet, a character-frequency tuple avoids sorting each word.

Decide how casing and Unicode should behave. A fixed lowercase letter count does not generalize to arbitrary characters. With sorted keys, time is O(total characters × log word length) and space is O(total characters).

Product of Array Except Self#

Core pattern: Combine prefix and suffix products.

Write prefix products into the output array. Then move right to left while maintaining a suffix product. This avoids division and handles zeros naturally.

Check empty-input expectations, one-element arrays, and inputs with multiple zeros. Time is O(n). Auxiliary space is O(1) when the output array does not count toward the limit.

Longest Consecutive Sequence#

Core pattern: Start only at sequence boundaries.

Put all values in a set. A value starts a sequence only when value - 1 is absent. Count forward from those starts.

Duplicates disappear in the set. Negative values work without changes. Expected time is O(n) and space is O(n). The boundary check prevents you from repeatedly traversing the same sequence.

String and Two-Pointer Questions#

Two-pointer solutions become easier to explain when you state what each pointer represents and why one of them must move.

Valid Palindrome#

Normalize characters according to the prompt. Move one pointer from each end, skipping characters that do not count. The invariant is that everything outside the pointers has already matched.

Clarify casing, punctuation, empty strings, and Unicode. Python’s isalnum() and lower() have Unicode-aware behavior that may differ from an ASCII-only prompt.

Time is O(n). A direct two-pointer implementation uses O(1) auxiliary space.

Valid Anagram#

Count characters in the first string and subtract counts using the second. Alternatively, compare sorted strings.

Clarify whether uppercase and lowercase differ and whether inputs can contain arbitrary Unicode characters. Duplicate characters make counts necessary; a set alone loses multiplicity.

Counting takes O(n) time and O(k) space, where k is the number of distinct characters.

Longest Palindromic Substring#

Treat every character and every gap between characters as a possible center. Expand while the two sides match.

The pointer invariant is that the current interval remains a palindrome until the next comparison fails. Test empty input, repeated characters, and even-length palindromes.

Center expansion takes O(n²) time and O(1) auxiliary space.

Container With Most Water#

Start with pointers at both ends. Compute the area, then move the pointer at the shorter line.

The shorter height limits the current area. Moving the taller pointer inward cannot improve that limiting height while width decreases. That is the key argument, not just an implementation detail.

Time is O(n) and auxiliary space is O(1).

Linked List, Stack, and Queue Questions#

These data structure interview questions test whether you can preserve state while links or stack contents change.

Reverse Linked List#

Maintain previous, current, and next_node. Save the next node before changing current.next.

The common failure is overwriting the only reference to the remainder of the list. State the invariant: previous is the reversed prefix, and current begins the untouched suffix.

Time is O(n) and space is O(1).

Merge Two Sorted Lists#

A dummy node removes special handling for the first output node. Keep a tail pointer and attach the smaller current node from either list.

Do not forget to append the remaining suffix after one list ends. Reusing nodes takes O(n + m) time and O(1) auxiliary space.

Linked List Cycle#

Move one pointer one step and another two steps. If a cycle exists, they eventually meet. If the fast pointer reaches the end, the list has no cycle.

Check both fast and fast.next before advancing. Time is O(n) and space is O(1).

Valid Parentheses#

Push opening brackets. For each closing bracket, verify that the stack top contains its matching opener.

The stack invariant is precise: it contains unmatched opening brackets in encounter order. A closing bracket with an empty stack fails immediately. A nonempty stack at the end also fails.

Time is O(n) and space is O(n).

Min Stack#

Store each value with the minimum seen at that depth, or maintain a second stack of minimum values.

Duplicates matter. If the current minimum appears twice, popping one copy must not discard the other. Push, pop, top, and minimum lookup each take O(1) time. Total space is O(n).

Tree and Graph Questions#

Tree and graph questions usually reduce to traversal order, maintained state, and a clear visited rule.

Maximum Depth of Binary Tree#

Use recursive DFS and return one plus the larger child depth. The base case for a missing node is zero.

Time is O(n). Space is O(h) for the recursion stack, where h is tree height.

Validate Binary Search Tree#

Carry lower and upper bounds into each recursive call. Checking only a node against its immediate children is insufficient because a violation may come from an ancestor.

Decide how duplicates are treated. Under strict ordering, each value must fall strictly inside its valid range. Time is O(n) and stack space is O(h).

Binary Tree Level Order Traversal#

Use BFS with a queue. Capture the queue length at the start of each level, then process exactly that many nodes.

Time is O(n). Space is O(w), where w is the maximum tree width. The tree traversal pattern guide provides related traversal shapes.

Number of Islands#

Scan every cell. When you find unvisited land, increment the count and mark the entire connected component with DFS or BFS.

Be explicit about whether diagonal cells connect. Time is O(rows × columns) and visited or traversal space can reach O(rows × columns). Use the Number of Islands problem reference for a full walkthrough.

Course Schedule#

Model each prerequisite as a directed edge. Use indegrees and a queue, or use DFS with visiting states, to detect a cycle.

The question is not ordinary reachability. It asks whether the directed graph has a valid topological ordering. Time is O(V + E) and space is O(V + E). The topological sort guide covers the reusable pattern.

Intervals, Heaps, Backtracking, and Dynamic Programming#

Recognition cues help you choose a pattern before you start coding.

For dynamic programming, define the state in one sentence before writing the recurrence. Then name the base case and evaluation order. The dynamic programming guide goes deeper, while the pattern reference groups the broader question bank.

Worked Example: Two Sum From Prompt to Final Answer#

A complete answer to [LeetCode 1: Two Sum) starts with the contract, not the code.

Clarify the prompt#

Ask concise questions:

• Should I return indices or values?
• Can the input contain duplicate values?
• May I use the same element twice?
• Is exactly one valid answer guaranteed?
• Does the order of the returned indices matter?

Assume you must return two distinct indices, duplicate values are allowed, and one answer exists.

Establish the baseline#

The direct approach checks every pair. It is easy to verify, but it takes O(n²) time.

The repeated work is searching the remainder of the array for a matching value. A hash map replaces that scan with a membership lookup.

For a current value x, the required earlier value is target - x. Check for it before inserting x. That order prevents one element from matching itself.

def two_sum(nums, target):
    seen = {}

    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index

    return []

Trace a concrete input#

Use nums = [2, 7, 11, 15] and target = 9.

• At index 0, the value is 2. The complement is 7. It is not in seen, so store {2: 0}.
• At index 1, the value is 7. The complement is 2.
• The map contains 2 at index 0, so return [0, 1].

A duplicate-value case also works. For [3, 3] with target 6, the first 3 is stored before the second one checks for it.

Analyze complexity#

The loop visits each element once. Hash map lookup and insertion have expected constant time, so total expected time is O(n). The map can contain up to n entries, giving O(n) space.

Test compactly#

assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([-4, 10, 3], 6) == [0, 1]
assert two_sum([], 5) == []

While coding, you can explain it this way:

I keep a map from values I have already visited to their indices. At each position, I calculate the complement. If it is already in the map, I have two distinct indices that reach the target. Otherwise, I save the current value for later elements.

That explanation identifies the state, invariant, and reason the algorithm works.

How to Answer When You Do Not See the Solution Immediately#

Start with a correct baseline, then use its repeated work to find the optimization.

Say what you know:

• “I can solve this by checking every pair.”
• “That revisits the same suffix many times.”
• “I want faster membership checks.”
• “A set or map may replace the repeated scan.”

Small examples can expose the missing state. Trace three or four elements by hand. Write down what you repeatedly ask about the earlier input. That question often identifies the data structure.

Constraints also narrow the choice. Sorted input suggests binary search or two pointers. Shortest-path language suggests BFS in an unweighted graph. Dependencies suggest topological ordering. Repeated overlapping subproblems suggest dynamic programming.

Useful recovery prompts include:

• What is the simplest correct algorithm?
• Which operation dominates its runtime?
• What information would let me avoid repeating that operation?
• Can I sort without violating the output requirements?
• Do I need order, membership, frequency, minimum, or maximum?
• What must remain true after each loop iteration?
• Can I solve a smaller version of the same problem?

You do not need to recognize every pattern immediately. You need to keep producing checkable progress: a baseline, an example, an invariant, and a reasoned next step.