Skip to content
Interview prep

Algorithms and live coding

How to estimate the complexity of code, which data structures and algorithms to keep in your head, and how to solve a problem in front of an interviewer. Live coding doesn’t test whether you memorised algorithms; it tests whether you can reason out loud, pick the right technique and honestly assess your own solution.

Before this topic: Collections and LINQ.

Junior+

What is Big O notation and how do you estimate the complexity of code?

Section titled “What is Big O notation and how do you estimate the complexity of code?”
Answer

What it is

O(f(n)) shows the shape of growth, not seconds: how many times more work there is when the input grows. Make n 10 times bigger and O(n) runs 10 times longer, while O(n²) runs 100 times longer.

Common classes

Complexity Name Example
O(1) constant array element by index
O(log n) logarithmic binary search
O(n) linear one pass over an array
O(n log n) linearithmic sorting with Array.Sort
O(n²) quadratic all pairs of elements
O(2^n) exponential enumerating all subsets

How to estimate

  1. A loop over n items — n × the cost of the body.
  2. Nested loops multiply: two loops over n — O(n²).
  3. Sequential blocks add up, and the dominant one wins: O(n) + O(n²) = O(n²).
  4. Constants are dropped: two passes — O(2n) = O(n).
  5. The range is halved at each step — O(log n).

Common mistake

Assuming code without nested loops is linear. list.Insert(0, x) or s += x in a loop cost O(n) each, so the whole loop is O(n²).

Takeaway: Big O shows how work grows with the input, not how many milliseconds it takes.

How it works

Time and space are estimated separately. Space means extra memory, not counting the input: a pass with a HashSet<T> costs O(n) space, a double loop costs O(1).

Case Meaning Example
Worst a bound for any input quicksort with bad pivots — O(n²)
Average expectation on a typical input hash table lookup — O(1)
Amortized average over a series of operations List<T>.Add — O(1)

Amortized analysis is not about probability. It is a guarantee for any series: the rare expensive operations are paid for by many cheap ones.

Pitfalls

  • Hidden cost of a call. string += copies the string, List<T>.Remove shifts elements — each call is O(n).
  • Two parameters. A loop over n orders with a nested loop over m items is O(n·m), not O(n²).
  • Recursion uses memory. A depth of d takes O(d) stack space, even without any collections.
  • Repeated enumeration. Count() on a lazy IEnumerable<T> inside a loop walks the sequence again every time.

Rule of thumb

For every solution, give two estimates — time and space — and say which case you mean.

Takeaway: complexity is a pair of time and space plus the case: worst, average or amortized.

Under the hood

  • O is an upper bound, Ω a lower bound, Θ a tight bound. Comparison sorting cannot beat Ω(n log n) in the worst case.
  • Recursion is analysed with a recurrence. Binary search: T(n) = T(n/2) + O(1), which is O(log n). Mergesort: T(n) = 2T(n/2) + O(n), which is O(n log n).
  • Naive recursive Fibonacci makes an exponential number of calls: every branch splits in two.

Cost

  • Big O hides constants: allocations, CPU cache misses, delegate calls.
  • For small n, constants decide. That’s why Array.Sort sorts partitions of up to 16 elements with insertion sort, even though it’s O(n²).

Trade-offs

  • Time versus memory. A HashSet<T> turns O(n²) into O(n) at the price of O(n) memory. Precomputation — an index, prefix sums — moves work into preparation.
  • Worst case on untrusted input. An attacker crafts input that hits the worst case: hash collisions, catastrophic regex backtracking. For regular expressions, .NET 7+ has RegexOptions.NonBacktracking, which runs in time linear in the input length.

How to check in production

BenchmarkDotNet with [Params] over several values of n shows the growth curve: time grows 4× when n doubles — the algorithm is quadratic. The hot method shows up in a dotnet-trace or PerfView trace.

Takeaway: asymptotics rules out bad solutions, while constants, memory and measurements decide between good ones.

