Data structures & algorithms

#Big-O describes growth, not seconds

If order volume grows tenfold, does processing grow tenfold or a hundredfold? Big-O bounds the growth of time or space with input size, ignoring constants and lower-order terms. State whether you mean worst-case, expected or amortized cost; Big-O alone does not automatically mean worst-case.

// n orders, m customers; customer IDs are unique.
var byId = customers.ToDictionary(c => c.Id); // (1) expected O(m)
foreach (var order in orders) // (2) expected O(n) overall
{
    if (byId.TryGetValue(order.CustomerId, out var customer))
        Console.WriteLine(customer.Name);
}

Sequential costs add; nested costs depend on actual iteration counts, so nesting alone does not imply O(n²). List.Add can cost O(n) during resizing but is O(1) amortized over a sequence of additions. Amortized analysis does not assume random input. Also measure practical performance: locality, I/O and constants matter.

#Arrays, List and LinkedList

Arrays have fixed length; List<T> uses a growable backing array. Elements are contiguous, but for reference-type T those elements are references, not necessarily the objects themselves.

var order = new LinkedList<int>(); // .NET LinkedList is doubly linked.
var node = order.AddLast(42); // (1)
order.AddBefore(node, 17); // (2)
order.Remove(node); // (3)

Usually start with List. LinkedList suits direct node access and frequent moves, such as an LRU combining a dictionary with a doubly linked list.

#Stack, Queue and PriorityQueue

Choose the service order first. A stack is LIFO, like stacked plates: last in, first out. A queue is FIFO, like an arrival-ordered line. A priority queue chooses by priority rather than arrival time.

var undo = new Stack<string>();
undo.Push("edit");
string action = undo.Pop(); // (1)

var waiting = new Queue<int>();
waiting.Enqueue(42);
int next = waiting.Dequeue(); // (2)

var jobs = new PriorityQueue<string, int>(); // .NET 6+
jobs.Enqueue("routine", 5);
jobs.Enqueue("urgent", 1);
string first = jobs.Dequeue(); // (3) urgent

.NET's PriorityQueue uses an array-backed quaternary min-heap; heaps need not be binary. These collections are not durable brokers or automatically thread-safe queues. Consider Channel for asynchronous producer-consumer flow.

#Hash tables: a hash is not equality

To find a product quickly, hashing selects a bucket and equality identifies the actual key. Collisions are normal: different keys may share a bucket or hash. Lookup is expected O(1) with suitable hashing and distribution, but worst-case O(n), and hashing itself may depend on key length.

1. Compute the hash using the comparer.
2. Map it to a bucket; real implementations handle sign and numeric bounds.
3. Check candidates using hash and equality.
4. Resize and redistribute entries when necessary.

Chaining connects colliding entries; .NET Dictionary uses an entries array with index links. Open addressing probes alternative slots. Load factor relates entry count to available buckets; increased occupancy can increase collisions and trigger growth.

public override int GetHashCode() => 1;

public override int GetHashCode() => HashCode.Combine(StoreId, Sku);

These methods belong inside a key type with a matching Equals implementation. A value key such as record ProductKey(int StoreId, string Sku) is simpler. Equal keys must have equal hashes, but equal hashes do not establish equality. Do not mutate equality-relevant key fields after insertion. Do not persist GetHashCode as an identifier or cross-process partition key; values can change between runs. Choose string comparison semantics explicitly for the contract.

#Trees, BSTs, heaps, tries and B-trees

Trees model hierarchies, but their invariants determine efficient operations. A BST keeps smaller values left and larger values right. Search costs O(h): O(log n) when balanced, O(n) when it degenerates into a chain. AVL and red-black trees maintain balance; SortedDictionary and SortedSet use red-black trees.

public sealed class TreeNode(int value)
{
    public int Value = value;
    public TreeNode? Left, Right;
}
bool Contains(TreeNode? node, int target)
{
    while (node is not null)
    {
        if (node.Value == target) return true;
        node = target < node.Value ? node.Left : node.Right; // (1)
    }
    return false;
}
int MaxDepth(TreeNode? node) => node is null ? 0
    : 1 + Math.Max(MaxDepth(node.Left), MaxDepth(node.Right)); // (2)

