Language

C# for interviews

Idioms, collections, ListNode/TreeNode, and the heap the templates actually run. .NET 10.

The solution tests run on .NET 10, which is the compiler these fences were run with (dotnet run --file). Each fence is its own program.

int is a 32-bit two’s complement value. long is 64-bit. The default context wraps on overflow. Bit patterns that depend on that width are on the bit-manipulation pattern page.

Division, remainder, overflow

if (-3 / 2 != -1) throw new InvalidOperationException("div");
if (-3 % 2 != -1) throw new InvalidOperationException("mod");
if (unchecked(-int.MinValue) != int.MinValue) throw new InvalidOperationException("wrap");

int min = int.MinValue;
bool threw = false;
try {
    checked { int x = -min; _ = x; }
} catch (OverflowException) {
    threw = true;
}
if (!threw) throw new InvalidOperationException("checked");

if ((1L << 31) != 2147483648L) throw new InvalidOperationException("wide");

Integer / truncates toward zero. The remainder takes the sign of the dividend. Python’s // floors and its % takes the sign of the divisor, so a port of a Python snippet needs a second look on negative inputs.

Negating int.MinValue overflows: checked throws, unchecked stays on int.MinValue. A wide positive shift uses long, written 1L << 31.

Strings and StringBuilder

string s = "ab,cd";
if (s[0] != 'a' || s[^1] != 'd') throw new InvalidOperationException("index");
if (s[1..4] != "b,c") throw new InvalidOperationException("slice");
if (string.Join("", s.Reverse()) != "dc,ba") throw new InvalidOperationException("rev");
if (s.Split(',')[0] != "ab" || s.Split(',')[1] != "cd") throw new InvalidOperationException("split");
if (string.Join(" ", new[] { "ab", "cd" }) != "ab cd") throw new InvalidOperationException("join");
if (s.Replace("ab", "xy") != "xy,cd") throw new InvalidOperationException("replace");
if (!s.StartsWith("ab") || !s.EndsWith("cd")) throw new InvalidOperationException("ends");
if (s.IndexOf('z') != -1) throw new InvalidOperationException("indexof");
if (s.Contains("cd") == false) throw new InvalidOperationException("contains");

var sb = new System.Text.StringBuilder();
sb.Append("ab");
sb.Append('c');
if (sb.ToString() != "abc") throw new InvalidOperationException("sb");

string name = "ada";
if ($"{name} {2}" != "ada 2") throw new InvalidOperationException("interp");

s[^1] is the last character. s[1..4] is the half-open range. IndexOf returns -1 when the piece is missing. Strings are immutable; Replace returns a new string and replaces every match. StringBuilder is the buffer when you append in a loop.

Interpolation is $"{expr}". A format after the colon is a .NET format string.

Dictionary, HashSet, and two-sum

This is the shape of the hashing template. TryGetValue returns false when the key is missing. Indexing a missing key throws.

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

int[] pair = TwoSum([2, 7, 11, 15], 9);
if (pair[0] != 0 || pair[1] != 1) throw new InvalidOperationException("two sum");

var set = new HashSet<int> { 1, 1, 2 };
if (set.Count != 2 || !set.Contains(2)) throw new InvalidOperationException("set");
set.Add(3);
set.Remove(1);
if (set.Contains(1) || !set.Contains(3)) throw new InvalidOperationException("mut");

var ordered = new SortedSet<int> { 3, 1, 2 };
if (ordered.Min != 1 || ordered.Max != 3) throw new InvalidOperationException("sorted");

HashSet is unordered membership. SortedSet keeps values in order and exposes Min / Max. ContainsKey is the Dictionary membership test when you do not need the value.

Lists, sort, and jagged rows

var nums = new List<int> { 10, 2, 1 };
nums.Sort();
if (nums[0] != 1 || nums[1] != 2 || nums[2] != 10) throw new InvalidOperationException("sort");

int[] row = [0, 0];
int[][] shared = [row, row];
shared[0][0] = 1;
if (shared[1][0] != 1) throw new InvalidOperationException("shared");

int[][] grid = [[0, 0], [0, 0]];
grid[0][0] = 1;
if (grid[1][0] != 0) throw new InvalidOperationException("jagged");

int[] arr = [1, 2, 3];
if (arr.Length != 3) throw new InvalidOperationException("len");
nums.Add(4);
if (nums[^1] != 4) throw new InvalidOperationException("add");

List<int>.Sort orders by numeric value. An int[] has a fixed Length; a List<int> grows with Add. Each new row is its own array. Reusing one array object makes a write show up in every row that holds it. LeetCode-style matrices in the templates are jagged int[][].

foreach, yield, and local functions

var seen = new List<int>();
foreach (var value in new[] { 1, 2, 3 }) seen.Add(value);
if (!seen.SequenceEqual([1, 2, 3])) throw new InvalidOperationException("foreach");

IEnumerable<int> Range(int n) {
    for (int i = 0; i < n; i++) yield return i;
}
if (!Range(3).SequenceEqual([0, 1, 2])) throw new InvalidOperationException("yield");