Example
int[] data = [3, 8, 1, 9, 4, 8];


Console.WriteLine(HasDuplicatesPairs(data));  // True
Console.WriteLine(HasDuplicatesHashSet(data)); // True
Console.WriteLine(HasDuplicatesSorted(data));  // True


// All pairs: O(n²) time, O(1) space
static bool HasDuplicatesPairs(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++) // n(n-1)/2 comparisons
            if (a[i] == a[j]) return true;
    return false;
}


// One pass: O(n) average time, O(n) space
static bool HasDuplicatesHashSet(int[] a)
{
    var seen = new HashSet<int>();
    foreach (int x in a)
        if (!seen.Add(x)) return true; // Add returns false for a repeat
    return false;
}


// Sort a copy and compare neighbours: O(n log n) time, O(n) space for the copy
static bool HasDuplicatesSorted(int[] a)
{
    int[] copy = [.. a];
    Array.Sort(copy);
    for (int i = 1; i < copy.Length; i++)
        if (copy[i] == copy[i - 1]) return true;
    return false;
}

Three solutions to one problem — three different time/space trade-offs. Sorting in place would make space O(1), but it would mutate the caller’s array.

Sources
Junior+

Which data structures should you know and what is each one for?

Section titled “Which data structures should you know and what is each one for?”
Answer

What it is

  • Stack — LIFO: last in, first out. Queue — FIFO: first in, first out.
  • A search tree keeps keys in order, a heap always knows the smallest element.
  • A graph is vertices and edges: roads, dependencies, connections between people.

How to use

Structure .NET type Typical task
Array T[], List<T> data by index
Stack Stack<T> brackets, undo, depth-first traversal
Queue Queue<T> jobs in order, breadth-first traversal
Hash table Dictionary, HashSet<T> lookup, counting, duplicates
Search tree SortedSet<T>, SortedDictionary order, minimum, ranges
Heap PriorityQueue<TElement, TPriority> jobs by priority, top-k

Common mistake

Writing your own structure in an interview when a ready-made one exists. Unless asked otherwise, the interviewer usually expects Stack<T> or PriorityQueue, not a hand-rolled class.

Takeaway: pick the structure by the operation that has to be fast.

How it works

Structure Lookup Insert and delete
Array, List<T> by index O(1), by value O(n) at the end O(1) amortized, in the middle O(n)
LinkedList<T> O(n) O(1) at a known node
Stack<T>, Queue<T> top or head only, O(1) O(1) amortized
Dictionary, HashSet<T> O(1) on average O(1) on average
SortedSet<T>, SortedDictionary O(log n) O(log n)
PriorityQueue minimum O(1) O(log n)

Trees and heaps

  • Search tree. A lookup walks down from the root: smaller goes left, larger goes right. The cost equals the height of the tree. Without balancing, sorted input stretches the tree into a list and gives O(n), so .NET uses a balanced red-black tree.
  • Heap. A tree stored in an array where a parent is never larger than its children, so the minimum sits at the root. Insertion sifts an element up, extraction sifts the new root down — O(log n).

Pitfalls

  • PriorityQueue doesn’t keep insertion order for equal priorities, and UnorderedItems doesn’t enumerate by priority.
  • Stack<T> enumerates from the top, not in insertion order.
  • How Dictionary works and what hashing costs is covered in Collections and LINQ.

Rule of thumb

Name the dominant operation of the task, and the structure follows from it: lookup by key — hash table, order — tree, minimum — heap, processing order — stack or queue.

Takeaway: every structure speeds up some operations at the expense of others, and choosing one answers the question “what do we do most often”.

Under the hood

  • PriorityQueue<TElement, TPriority> is an array-backed quaternary (4-ary) min-heap: the tree is shallower than a binary one, and a node’s children sit next to each other in memory.
  • There’s no “update priority” operation. Remove, added in .NET 9, scans linearly — O(n).
  • A graph is stored as an adjacency list, Dictionary<int, List<int>>: O(V + E) memory. An adjacency matrix bool[,] checks an edge in O(1) but takes O(V²) — it’s for dense graphs.

