Coding problems, solved

#A six-step interview method

The goal is a correct solution with an explanation of why it works, not memorized code. Explain meaningful decisions as you work.

1. Restate the task and clarify constraints: empty input, negatives, duplicates, numeric bounds, mutation and the no-solution result.
2. Write a normal example and boundary cases and agree the output.
3. Describe brute force and its complexity as a baseline.
4. Improve it using a clear invariant or recurrence, explaining memory trade-offs.
5. Code with meaningful names and explain decisions without narrating every keystroke.
6. Trace examples and edge cases; report time, auxiliary space and output space.

#1. Two Sum

Problem: Return zero-based indices of two distinct elements totaling target, or an empty array. [2,7,11,15], 9 → [0,1]. Idea: Store earlier values and look for the complement instead of testing every pair in O(n²).

Try it before opening the solution: input [2,7,11,15] with target = 9 should return [0,1]. Also test an empty array, no solution, and repeated values such as [3,3], 6.

int[] TwoSum(int[] values, int target)
{
    var seen = new Dictionary<long, int>();
    for (int i = 0; i < values.Length; i++)
    {
        long need = (long)target - values[i]; // (1)
        if (seen.TryGetValue(need, out int previous)) return [previous, i];
        seen[values[i]] = i; // (2)
    }
    return [];
}

#2. Duplicates and first unique character

Problems: Detect a repeated number, and find the first non-repeating character index or -1. Examples: [1,2,1] → true, "aabbc" → 4. Idea: Use membership for duplicates and frequency followed by ordered scanning for uniqueness. The character example accepts lowercase English only.

bool ContainsDuplicate(int[] values)
{
    var seen = new HashSet<int>();
    foreach (int value in values)
        if (!seen.Add(value)) return true; // (1)
    return false;
}
int FirstUniqueChar(string text)
{
    var count = new int[26];
    foreach (char c in text) count[c - 'a']++;
    for (int i = 0; i < text.Length; i++)
        if (count[text[i] - 'a'] == 1) return i; // (2)
    return -1;
}

Complexity: Duplicate detection is expected O(n) time and O(u) space for distinct values. Unique-character search is O(n) time and O(1) space for the fixed alphabet. Test empty and fully repeated inputs; broader text requires a different counter and an agreed character definition.

#3. Valid anagram and group anagrams

Problems: Check equal character frequencies and group matching words. listen and silent are anagrams; [eat,tea,tan] → [[eat,tea],[tan]]. Idea: Use counts for lowercase-English validation and sorted char signatures for case-sensitive grouping.

bool IsAnagram(string first, string second)
{
    if (first.Length != second.Length) return false;
    var count = new int[26];
    for (int i = 0; i < first.Length; i++)
    {
        count[first[i] - 'a']++;
        count[second[i] - 'a']--; // (1)
    }
    return count.All(value => value == 0);
}
List<List<string>> GroupAnagrams(string[] words)
{
    var groups = new Dictionary<string, List<string>>(StringComparer.Ordinal);
    foreach (string word in words)
    {
        char[] letters = word.ToCharArray();
        Array.Sort(letters);
        string key = new(letters); // (2)
        if (!groups.TryGetValue(key, out var group)) groups[key] = group = [];
        group.Add(word);
    }
    return groups.Values.ToList();
}

Complexity: Validation takes O(n) time and O(1) space. Grouping takes expected O(w × k log k) time for w words of maximum length k, with O(wk) upper-bound storage for signatures and groups. A count signature avoids sorting for a fixed alphabet. Test empty strings and repeated words.

#4. Top K frequent elements

Problem: Return the k most frequent values; [1,1,1,2,2,3], 2 → [1,2]. Idea: Count frequencies and keep a size-k min-heap. Any tied selection is valid; result order is unspecified. k must be between zero and the distinct count.

int[] TopKFrequent(int[] values, int k)
{
    var counts = new Dictionary<int, int>();
    foreach (int value in values)
        counts[value] = counts.GetValueOrDefault(value) + 1; // (1)
    if (k < 0 || k > counts.Count) throw new ArgumentOutOfRangeException(nameof(k));
    if (k == 0) return [];
    var heap = new PriorityQueue<int, int>();
    foreach (var (value, count) in counts)
    {
        heap.Enqueue(value, count);
        if (heap.Count > k) heap.Dequeue(); // (2)
    }
    var result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.Dequeue();
    return result;
}

Complexity: Expected O(n + u log(k + 1)) time and O(u + k) space, where u is distinct count. Sorting counts is simpler but costs O(u log u). Frequency buckets give expected O(n) time with O(n + u) space. Test k=0, k=u and ties.

#5. Product of array except self

Problem: Return the product of all other elements without division; [1,2,3,4] → [24,12,8,6]. Idea: Multiply the prefix before each position by the suffix after it. All intermediate products must fit long; checked detects violations.

