C# Coding Interview — Cheat Sheet

1 · What the question says → pattern → C# tool

1. Sliding Window: “contiguous subarray”, “substring”, “window of size k”. int[26] or Dictionary<char,int> counts.
2. Two Pointers: “sorted” plus “pair, triplet, sum to target”. Array.Sort, two ints.
3. Fast & Slow: “cycle”, “middle of the list”, “repeats forever”. Two ListNode? refs, compare with ==.
4. Merge Intervals: “intervals”, “meetings”, “start and end”. Array.Sort(a, (x, y) => x[0].CompareTo(y[0])).
5. Cyclic Sort: “n numbers in 1..n”, “missing”, “duplicate”. Swap with (a[i], a[j]) = (a[j], a[i]).
6. List Reversal: “reverse the list”, “in place”, “O(1) space”. prev, curr, next refs.
7. BFS: “level by level”, “fewest steps”, “nearest”. Queue<T>, mark seen on push.
8. DFS: “all paths”, “connected region”, “does a path exist”. Local function, or Stack<T> when deep.
9. Top K Heaps: “top K”, “K most frequent”, “K closest”. Size-k PriorityQueue<T, int>.
10. Backtracking: “all subsets”, “all permutations”, “place N things”. List<int> trail, add [.. trail].
11. Binary Search: “rotated”, “first index where”, “minimise the max”. Own loop, lo + (hi - lo) / 2.
12. DP: “how many ways”, “min cost”, “longest subsequence”. long[n + 1] table, or a Dictionary memo.
13. Prefix Sum: “sums to exactly k”, “values may be negative”. Dictionary<long,int> { [0] = 1 }.
14. Monotonic Stack: “next greater”, “span”, “histogram”. Stack<int> of indices.
15. Topological Sort: “prerequisites”, “build order”. int[] indegree plus Queue<int>.
16. Union-Find: “connected components”, “edges arrive one at a time”. int[] parent, int[] rank.
17. Greedy: “reach the end”, a provable local choice. Sort, then one pass.
18. Trie: “prefix”, “dictionary of words”, “wildcard”. TrieNode?[26] children.
19. Bits: “appears once”, “no + or -”, “set bits”. ^, &, BitOperations.PopCount.
20. K-way / Two Heaps: “K sorted lists”, “running median”. Two PriorityQueues, one reversed.
21. Dijkstra: “weighted edges”, “cheapest path”. PriorityQueue<int,long>, skip stale.
22. Monotonic Deque: “max in every window”. No built-in deque: int[] ring buffer or LinkedList.
23. Design: “design a class”, “O(1) get and put”. Dictionary plus LinkedList nodes.

2 · Input size → expected complexity

• n ≤ 12: O(n!), permutations.
• n ≤ 20: O(2ⁿ), subsets, bitmask.
• n ≤ 100: O(n⁴), four loops.
• n ≤ 500: O(n³), Floyd-Warshall.
• n ≤ 5,000: O(n²), DP over pairs.
• n ≤ 10⁵: O(n log n), sort, heap, binary search.
• n ≤ 10⁶: O(n), one pass.
• n > 10⁸: O(log n), search the answer, use long.

Budget about 10⁸ simple operations per second in C#. Heavy LINQ costs several times more.

3 · Constraints are hints

• “O(1) extra space”: two pointers, in-place, Floyd.
• “Do not modify the input”: no Array.Sort. Cycle detection, binary search.
• “Must be O(log n)”: binary search, an instruction.
• “The array is sorted”: never mentioned by accident.
• “Values may be negative”: kills the sliding window.
• “Fits in 32 bits”: the answer does. Middle steps may need long.
• “Queries one at a time”: Union-Find, heap, SortedSet.
• n huge, k small: size-k heap, O(n log k).
• “Lowercase letters only”: int[26], O(1) space.

4 · C# costs that bite