Cost

  • Node-based structures (LinkedList<T>, SortedSet<T>) create an object per element: an allocation, an object header, references, scattering across the heap.
  • Array-based structures (List<T>, Queue<T>, PriorityQueue) store elements contiguously and are friendlier to the CPU cache.

Trade-offs

Task Option Cost
top-k out of n PriorityQueue of size k O(n log k) instead of O(n log n)
Dijkstra PriorityQueue with duplicates extra entries, skipping stale ones
Dijkstra with removal SortedSet of (distance, vertex) pairs O(log n) removal, but nodes
Rare inserts into ordered data sorted List<T> plus BinarySearch O(n) insert, but contiguous memory

How to check in production

The number of node objects shows up in dotnet-gcdump. When choosing between two structures, confirm it with BenchmarkDotNet and [MemoryDiagnoser] on realistic data volumes.

Takeaway: asymptotics drives the choice of structure, while memory layout and missing operations decide how it behaves in production.

Example
// Heap: the lowest priority comes out first
var tasks = new PriorityQueue<string, int>();
tasks.Enqueue("deploy", 2);
tasks.Enqueue("hotfix", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine(tasks.Dequeue()); // hotfix — O(log n)


// Search tree: order, minimum and ranges
var prices = new SortedSet<int> { 50, 10, 40, 20, 30 };
Console.WriteLine(prices.Min);                                      // 10
Console.WriteLine(string.Join(",", prices.GetViewBetween(15, 40))); // 20,30,40


// Stack: bracket matching — a classic task
Console.WriteLine(IsBalanced("([]{})")); // True
Console.WriteLine(IsBalanced("(]"));     // False


static bool IsBalanced(string s)
{
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else if (stack.Count == 0 || stack.Pop() != Opening(c)) return false;
    }
    return stack.Count == 0; // unclosed brackets are an error too
}


static char Opening(char close) => close switch { ')' => '(', ']' => '[', _ => '{' };
Sources
Middle+

Which sorting and searching algorithms should you know?

Section titled “Which sorting and searching algorithms should you know?”
Answer

What it is

  • Linear search checks elements one by one: O(n), works on any array.
  • Binary search needs a sorted array and halves the range: O(log n). A million elements take at most 20 steps.

How binary search works

  1. Bounds: lo = 0, hi = n - 1.
  2. Middle: mid = lo + (hi - lo) / 2.
  3. a[mid] == target — found.
  4. a[mid] < target — search to the right: lo = mid + 1. Otherwise to the left: hi = mid - 1.
  5. Repeat while lo <= hi. When the bounds cross, the element isn’t there.

How to use

  • Sorting: Array.Sort(array), list.Sort(), items.OrderBy(x => x.Name).
  • Searching: Array.BinarySearch and List<T>.BinarySearch. If the element is missing, they return a negative number, and ~result is the index where it should be inserted.

Common mistake

Running binary search on an unsorted array. There’s no exception — just a wrong answer.

Takeaway: binary search is O(log n), but only on sorted data; take sorting from the library.

How it works

Algorithm Time Memory and stability
Insertion O(n²), close to O(n) on nearly sorted data O(1), stable
Quicksort O(n log n) average, O(n²) worst O(log n) stack, unstable
Merge O(n log n) always O(n), stable
Heap O(n log n) always O(1), unstable

A stable sort preserves the original order of equal elements. It matters when the data is already ordered by another field.

What .NET uses

Method Algorithm Stable
Array.Sort, List<T>.Sort, Span<T>.Sort() introsort, in place no
OrderBy, ThenBy (LINQ) sort in a buffer yes