long[] ProductExceptSelf(int[] values)
{
    var result = new long[values.Length];
    long prefix = 1;
    for (int i = 0; i < values.Length; i++)
    {
        result[i] = prefix; // (1)
        if (i < values.Length - 1) prefix = checked(prefix * values[i]);
    }
    long suffix = 1;
    for (int i = values.Length - 1; i >= 0; i--)
    {
        result[i] = checked(result[i] * suffix); // (2)
        if (i > 0) suffix = checked(suffix * values[i]);
    }
    return result;
}

Complexity: O(n) time, O(1) auxiliary space excluding O(n) output. Empty input returns empty; a singleton returns the empty product, 1. Test one zero, two zeros and negatives. BigInteger supports larger values but multiplication is no longer constant-cost.

#6. Maximum subarray and stock profit

Problems: Find the maximum nonempty contiguous subarray sum, and the best single buy-then-sell profit for non-negative daily prices. Examples: [-2,1,-3,4,-1,2,1] → 6, [7,1,5,3,6,4] → 5. Idea: Track the best sum ending here, or the lowest earlier price.

Try it before opening the solution: the maximum subarray sum for [-2,1,-3,4,-1,2,1,-5,4] is 6, and the best profit for prices [7,1,5,3,6,4] is 5. Also test all-negative values (return the least-negative value) and descending or empty prices (profit is zero).

long MaxSubarray(int[] values)
{
    if (values.Length == 0) throw new ArgumentException("Nonempty input required");
    long current = values[0], best = current;
    for (int i = 1; i < values.Length; i++)
    {
        current = Math.Max(values[i], current + values[i]); // (1)
        best = Math.Max(best, current);
    }
    return best;
}
long MaxProfit(int[] prices)
{
    int minimum = int.MaxValue;
    long best = 0;
    foreach (int price in prices)
    {
        minimum = Math.Min(minimum, price);
        best = Math.Max(best, (long)price - minimum); // (2)
    }
    return best;
}

#7. In-place array patterns

Problems: Move zeros to the end while preserving other order; find the missing number among distinct values from 0 through n; compact a sorted array and return its unique-prefix length. Examples: [0,1,0,3] → [1,3,0,0], [3,0,1] → 2, [1,1,2] → length 2.

void MoveZeroes(int[] values)
{
    int write = 0;
    for (int read = 0; read < values.Length; read++)
        if (values[read] != 0) values[write++] = values[read]; // (1)
    while (write < values.Length) values[write++] = 0;
}
int MissingNumber(int[] values)
{
    int missing = values.Length;
    for (int i = 0; i < values.Length; i++) missing ^= i ^ values[i]; // (2)
    return missing;
}
int RemoveDuplicates(int[] sorted)
{
    if (sorted.Length == 0) return 0;
    int write = 1;
    for (int read = 1; read < sorted.Length; read++)
        if (sorted[read] != sorted[write - 1]) sorted[write++] = sorted[read]; // (3)
    return write;
}

Idea and complexity: Read/write pointers or XOR; all three use O(n) time and O(1) extra space. The first and third mutate input; the second requires distinct in-range values. Test empty, all-zero and all-equal inputs; missing-number returns 0 for empty input.

#8. Merge intervals

Problem: Merge overlapping closed intervals; [[1,3],[2,6],[8,10]] → [[1,6],[8,10]]. Starts do not exceed ends. Idea: Sort by start and compare with the latest result. Touching endpoints merge here; half-open booking intervals may require a different rule.

int[][] MergeIntervals(int[][] intervals)
{
    var sorted = intervals.OrderBy(item => item[0]).ToArray();
    var result = new List<int[]>();
    foreach (var item in sorted)
    {
        if (result.Count == 0 || item[0] > result[^1][1])
            result.Add([item[0], item[1]]); // (1)
        else result[^1][1] = Math.Max(result[^1][1], item[1]); // (2)
    }
    return result.ToArray();
}

Complexity: O(n log n) time and O(n) space for sorting and output. Test touching, nested and unsorted intervals. Pairwise overlap handling is more expensive and harder to maintain than the sorted scan.

#9. Palindromes and string reversal

Problems: Check a palindrome ignoring case and non-alphanumeric chars, reverse a char array in place, and reverse space-separated words. "A man, a plan, a canal: Panama" → true; " hello world " → "world hello". Idea: Two pointers from the ends, or split and reverse words.

bool IsPalindrome(string text)
{
    int left = 0, right = text.Length - 1;
    while (left < right)
    {
        if (!char.IsLetterOrDigit(text[left])) { left++; continue; }
        if (!char.IsLetterOrDigit(text[right])) { right--; continue; }
        if (char.ToLowerInvariant(text[left]) != char.ToLowerInvariant(text[right]))
            return false; // (1)
        left++; right--;
    }
    return true;
}
void Reverse(char[] text)
{
    for (int left = 0, right = text.Length - 1; left < right; left++, right--)
        (text[left], text[right]) = (text[right], text[left]); // (2)
}
string ReverseWords(string text) =>
    string.Join(' ', text.Split(' ', StringSplitOptions.RemoveEmptyEntries).Reverse());