int Add(int a, int b = 0) => a + b;
if (Add(1) != 1 || Add(1, 2) != 3) throw new InvalidOperationException("local");

(int x, int y) = (3, 4);
if (x != 3 || y != 4) throw new InvalidOperationException("deconstruct");
(x, y) = (y, x);
if (x != 4 || y != 3) throw new InvalidOperationException("swap");

foreach walks anything IEnumerable. yield return builds an iterator; the body runs as the caller pulls values. A local function can sit next to the top-level statements in a file-based program. Tuple deconstruction swaps two bindings without a temp.

for (int i = 0; i < n; i++) is the index form. while and do exist. break leaves the loop; continue skips the rest of the body.

Classes, records, and nullability

var c = new Counter();
if (c.Inc() != 1 || c.Value != 1) throw new InvalidOperationException("class");
if (new Point(1, 2) != new Point(1, 2)) throw new InvalidOperationException("eq");
if (new Point(1, 2) == new Point(1, 3)) throw new InvalidOperationException("neq");

string? missing = null;
if ((missing ?? "default") != "default") throw new InvalidOperationException("coal");
if (missing?.Length != null) throw new InvalidOperationException("cond");

class Counter {
    public int Value { get; private set; }
    public int Inc() => ++Value;
}
record Point(int X, int Y);

A class compares by reference. A record compares by value and deconstructs into its parameters. string? is a nullable reference; ?? supplies a fallback and ?. short-circuits. Indexing a missing Dictionary key throws; TryGetValue does not.

Heap

PriorityQueue<TElement, TPriority> dequeues the smallest priority first. The heap top-K template stores the value as both element and priority, then drops the smallest once the queue is past k.

int FindKthLargest(int[] nums, int k) {
    var pq = new PriorityQueue<int, int>();
    foreach (var x in nums) {
        pq.Enqueue(x, x);
        if (pq.Count > k) pq.Dequeue();
    }
    return pq.Peek();
}

if (FindKthLargest([3, 2, 1, 5, 6, 4], 2) != 5) throw new InvalidOperationException("kth");

var max = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
max.Enqueue(3, 3);
max.Enqueue(1, 1);
if (max.Dequeue() != 3) throw new InvalidOperationException("max");

A reversed comparer turns the same queue into a max-heap. Negating the priority also works until the value is int.MinValue, whose negation overflows.

Deque

The sliding-window template uses LinkedList<int>, so both ends are O(1). Queue<T> only offers the back and the front. Stack<T> is the one end.

int[] MaxSlidingWindow(int[] nums, int k) {
    var dq = new LinkedList<int>();
    var res = new List<int>();
    for (int i = 0; i < nums.Length; i++) {
        while (dq.Count > 0 && dq.First!.Value <= i - k) dq.RemoveFirst();
        while (dq.Count > 0 && nums[dq.Last!.Value] <= nums[i]) dq.RemoveLast();
        dq.AddLast(i);
        if (i >= k - 1) res.Add(nums[dq.First!.Value]);
    }
    return res.ToArray();
}

int[] got = MaxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
int[] want = [3, 3, 5, 5, 6, 7];
if (!got.SequenceEqual(want)) throw new InvalidOperationException("window");

var stack = new Stack<int>();
stack.Push(1);
if (stack.Pop() != 1) throw new InvalidOperationException("stack");
var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
if (queue.Dequeue() != 1) throw new InvalidOperationException("queue");

Binary search

The template uses lo + ((hi - lo) >> 1). Subtracting first keeps the sum inside int for non-negative indexes. (lo + hi) >> 1 can overflow int when both ends are large.

int BinarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.Length;
    while (lo < hi) {
        int mid = lo + ((hi - lo) >> 1);
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo < nums.Length && nums[lo] == target ? lo : -1;
}

if (BinarySearch([1, 3, 3, 7], 3) != 1) throw new InvalidOperationException("hit");
if (BinarySearch([1, 3, 3, 7], 4) != -1) throw new InvalidOperationException("miss");
if (BinarySearch([], 1) != -1) throw new InvalidOperationException("empty");

LINQ

int[] nums = [1, 2, 3, 4];
int sum = nums.Where(x => x % 2 == 0).Sum();
if (sum != 6) throw new InvalidOperationException("sum");
if (nums.Count(x => x > 2) != 2) throw new InvalidOperationException("count");
if (nums.Max() != 4) throw new InvalidOperationException("max");

Where then Sum scans once. A Where or Any written inside a for loop scans again on every iteration. A hand-written loop keeps that cost visible.

Math

if (Math.Abs(-3) != 3) throw new InvalidOperationException("abs");
if (Math.Max(1, 4) != 4) throw new InvalidOperationException("max");
if (Math.Clamp(9, 0, 5) != 5) throw new InvalidOperationException("clamp");
if (Math.DivRem(7, 3) != (2, 1)) throw new InvalidOperationException("divrem");
if (int.IsPositive(4) == false) throw new InvalidOperationException("sign");
if (Math.Min(1L, 2L) != 1L) throw new InvalidOperationException("long");

