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: Kadane’s algorithm: keep a running sum; if it goes negative, reset to 0 (or start fresh at the next element). Track the best running sum seen. This finds the contiguous subarray with maximum sum in O(n).

Problem statement

Given an integer array, find the contiguous subarray with the largest sum and return that sum.

Interview approach

1. Mention divide-and-conquer O(n log n) if asked for alternatives.
2. Explain local decision: extend current subarray or start new at i.
3. Handle all-negative arrays carefully (max element, not 0).

Sample solution

int MaxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.Length; i++) {
        cur = Math.Max(nums[i], cur + nums[i]);
        best = Math.Max(best, cur);
    }
    return best;
}

Complexity

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

Edge cases to mention

• All negative numbers
• Single element
• Mix of positives and zeros

Common follow-ups

• Also return the start/end indices
• Circular maximum subarray

If the interviewer allows empty subarray, resetting to 0 is fine; otherwise use the version above.

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: Build prefix products from the left and suffix products from the right. For index i, answer[i] = prefix[i] * suffix[i]. You can do it with one output array and one running suffix to achieve O(1) extra space (excluding output).

Interview approach

1. Clarify: no division; O(n) time expected.
2. First pass: answer[i] = product of all left of i.
3. Second pass from right: multiply by running right product.

Sample solution