Complexity: Palindrome and char reversal take O(n) time and O(1) space. ReverseWords takes O(n) time and space and normalizes spaces; tabs are not separators here. Test empty, punctuation-only and single-word inputs.

#10. Longest substring without repetition

Problem: Find the longest substring containing no repeated char; abcabcbb → 3. Idea: Maintain a distinct-character window and a map of last positions. Sorting would destroy the required order.

int LongestUniqueSubstring(string text)
{
    var last = new Dictionary<char, int>();
    int left = 0, best = 0;
    for (int right = 0; right < text.Length; right++)
    {
        if (last.TryGetValue(text[right], out int previous))
            left = Math.Max(left, previous + 1); // (1)
        last[text[right]] = right;
        best = Math.Max(best, right - left + 1); // (2)
    }
    return best;
}

Complexity: Expected O(n) time, O(min(n, alphabet)) space. Empty input gives zero; repeated identical chars give one. This counts chars; perceived-character requirements need different segmentation and position tracking.

#11. Sorted Two Sum and container with most water

Problems: Return one-based indices summing to target in a sorted array, or empty; find the largest container area between non-negative heights. [2,7,11,15], 9 → [1,2]; [1,8,6,2,5,4,8,3,7] → 49. Idea: Safely discard one endpoint instead of checking every pair.

int[] TwoSumSorted(int[] sorted, int target)
{
    int left = 0, right = sorted.Length - 1;
    while (left < right)
    {
        long sum = (long)sorted[left] + sorted[right];
        if (sum == target) return [left + 1, right + 1];
        if (sum < target) left++; else right--; // (1)
    }
    return [];
}
long MaxArea(int[] heights)
{
    int left = 0, right = heights.Length - 1;
    long best = 0;
    while (left < right)
    {
        long area = (long)Math.Min(heights[left], heights[right]) * (right - left);
        best = Math.Max(best, area);
        if (heights[left] < heights[right]) left++; else right--; // (2)
    }
    return best;
}

Complexity: Both take O(n) time and O(1) space instead of O(n²). long protects sums and areas for non-negative int heights. Test fewer than two elements, equal heights and absent sum solutions.

#12. Valid parentheses

Problem: Check bracket balance and nesting: ([]{}) is valid, (] is not. Idea: The latest opener must close first, so use a stack. This contract rejects characters other than the six bracket symbols.

bool ValidParentheses(string text)
{
    var stack = new Stack<char>();
    foreach (char c in text)
    {
        if (c is '(' or '[' or '{') { stack.Push(c); continue; }
        char expected = c switch { ')' => '(', ']' => '[', '}' => '{', _ => '\0' };
        if (expected == '\0' || !stack.TryPop(out char open) || open != expected)
            return false; // (1)
    }
    return stack.Count == 0; // (2)
}