A heap excels at repeatedly extracting the minimum but arbitrary value search costs O(n). Tries can consume substantial memory; a sorted array with a prefix range may be simpler. B-trees are not binary trees, and not every database index uses them.

#Graphs, BFS and DFS

A graph represents vertices connected by edges: users and relationships, dependencies or road networks. Establish direction and weights. An adjacency list uses O(V + E) space; a matrix uses O(V²) but supports O(1) edge-presence checks.

var graph = new Dictionary<int, List<int>>
{
    [1] = [2, 3], [2] = [4], [3] = [4], [4] = []
};
List<int> Bfs(int start)
{
    var seen = new HashSet<int> { start }; // (1)
    var queue = new Queue<int>([start]);
    var order = new List<int>();
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        order.Add(node);
        foreach (int next in graph[node])
            if (seen.Add(next)) queue.Enqueue(next); // (2)
    }
    return order;
}
void Dfs(int node, HashSet<int> seen, List<int> order)
{
    if (!seen.Add(node)) return; // (3)
    order.Add(node);
    foreach (int next in graph[node]) Dfs(next, seen, order);
}

A visited set alone does not detect directed cycles: use active-stack state or topological sorting. For undirected graphs, distinguish the parent edge, accounting for multiple edges if allowed.

#Dijkstra and topological ordering

In a graph, a vertex is a node such as a city and an edge is a road between nodes. BFS (breadth-first search) suits equal-cost roads; DFS (depth-first search) follows one path deeply before backtracking. Here each edge has a weight such as road cost. Dijkstra uses relaxation: calculate a route through a new edge and replace the saved best cost when it is lower. Topological sorting uses indegree, the number of incoming prerequisites, and begins with nodes that have none.

For example, finding the cheapest route between cities is not ordinary BFS if roads have different costs. Dijkstra stores the best known distance to each city and removes the cheapest candidate from a priority queue; when a cheaper route appears, it updates the distance and adds a new candidate. This works only with non-negative weights: a later path cannot make a finalized city cheaper. A min-heap is a queue that removes the smallest priority first.

Topological sorting solves a different problem: ordering tasks so each prerequisite comes before the task that depends on it. This is possible only for a DAG, a directed graph with no cycle. The code assumes valid vertex IDs, non-negative integer weights and adjacency-list input.

// Vertices: 0..n-1. Weights are non-negative ints.
long[] Dijkstra(List<(int To, int Weight)>[] graph, int start)
{
    var distance = new long[graph.Length];
    Array.Fill(distance, long.MaxValue);
    distance[start] = 0;
    var heap = new PriorityQueue<int, long>();
    heap.Enqueue(start, 0);
    while (heap.TryDequeue(out int node, out long cost))
    {
        if (cost != distance[node]) continue; // (1)
        foreach (var (to, weight) in graph[node])
        {
            if (weight < 0) throw new ArgumentException("Negative weight");
            long candidate = checked(cost + weight);
            if (candidate >= distance[to]) continue;
            distance[to] = candidate; // (2)
            heap.Enqueue(to, candidate);
        }
    }
    return distance;
}

int[] TopologicalSort(List<int>[] graph)
{
    var degree = new int[graph.Length];
    foreach (var edges in graph)
        foreach (int to in edges) degree[to]++;
    var ready = new Queue<int>();
    for (int i = 0; i < degree.Length; i++)
        if (degree[i] == 0) ready.Enqueue(i); // (3)
    var result = new List<int>();
    while (ready.TryDequeue(out int node))
    {
        result.Add(node);
        foreach (int to in graph[node])
            if (--degree[to] == 0) ready.Enqueue(to);
    }
    if (result.Count != graph.Length) // (4)
        throw new InvalidOperationException("Directed cycle");
    return result.ToArray();
}

