Interview Q&A

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: Hash map from key → node plus a doubly linked list ordered by recency. get/put are O(1): move accessed node to front; on capacity eviction remove from tail. This is one of the most asked system-design-lite coding questions.

Interview approach

1. Clarify capacity and that both get and put must be O(1).
2. Explain why list alone or map alone is not enough.
3. Implement move-to-front and remove-tail helpers.
4. Handle update of existing key in put.

Complexity

get/put O(1) average; Space O(capacity).

Common follow-ups

• LFU Cache
• Thread-safe LRU
• TTL expiration

Mistakes to avoid

• Forgetting to update value on put for existing key
• Losing list pointers when removing

In C#, LinkedList + Dictionary is the standard interview implementation.

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: 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: 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.

Short answer: Use preorder with null markers (e.g. "#") or level-order BFS with nulls. Deserialization consumes the same format with a queue/iterator. Clarify the string format with the interviewer first.

Complexity

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

Pick one format and stick to it — inconsistency is a common fail point.

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: Water at i is min(leftMax, rightMax) − height[i]. Compute with two arrays, or optimize with two pointers moving from ends while tracking leftMax/rightMax. Stack-based solution processes bars as histogram valleys.

Complexity

Two pointers O(n) time, O(1) space.

Relate it to Container With Most Water but stress per-index water units.