Complexity: O(n) time and O(n) worst-case nesting space. Test )(, (( and valid nesting. Checking full source code requires handling strings and comments rather than counting brackets alone.

#13. Warm-ups: FizzBuzz, compression, word count and primes

Problems: Generate FizzBuzz from 1 through non-negative n; compress runs only if shorter; count case-insensitive words using specified separators; test primality. Examples: 15 → FizzBuzz, aaabbc → a3b2c1 but keep the original because length does not improve, 29 → true. Idea: Handle intersecting conditions first, scan runs, aggregate tokens and test divisors only through the square root.

IEnumerable<string> FizzBuzz(int n)
{
    for (long i = 1; i <= n; i++)
        yield return (i % 3, i % 5) switch
        {
            (0, 0) => "FizzBuzz", (0, _) => "Fizz", // (1)
            (_, 0) => "Buzz", _ => i.ToString()
        };
}
string Compress(string text)
{
    var buffer = new StringBuilder();
    for (int i = 0; i < text.Length;)
    {
        int end = i + 1;
        while (end < text.Length && text[end] == text[i]) end++;
        buffer.Append(text[i]).Append(end - i); // (2)
        i = end;
    }
    return buffer.Length < text.Length ? buffer.ToString() : text;
}
Dictionary<string, int> WordCount(string text)
{
    var counts = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
    char[] separators = [' ', '\t', '\r', '\n', '.', ','];
    foreach (string word in text.Split(separators, StringSplitOptions.RemoveEmptyEntries))
        counts[word] = counts.GetValueOrDefault(word) + 1;
    return counts;
}
bool IsPrime(int value)
{
    if (value < 2) return false;
    for (int divisor = 2; (long)divisor * divisor <= value; divisor++) // (3)
        if (value % divisor == 0) return false;
    return true;
}

Complexity: FizzBuzz uses O(n) iterator steps and O(1) iterator state excluding produced strings; total digit output depends on number length. Compression is O(n) time and space. WordCount is expected O(L) time and O(L) space with Split, for text length L. Prime testing is O(√value) time and O(1) space. Test 0, 1, 2 and squares such as 49; this tokenizer is not full linguistic analysis.

#14. Reverse a list, detect cycles and find the middle

Problems: Reverse a singly linked list, detect a cycle and return its middle. For even length return the second middle. 1 → 2 → 3 reverses to 3 → 2 → 1. Reverse and Middle require an acyclic list. Idea: Save next before rewiring, or use slow/fast pointers.

public sealed class ListNode(int value, ListNode? next = null)
{
    public int Value = value;
    public ListNode? Next = next;
}
ListNode? ReverseList(ListNode? head)
{
    ListNode? previous = null;
    while (head is not null)
    {
        var next = head.Next; // (1)
        head.Next = previous;
        previous = head;
        head = next;
    }
    return previous;
}
bool HasCycle(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
        if (ReferenceEquals(slow, fast)) return true; // (2)
    }
    return false;
}
ListNode? Middle(ListNode? head)
{
    ListNode? slow = head, fast = head;
    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }
    return slow; // (3)
}

Complexity: All three take O(n) time and O(1) space; for cycle detection n counts distinct reachable nodes. Recursive reversal requires O(n) stack. Test self-cycles, singletons and odd/even lengths.

#15. Merge two sorted lists

Problem: Merge two ascending lists; [1,3] and [2,4] → [1,2,3,4]. Inputs are acyclic and share no nodes. Idea: Repeatedly select the smaller head, using a dummy node to avoid a first-node special case.

// Uses ListNode from problem 14; reuses and rewires input nodes.
ListNode? MergeTwoLists(ListNode? first, ListNode? second)
{
    var dummy = new ListNode(0);
    var tail = dummy;
    while (first is not null && second is not null)
    {
        if (first.Value <= second.Value)
        {
            tail.Next = first; first = first.Next; // (1)
        }
        else { tail.Next = second; second = second.Next; }
        tail = tail.Next;
    }
    tail.Next = first ?? second; // (2)
    return dummy.Next;
}

Complexity: O(n + m) time and O(1) auxiliary space; input links are mutated. Preserving immutable inputs requires new nodes and O(n + m) output space. Test two null lists, one empty list and equal values.

#16. An LRU cache

Problem: Implement a positive-capacity cache with expected O(1) get and put, evicting the least recently used item. Idea: A dictionary finds nodes and a doubly linked list tracks recency. At capacity two, put A, put B, get A, put C evicts B.

public sealed class LruCache<TKey, TValue> where TKey : notnull
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Value)>> _map =
        new();
    private readonly LinkedList<(TKey Key, TValue Value)> _order = new();
    public LruCache(int capacity)
    {
        ArgumentOutOfRangeException.ThrowIfNegativeOrZero(capacity);
        _capacity = capacity;
    }
    public bool TryGet(TKey key, out TValue value)
    {
        if (!_map.TryGetValue(key, out var node))
        {
            value = default!;
            return false;
        }
        _order.Remove(node);
        _order.AddFirst(node); // (1)
        value = node.Value.Value;
        return true;
    }
    public void Put(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var existing))
        {
            existing.Value = (key, value);
            _order.Remove(existing);
            _order.AddFirst(existing);
            return;
        }
        if (_map.Count == _capacity)
        {
            var oldest = _order.Last!;
            _map.Remove(oldest.Value.Key);
            _order.RemoveLast(); // (2)
        }
        _map[key] = _order.AddFirst((key, value));
    }
}

Complexity: Expected O(1) per operation and O(capacity) space with constant-cost key hashing. This is not thread-safe; protect both structures with one locking policy when shared. It has no TTL or byte-based sizing. Use a cache library for application requirements without assuming exact LRU. Test updates, capacity one, misses and invalid capacity.

#17. Queue using two stacks and a Min Stack

Problems: Build FIFO behavior using stacks and a stack exposing the current minimum in O(1). Idea: Reverse incoming into outgoing only when outgoing is empty; store the minimum-so-far with each MinStack entry. Pushing 3, 1, 2 gives minimum 1, including after popping 2.

public sealed class StackQueue<T>
{
    private readonly Stack<T> _incoming = new(), _outgoing = new();
    public void Enqueue(T value) => _incoming.Push(value);
    public T Dequeue()
    {
        if (_outgoing.Count == 0)
            while (_incoming.Count > 0) _outgoing.Push(_incoming.Pop()); // (1)
        return _outgoing.Pop();
    }
}
public sealed class MinStack
{
    private readonly Stack<(int Value, int Minimum)> _entries = new();
    public void Push(int value) => _entries.Push((value,
        _entries.Count == 0 ? value : Math.Min(value, _entries.Peek().Minimum))); // (2)
    public int Pop() => _entries.Pop().Value;
    public int GetMin() => _entries.Peek().Minimum;
}