Assume valid vertex IDs and test self-loops and disconnected graphs. Consider Bellman-Ford for negative weights instead of Dijkstra. A topological order need not be unique.

#Binary search and lower bound

Sorted data or a monotonic predicate lets you discard half the search space at each step, like searching a dictionary. The target need not be an existing element: you can find the first feasible value, such as minimum capacity meeting a delivery deadline.

int BinarySearch(int[] sorted, int target)
{
    int lo = 0, hi = sorted.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2; // (1)
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1; // (2)
        else hi = mid - 1;
    }
    return -1;
}
int LowerBound(int[] sorted, int target)
{
    int lo = 0, hi = sorted.Length; // (3) half-open interval
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Time is O(log n), space O(1) on an array. Array.BinarySearch and List.BinarySearch return a negative bitwise complement of the insertion position when absent. Sorting only to answer one search can cost O(n log n), worse than a single O(n) scan.

#Sorting: quicksort, mergesort and trade-offs

Sorting enables searching, grouping and interval processing, but choose based on stability, memory and worst-case needs. Quicksort partitions around a pivot; mergesort sorts two halves and merges them.

void QuickSort(int[] values, int lo, int hi)
{
    if (lo >= hi) return;
    int pivot = Partition(values, lo, hi); // (1)
    QuickSort(values, lo, pivot - 1);
    QuickSort(values, pivot + 1, hi);
}
int Partition(int[] values, int lo, int hi)
{
    int pivot = values[hi], write = lo;
    for (int read = lo; read < hi; read++)
        if (values[read] < pivot)
        {
            (values[write], values[read]) = (values[read], values[write]);
            write++;
        }
    (values[write], values[hi]) = (values[hi], values[write]);
    return write;
}

int[] MergeSort(int[] values)
{
    if (values.Length <= 1) return values;
    int mid = values.Length / 2;
    return Merge(MergeSort(values[..mid]), MergeSort(values[mid..])); // (2)
}
int[] Merge(int[] left, int[] right)
{
    var result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
        result[k++] = left[i] <= right[j] ? left[i++] : right[j++]; // (3)
    while (i < left.Length) result[k++] = left[i++];
    while (j < right.Length) result[k++] = right[j++];
    return result;
}

k is key-range size for counting or radix base for radix; d is digit count. Stability preserves the original order of items with equal keys. Random pivots reduce worst-case probability, and three-way partitioning helps duplicates; neither guarantees O(n log n) worst-case time. Array.Sort uses unstable introsort; LINQ OrderBy is stable. Prefer library sorting in application code. For data larger than RAM, use external merge sorting over sorted runs.

#Recursion, divide and conquer, DP and greedy

Recursion expresses a problem in smaller instances and needs a base case and progress toward it. Divide and conquer solves independent pieces and combines them. DP reuses overlapping subproblems, with optimal substructure for optimization; counting problems also use DP. Greedy commits to a local choice and requires a problem-specific correctness argument.

// Inputs for these Fibonacci examples: 0..92, fitting in long.
long FibNaive(int n) => n < 2 ? n : FibNaive(n - 1) + FibNaive(n - 2);
long FibMemo(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;
    if (memo.TryGetValue(n, out long value)) return value; // (1)
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}
long Fib(int n)
{
    if (n < 2) return n;
    long previous = 0, current = 1;
    for (int i = 2; i <= n; i++)
        (previous, current) = (current, previous + current); // (2)
    return current;
}
// Positive coin values, non-negative amount, feasible array size.
int CoinChange(int[] coins, int amount)
{
    var best = new int[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); // (3)
    return best[amount] == int.MaxValue ? -1 : best[amount];
}

With coins 1, 3, 4 and amount 6, greedy chooses 4, 1, 1 but 3, 3 is better. A few examples cannot establish greedy correctness. Deep recursion can overflow the stack; use an explicit stack or bottom-up computation when depth is large.

#A problem-solving pattern map

A pattern suggests a hypothesis, not a finished answer. Establish an invariant or recurrence and check constraints before choosing it.