Pitfalls

  • Search bounds. Mixing lo < hi with hi = mid - 1, or lo <= hi with hi = mid, skips an element or loops forever.
  • Duplicates. Array.BinarySearch returns the index of one of the equal elements, not necessarily the first. For the first occurrence you need the “lower bound” variant.
  • An a - b comparer. It overflows on large numbers. Use a.CompareTo(b).

Rule of thumb

Don’t write your own sort in production code. Need stability — use OrderBy or a comparer with a tie-breaker. Test binary search on an empty array, a single element and elements at both ends.

Takeaway: Array.Sort is fast and unstable, OrderBy is stable and costs more memory, and binary search breaks at the boundaries.

Under the hood

Introsort in Array.Sort, per the documentation:

  1. A partition of up to 16 elements — insertion sort.
  2. The number of partitions exceeds 2·log n — heapsort.
  3. Otherwise — quicksort.

This protects quicksort from its O(n²) worst case. .NET Framework 4 and earlier used plain quicksort.

Cost

  • Array.Sort on primitives without a comparer doesn’t invoke a delegate per comparison. With a Comparison<T>, every comparison is an indirect call.
  • OrderBy copies elements into a buffer, computes an array of keys and sorts indexes — O(n) extra memory.
  • The Ω(n log n) lower bound applies only to comparison sorts. Counting sort or radix sort handle integers from a small range in O(n + k).

Trade-offs

  • Full or partial sort. If you need the k smallest, a heap at O(n log k) beats sorting at O(n log n).
  • Sort or hash. A one-off search in unsorted data is a linear scan. Many searches — sort plus binary search, or a HashSet<T>.
  • Data doesn’t fit in memory. External merge sort: sort chunks, then merge them. That’s also how a database sorts when it runs out of memory.

How to check in production

BenchmarkDotNet with [MemoryDiagnoser] on real data compares Array.Sort and OrderBy: the difference in allocations is visible immediately.

Takeaway: introsort gives O(n log n) in the worst case without a buffer at the cost of stability, and picking a sort method is picking between stability and memory.

Example
int[] sorted = [1, 3, 5, 7, 9, 11];


Console.WriteLine(BinarySearch(sorted, 7));       // 3
Console.WriteLine(BinarySearch(sorted, 4));       // -1
Console.WriteLine(BinarySearch([], 4));           // -1 — empty array
Console.WriteLine(Array.BinarySearch(sorted, 4)); // -3: ~(-3) = 2 — where 4 should go


static int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;     // search in [lo, hi] inclusive
    while (lo <= hi)                   // <=, otherwise we skip the last candidate
    {
        int mid = lo + (hi - lo) / 2;  // not (lo + hi) / 2: int overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; // mid is already checked
        else hi = mid - 1;
    }
    return -1;
}
Sort stability
Order[] orders = [new(1, "B"), new(2, "A"), new(3, "B"), new(4, "A")];


// OrderBy is stable: equal Customer values keep their original order
var byCustomer = orders.OrderBy(o => o.Customer).Select(o => o.Id);
Console.WriteLine(string.Join(" ", byCustomer)); // 2 4 1 3


// Array.Sort is unstable: add a second key to guarantee the order
var copy = orders.ToArray();
Array.Sort(copy, (x, y) =>
{
    int byName = string.CompareOrdinal(x.Customer, y.Customer);
    return byName != 0 ? byName : x.Id.CompareTo(y.Id);
});
Console.WriteLine(string.Join(" ", copy.Select(o => o.Id))); // 2 4 1 3


record Order(int Id, string Customer);

With four elements Array.Sort uses insertion sort and happens to keep the order, but on large arrays there’s no guarantee — hence the second key.

Sources
Middle+

Recursion and dynamic programming: how do you recognise and solve the problem?

Section titled “Recursion and dynamic programming: how do you recognise and solve the problem?”
Answer

What it is

A recursive function has two parts:

  1. Base case — an answer without recursion: Fib(0) = 0, Fib(1) = 1.
  2. Recursive step — reduction to a smaller problem: Fib(n) = Fib(n - 1) + Fib(n - 2).