Complexity: Queue operations are O(1) amortized, but one dequeue may take O(n). MinStack push is O(1) amortized for backing storage; pop and GetMin are O(1). Both use O(n) space and are not thread-safe. Empty removal or minimum access throws InvalidOperationException; offer Try APIs if required.

#18. Kth largest and merging K sorted sequences

Problems: Find the kth largest element counting duplicates, and merge k sorted arrays. [3,2,1,5,6,4], k=2 → 5. Idea: Retain a size-k heap of large values, or keep the next candidate from each sequence in a heap.

int KthLargest(int[] values, int k)
{
    if (k < 1 || k > values.Length) throw new ArgumentOutOfRangeException(nameof(k));
    var heap = new PriorityQueue<int, int>();
    foreach (int value in values)
    {
        heap.Enqueue(value, value);
        if (heap.Count > k) heap.Dequeue(); // (1)
    }
    return heap.Peek();
}
IEnumerable<int> MergeKSorted(int[][] sequences)
{
    var heap = new PriorityQueue<(int Row, int Index), int>();
    for (int row = 0; row < sequences.Length; row++)
        if (sequences[row].Length > 0) heap.Enqueue((row, 0), sequences[row][0]);
    while (heap.TryDequeue(out var item, out int value))
    {
        yield return value; // (2)
        int next = item.Index + 1;
        if (next < sequences[item.Row].Length)
            heap.Enqueue((item.Row, next), sequences[item.Row][next]);
    }
}

Complexity: kth takes O(n log(k + 1)) time and O(k) space. Merge takes O(k + N log(k + 1)) time and O(k) auxiliary space, excluding materialized output, for N total items. Quickselect offers expected O(n) kth selection but usually mutates input and can degrade to O(n²). Test empty sequences, duplicates and invalid k.

#19. Depth, inversion, level order and BST validation

Problems: Find maximum depth, swap left and right recursively, return levels, and validate a strict BST without duplicates. Input must be an acyclic tree without shared child nodes. Idea: Recurse over subtrees, use a queue for levels, and propagate ancestor bounds. Root 2 with children 1 and 3 has depth 2 and levels [[2],[1,3]].

public sealed class TreeNode(int value)
{
    public int Value = value;
    public TreeNode? Left, Right;
}
int MaxDepth(TreeNode? node) => node is null ? 0
    : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right));
TreeNode? Invert(TreeNode? node)
{
    if (node is null) return null;
    (node.Left, node.Right) = (Invert(node.Right), Invert(node.Left)); // (1)
    return node;
}
List<List<int>> LevelOrder(TreeNode? root)
{
    var result = new List<List<int>>();
    if (root is null) return result;
    var queue = new Queue<TreeNode>([root]);
    while (queue.Count > 0)
    {
        var level = new List<int>();
        for (int remaining = queue.Count; remaining > 0; remaining--) // (2)
        {
            var node = queue.Dequeue();
            level.Add(node.Value);
            if (node.Left is not null) queue.Enqueue(node.Left);
            if (node.Right is not null) queue.Enqueue(node.Right);
        }
        result.Add(level);
    }
    return result;
}
bool IsValidBst(TreeNode? node, long minimum = long.MinValue,
    long maximum = long.MaxValue) => node is null
    || (node.Value > minimum && node.Value < maximum // (3)
        && IsValidBst(node.Left, minimum, node.Value)
        && IsValidBst(node.Right, node.Value, maximum));

Complexity: Each operation takes O(n) time. Recursion uses O(h) stack; level order uses an O(w) queue excluding O(n) output, for maximum width w. Test null, skewed trees and descendants violating a distant ancestor. Use iterative traversal for excessive depth.

#20. Number of islands

Problem: Count horizontally or vertically connected '1' groups in a rectangular '0'/'1' grid; diagonals do not connect. ["110","010","001"] → 2. Idea: Each unvisited land cell starts an island; flood-fill it with BFS to avoid deep recursion.

int NumberOfIslands(char[][] grid)
{
    if (grid.Length == 0) return 0;
    int rows = grid.Length, columns = grid[0].Length, islands = 0;
    (int Dr, int Dc)[] directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];
    var queue = new Queue<(int Row, int Column)>();
    for (int row = 0; row < rows; row++)
        for (int column = 0; column < columns; column++)
        {
            if (grid[row][column] != '1') continue;
            islands++;
            grid[row][column] = '0';
            queue.Enqueue((row, column)); // (1)
            while (queue.TryDequeue(out var cell))
                foreach (var (dr, dc) in directions)
                {
                    int r = cell.Row + dr, c = cell.Column + dc;
                    if (r < 0 || c < 0 || r >= rows || c >= columns) continue;
                    if (grid[r][c] != '1') continue;
                    grid[r][c] = '0'; // (2)
                    queue.Enqueue((r, c));
                }
        }
    return islands;
}