int[] ProductExceptSelf(int[] nums) {
    int n = nums.Length;
    var ans = new int[n];
    ans[0] = 1;
    for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

Complexity

Time O(n), Space O(1) extra (output not counted).

Edge cases to mention

• Zeros in the array (one zero vs two zeros)
• Negatives

Never use division in the interview version — many panels explicitly forbid it.

Short answer: Sort the array. Fix one number, then use two pointers on the remainder to find pairs that sum to −fixed. Skip duplicates carefully to return unique triplets. Overall O(n²).

Interview approach

1. Sort ascending.
2. For i from 0..n-3, skip duplicate nums[i].
3. Left = i+1, right = n-1; move based on sum vs 0.
4. When sum == 0, record triplet and skip duplicate left/right.

Complexity

Time O(n²), Space O(1) extra besides output (sorting may use O(log n)).

Edge cases to mention

• Fewer than 3 elements
• All zeros
• Many duplicates

Common follow-ups

• 4Sum
• 3Sum Closest

Mistakes to avoid

• Forgetting to skip duplicates → wrong unique set
• Using the same index twice

Sorting + two pointers is the pattern interviewers expect after Two Sum.

Short answer: Two pointers at both ends. Area = min(height[L], height[R]) * (R − L). Move the pointer at the shorter line inward, because width shrinks and only a taller line can improve area. O(n) time.

Complexity

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

Edge cases to mention

• Length 2
• Strictly increasing heights

Common follow-ups

• Trapping Rain Water (harder, needs prefix max or stack)

Prove the greedy move: the shorter side is the bottleneck.

Short answer: Sliding window with a map/set of characters in the current window. Expand right; when a duplicate appears, shrink left until the window is unique again. Track max window length.

Sample solution

int LengthOfLongestSubstring(string s) {
    var last = new Dictionary<char, int>();
    int left = 0, best = 0;
    for (int right = 0; right < s.Length; right++) {
        char c = s[right];
        if (last.TryGetValue(c, out int prev) && prev >= left)
            left = prev + 1;
        last[c] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

Complexity

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

Edge cases to mention

• Empty string
• All unique
• All same character
• Unicode / case sensitivity

Name the pattern “variable-size sliding window” — it signals seniority.

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: Each node must lie within an allowed (low, high) range. Recurse left with high = node.val and right with low = node.val. Alternatively, inorder traversal must produce a strictly increasing sequence.

Complexity

Time O(n), Space O(h) recursion height.

Mistakes to avoid

• Only comparing with immediate children (misses deeper violations)
• Using ≤ when duplicates are not allowed

Pass long.MinValue/MaxValue (or nullable bounds) to avoid int overflow edge cases.

Short answer: Scan the grid. When you find a '1', increment island count and DFS/BFS to sink (mark visited) the entire connected land component. Count how many times you start a flood fill.

Complexity

Time O(rows * cols), Space O(rows * cols) worst-case recursion/queue.

Edge cases to mention

• Empty grid
• All water
• Diagonal connectivity? (usually 4-directional only)

Common follow-ups

• Max area of island
• Number of distinct islands
• Surrounded regions

Clarify 4-direction vs 8-direction before coding.

Short answer: Model prerequisites as a directed graph. Detect a cycle with DFS colors (white/gray/black) or Kahn’s algorithm (BFS indegrees). If a cycle exists, you cannot finish all courses.

Complexity

Time O(V + E), Space O(V + E).

Common follow-ups

• Course Schedule II — return a valid order (topological sort)
• Parallel semester counting

Say “topological sort / cycle detection” early — that is the pattern name they want.

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: Unbounded knapsack DP: dp[a] = minimum coins to make amount a. For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1). Initialize dp[0] = 0 and others to +∞. Return -1 if unreachable.

Complexity

Time O(amount * coins), Space O(amount).

Edge cases to mention

• Amount 0 → 0
• No combination possible → -1
• Coin larger than amount

Common follow-ups

• Coin Change II — number of combinations
• Fewest coins with limited supply

Mention top-down memoization as an alternative to bottom-up.

Short answer: Classic DP is O(n²): dp[i] = best LIS ending at i. The optimized patience-sorting / binary-search approach maintains tails of increasing subsequences in O(n log n). Mention both; implement O(n²) unless asked for optimal.

Complexity

DP O(n²); patience sorting O(n log n).

Common follow-ups

• Print one LIS
• Longest decreasing / bitonic subsequence

Interviewers love hearing both complexities even if you code the simpler DP.

Short answer: Sort intervals by start. Scan and merge when the next start ≤ current end; otherwise push current and start a new one. O(n log n) from sorting.

Sample solution

int[][] Merge(int[][] intervals) {
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
    var res = new List<int[]>();
    foreach (var iv in intervals) {
        if (res.Count == 0 || res[^1][1] < iv[0]) res.Add(iv);
        else res[^1][1] = Math.Max(res[^1][1], iv[1]);
    }
    return res.ToArray();
}

Complexity

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

Common follow-ups

• Insert Interval
• Meeting Rooms II (min rooms / sweep line)
• Employee Free Time

Sorting by start is non-negotiable — say it before coding.

Short answer: Modified binary search: check which half is sorted, then decide whether the target lies in that sorted half. Still O(log n).

Interview approach

1. Compute mid.
2. If left half sorted (nums[lo] ≤ nums[mid]): if target in [lo, mid) go left else right.
3. Else right half sorted: if target in (mid, hi] go right else left.

Complexity

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

Edge cases to mention

• No rotation
• Duplicates (harder — may degrade to O(n))
• Single element

Draw a rotated array and mark the sorted half each step while explaining.

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: Two pointers with a gap of n. Advance fast n steps, then move both until fast hits the end; slow.next is the node to delete. One pass, O(1) space.

Edge cases to mention

• Remove head (n == length)
• Single node list
• n = 1 (remove tail)

Use a dummy head so deleting the real head is uniform.

Short answer: BFS with a queue. Process level size at a time, enqueue children, and collect values per level into a list of lists.

Complexity

Time O(n), Space O(n) for the queue/result.

Common follow-ups

• Zigzag level order
• Average of levels
• Right side view

Capturing level size before the inner loop is the key detail interviewers watch for.

Short answer: BST: walk from root — if both values are smaller go left, both larger go right, else current is LCA. General binary tree: recurse; if both sides return non-null, current is LCA; else return the non-null side.

Complexity

BST average O(h); general tree O(n).

Ask which tree type — the optimal approach changes.

Short answer: Count frequencies with a hash map. Then either use a min-heap of size k (O(n log k)) or bucket sort by frequency (O(n)) since frequencies are in 1..n.

Complexity

Heap O(n log k); bucket O(n).

Common follow-ups

• Top K frequent words (tie-break lexicographically)
• Kth largest element

Prefer bucket sort when you want to show O(n) mastery.