Why dynamic programming

Naive Fib(n) computes the same thing many times: Fib(5) calls Fib(3) twice and Fib(2) three times. The number of calls grows exponentially, and Fib(50) takes tens of billions of calls.

How to use

Store each subproblem’s answer in a dictionary or an array, and check for it before computing. Then Fib(50) is 50 computations.

Common mistake

Forgetting the base case or writing a step that doesn’t shrink the problem. The recursion becomes infinite, and StackOverflowException kills the process — try/catch won’t catch it.

Takeaway: recursion is a base case plus a step towards it, and DP is recursion that never computes the same thing twice.

How it works

Every call pushes a frame with arguments and local variables onto the stack. Depth d means O(d) memory, and stack size is limited: per the .NET docs, the default is 1.5 MB on Windows and macOS and 8 MB on Linux.

How to solve a DP problem

  1. State. What dp[s] means: for example, the minimum number of coins for sum s.
  2. Transition. dp[s] = min(dp[s - c] + 1) over all coins c.
  3. Base. dp[0] = 0.
  4. Order and answer. Sums from 0 to amount; the answer is dp[amount].
  5. Complexity. States × transition: O(amount · k) for k coins.

When to choose what

Approach Pro Con
Memoization (top-down) code mirrors the formula, computes only needed states recursion depth, dictionary overhead
Tabulation (bottom-up) no recursion, easy to compress memory you must know the fill order

Classics

  • Fibonacci — O(n) time, O(1) memory with tabulation.
  • Coin change — O(amount · k).
  • Longest common subsequence (LCS) of two strings of lengths n and m: if the characters match, dp[i, j] = dp[i - 1, j - 1] + 1, otherwise max(dp[i - 1, j], dp[i, j - 1]). O(n·m).

Pitfalls

Greedy isn’t always optimal. Coins 1, 3 and 4, sum 6: greedy gives 4 + 1 + 1 — three coins, while the optimum is 3 + 3 — two.

Takeaway: a DP problem is solved by defining the state, the transition and the base, and memoization and tabulation are two ways to walk the same states.

Under the hood

  • A stack frame holds arguments, local variables and the return address. StackOverflowException can’t be caught: the process terminates.
  • RuntimeHelpers.EnsureSufficientExecutionStack() throws an ordinary InsufficientExecutionStackException when stack space is running low. That’s how recursive expression tree visitors and parsers protect themselves.
  • The C# compiler doesn’t mark tail calls. The JIT sometimes optimizes them on its own, but you can’t rely on it.

Cost

  • Memoization with a dictionary means hashing and allocations. If the state is a small integer, an array is faster.
  • The LCS table takes O(n·m) memory. If you only need the length, two rows are enough: O(min(n, m)).

Trade-offs

  • Recursion versus an explicit stack. Recursion reads better for trees and depth-first traversal. If depth depends on the input — nested JSON, a long chain of references — use a Stack<T> and a loop.
  • Memoization versus tabulation. Memoization is easier to write in an interview straight from a recursive formula. Tabulation is safer and lets you compress memory.

How to check in production

A stack overflow kills the process without anything in the usual log. The runtime prints Stack overflow. and the repeated frames to stderr, and a crash dump (DOTNET_DbgEnableMiniDump=1) can be opened in dotnet-dump to inspect the stack.

Takeaway: DP is states and transitions, and in .NET recursion over untrusted data is replaced with a loop because a stack overflow can’t be caught.

Fibonacci: memoization and tabulation
Console.WriteLine(FibMemo(50, new Dictionary<int, long>())); // 12586269025
Console.WriteLine(FibTable(50));                             // 12586269025


// Top-down: recursion plus a cache, O(n) time and O(n) memory
static long FibMemo(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;                               // base case
    if (memo.TryGetValue(n, out long cached)) return cached;
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}