Complexity: O(RC) time and O(RC) worst-case queue space. The grid is mutated; use an O(RC) visited structure if mutation is forbidden. Test empty grids, empty rows, all water and all land. Jagged rows require validation or a different contract.

#21. Climbing stairs and House Robber

Problems: Count ways to climb n stairs using steps of one or two, and maximize a sum of non-adjacent non-negative values. The latter is known as House Robber and can model selecting non-adjacent booking slots. n=3 → 3; [2,7,9,3,1] → 12. Idea: Each state depends on the previous two.

long ClimbStairs(int n)
{
    if (n < 0 || n > 91) throw new ArgumentOutOfRangeException(nameof(n));
    long previous = 1, current = 1; // ways(0), ways(1)
    for (int i = 2; i <= n; i++)
        (previous, current) = (current, checked(previous + current)); // (1)
    return current;
}
long MaxNonAdjacent(int[] values)
{
    long previous2 = 0, previous1 = 0;
    foreach (int value in values)
        (previous2, previous1) =
            (previous1, Math.Max(previous1, previous2 + value)); // (2)
    return previous1;
}

Complexity: O(n) time and O(1) space, instead of exponential unmemoized recursion. Test zero/one stairs and empty/singleton arrays. Reconstructing selected positions generally requires O(n) decision or state storage.

#22. Coin change and longest common subsequence

Problems: Find the fewest positive coins forming a non-negative amount, or -1; find the longest common subsequence length, allowing gaps. [1,3,4], 6 → 2; abcde and ace → 3. Idea: Define states, base cases and recurrence before writing loops.

int CoinChange(int[] coins, int amount)
{
    ArgumentOutOfRangeException.ThrowIfNegative(amount);
    if (coins.Any(coin => coin <= 0)) throw new ArgumentException("Positive coins only");
    var best = new int[checked(amount + 1)];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int value = 1; value <= amount; value++)
        foreach (int coin in coins)
            if (coin <= value && best[value - coin] != int.MaxValue)
                best[value] = Math.Min(best[value], best[value - coin] + 1); // (1)
    return best[amount] == int.MaxValue ? -1 : best[amount];
}
int Lcs(string first, string second)
{
    var length = new int[first.Length + 1, second.Length + 1];
    for (int i = 1; i <= first.Length; i++)
        for (int j = 1; j <= second.Length; j++)
            length[i, j] = first[i - 1] == second[j - 1]
                ? length[i - 1, j - 1] + 1 // (2)
                : Math.Max(length[i - 1, j], length[i, j - 1]);
    return length[first.Length, second.Length];
}

Complexity: Coin change takes O(amount × c) time and O(amount) space; allocation must fit memory, and time is pseudo-polynomial in amount's encoding. LCS takes O(nm) time and space, reducible to O(min(n,m)) space for length alone. Test zero/unreachable amounts and empty strings; greedy is not generally correct for arbitrary coins.

#23. Rate limiting, debounce and retry

Problems: Allow at most N requests per client in a rolling window, process the latest value after a quiet period, and retry a transiently failing read with a bounded policy. Idea: Timestamp queues, cancellation of earlier waits, and bounded backoff with jitter. A limit of two rejects the third request in one window. Debouncing coalesces a burst; it is not rate limiting.

// Also requires System.Collections.Concurrent.
public sealed class SlidingWindowLimiter
{
    private readonly int _limit;
    private readonly TimeSpan _window;
    private readonly TimeProvider _clock;
    private readonly ConcurrentDictionary<string, Queue<long>> _hits = new();
    public SlidingWindowLimiter(int limit, TimeSpan window, TimeProvider clock)
    {
        ArgumentOutOfRangeException.ThrowIfNegativeOrZero(limit);
        if (window <= TimeSpan.Zero) throw new ArgumentOutOfRangeException(nameof(window));
        _limit = limit; _window = window; _clock = clock;
    }
    public bool Allow(string client)
    {
        var hits = _hits.GetOrAdd(client, _ => new Queue<long>());
        lock (hits) // (1)
        {
            long now = _clock.GetTimestamp();
            while (hits.Count > 0 && _clock.GetElapsedTime(hits.Peek(), now) >= _window)
                hits.Dequeue();
            if (hits.Count >= _limit) return false;
            hits.Enqueue(now);
            return true;
        }
    }
}

