Interview Q&A

Short answer: Use a hash map from value → index while scanning once. For each number x, check if target − x is already seen; if yes, return both indices. This is O(n) time and O(n) space — the expected answer after you briefly mention the O(n²) nested-loop brute force.

Problem statement

Given an array of integers and a target, return indices of two numbers that add up to the target. Assume exactly one solution and you may not use the same element twice.

Interview approach

1. Clarify constraints: duplicates allowed? multiple answers? need indices or values?
2. State brute force: check every pair in O(n²).
3. Propose hash map: while iterating i, look up target − nums[i].
4. Store nums[i] → i after the lookup (avoid using the same index).
5. Walk through a small example out loud.
6. State time/space and discuss follow-ups (sorted array → two pointers).

Brute force (mention first)

Nested loops comparing every pair — correct but too slow for large n.

Optimal idea

One pass with Dictionary/HashMap. Lookup is average O(1).

Sample solution

// C#
int[] TwoSum(int[] nums, int target) {
    var map = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++) {
        int need = target - nums[i];
        if (map.TryGetValue(need, out int j)) return new[] { j, i };
        map[nums[i]] = i;
    }
    throw new InvalidOperationException("No solution");
}

Complexity

Time O(n), Space O(n).

Edge cases to mention

• Negative numbers
• Duplicates (e.g. [3,3], target 6)
• Empty or single-element array (no solution)

Common follow-ups

• What if the array is sorted?
• Return all unique pairs instead of indices
• Three Sum

Mistakes to avoid

• Adding to the map before checking (can reuse same index)
• Forgetting to discuss complexity

Always start with brute force, then optimize — interviewers score communication as much as code.

Short answer: Track the minimum price so far while scanning left to right. At each day, compute profit = price − minSoFar and keep the maximum profit. One pass, O(1) extra space.

Problem statement

prices[i] is the stock price on day i. You may buy once and sell once later. Return the maximum profit (0 if no profit).

Interview approach

1. Clarify: only one buy and one sell; sell after buy.
2. Reject nested O(n²) “try every buy/sell pair” as too slow.
3. Maintain minPrice and maxProfit while iterating.
4. Update maxProfit when prices[i] − minPrice is better.

Sample solution

int MaxProfit(int[] prices) {
    int minPrice = int.MaxValue, best = 0;
    foreach (int p in prices) {
        if (p < minPrice) minPrice = p;
        else best = Math.Max(best, p - minPrice);
    }
    return best;
}

Complexity

Time O(n), Space O(1).

Edge cases to mention

• Strictly decreasing prices → 0
• Single day → 0
• All equal prices → 0

Common follow-ups

• Unlimited transactions
• At most k transactions
• Cooldown / fees

Say “running minimum” out loud — it shows you understand the greedy invariant.

Short answer: Insert elements into a HashSet while scanning. If an insert fails (already present), return true. Sorting and comparing neighbors also works in O(n log n) with O(1) extra space if sorting in place is allowed.

Sample solution

bool ContainsDuplicate(int[] nums) {
    var seen = new HashSet<int>();
    foreach (int n in nums)
        if (!seen.Add(n)) return true;
    return false;
}

Complexity

HashSet: Time O(n), Space O(n). Sort: Time O(n log n), Space O(1)/O(n).

Common follow-ups

• Contains Duplicate II (distance ≤ k)
• Contains Duplicate III (value range)

Ask whether O(1) space matters — that steers you to sorting vs hashing.

Short answer: Valid Anagram: count character frequencies (or sort both strings). Group Anagrams: use a frequency signature or sorted string as dictionary key and bucket words together.

Complexity

Valid: O(n). Group: O(n * k log k) with sort key, or O(n * k) with count key (k = word length).

Common follow-ups

• Anagrams with Unicode
• Find if any two are anagrams in a stream

Prefer count[26] for lowercase English — faster and shows constraint awareness.