// Bottom-up: no recursion, O(n) time and O(1) memory
static long FibTable(int n)
{
    long prev = 0, cur = 1;
    for (int i = 0; i < n; i++)
        (prev, cur) = (cur, prev + cur);
    return prev;
}
Coin change
Console.WriteLine(MinCoins([1, 5, 10, 25], 63)); // 6: 25 + 25 + 10 + 1 + 1 + 1
Console.WriteLine(MinCoins([1, 3, 4], 6));       // 2: 3 + 3, greedy would use 3 coins
Console.WriteLine(MinCoins([2], 3));             // -1: impossible


// dp[s] is the minimum number of coins for sum s; O(amount · k) time, O(amount) memory
static int MinCoins(int[] coins, int amount)
{
    var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;                                    // base: sum 0 takes zero coins
    for (int s = 1; s <= amount; s++)
        foreach (int c in coins)
            if (c <= s && dp[s - c] != int.MaxValue)
                dp[s] = Math.Min(dp[s], dp[s - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
Sources
Senior+

How do you approach a live coding task and which techniques come up most often?

Section titled “How do you approach a live coding task and which techniques come up most often?”
Answer

What it is

Live coding means solving a problem in front of the interviewer in an editor or on a whiteboard. They assess your reasoning, your code and how you test it.

How to use

  1. Clarify the problem. Input size, negative numbers, duplicates, empty input, what to return when there’s no answer.
  2. Work through an example by hand. It proves you understood the task.
  3. Name the brute-force solution and its complexity, even if it’s slow.
  4. Improve it. Find the repeated work and remove it.
  5. Write the code with clear names.
  6. Test out loud: the example, empty input, one element, duplicates.

Common mistake

Silently writing code right after reading the problem. If the solution hits a dead end, the interviewer has no way to help you and nothing to assess.

Takeaway: in live coding the solution is a process out loud: problem, example, simple solution, improvement, testing.

When to choose what

Signal in the problem Technique Complexity
Pair, duplicate, frequencies hash table O(n), O(n) memory
Sorted array, pair, palindrome two pointers O(n), O(1) memory
Longest or shortest subarray sliding window O(n)
Many range-sum queries prefix sums O(n) setup, O(1) per query
Unweighted shortest path, grid BFS O(V + E)
Connectivity, all paths, search DFS O(V + E)
Order with dependencies topological sort O(V + E)
k largest PriorityQueue of size k O(n log k)

Walkthrough: two sum

Find the indexes of two numbers that add up to target. Brute force — all pairs, O(n²). Speed-up: for each x, look up target - x among the numbers already seen in a Dictionary. Total: O(n) time and O(n) memory.

Walkthrough: longest substring without repeats

The window [left, right] grows to the right. If a character is already in the window, left jumps past its previous position. Each index moves at most once — O(n).

Pitfalls

  • Sum overflow: sum a large int array into a long.
  • BFS and DFS without marking visited vertices loop forever on a graph with a cycle.
  • Modifying a collection during foreach throws InvalidOperationException.

Rule of thumb

Recognise the technique from the signal in the problem first, then write code.

Takeaway: most tasks boil down to about ten techniques, and recognising the technique is half the solution.

How to talk while solving

  • State your assumptions: “I’m assuming the input fits in memory.”
  • Name the complexity of an option before writing code.
  • First a plan in two or three sentences, then the code.
  • Stuck — say what you’re considering and ask about the constraints.
  • After coding, trace the example line by line, like a debugger.

Trade-offs

  • Time versus memory. A hash table gives O(n) with O(n) memory. Sorting plus two pointers is O(n log n) but O(1) extra memory, if you’re allowed to modify the input.
  • Mutating the input. Sorting in place changes the caller’s array — ask whether that’s allowed.
  • Recursion versus an explicit stack. Recursive DFS is shorter, while a Stack<T> survives a deep graph.

Walkthrough: topological sort

Kahn’s algorithm:

  1. Count the in-degree of every vertex.
  2. Put vertices with no incoming edges into a queue.
  3. Dequeue a vertex, add it to the result, decrement the in-degree of its neighbours. When one reaches zero, enqueue it.
  4. If the result doesn’t contain all vertices, the graph has a cycle.

Complexity — O(V + E). This is how build steps, migrations and jobs with dependencies get ordered.

How to check the solution

  • Edge cases: empty input, one element, all elements equal, negative numbers, maximum n.
  • Estimate against the constraints: at n = 10^5, an O(n²) solution is 10^10 operations — seconds instead of milliseconds.

Takeaway: at senior level they assess not only the algorithm but how you drive the solution: assumptions, trade-offs and self-checking.

Hash table and sliding window
Console.WriteLine(string.Join(",", TwoSum([2, 7, 11, 15], 9))); // 0,1
Console.WriteLine(LongestUniqueRun("abcabcbb"));                // 3: "abc"
Console.WriteLine(LongestUniqueRun(""));                        // 0 — edge case


// For each x, look up target - x among the numbers seen: O(n) time, O(n) memory
static int[] TwoSum(int[] nums, int target)
{
    var indexOf = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        if (indexOf.TryGetValue(target - nums[i], out int j)) return [j, i];
        indexOf[nums[i]] = i;
    }
    return [];
}


// Window [left, right] without repeats: O(n), each index moves once
static int LongestUniqueRun(string s)
{
    var lastSeen = new Dictionary<char, int>();
    int best = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        if (lastSeen.TryGetValue(s[right], out int prev) && prev >= left)
            left = prev + 1;                      // jump past the repeat
        lastSeen[s[right]] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}
Two pointers and prefix sums
int[] sorted = [1, 2, 4, 7, 11, 15];
Console.WriteLine(PairWithSum(sorted, 15)); // (4, 11)
Console.WriteLine(PairWithSum(sorted, 100) is null); // True — no such pair


int[] sales = [3, 1, 4, 1, 5, 9];
var prefix = new int[sales.Length + 1];      // prefix[i] is the sum of the first i elements
for (int i = 0; i < sales.Length; i++)
    prefix[i + 1] = prefix[i] + sales[i];
Console.WriteLine(prefix[5] - prefix[2]);    // 10: sales[2] + sales[3] + sales[4] in O(1)


// Sorted array, pointers from both ends: O(n) time, O(1) memory
static (int, int)? PairWithSum(int[] a, int target)
{
    int left = 0, right = a.Length - 1;
    while (left < right)
    {
        int sum = a[left] + a[right];
        if (sum == target) return (a[left], a[right]);
        if (sum < target) left++;            // need a bigger sum
        else right--;                        // need a smaller sum
    }
    return null;
}
Topological sort (Kahn's algorithm)
// Edge a → b: step a must run before b
var graph = new Dictionary<string, string[]>
{
    ["restore"] = ["build"],
    ["build"] = ["test", "pack"],
    ["test"] = ["deploy"],
    ["pack"] = ["deploy"],
    ["deploy"] = [],
};
Console.WriteLine(string.Join(" ", TopoSort(graph))); // restore build test pack deploy


// O(V + E): BFS over vertices that have no incoming edges left
static List<string> TopoSort(Dictionary<string, string[]> graph)
{
    var inDegree = graph.Keys.ToDictionary(v => v, _ => 0);
    foreach (var targets in graph.Values)
        foreach (var t in targets) inDegree[t]++;


    var queue = new Queue<string>(inDegree.Where(p => p.Value == 0).Select(p => p.Key));
    var order = new List<string>();
    while (queue.Count > 0)
    {
        var v = queue.Dequeue();
        order.Add(v);
        foreach (var t in graph[v])
            if (--inDegree[t] == 0) queue.Enqueue(t);
    }
    if (order.Count != graph.Count) throw new InvalidOperationException("Cycle detected");
    return order;
}
Sources