Interview Q&A

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: 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: 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: 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: 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: DFS from each cell matching the first letter. Mark visited, explore 4 directions for the next character, then unmark (backtrack). Return true as soon as the word is completed.

Complexity

Time roughly O(N * 4^L) worst case (N cells, L word length); Space O(L) recursion.

Edge cases to mention

• Word longer than board cells
• Reuse of same cell (forbidden)
• Single-letter word

Emphasize marking/unmarking — that is the backtracking signature.

Short answer: Each node has children map/array[26] and an isEnd flag. insert/search/startsWith walk character by character. Tries shine for autocomplete and dictionary prefix queries.

Complexity

Time O(L) per operation (L = word length), Space O(total characters).

Common follow-ups

• Word Search II (Trie + backtracking)
• Replace Words

Ask if alphabet is lowercase English — array[26] is cleaner than Dictionary.

Short answer: Prioritize: Arrays/Hashing, Two Pointers, Sliding Window, Binary Search, Stack, Linked List, Trees (BFS/DFS), Graphs (BFS/DFS/topo), Heaps, Intervals, 1-D DP, Backtracking, and LRU-style design. Pattern recognition beats memorizing hundreds of problems.

Interview approach

1. Finish Blind 75 or NeetCode 150-style coverage once.
2. Timed practice: aim to solve mediums in ~25 minutes with explanation.
3. Always narrate brute force → optimize → complexity → edge cases.
4. Revisit company-tagged mediums from the last 6–12 months.

Depth on patterns beats shallow volume. Quality reps with explanation win offers.

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.

Short answer: BFS/DFS while maintaining a map from original node → clone. For each neighbor, clone if missing, then link clones. Prevents infinite loops on cycles.

Complexity

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

The visited/clone map is mandatory — say it before writing loops.

Short answer: Min-heap of size k: O(n log k). Quickselect (partition) average O(n), worst O(n²). Sorting is O(n log n) — mention then improve.

Common follow-ups

• Kth largest in a stream
• Find median

If they care about worst-case, discuss heap; if average-case, mention Quickselect.

Short answer: Transpose the matrix, then reverse each row (for 90° clockwise). Alternatively rotate layer-by-layer swapping four cells. Both are O(n²) time and O(1) extra space.

Transpose + reverse is easier to get right under pressure.

Short answer: Diameter is the longest path between any two nodes (edges count). DFS returns height; at each node update global max of leftHeight + rightHeight. O(n).

Path may not pass through the root — that is the common trap.

Short answer: Keep a normal stack plus an auxiliary stack of current minima (or store pairs). push/pop/top/getMin all O(1). On push, push min(x, currentMin) onto the min stack.

Complexity

All operations O(1), Space O(n).

Do not scan the stack for getMin — that is O(n) and fails the prompt.

Short answer: Subsets: at each index choose include/exclude (or loop-based cascading). Permutations: swap/choose unused elements recursively. Always discuss time complexity exponential in n and when to prune.

Complexity

Subsets O(n * 2^n); Permutations O(n * n!).

Draw the decision tree for n=3 — it proves you understand recursion depth.

Short answer: DFS while tracking parent: visiting an already-visited neighbor that is not the parent means a cycle. Union-Find (Disjoint Set) also works for edge lists: union fails if both ends share a parent.

Complexity

Time O(V + E).

Do not reuse the directed-graph “gray node” story without adjusting for parent.