// Single-caller async stream; inputs yield promptly and honor cancellation.
async Task DebounceAsync<T>(IAsyncEnumerable<T> source, TimeSpan quiet,
    Func<T, CancellationToken, Task> apply, CancellationToken ct)
{
    if (quiet <= TimeSpan.Zero) throw new ArgumentOutOfRangeException(nameof(quiet));
    using var stop = CancellationTokenSource.CreateLinkedTokenSource(ct);
    await using var iterator = source.GetAsyncEnumerator(stop.Token);
    Task<bool>? next = null;
    try
    {
        next = iterator.MoveNextAsync().AsTask();
        while (await next)
        {
            T latest = iterator.Current;
            next = iterator.MoveNextAsync().AsTask();
            while (true)
            {
                using var timer = CancellationTokenSource.CreateLinkedTokenSource(ct);
                Task delay = Task.Delay(quiet, timer.Token);
                Task winner = await Task.WhenAny(next, delay); // (2)
                if (winner == delay)
                {
                    await delay; // observe cancellation before invoking the handler
                    await apply(latest, ct);
                    break;
                }
                if (!await next)
                {
                    await delay; // finish the existing quiet period, without restarting it
                    await apply(latest, ct); // flush final value after quiet period
                    return;
                }
                timer.Cancel();
                latest = iterator.Current;
                next = iterator.MoveNextAsync().AsTask();
            }
        }
    }
    finally
    {
        stop.Cancel();
        if (next is not null)
        {
            try { await next; }
            catch (OperationCanceledException) when (stop.IsCancellationRequested) { }
        }
    }
}

// The delegate must classify failures: true only for safe transient retries.
async Task<T> RetryReadAsync<T>(Func<CancellationToken, Task<T>> read,
    Func<Exception, bool> isTransient, int attempts, CancellationToken ct)
{
    if (attempts < 1 || attempts > 8)
        throw new ArgumentOutOfRangeException(nameof(attempts));
    for (int attempt = 1; ; attempt++)
    {
        ct.ThrowIfCancellationRequested();
        try { return await read(ct); }
        catch (Exception error) when (error is not OperationCanceledException
            && attempt < attempts && isTransient(error)) // (3)
        {
            int milliseconds = 100 * (1 << (attempt - 1)) + Random.Shared.Next(100);
            await Task.Delay(milliseconds, ct);
        }
    }
}

Complexity: The limiter is expected amortized O(1) per call and O(C × limit) memory; one call can expire O(limit) timestamps. It does not remove inactive clients, so unbounded client IDs require coordinated cleanup that prevents parallel queues for one key. Debounce uses O(n) scheduling and O(1) extra state excluding source/handler buffers. Retry costs O(attempts × read cost), plus delays, with O(1) state.

These are exercises, not complete operational libraries: the limiter is local, and a Redis fixed-window counter is not equivalent to an exact rolling window. Consider ASP.NET Core rate limiting, a debounce library or pipeline with explicit lifecycle, and Microsoft.Extensions.Http.Resilience for HTTP with an idempotency-aware policy. Test time boundaries, cancellation, transient-then-success and permanent failure.

#24. Allocate a discount without losing cents

Problem: Allocate an invoice discount proportionally while preserving its exact total. Every amount in this example is in cents: [100,200,300], 100 → [17,33,50]. Idea: Use largest remainders in minor currency units instead of pushing all rounding error into one line, which can create negative shares. Inputs are non-negative integer cents, totals fit long, and discount does not exceed the invoice total.

// Requires System.Numerics for exact integer products.
long[] AllocateCents(long[] lines, long discount)
{
    if (discount < 0 || lines.Any(value => value < 0))
        throw new ArgumentException("Non-negative amounts required");
    long total = 0;
    foreach (long value in lines) total = checked(total + value);
    if (discount > total) throw new ArgumentException("Discount exceeds total");
    var shares = new long[lines.Length];
    if (total == 0) return shares;
    var remainders = new System.Numerics.BigInteger[lines.Length];
    long allocated = 0;
    for (int i = 0; i < lines.Length; i++)
    {
        var product = (System.Numerics.BigInteger)discount * lines[i];
        shares[i] = (long)System.Numerics.BigInteger.DivRem(
            product, total, out remainders[i]); // (1)
        allocated += shares[i];
    }
    int[] order = Enumerable.Range(0, lines.Length)
        .OrderByDescending(i => remainders[i]).ThenBy(i => i).ToArray();
    long remaining = discount - allocated;
    for (int i = 0; i < remaining; i++) shares[order[i]]++; // (2)
    return shares;
}

Complexity: O(n log n) time and O(n) space; products here are bounded by two long inputs. Use validated decimal conversion at monetary input/display boundaries. Cents assume a two-decimal currency, not every currency. Test zero totals, full discounts and many tiny lines; verify exact sum and each share between zero and its line value. Allocation policy is a documented business decision.

#25. Group orders and duplicate keys in a large file

Problems: Find the top three customers by paid-order revenue during the last 30 days through now, and detect duplicate SKUs in a file larger than RAM. Idea: Filter, group, aggregate and sort; or stream keys with a set. Two paid orders of 10 and 20 for one customer total 30. The file contract is one key per line, not general CSV.