• list.Add, list[i], RemoveAt(Count - 1): O(1).
• list.Insert(0, x), RemoveAt(0), Remove(x): O(n).
• list.Contains versus set.Contains: O(n) versus O(1).
• Dictionary and HashSet ops: O(1) average. String keys hash in O(length).
• Queue and Stack push and pop: O(1).
• PriorityQueue Enqueue, Dequeue: O(log n). Peek O(1). Heapify ctor O(n). Remove O(n).
• SortedSet, SortedDictionary: O(log n), red-black trees.
• Array.BinarySearch: O(log n). A miss returns ~insertionPoint.
• a[i..j], s[i..j], Substring: O(k), a copy. AsSpan(i..j): O(1).
• s += x in a loop: O(n²). StringBuilder: O(n).
• Array.Sort, List.Sort: O(n log n), not stable. OrderBy: stable.
• LINQ Count(), Max(), Contains(): O(n) each, every time.

Max-heap: Comparer<int>.Create((a, b) => b.CompareTo(a)). Details in Guide 1.

5 · C# traps that cost offers

• int overflow is silent. Use long, (long)a * b, checked.
• Midpoint: lo + (hi - lo) / 2, never (lo + hi) / 2.
• Comparers: a.CompareTo(b), never a - b.
• dict[key] read throws on a miss. Use GetValueOrDefault, TryGetValue.
• No decrease-key. Enqueue again, skip stale entries on dequeue.
• No deque. Ring buffer or LinkedList<T>. Say so.
• Editing a list in foreach throws. Loop backwards or use RemoveAll.
• Struct from a list is a copy. Write it back, or use a class.
• Arrays as keys compare by reference. Use value tuples.
• Jagged rows start null. Create each row in a loop.
• Stack overflow cannot be caught. Deep DFS needs an explicit Stack<T>.
• -7 / 2 == -3, -7 % 3 == -1. Floor mod: ((a % m) + m) % m.
• Deferred LINQ reruns on every enumeration. ToList() once.
• Dictionary order is not guaranteed. Sort before returning.

6 · Pattern traps

• Length of [left, right] is right - left + 1.
• Mark visited on push, not on pop, in BFS.
• Add a copy of the trail in backtracking, and always un-choose.
• Sort by end to choose intervals, by start to merge them.
• A min-heap keeps the K largest. The root is what you evict.
• left = mid loops forever. Use mid + 1.
• Register the clone before recursing, or a cycle never ends.
• BinarySearch on duplicates returns any match. Write a lower bound.

7 · The script, 45 minutes

• 3 min: clarify, then restate the problem and get a yes.
• 2 min: work their example by hand. Invent one edge case.
• 2 min: state the brute force and its cost. Do not code it.
• 6 min: name the waste, name the pattern, cost it, ask before coding.
• 18 min: guard clauses first. Real names. Narrate decisions, not syntax.
• 6 min: dry-run a written trace. Diagnose out loud before fixing.
• 3 min: time, space, what n means, worst versus average. One follow-up.

8 · Seven questions to ask, always

1. How large can the input get?
2. Can the values be negative? Zero?
3. Can it be empty, null, or one element?
4. Are duplicates possible?
5. May I modify the input?
6. If several answers are valid, does it matter which?
7. Can the result pass the int range?

9 · Edge cases by input type

• Array: empty, null, one, two, all equal, sorted, reversed, all negative, int.MinValue.
• String: empty, one char, all same, palindrome, case, spaces.
• Linked list: null, one node, two, target at head, at tail, a cycle.
• Tree: null, one node, left-only chain, perfect, duplicates.
• Graph: no edges, self-loop, cycle, disconnected, duplicate edges.
• Grid: empty, one cell, one row, all blocked, all open.
• Intervals: empty, touching ends, nested, identical.
• k or target: k = 0, k = 1, k = n, k > n, target above the total.

10 · The five boundary checks

1. Before the first pass: are the seeds right?
2. First pass: does it read nums[i - 1] at i = 0?
3. Last pass: does it read past the end?
4. After the loop: a stack still holding items, a final group never flushed?
5. Does every path move something, so the loop ends?

Debug.Assert disappears in Release builds. Collect failures or throw. See Guide 4.

11 · Say these out loud

• “The brute force is O(n²). At n = 10⁵ that is 10¹⁰, too slow.”
• “Both pointers only move forward, so it is O(n) amortised.”
• “Shall I code that?”
• “The running sum is a long, because the int would overflow.”
• “.NET has no deque, so I will use a ring buffer.”
• “I am sorting in place, which changes the caller’s array.”
• “Average O(1). An adversarial hash makes it O(n).”