Short answer: Push opening brackets. On a closing bracket, pop and check it matches. At the end the stack must be empty. Covers (), {}, [] in one pass.

Sample solution

bool IsValid(string s) {
    var st = new Stack<char>();
    foreach (char c in s) {
        if (c is '(' or '[' or '{') st.Push(c);
        else {
            if (st.Count == 0) return false;
            char o = st.Pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
                return false;
        }
    }
    return st.Count == 0;
}

Complexity

Time O(n), Space O(n).

Edge cases to mention

• Empty string → true
• Only closers
• Nested mixed types

Common follow-ups

• Longest valid parentheses
• Minimum remove to make valid
• Generate parentheses

This is a common phone-screen opener — nail it quickly and cleanly.

Short answer: Iterative: three pointers prev, curr, next. Flip curr.next to prev and advance. Recursive: reverse the rest, then point head.next.next = head and head.next = null. Iterative is usually preferred in interviews for O(1) stack space.

Complexity

Time O(n). Iterative space O(1); recursive space O(n) call stack.

Edge cases to mention

• Empty list
• Single node
• Cycle (clarify — usually assume none)

Common follow-ups

• Reverse nodes in k-group
• Reverse between left and right

Draw 3 nodes on the whiteboard before coding — it prevents pointer bugs.

Short answer: Use a dummy head and append the smaller of the two current nodes until one list is exhausted, then attach the remainder. Recursive merge is elegant but uses stack space.

Complexity

Time O(n + m), Space O(1) iterative.

Common follow-ups

• Merge k sorted lists (heap / divide-and-conquer)
• Merge sorted arrays in-place

Dummy node avoids special-casing the head — a small habit that impresses interviewers.

Short answer: Climbing Stairs: ways(n) = ways(n-1) + ways(n-2) — Fibonacci DP. House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — cannot rob adjacent houses. Both reduce to O(1) space with two rolling variables.

Complexity

Time O(n), Space O(1) optimized.

Common follow-ups

• House Robber II (circular)
• Climbing stairs with 1..k steps
• Decode Ways

Always define the recurrence in words before writing code.

Short answer: Maintain inclusive or exclusive bounds consistently. Compute mid carefully (lo + (hi − lo) / 2) to avoid overflow. Decide whether you want lower-bound, upper-bound, or exact match before coding.

Complexity

Time O(log n), Space O(1).

Mistakes to avoid

• Off-by-one infinite loops
• Using (lo+hi)/2 overflow on large ints
• Mixing inclusive/exclusive bounds

State the loop invariant: “answer is always inside [lo, hi]”.

Short answer: Clarify inputs/outputs/constraints first. Propose brute force, then optimize. Speak while coding, test with an example, and state complexity. Silence is riskier than imperfect code with clear thinking.

Interview approach

1. Restate the problem in one sentence.
2. Ask about constraints, duplicates, nulls, and expected complexity.
3. Outline approaches and pick one with justification.
4. Code incrementally; verify with a dry run.
5. Discuss trade-offs and follow-ups even if time ends.

Mistakes to avoid

• Jumping into code silently
• Ignoring edge cases
• Optimizing prematurely without a correct baseline

Interviewers hire teammates — communication is part of the score.

Short answer: Floyd’s tortoise and hare: slow moves 1, fast moves 2. If they meet, there is a cycle. To find the cycle entrance, reset one pointer to head and move both one step until they meet.

Complexity

Time O(n), Space O(1) — better than HashSet of visited nodes.

Common follow-ups

• Find cycle start
• Find cycle length

Mention both HashSet and Floyd; then choose Floyd for O(1) space.

Short answer: BFS uses a queue and finds shortest paths in unweighted graphs / level order. DFS uses a stack/recursion and is natural for path existence, cycle detection, topological sort, and flood fill. Pick based on what “best” means.

If the question says “shortest” on an unweighted graph, default to BFS.