public record Order(int CustomerId, DateTimeOffset CreatedAt,
    string Status, decimal Total);
public record CustomerRevenue(int CustomerId, decimal Revenue);
List<CustomerRevenue> TopCustomers(IEnumerable<Order> orders, DateTimeOffset now) =>
    orders.Where(order => order.Status == "Paid"
        && order.CreatedAt >= now.AddDays(-30) && order.CreatedAt <= now)
    .GroupBy(order => order.CustomerId)
    .Select(group => new CustomerRevenue(group.Key, group.Sum(order => order.Total)))
    .OrderByDescending(customer => customer.Revenue)
    .ThenBy(customer => customer.CustomerId).Take(3).ToList(); // (1)

async IAsyncEnumerable<string> DuplicateSkus(string path,
    [System.Runtime.CompilerServices.EnumeratorCancellation] CancellationToken ct = default)
{
    var seen = new HashSet<string>(StringComparer.Ordinal);
    using var reader = new StreamReader(path);
    while (await reader.ReadLineAsync(ct) is { } sku)
        if (!seen.Add(sku)) yield return sku; // (2)
}

Complexity: The grouping query takes O(n + u log u) time and O(n + u) space because LINQ GroupBy retains elements. Streaming uses expected O(B) processing for B characters but retains every distinct key: memory grows with total distinct-key characters. If that exceeds memory, use external merge sort or stable hash partitioning with consistent equality, then process partitions; skew may require repartitioning. A Bloom filter alone is not exact. General CSV needs quoted-field and embedded-newline parsing, and line-length limits must be defined.

#26. Rotate a matrix

Problem: Rotate an n×n matrix ninety degrees clockwise in place; [[1,2],[3,4]] → [[3,1],[4,2]]. Idea: Transpose, then reverse each row. A non-square matrix changes dimensions and needs a different contract or allocation.

void RotateMatrix(int[][] matrix)
{
    int n = matrix.Length;
    if (matrix.Any(row => row.Length != n))
        throw new ArgumentException("Square matrix required");
    for (int row = 0; row < n; row++)
        for (int column = row + 1; column < n; column++)
            (matrix[row][column], matrix[column][row]) =
                (matrix[column][row], matrix[row][column]); // (1)
    foreach (var row in matrix) Array.Reverse(row); // (2)
}

Complexity: O(n²) time and O(1) extra space. Input is mutated and rows must be distinct arrays rather than aliased references. Test 0×0, 1×1 and 3×3; counterclockwise rotation uses a different reversal arrangement.

#27. Subarray sum equals K

Problem: Count nonempty contiguous subarrays summing to k, allowing negatives and zeros. [1,1,1], 2 → 2; [0,0], 0 → 3. Idea: Since currentPrefix - previousPrefix = k, every earlier occurrence of currentPrefix-k supplies a valid start.

long SubarraySum(int[] values, long k)
{
    var frequency = new Dictionary<long, long> { [0] = 1 }; // (1)
    long prefix = 0, count = 0;
    foreach (int value in values)
    {
        prefix += value;
        // (2) A difference outside long cannot be a stored prefix.
        bool safe = k >= 0 ? prefix >= long.MinValue + k
            : prefix <= long.MaxValue + k;
        if (safe) count += frequency.GetValueOrDefault(prefix - k);
        frequency[prefix] = frequency.GetValueOrDefault(prefix) + 1; // (3)
    }
    return count;
}

Complexity: Expected O(n) time and O(n) space, versus O(n²) for every start and end. A long count accommodates subarray counts for int-length arrays. The usual sum-based sliding window fails with negatives. Test empty input, negative k, zeros and repeated prefixes.

#28. Course schedule

Problem: Courses are numbered 0 through n-1; each pair [course, prerequisite] requires the second before the first. Can all courses finish? n=2, [[1,0]] → true; adding [0,1] creates a cycle and returns false. Idea: Apply Kahn's topological sort to the directed graph.

bool CanFinish(int n, int[][] prerequisites)
{
    ArgumentOutOfRangeException.ThrowIfNegative(n);
    var graph = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
    var degree = new int[n];
    foreach (var pair in prerequisites)
    {
        int course = pair[0], prerequisite = pair[1];
        graph[prerequisite].Add(course); // (1)
        degree[course]++;
    }
    var ready = new Queue<int>();
    for (int course = 0; course < n; course++)
        if (degree[course] == 0) ready.Enqueue(course);
    int completed = 0;
    while (ready.TryDequeue(out int course))
    {
        completed++;
        foreach (int dependent in graph[course])
            if (--degree[dependent] == 0) ready.Enqueue(dependent); // (2)
    }
    return completed == n; // (3)
}

Complexity: O(V + E) time and space including the graph. With no edges, n=0 returns true. Test self-loops, disconnected courses and duplicate pairs. Store processed vertices if the order itself is requested; valid orders may differ.