Math.Abs(int.MinValue) overflows in a checked context. DivRem returns the pair (quotient, remainder) with toward-zero division. Prefer long when a product can pass int.MaxValue.

Linked lists

The linked-list template is this node plus reverse and a dummy-head merge.

var a = new ListNode(1, new ListNode(2, new ListNode(3)));
var rev = ReverseList(a);
if (ToList(rev) is not [3, 2, 1]) throw new InvalidOperationException("rev");

ListNode ReverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        var nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

List<int> ToList(ListNode head) {
    var outList = new List<int>();
    while (head != null) {
        outList.Add(head.val);
        head = head.next;
    }
    return outList;
}

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; }
}

Walk with while (cur != null). A dummy head keeps the merge loop from special-casing the first node. null is the empty list. Types in a file-based program sit after the top-level statements.

Trees

var root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4)));
if (MaxDepth(root) != 3) throw new InvalidOperationException("depth");
var levels = LevelOrder(root);
if (levels.Count != 3 || levels[0][0] != 1 || levels[2][0] != 4)
    throw new InvalidOperationException("level");

int MaxDepth(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.Max(MaxDepth(node.left), MaxDepth(node.right));
}

List<List<int>> LevelOrder(TreeNode node) {
    var res = new List<List<int>>();
    if (node == null) return res;
    var q = new Queue<TreeNode>();
    q.Enqueue(node);
    while (q.Count > 0) {
        int size = q.Count;
        var level = new List<int>();
        for (int i = 0; i < size; i++) {
            var n = q.Dequeue();
            level.Add(n.val);
            if (n.left != null) q.Enqueue(n.left);
            if (n.right != null) q.Enqueue(n.right);
        }
        res.Add(level);
    }
    return res;
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

Recursion on left and right is the DFS template. Level-order snapshots q.Count so the current level stays isolated from the children just enqueued.

Graphs

The graph-DFS template stores undirected edges as List<int>[]. Grid flood fill is a stack of (r, c) cells.

if (CountComponents(4, [[0, 1], [2, 3]]) != 2) throw new InvalidOperationException("cc");
int[][] filled = FloodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2);
if (filled[0][0] != 2 || filled[2][1] != 0 || filled[2][2] != 1)
    throw new InvalidOperationException("fill");

int CountComponents(int n, int[][] edges) {
    var adj = new List<int>[n];
    for (int i = 0; i < n; i++) adj[i] = new List<int>();
    foreach (var e in edges) { adj[e[0]].Add(e[1]); adj[e[1]].Add(e[0]); }
    var visited = new bool[n];
    int count = 0;
    for (int v = 0; v < n; v++) {
        if (!visited[v]) { Dfs(v); count++; }
    }
    return count;
    void Dfs(int v) {
        visited[v] = true;
        foreach (var u in adj[v]) if (!visited[u]) Dfs(u);
    }
}

int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
    int orig = image[sr][sc];
    if (orig == newColor) return image;
    int rows = image.Length, cols = image[0].Length;
    var stack = new Stack<(int r, int c)>();
    stack.Push((sr, sc));
    while (stack.Count > 0) {
        var (r, c) = stack.Pop();
        if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] != orig) continue;
        image[r][c] = newColor;
        stack.Push((r + 1, c)); stack.Push((r - 1, c));
        stack.Push((r, c + 1)); stack.Push((r, c - 1));
    }
    return image;
}

orig == newColor is the early return that stops an infinite rewrite of the same color. A local function (Dfs) closes over visited and adj.

Union-Find

Path compression plus union by rank. Union returns whether the two nodes were in different components.

var uf = new UnionFind(4);
if (!uf.Union(0, 1) || !uf.Union(2, 3)) throw new InvalidOperationException("union");
if (uf.Union(0, 1)) throw new InvalidOperationException("dup");
if (uf.Components != 2) throw new InvalidOperationException("cc");

class UnionFind {
    readonly int[] parent;
    readonly int[] rank;
    public int Components { get; private set; }
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        Components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]);
    public bool Union(int a, int b) {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        Components--;
        return true;
    }
}

Trie

var t = new Trie();
t.Insert("apple");
if (!t.Search("apple") || t.Search("app")) throw new InvalidOperationException("search");
if (!t.StartsWith("app")) throw new InvalidOperationException("prefix");

class TrieNode {
    public Dictionary<char, TrieNode> Children = new();
    public bool IsWord;
}
class Trie {
    readonly TrieNode root = new();
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.Children.TryGetValue(ch, out var next)) {
                next = new TrieNode();
                node.Children[ch] = next;
            }
            node = next;
        }
        node.IsWord = true;
    }
    public bool Search(string word) {
        var node = Walk(word);
        return node != null && node.IsWord;
    }
    public bool StartsWith(string prefix) => Walk(prefix) != null;
    TrieNode Walk(string s) {
        var node = root;
        foreach (var ch in s) {
            if (!node.Children.TryGetValue(ch, out node)) return null;
        }
        return node;
    }
}

Search needs IsWord. StartsWith only needs the walk to survive.