Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I cover greedy algorithms. 

When to use Greedy algorithms

Recognize the problems that can be solved by greedy algorithms by the following signs:

• The problem asks for a maximum or minimum value under constraints (e.g., max profit, min jumps, min number of something, max items selected).
• A locally optimal choice at each step leads to a globally optimal solution (greedy choice property).
• Making the best immediate decision never forces you to regret it later (no need to backtrack or reconsider past choices).
• The problem has optimal substructure but greedy avoids full dynamic programming (DP) by using a simple rule or priority.
• Sorting or prioritizing by a specific key (end time, value/weight ratio, farthest reach, density) unlocks the optimal solution.
• Brute force or DP would be too slow (exponential or quadratic), but a greedy rule gives linear or n log n time.

Classic patterns appear: activity selection, interval scheduling, fractional knapsack, coin change (canonical coins), jump game reachability, task scheduling with cooldown.

An algorithm is greedy when it follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

Classic greedy algorithm problems:

• Jump Game I & II
• Task Scheduler
• Fractional Knapsack
• Activity Selection / Non-overlapping Intervals
• Huffman Coding
• Minimum Number of Platforms (train scheduling)

One sentence rule: "If I can always pick the 'best' available option right now according to some clear criterion, and doing so never hurts the final answer, it's probably greedy."

Example - Activity selection

The classic "poster problem" for greedy algorithms is Activity Selection (also known as Interval Scheduling).

Problem statement: You are given n activities with their start time and finish time. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time. Return the maximum number of activities that can be selected.

Example: activities = [[1,4], [3,5], [0,6], [5,7], [3,8], [5,9], [6,10], [8,11], [8,12], [2,14], [12,16]]

Output: 4 (one possible selection: [1,4], [5,7], [8,11], [12,16])

Constraints:

• 1 <= n <= 10⁵
• 0 <= start < finish <= 10⁹

Let's see how a naive solution would look like, using DP and brute force:

var countOps = 0;

// Extremely slow - exponential time
int MaxActivitiesNaive(int[][] activities)
{
    var n = activities.Length;
    var max = 0;

    // Generate all 2^n subsets (impossible for n>20)
    for (var mask = 0; mask < (1 << n); mask++)
    {
        List<int[]> selected = [];
        for (var i = 0; i < n; i++)
        {
            if ((mask & (1 << i)) != 0)
            {
                selected.Add(activities[i]);
            }
        }
        countOps++;
        if (IsNonOverlapping(selected))
        {
            max = Math.Max(max, selected.Count);
        }
    }
    return max;
}

bool IsNonOverlapping(List<int[]> acts)
{
    if (acts.Count <= 1) return true;

    // Sort by start time
    acts.Sort((a, b) => a[0].CompareTo(b[0]));

    // Check consecutive pairs
    for (var i = 1; i < acts.Count; i++)
    {
        var (prevEnd, currStart) = (acts[i - 1][1], acts[i][0]);

        // If previous ends after (or at) current starts -> overlap
        if (prevEnd > currStart)
        {
            return false;
        }
    }

    return true;
}

int[][] activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], 
                      [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
Console.WriteLine(MaxActivitiesNaive(activities));
Console.WriteLine(countOps);

This code will display 4, as expected, and then display 2048, the number of checks for IsNonOverlapping.

Why it fails:

• Time complexity O(2ⁿ * n log n) which is useless for n > 20
• No smart way to prune invalid subsets early

Now let's check the optimal Greedy Solution:

• Sort activities by finish time (earliest ending first).
• Then greedily pick the next activity that starts after the previous one ends.

var countOps = 0;

int MaxActivities(int[][] activities)
{
    if (activities == null || activities.Length == 0) return 0;

    // Sort by finish time - this is the greedy choice
    Array.Sort(activities, (a, b) => a[1].CompareTo(b[1]));
    countOps += (int)Math.Ceiling(activities.Length * Math.Log(activities.Length));

    var count = 1;
    var lastEnd = activities[0][1];  // finish time of first selected

    for (var i = 1; i < activities.Length; i++)
    {
        countOps++;
        // Can take this activity if it starts after last selected ends
        if (activities[i][0] >= lastEnd)
        {
            count++;
            lastEnd = activities[i][1];
        }
    }

    return count;
}

int[][] activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], 
                      [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
Console.WriteLine(MaxActivities(activities));
Console.WriteLine(countOps);

This displays a countOps of 37.

This is optimal because:

• Time: O(n log n) due to sorting + O(n) pass
• Space: O(1) extra (or O(log n) for sort)
• Correctness: Proof relies on "greedy stays ahead" or "exchange argument"
• Earliest finish leaves maximum room for future activities
• Any optimal solution can be transformed into this greedy one without decreasing size

This problem is the "hello world" of greedy algorithms:

• Simple to understand
• Shows why greedy works when many people think dynamic programming (DP) is needed
• Easy to prove correctness in interviews
• Appears in countless variations (meeting rooms, non-overlapping intervals, weighted interval scheduling -> DP)

Theory

OK, you will hate me for this, but I found it an interesting tidbit. And if the interview guy knows what a matroid is, you're either applying for a really good company or you're totally screwed. Anyway...

Greedy algorithms and matroids are very closely related in a precise mathematical way, as matroids provide one of the cleanest and most general explanations for when and why greedy algorithms work. But first we need some quick definitions:

Greedy algorithm: At each step, make the locally optimal choice (pick the best-looking option right now) according to some criterion, hoping it leads to a globally optimal solution.

Matroid: A mathematical structure that generalizes the notion of "independence" (like linear independence in vector spaces or acyclic sets in graphs).

It has two key axioms:

• Hereditary property: If a set is independent, all its subsets are independent.
• Exchange property: If two independent sets A and B exist and |A| < |B|, then there exists an element in B that can be added to A while keeping it independent.

The fundamental theorem (the relationship between them) was developed by Jack Edmonds and others in 1971: A greedy algorithm correctly finds the maximum-weight independent set in a weighted set system if and only if the set system is a matroid.

In other words:

• If the problem can be modeled as finding a maximum-weight independent set in a matroid, then the greedy algorithm (sort by weight descending, add if it keeps independence) is guaranteed to give the optimal solution.
• If greedy works correctly on a problem, then the underlying structure is usually a matroid (or can be reduced to one).

Greedy fails when not a matroid:

• 0/1 Knapsack: Greedy by value/weight ratio can fail - no matroid structure (doesn't satisfy exchange)
• General coin change (non-canonical denominations): Greedy can give suboptimal - not a matroid
• Traveling Salesman Problem: Greedy nearest neighbor fails badly - no matroid

The matroid is the set of rules, not anything in the problem statement, so that might be confusing. Let's simplify that for the five year old mind of a software developer. You have a pile of toys and in that case a matroid is a set of rules that tells you:

• if any handful of toys is considered "good", then any smaller handful is also "good". There is no way you can split a "good" pile of toys and get a "bad" one.
• if any two handfuls are "good", then moving any toy from one to the other also results in two "good" handfuls.

In our example above, the toys were the activities, the good handfuls were sets of non-overlapping activities, therefore the algorithm is proven to give the optimal solution.

Greedy algorithm template

And even if the name indicates something very generic, there is in fact a "template" of greedy algorithms:

1. define the greedy choice criterion - in our case, activity start time. Other examples:
   • Earliest finish time
   • Highest value/weight ratio
   • Maximum jump distance
   • Smallest end time
2. sort or prioritize the elements - this is a most common first step
   • sort arrays or use a priority queue if dynamic selection is needed
3. initialize result/tracking variables:
   • result count = 0
   • current end time / current capacity / current position / etc. = starting value
   • sometimes a "last selected" pointer or index
4. Iterate through the elements and for each:
   • Check if adding it is safe / possible / non-conflicting (greedy check: does it fit with previous choices?)
   • If yes, add it to solution (increment count, update end time/remaining capacity/position)
   • If no, skip it
5. Return the result

Variations of the template

• No sorting needed (pure linear pass)
  • Example: Jump Game I & II
  • Track farthest reachable, update when you hit current end
• Priority queue instead of sort
  • Example: Task Scheduler, Huffman coding
  • Repeatedly pick the max/min element from heap
• Two pointers or sliding window
  • Some greedy problems (longest substring, min platforms) use greedy + two pointers instead of explicit sort

In other words: prioritize by the magic key, then greedily take every valid next item that doesn't break the constraints.

Example - Task scheduler

Let's try to solve a more difficult problem. Let's call it Task Scheduler.

Problem statement: You are given n tasks represented by an array tasks where tasks[i] is the time needed to complete task i. You must schedule all tasks on a single CPU with these rules:

• The CPU can only work on one task at a time, and each task takes one unit of time to execute.
• After finishing a task, there must be at least cooldown units of time before you can start the same task again (if there are identical tasks).
• Tasks are not all unique - there can be duplicates (same task type).

You want to find the minimum total time needed to complete all tasks (including idle time). Return the minimum time units required.

Example: tasks = [1,1,2,2,3], cooldown = 2 - Output: 5

One possible schedule: 1,2,3,1,2

Total time = 5 (no idle slots)

int TaskScheduler(int[] tasks, int cooldown)
{
  // Step 1: Count the frequency of each task type (since same value = same type)
  // We use a dictionary to store how many instances of each task value there are
  var freq = new Dictionary<int, int>();
  foreach (var t in tasks)
  {
    freq[t] = freq.GetValueOrDefault(t, 0) + 1;
  }

  // Step 2: Create a max-heap (priority queue) to always pick the task type with
  // the most remaining instances. We use a custom comparer to make it max-heap
  // based on count (higher count first)
  var pq = new PriorityQueue<(int count, int task), int>(
    // Max-heap: higher count has higher priority
    Comparer<int>.Create((a, b) => b.CompareTo(a))  
  );

  // Enqueue all task types with their initial counts
  foreach (var kv in freq)
  {
    // Enqueue (count, task), prioritized by count
    pq.Enqueue((kv.Value, kv.Key), kv.Value);
  }

  // Step 3: Create a min-heap for tasks on cooldown
  // This tracks when a task type becomes available again after cooldown
  // (timeAvailable, task), prioritized by timeAvailable (earliest first)
  var cooldownQueue = new PriorityQueue<(int timeAvailable, int task), int>();

  // Step 4: Simulate time starting from 0
  var time = 0;

  // Loop until no more tasks in ready queue or cooldown queue
  while (pq.Count > 0 || cooldownQueue.Count > 0)
  {
    // Increment time by 1 each cycle (each unit represents a potential work or idle slot)
    time++;

    // Step 5: Move any tasks whose cooldown has ended back to the ready priority queue
    // Check the earliest cooldown task and dequeue if its timeAvailable <= current time
    while (cooldownQueue.Count > 0 && cooldownQueue.Peek().timeAvailable <= time)
    {
      var (availTime, task) = cooldownQueue.Dequeue();  // Remove from cooldown
      var remaining = freq[task];  // Get current remaining count for this task
      if (remaining > 0)
      {
        // Re-add to ready queue if still work left
        pq.Enqueue((remaining, task), remaining);
      }
    }

    // Step 6: If there is a ready task (pq not empty),
    // execute one instance of the most frequent one
    if (pq.Count > 0)
    {
      var (count, task) = pq.Dequeue();  // Get the task with highest remaining count
      count--;  // Execute one instance (decrement remaining)
      freq[task] = count;  // Update frequency

      // If still remaining instances, put it back on cooldown
      // Available again after current time + cooldown + 1 
      // (since time already includes this execution)
      if (count > 0)
      {
        cooldownQueue.Enqueue((time + cooldown + 1, task), time + cooldown + 1);
      }
    }
    // Else: No ready task -> CPU idles this time unit 
    // (time already incremented, so idle is counted)
  }

  // The final time is the minimum total units needed (work + idle)
  return time;
}

int[] tasks = [1, 1, 2, 2, 3];
int cooldown = 2;
Console.WriteLine(TaskScheduler(tasks, cooldown));

Here's what makes this solution greedy:

• It makes locally optimal choices at each step - at every time unit where the CPU can work (when pq is not empty), the code always picks the task type with the highest remaining count (the "best" available choice right now).
  • This is done via the max-heap (pq):var (count, task) = pq.Dequeue();
  • Picking the task with the most remaining instances is the greedy decision, it focuses on the current bottleneck (the type that still has the most work left).
• The greedy choice property holds (or is strongly believed to) - the key insight is: always working on the task type that has the most unfinished work (when it's ready) minimizes the total time, because it reduces the chance of being stuck waiting for cooldowns later.
  • This is the "never regret" part: choosing the highest-remaining task early tends to balance the load and avoid long idle periods caused by waiting for one type to become available again.
  • In practice, this heuristic works very well for this problem (and is the standard accepted greedy strategy).
• Irreversible decisions, no backtracking - once a task instance is executed at a certain time, the code never undoes it or reconsiders it.
  • No recursion, no trying alternative branches, no memoization table, just forward progress.
  • After executing: count--; freq[task] = count; if (count > 0) cooldownQueue.Enqueue(...); the choice is committed, and the task goes on cooldown if needed.
• Uses a priority queue to enforce the greedy rule. The max-heap is the classic greedy tool here:
  • It guarantees that at every decision point, you get the "best" (highest remaining count) ready task instantly.
  • This replaces sorting the entire input upfront (which wouldn't work well because tasks become ready dynamically over time).
• Overall algorithm is greedy-driven simulation - the loop simulates time tick by tick.
  • At each tick:
    • Move expired cooldown tasks back to ready (pq)
    • If anything is ready, greedily execute the one with most remaining work
    • If nothing ready, idle (time++ anyway)
  • This is a greedy event-driven simulation: always do the currently best possible action.

So it repeatedly chooses the currently best option (task with most remaining instances) using a max-heap. It relies on the greedy intuition that prioritizing high-remaining tasks leads to the minimum total time (the greedy choice property). There is no exhaustive search, no backtracking, no DP table, just forward greedy decisions.

However, if you were working on a real piece of software, this would probably not get you promoted. And the reason is that this entire thing can be calculated mathematically.

int[] tasks = [1, 1, 2, 2, 3];
int cooldown = 2;

var maxFreq = 0;
var countMax = 0;

foreach (var f in tasks.GroupBy(t=>t).Select(t=>t.Count()))
{
    if (f > maxFreq)
    {
        maxFreq = f;
        countMax = 1;
    }
    else if (f == maxFreq)
    {
        countMax++;
    }
}
var result = Math.Max(tasks.Length,(maxFreq - 1) * (cooldown + 1) + countMax);
Console.WriteLine(result);

maxFreq = the highest frequency of any single task type
countMax = how many task types have exactly that max frequency

Think of the schedule as consisting of "frames" or "cycles" separated by cooldown gaps. The task that appears most often creates the backbone of the schedule. Each pair of occurrences of that task needs at least cooldown idle slots between them. So for maxFreq occurrences you need (maxFreq - 1) gaps between them and each gap must be at least cooldown units long.

Therefore, you need (maxFreq - 1) * cooldown mandatory idle slots. Then add the maxFreq work slots for that frequent task, plus the work done by other tasks that can fill the gaps or after the last occurrence.

The tightest lower bound becomes: (maxFreq - 1) * (cooldown + 1) + countMax :

• (maxFreq - 1) gaps, each at least cooldown + 1 long (cooldown idles + 1 work slot for next same task)
• the number of tasks that share the max frequency (they all finish in the last cycle)

Finally take the max with total number of tasks (because you can't finish faster than the number of tasks if no idles are needed).

Conclusion

Greedy algorithms are useful when you can make an optimal decision at every step without fear of previous choices. In order word, independent choices. You need an insight about what the requirement actually is: sometimes greedy algorithm is another word for "Oh! That's what you really want!". And if you think well enough, you might not even need any greed, just computation.

That is why when you go on these algorithm interview sites, the problems in the greedy algorithm category have the most confusing descriptions and the most comments from people who didn't get what was asked of them.

Remember the matroid. In case of emergency, bring that up and see the other guy go silent.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I will cover Backtracking.

When to use Backtracking

Recognize a problem that can be solved with Backtracking by these signs:

• The problem asks for all possible solutions / combinations / permutations / arrangements / configurations.
• You need to find one (or all) valid solution(s) by making a sequence of choices/decisions.
• There is a decision tree structure: at each step you choose one option from several candidates.
• The number of possibilities is exponential (n!, 2ⁿ, etc.) but you can prune invalid branches early to avoid full enumeration.
• You can build the solution incrementally and check validity as you go (partial solutions are meaningful).
• Constraints allow early termination of a branch (e.g., sum exceeds target, board conflict, duplicate choice, invalid move).
• The problem involves puzzles, combinatorial search, or constraint satisfaction (Sudoku, N-Queens, crosswords, partitioning).

Words/phrases in the problem: "all possible", "generate", "find all combinations", "all permutations", "solve", "place", "fill", "arrange", "valid configurations", "every way to..."

Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Classic backtracking problem patterns:

• Generate all subsets / combinations / permutations (with or without duplicates)
• N-Queens / chess piece placement puzzles
• Sudoku solver
• Word search / Boggle
• Palindrome partitioning
• Restore IP addresses
• Combination sum (with target)
• Letter combinations of a phone number
• Generate parentheses
• Rat in a maze / path finding with constraints

One-sentence rule: If the problem feels like "try every reasonable choice, go deeper, undo if it fails, and collect valid complete solutions" it is almost certainly backtracking.

Example - N-Queens

This is a problem often called "N-queens"

Problem statement: Place N queens on an N x N chessboard so that no two queens attack each other. Queens attack horizontally, vertically, or diagonally. Return one valid board configuration (or all, as a variation).

Represent the board as a list of strings where 'Q' = queen and '.' = empty.

Constraints: 1 <= N <= 9 (for N=1 to N=9 there is always at least one solution).

Example for N=4 (one possible solution):

. Q . .
. . . Q
Q . . .
. . Q .

Output as: [".Q..","...Q","Q...","..Q."]

Here is a naive implementation:

using System.Text;

var count = 0;

IList<IList<string>> SolveNQueens(int n)
{
    var result = new List<IList<string>>();
    char[,] board = new char[n, n];
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            board[i, j] = '.';

    PlaceQueensNaive(board, 0, n, result);
    return result;
}

void PlaceQueensNaive(char[,] board, int row, int n, IList<IList<string>> result)
{
    count++;
    if (row == n)
    {
        // Check if valid (very late)
        if (IsValid(board, n))
        {
            var sol = new List<string>();
            for (var i = 0; i < n; i++)
            {
                var sb = new StringBuilder();
                for (var j = 0; j < n; j++)
                    sb.Append(board[i, j]);
                sol.Add(sb.ToString());
            }
            result.Add(sol);
        }
        return;
    }
    for (var col = 0; col < n; col++)
    {
        board[row, col] = 'Q';
        PlaceQueensNaive(board, row + 1, n, result);
        board[row, col] = '.';  // backtrack
    }
}

bool IsValid(char[,] board, int n)
{
    // Check columns and diagonals for each queen
    for (var r = 0; r < n; r++)
    {
        for (var c = 0; c < n; c++)
        {
            if (board[r, c] != 'Q') continue;

            // Check right, down-right, down-left from this queen
            // (we only need to check one direction because we fill row by row)

            // Same column below
            for (var i = r + 1; i < n; i++)
                if (board[i, c] == 'Q') return false;

            // Down-right diagonal
            for (var i = r + 1, j = c + 1; i < n && j < n; i++, j++)
                if (board[i, j] == 'Q') return false;

            // Down-left diagonal
            for (var i = r + 1, j = c - 1; i < n && j >= 0; i++, j--)
                if (board[i, j] == 'Q') return false;
        }
    }

    return true;
}

var result = SolveNQueens(4);
Console.WriteLine("Executions: " + count);
foreach (var solution in result)
{
    Console.WriteLine(string.Join("\r\n", solution));
    Console.WriteLine();
}

Now, this outputs the two possible solutions for N=4 and 341 executions.

The IsValid method is not the most efficient implementation, but it's readable (also not really the focus of the post).

There are several issues with PlaceQueensNaive, though:

• Tries every cell -> nⁿ possibilities (for n=9: ~387 million)
• Validation only at the end -> wastes time exploring invalid partial boards
• No early pruning -> extremely slow even for n=8

Let's see a good solution:

using System.Text;

var count = 0;

IList<IList<string>> SolveNQueens(int n)
{
    var result = new List<IList<string>>();
    var board = new char[n, n];
    for (var i = 0; i < n; i++)
        for (var j = 0; j < n; j++)
            board[i, j] = '.';

    var cols = new bool[n];
    var diag1 = new bool[2 * n - 1];  // row + col
    var diag2 = new bool[2 * n - 1];  // row - col + (n-1)

    Backtrack(0, board, cols, diag1, diag2, n, result);
    return result;
}

void Backtrack(int row, char[,] board, bool[] cols, bool[] diag1, bool[] diag2, int n, IList<IList<string>> result)
{
    count++;
    if (row == n)
    {
        var sol = new List<string>();
        for (var i = 0; i < n; i++)
        {
            var sb = new StringBuilder();
            for (var j = 0; j < n; j++) sb.Append(board[i, j]);
            sol.Add(sb.ToString());
        }
        result.Add(sol);
        return;
    }

    for (var col = 0; col < n; col++)
    {
        var d1 = row + col;
        var d2 = row - col + n - 1;

        if (cols[col] || diag1[d1] || diag2[d2]) continue;  // prune - attacked

        // Place
        board[row, col] = 'Q';
        cols[col] = true;
        diag1[d1] = true;
        diag2[d2] = true;

        Backtrack(row + 1, board, cols, diag1, diag2, n, result);

        // Backtrack
        board[row, col] = '.';
        cols[col] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

var result = SolveNQueens(4);
Console.WriteLine("Executions: " + count);
foreach (var solution in result)
{
    Console.WriteLine(string.Join("\r\n", solution));
    Console.WriteLine();
}

Why this is optimal:

• One queen per row -> n! instead of n²
• Immediate pruning with column + diagonal tracking -> most branches die early
• Time: O(n!) worst case but in practice much faster due to heavy pruning
• For n=9 it runs almost instantly

The count of executions is 17.

Backtracking template

While the code above was simple and clear, it still carries a lot of the particular problem details. Can we imagine a generic backtracking solution? And we kind of can:

• start with a mechanism of generating candidate steps or a list of them
• then prepare a result which is a list of lists of steps
  • each list of steps will represent a solution and the result is the list of solutions
• then call the backtracking method, by adding an empty list as a partial solution
• In the method code:
  • first check if solution is valid, and if so add it to the result and return from the method
    • you may want to exit here permanently if the requirement is to find just a single solution
  • then check if you can prune it (invalidate partial solution as soon as possible), and if so return (abandon it)
  • then for all possible steps:
    • check if the step is valid for the partial solution (and if not, skip it)
    • add (place) the step to the solution - this represents the solution with an extra step
    • call the method on the new solution
    • remove (backtrack) the step from the solution - this prepares the solution for the next step

That's it. You note that we've used the recursive function idea here, but we can use a queue with the same purpose:

• start with a mechanism of generating candidate steps or a list of them
• then prepare a result which is a list of lists of steps
  • each list of steps will represent a solution and the result is the list of solutions
• then prepare a queue of lists of steps
  • each list of steps is a partial solution, the queue is the work list
• while there are items in the queue:
• dequeue an item
• first check if solution is valid, and if so add it to the result and continue to the next item in the queue
  • you may want to exit here permanently if the requirement is to find just a single solution
• then check if you can prune the solution, and if so continue to the next item in the queue
• then for all possible valid steps:
  • enqueue a new item from the solution with the step applied

So... where's the backtracking? These two forms are called recursive and iterative backtracking. The second gives you more control and might be needed when there are a lot of possible steps to escape the limitation of the call stack size. You may recognize it as the BFS/DFS method described in my previous post. Queue for BFS, stack for DFS.

You see, a lot of people refer to just the recursive version of backtracking as backtracking. It is:

• shorter and more elegant to write
• the "backtrack" action is implicit (you just return from the method)
• the undo step is done automatically when the method exits
• recursion uses the call stack

The iterative version is:

• more verbose
• you have to create a solution explicitly (generate/copy and add new list to queue)
• uses the heap, so it doesn't do stack overflows
• it doesn't backtrack as much as it doesn't follow up on invalid partial solutions 

Personally, I prefer the second, because it's more flexible and offers more control, but you be the judge.

Example - Generate parentheses

An almost as common interview question for backtracking is the Generate Parentheses problem.

Problem statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

And here is the solution:

IList<string> Backtrack(int n, string current="", int open=0, int close=0,  IList<string> result=null)
{
    result ??= [];
    // Base case: we used exactly n pairs and string is complete
    if (current.Length == n * 2)
    {
        result.Add(current);
        return result;
    }

    // Choice 1: add an opening parenthesis (if we can)
    if (open < n)
    {
        Backtrack(n, current + "(", open + 1, close, result);
    }

    // Choice 2: add a closing parenthesis (only if more opens than closes)
    if (close < open)
    {
        Backtrack(n, current + ")", open, close + 1, result);
    }
    return result;
}

var result = Backtrack(3);
Console.WriteLine(string.Join("\r\n",result));

I got a little fancy here:

• I used the same method as the solve and the backtrack method, taking advantage of the default parameter value feature of C#, but that meant I had to return the result all the time
• There is no loop over steps, because there are just two of them
• The pruning is done before calling the backtracking method, by checking the open and close values
• There is no backtracking per se, since we are using a new copy (concatenated string) in all calls
• You want to get extra fancy? Use a StringBuilder instead of a string, Append the parentheses, then decrement the StringBuilder length when you exit, thus implementing literal backtracking.
  • there is a gotcha here, though, see below in the Generic backtracking section

The output is the five possible solutions.

This is optimal because:

• Time complexity: O(4ⁿ / sqrt(n)) - this is the number of valid Catalan number sequences, roughly O(4ⁿ).
• Backtracking prunes almost all invalid paths early.
• Space complexity: O(n) recursion depth + O(4ⁿ) for output storage.
• No extra arrays or complex state - just track count of open and close parentheses.
• Very clean and efficient - runs instantly even for n=8.

Generic backtracking

I have tried to implement a generic class that does backtracking solving. And I made it, but it was really ugly. I tried simplifying it in several ways, but in the end I gave up. Why? Because backtracking in itself is such a general solution to a lot of problems that trying to create a class to encapsulate that results in a very thin thing that requires the solution type to implement everything.

If you think about it, the solver has to implement:

• a type for the solution
• a type for the current state
• a way to generate valid steps based on current state (and possibly the list of existing solutions)
• a way to apply the steps on the current solution and state (and unapply them, if you want standard backtracking)
• a way to determine validity of a solution
• a way to extract/clone the result from the solution

And you realize that you either have to provide a lot of functions as parameters to the solver, or you have to combine the solution type and state type and implement the methods there. And in the second case, the solver itself does nothing in particular.

My implementation, in order to solve the generate parentheses problem, assumed any solution is an IList<TItem> and the TItem was (char ch, int open, int closed, int pairCount), which was frankly ridiculous.

Sometimes it pays off, though, to try to achieve such things in order to understand why they would not work and what are the underlying assumptions in your code.

For example, you never considered that in both examples above we needed to clone the solution in order to add it to the result. In the first example we were putting in the result sb.ToString(), which generates a clone of the StringBuilder, and in the second example we were using string concatenation, which generates a new string every time. If you had added the StringBuilder itself to the result list, then it would have held the reference to the same object several times.

Conclusion

Backtracking is an important tool in any developer's toolkit and it is one of the first theoretical computer science concepts you are being taught in school. The magic is in three steps: choose an option, explore deeper by recursing, unchoose when you return. Everything else (pruning, skipping duplicates, validity checks) is just smart decoration around this loop.

But once you look "under the hood" you realize that in order to implement classic backtracking you are relying on programming language constructs that add syntactic sugar to an otherwise differently defined problem: growing a list of possible solutions and eliminating them early if they cannot yield a valid solution.

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

  Today I will be covering Breadth First Search (BFS) in tree/graph traversals.

When to use BFS

  Recognize a problem that can be solved with BFS by these signs:

• The problem requires the shortest path, minimum steps, fewest moves, earliest time, or minimum operations in an unweighted graph, grid, tree, or similar structure (this is the single strongest signal - BFS is the only standard algorithm that guarantees shortest path in unweighted settings)
• All edges/moves have equal cost (unit cost / cost = 1, if costs vary -> Dijkstra / 0-1 BFS / A* instead)
• The solution needs level-by-level processing, results grouped by distance, or exploration ordered by increasing distance from the start(s) (includes collecting nodes per level, processing by depth, or any "by distance k" requirement)
• The problem has multi-source starting points (multiple cells/nodes begin simultaneously at distance/time 0) OR it involves spreading / propagation / infection / flooding from one or more origins over time

  Basically you are expanding your search by filling the solution space as close to the starting point as possible.

  Rule of thumb: if the problem says 'shortest', 'minimum steps', 'level by level' or 'multi-source spread' in an unweighted graph/grid/tree, then BFS is your friend.

Example - Shortest path in maze

In the previous post we've used a maze problem to demonstrate the use of depth first search (DFS). There we had to find if a maze can be solved, any solution would do, and it did find a solution which was ludicrously long. Now we're being asked to find the shortest path to escape the maze.

Problem statement: Given a 2D grid representing a maze (0 = open path, 1 = wall), find the minimum number of steps to go from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can move in 4 directions (up, down, left, right), but cannot go through walls or outside the grid. Return the shortest path length, or -1 if no path exists. Assume (0,0) and (m-1,n-1) are open (0).

Example grid (same as in the DFS post):

var maze = new int[][]
{
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 0]
};

Since we've already solved a maze question with DFS, why not do it here as well? Here is a possible attempt:

int minSteps = int.MaxValue;

int ShortestPath(int[][] maze, int row, int col, int steps = 0)
{
    var m = maze.Length;
    var n = maze[0].Length;

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return -1;

    if (row == m - 1 && col == n - 1)
    {
        minSteps = Math.Min(minSteps, steps);
        return minSteps;
    }

    // Mark as visited by setting to 1 (temporary)
    maze[row][col] = 1;

    // Explore all 4 directions
    ShortestPath(maze, row - 1, col, steps + 1);  // up
    ShortestPath(maze, row + 1, col, steps + 1);  // down
    ShortestPath(maze, row, col - 1, steps + 1);  // left
    ShortestPath(maze, row, col + 1, steps + 1);  // right

    // Backtrack: unmark
    maze[row][col] = 0;

    return minSteps == int.MaxValue ? -1 : minSteps;
}

var result = ShortestPath(maze, 0, 0);
Console.WriteLine(result);

The output is 6, which is correct, so is this a good solution? Let's see what the complexity of the algorithm is.

The time complexity is O(4^n*m) in worst cases (branching factor 4 - the directions - and depth up to m*n). This times out even on small grids! Then the marking and unmarking of things is also adding complexity and stack space: O(n*m), which would lead to stack overflows.

But what's worse is that this may not find the shortest path at all! And if it does, it explores longer paths when shorter ones exist.

With BFS, this doesn't happen. The standard form of a BFS solution looks like this:

public int SomeBfs(TreeNode root) {  // or int[][] grid, etc.
    if (root == null) return 0;
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    // bool[,] visited = ... if needed
    var level = 0;

    while (queue.Count > 0) {
        var size = queue.Count;  // process current level
        for (var i = 0; i < size; i++) {
            TreeNode node = queue.Dequeue();
            // Do something with node (e.g. collect value)
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        level++;
    }
    return level - 1;  // example: max depth
}

The inner loop processes one full level before moving deeper - that's the BFS guarantee - but it's not needed most of the time, since you can just dequeue node by node. The point is that by using a queue, you ensure a first in first out (FIFO) approach, proceeding one level further only when the previous one has been explored.

Let's see how that works for our problem:

int ShortestPath(int[][] maze)
{
    if (maze == null || maze.Length == 0)
        return -1;

    var m = maze.Length;
    var n = maze[0].Length;

    if (maze[0][0] == 1 || maze[m - 1][n - 1] == 1)
        return -1;

    var visited = new bool[m, n];
    var queue = new Queue<(int, int, int)>();
    queue.Enqueue((0, 0, 0));  // row, col, steps
    visited[0, 0] = true;

    int[][] directions = [
        [ -1, 0 ],
        [ 1, 0 ],
        [ 0, -1 ],
        [ 0, 1 ]
    ];  // up, down, left, right

    while (queue.Count > 0)
    {
        var (r, c, steps) = queue.Dequeue();

        if (r == m - 1 && c == n - 1)
            return steps;

        foreach (var dir in directions)
        {
            var nr = r + dir[0];
            var nc = c + dir[1];

            if (nr >= 0 && nr < m 
             && nc >= 0 && nc < n
             && maze[nr][nc] == 0 && !visited[nr, nc])
            {
                visited[nr, nc] = true;
                queue.Enqueue((nr, nc, steps + 1));
            }
        }
    }

    return -1;  // no path
}

Note the tuple used as the queue item type! In this kind of solutions, that type needs to hold all the information needed to process a step. In our case, it's the row and column position plus the number of steps to get there.

The execution is simple: start with (0,0,0 - top-left corner) in the queue, then process and remove items in the queue one by one and add four new ones, one for each direction. Constraints like never process the same cell twice, keeping in the borders of the grid and FIFO processing guarantee that when a solution is found, it's the shortest.

If you try to visualize how that works, imagine each cell as it is placed in the queue changing it's color to red:

If you have ever used a graphical image editor, you may recognize the "fill" feature, where you select a color to fill up the space taken by another color. That's another common problem for this kind of algorithm.

So, let's check the complexity. Time: O(n*m) as each cell is visited at most once. Space: O(n*m) for the visited array and the queue. BFS explores by increasing distance, so the first time it reaches the end is guaranteed to be the shortest path. No backtracking needed, and it stops as soon as possible.

Switching between DFS and BFS

I was planning on writing a separate post about this, but the setup is the same, so I will just make this another chapter here.

We've learned to use the stack of the programming language to do DFS, but for BFS we had to use our own data structure, the queue, where an item contains all of the information required to run a step. We also learned that the stack is limited (usually to around 1MB) so even a working DFS program might lead to a stack overflow if the input data is too large. This would not happen in the case of the BFS example. The queue would just take up as much space as it needs within the available memory. This means that using the default recursive execution mechanism of the programming language is making the solution brittle.

If only we could use the same mechanism we used for BFS to write a DFS solution! Well, if you think about it, the only reason the BFS is doing things level by level is the FIFO implementation of the queue. Replacing the queue with a stack (wait, stack? yes, it's the same thing as the one used by the recursive function calling) moves us from FIFO to LIFO (last in, first out) and translates BFS solutions to DFS solutions.

Replacing in our code above a Queue<T> with a Stack<T>, Enqueue with Push and Dequeue with Pop, you execute it and get the same result! But if you visualize the path the code takes, it looks like this:

Only the shape of the maze makes this finish in the same number of steps as the BFS one, so this is not a valid solution for the problem, but this simplifies the development model a little. All you need to do is write the same kind of code and choose the right data structure to generate a DFS or a BFS solution. And bonus points, you can tell the interviewers that you would never trust the tiny recursive execution stack to be large enough for your code.

Let's see the DFS example from the previous post, written with our own stack implementation:

bool HasPath(int[][] maze)
{
    var m = maze.Length;
    var n = maze[0].Length;

    var visited = new bool[m][];
    for (var i = 0; i < m; i++)
        visited[i] = new bool[n];
    var stack = new Stack<(int row, int col)>();
    stack.Push((0, 0));
    while (stack.TryPop(out var cell))
    {
        var (row, col) = cell;
        if (row < 0 || row >= m 
            || col < 0 || col >= n 
            || maze[row][col] == 1)
            continue;

        if (row == m - 1 && col == n - 1)
            return true;

        // avoid cycles by not visiting the same cell again
        if (visited[row][col])
            continue;

        // mark the cell as visited
        visited[row][col] = true;

        stack.Push((row-1, col));
        stack.Push((row+1, col));
        stack.Push((row, col-1));
        stack.Push((row, col+1));
    }
    return false;
}

var result = HasPath(maze);
Console.WriteLine(result);

This solution is completely equivalent, but using no recursion whatsoever. Note that the item type is just a pair of row and column, since the maze is a local parameter. To do that with recursion you need to declare a local function, which makes the code a lot less readable. Also, while maintaining the logic of the original method, this is not optimal. We are adding items in the stack and only checking the values in the item when we get it off the stack. If you check that before adding them to the stack, the code will become more efficient and even more readable.

The caveat, though, is that if you write the code badly, you have to wait for a memory overflow to know you fouled it up.

Example - Shortest path visiting all nodes

Let take a really nasty problem: Shortest Path Visiting All Nodes. This is a classic hard problem in the interviews, so let's see how it goes.

Problem statement: You are given an undirected, connected graph with n nodes labeled from 0 to n-1 and a list of edges (as adjacency list: graph[i] = list of neighbors of i). Return the length of the shortest path that visits every node exactly once (you can start at any node and return to visited nodes if needed, but must cover all). The path length is the number of edges traversed. If no such path exists, return -1 (but since the graph is connected, it always does).

Constraints

• 1 ≤ n ≤ 12
• 0 ≤ graph[i].Length < n (no self-loops, possible multiple edges but assume simple)
• The graph is undirected and connected.

Naive solution:

int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4

int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4

int minLength = int.MaxValue;

int ShortestPathLength(int[][] graph)
{
    var n = graph.Length;
    for (var start = 0; start < n; start++)
    {
        var visited = new bool[n];
        visited[start] = true;
        Dfs(graph, start, 1, visited, 0);  // node, visited count, path length
    }
    return minLength == int.MaxValue ? -1 : minLength;
}

void Dfs(int[][] graph, int node, int visitedCount, bool[] visited, int length)
{
    if (visitedCount == visited.Length)
    {
        minLength = Math.Min(minLength, length);
        return;
    }

    foreach (var nei in graph[node])
    {
        if (!visited[nei])
        {
            visited[nei] = true;
            Dfs(graph, nei, visitedCount + 1, visited, length + 1);
            visited[nei] = false;  // backtrack
        }
        else
        {
            // Even allow revisits? But this explodes
            Dfs(graph, nei, visitedCount, visited, length + 1);
        }
    }
}

Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));

The DFS one has the issues we've seen with the simple maze example above:

• exponential complexity explosion: O(n! * n)
• no guarantee that the found path is shortest
• backtracking is inefficient 
• missing state as it doesn't track visited nodes efficiently

This fails with a terrible stack overflow exception. Of course, we could implement this with a Stack<T> and reach a much worse timeout/memory overflow exception.

Let's take a look at the BFS solution with the correct implementation:

int[][] graph1 = [ [1, 2, 3], [0], [0], [0] ];
// Nodes: 0 connected to 1,2,3; others only to 0.
// Shortest path covering all: e.g., 3-0-1-0-2 (visits all, length 4)
// Output: 4

int[][] graph2 = [ [1], [0, 2, 4], [1, 3, 4], [2], [1, 2] ];
//A more connected graph.
//Shortest path: e.g., 0-1-2-3-4 (length 4, but check if shorter exists)
//Output: 4

int ShortestPathLength(int[][] graph)
{
    var n = graph.Length;
    var target = (1 << n) - 1;  // all nodes visited: 111...1 (n bits)

    Queue<(int node, int mask, int steps)> queue = new();
    var visited = new bool[n, 1 << n];  // node + mask visited?

    // Start from every node (multi-source)
    for (var i = 0; i < n; i++)
    {
        var initMask = 1 << i;
        queue.Enqueue((i, initMask, 0));
        visited[i, initMask] = true;
    }

    while (queue.Count > 0)
    {
        var (node, mask, steps) = queue.Dequeue();

        if (mask == target)
            return steps;

        foreach (var nei in graph[node])
        {
            var newMask = mask | (1 << nei);  // visit nei

            if (!visited[nei, newMask])
            {
                visited[nei, newMask] = true;
                queue.Enqueue((nei, newMask, steps + 1));
            }
        }
    }

    return -1;  // though always connected
}

Console.WriteLine(ShortestPathLength(graph1));
Console.WriteLine(ShortestPathLength(graph2));

Bonus: uses a bit mask to store the visited nodes for each step. Interview people love bit operations and premature optimizations.

The solution starts from every single node to find the shortest path, a classical BFS sign. In the beginning the queue has an item for each node, a mask with a bit for that node only and a counter for the steps. Then it removes items one by one and adds items for each of the neighbors, mask updated, counter incremented. Again, because we use a FIFO queue, when we first get to the target (the mask is filled with 1s), it's guaranteed to have a the smallest count of steps. 

Note that this would also fail if n were allowed to be much larger than 12.

Time complexity: O(n * 2ⁿ * E / n) ≈ O(n * 2ⁿ) since E small - for n=12, ~50k states * avg degree ~3-5 = ~200k operations, fast.

Space complexity: O(n * 2ⁿ) for visited (~50k bools).

Example - Binary tree level order traversal

Let's do one more: Binary Tree Level Order Traversal.

Problem statement: Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Return the result as a list of lists, where each inner list contains the node values at that level.

Example:  

Output: [[3],[9,20],[15,7]]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 ≤ Node.val ≤ 1000

So here's the code:

IList<IList<int>> LevelOrder(TreeNode root)
{
    var result = new List<IList<int>>();

    if (root == null)
    {
        return result;
    }

    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        // Number of nodes at current level
        var levelSize = queue.Count;
        // Values for this level
        var currentLevel = new List<int>();

        // Process all nodes at the current level
        for (var i = 0; i < levelSize; i++)
        {
            TreeNode node = queue.Dequeue();
            currentLevel.Add(node.Value);

            // Enqueue children for the next level
            if (node.Left != null)
            {
                queue.Enqueue(node.Left);
            }
            if (node.Right != null)
            {
                queue.Enqueue(node.Right);
            }
        }

        result.Add(currentLevel);
    }

    return result;
}

TreeNode root = new()
{
    Value = 3,
    Left = new() { Value = 9 },
    Right = new()
    {
        Value = 20,
        Left = new() { Value = 15 },
        Right = new() { Value = 7 }
    }
};

var result = LevelOrder(root);
Console.WriteLine($"[ {string.Join(", ",result.Select(a=> $"[{string.Join(", ",a)}]"))} ]");

The time complexity is O(n) - we visit each node exactly once, the space complexity is O(w) - where w is the maximum width of the tree (size of the queue at the widest level), worst-case O(n) for a complete tree.

The inner for loop over queue.Count ensures we process one full level before moving deeper - that's what gives the level-by-level order. Without the level-size loop, you'd get a flat list instead of grouped by level.

DFS (recursive) can also collect levels (by passing depth parameter), but BFS feels more natural and intuitive for this exact requirement.

Conclusion

Exploring the solution space using graph traversal is a very powerful technique used in a lot of contexts. Go depth or breadth first, depending on the requirements, in order to get to the optimal solution.

• BFS: shortest path guarantee, but higher memory (queue can hold O(n) nodes)
• DFS: simpler recursion, lower memory in deep-but-narrow graphs, but no shortest-path promise
• When BFS loses: very deep trees, leading to recursion stack overflow risk (rare)
• Hybrid tip: use BFS when correctness > simplicity

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

  Today I will be covering depth first search (DFS) in tree/graph traversals.

When to use DFS

  Both DFS and BFS (Breadth First Search) are ways of exploring connected elements, but DFS comes more natural for people. You go as deep as you can, then backtrack when you get stuck. Unlike BFS, DFS explores exhaustively and doesn't care about levels. DFS is mostly used to find tree properties (depth, diameter), path finding, validation and most graph connectivity problems.

Recognize a problem that can be solved with DFS by these signs:

• it has a natural recursive structure (do the same thing for child/neighbor)
• you need to find a path or check the existence of one (and not necessarily the shortest one)
• the solution requires processing children/subtrees before their parents (height, diameter, subtree sum, bottom-up computation)
• is the problem about computing or validating a property along a path (path sum exists, is binary search tree (BST) valid, balanced tree, cycle exists)
• the input is a tree, binary tree, BST, N-ary tree, trie, or graph, and we do not need level-by-level processing or shortest-path distance

Basically you've got some kind of connected structure and you don't care about what happens on specific levels or you need to compare all paths to find the best.

Example - Maze path finding

The poster problem for DFS is maze path finding as it lends itself perfectly for the "go as deep as possible and backtrack" idea. Here is the problem statement:

Given a 2D grid representing a maze (0 = open path, 1 = wall), determine if there is a path from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can move in 4 directions (up, down, left, right), but cannot go through walls or outside the grid. Assume (0,0) and (m-1,n-1) are open (0).

Example grid:

var maze = new int[][]
{
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 0]
};

Let's look at the naive solution (recursion without visited marking):

bool HasPath(int[][] maze, int row, int col)
{
    var m = maze.Length;
    var n = maze[0].Length;

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return false;

    if (row == m - 1 && col == n - 1)
        return true;

    // Try all 4 directions
    return HasPath(maze, row - 1, col) ||  // up
           HasPath(maze, row + 1, col) ||  // down
           HasPath(maze, row, col - 1) ||  // left
           HasPath(maze, row, col + 1);    // right
}

var result = HasPath(maze, 0, 0);
Console.WriteLine(result);

Here we try all possible directions to get to a solution and the result is, because there are clearly several paths to the end... a StackOverflowException! This is the error thrown when the entire stack used internally for function recursion has been used up. In other words, we recursed ourselves out of memory. The problem is that we are going in loops forever: up, down, then up again and so on. The solution is marking the visited cells so that we don't do that:

bool HasPath(int[][] maze, int row, int col, 
    /* marking visited */bool[][] visited = null)
{
    var m = maze.Length;
    var n = maze[0].Length;

    // Initialize visited array on the first call
    if (visited == null)
    {
        visited = new bool[m][];
        for (int i = 0; i < m; i++)
            visited[i] = new bool[n];
    }

    if (row < 0 || row >= m || col < 0 || col >= n || maze[row][col] == 1)
        return false;

    if (row == m - 1 && col == n - 1)
        return true;

    // avoid cycles by not visiting the same cell again
    if (visited[row][col])
        return false;

    // mark the cell as visited
    visited[row][col] = true;

    // Try all 4 directions (with visited tracking)
    return HasPath(maze, row - 1, col, visited) ||  // up
           HasPath(maze, row + 1, col, visited) ||  // down
           HasPath(maze, row, col - 1, visited) ||  // left
           HasPath(maze, row, col + 1, visited);    // right
}

var result = HasPath(maze, 0, 0);
Console.WriteLine(result);

The result now is True, as expected.

Now, the path that this version of the code found is really inefficient, too, because of the way the choice of the direction is made, however, in "big O", the complexity is still time O(m*n) and space O(m*n) (because of the visited array). So remember that efficiency in theoretical terms is not the same as efficiency in engineering terms.

It's a nice idea to ponder on how would you alter the algorithm so that it doesn't always try to go back the way it came.

This code guarantees termination (a critical issue in recursive algorithms), avoids redundancy and finds a path - which is not necessarily optimal. Classic DFS. And it is depth first because it goes how far it can go before "backtracking" to a previous position and trying a new path. A breadth first search is obviously possible, but it would take a lot more resources. It would be the best solution for a requirement of finding the fastest path out of the maze, though.

Theory

Now you may have noticed that in this post about trees and graphs I presented something that works with arrays. That's because there is a lot - and I mean a lot - of theory related to graphs in computer science. Trees, too, but they are a special case of graphs, so... remember that when you walk outside looking for shade. OK, enough shade thrown on the computer scientists! It's just very easy to make fun of their hard work.

So let's delve a little in that theory by describing a few terms that will help us understand a true graph problem:

• A graph is a collection of points (called vertices or nodes) connected by lines (called edges)
  • Vertices / Nodes are the things you care about (people, cities, web pages, computers, tasks, etc.)
  • Edges are the relationships or connections between them (friendship, road, hyperlink, network cable, dependency, etc.)
• An undirected graph is a graph where the edges don't have a direction or rather they are always bidirectional. If A is connected to B, then B is connected to A.
• A directed graph (or a digraph) is a graph where edges have a direction. If an edge connects A to B, you need another edge to connect B to A.
• A connected graph is a graph where all the nodes are connected to at least another node.
• A cycle is a path that starts and ends at the same node.
• An acyclic graph is a graph with no cycles.
• A tree is a fully connected graph with no cycles. Trees are found everywhere because they represent hierarchies: parent-child relationships.
  • every tree is an acyclic graph, but not the other way around. An acyclic graph can have more than one components (separated groups of connected nodes). A tree has N-1 edges, where N is the number of nodes.
• A binary tree is a tree where a node has at most two children, usually called the left and the right child. Binary tree nodes are assholes, they think of one child as the right one and the other is just left out.
  • they are used a lot in computer science and algorithms, but we're not going to explain them here. As usual, follow the links in the blog to find out more, if you're interested.
  • we will need to know what a binary tree is for when we hear the term BST (Binary search tree) which is used for data structures with fast search, insert and delete.
• A binary search tree (BST) is a tree where:
  • the values of all the nodes in the left subtree are smaller than the value of the root node
  • the values of all the nodes in the right subtree are larger than the value of the root node
  • all subtrees are valid BSTs

Usually in these problems we get a class called TreeNode which holds an integer value and the two child nodes, something like this:

class TreeNode {
  public int Value {get;set;}
  public TreeNode Left {get;set;}
  public TreeNode Right {get;set;}
}

Use a struct or a record to show you're fancy, but then you will have to explain what's the difference between structs, records and classes.

Other problems use adjacency lists or some other ways of storing graph data.

With this nomenclature in mind, let's see some examples.

Example - Validate Binary Search Tree

Problem statement: Given the root of a binary tree, determine if it is a valid binary search tree.

The solution is simple:

bool IsValidBSTDfs(TreeNode node, int min=int.MinValue, int max=int.MaxValue)
{
    if (node == null) return true;

    if (node.Value <= min || node.Value >= max) return false;

    return IsValidBSTDfs(node.Left, min, node.Value)
        && IsValidBSTDfs(node.Right, node.Value, max);
}

I didn't provide a naive solution, because this is a very simple problem, but one of the common errors developers make in trying to solve it is to assume that if the node value of the current node is between left and right and then you recurse, the tree is a valid BST. However, that leads to cases where a value in the left subtree is larger than the root node or a smaller one in the right tree. Always check the requirements!

The time complexity of this is O(n), because it goes through all of the nodes once. The space complexity is O(h), where h is the height of the tree, with worse case scenario O(n) if a tree is composed of nodes with just one child and h=n.

Now you might ask how is this O(h) in space if there is a class for each node? Remember, the O notation measures the complexity of the solution, not of the problem. By recursing through h levels (even if that means it adds and removes n elements on the stack) the stack never increases with more than h elements.

Since we are talking about checking all nodes, a breadth first search is also possible. I will discuss this in the BFS post, but also in another post that I plan to do on how to NOT use the native language recursion and control the entire stack/queue yourself. When you do that, the code gets a little bit more complex, but then the difference between DFS and BFS becomes the choice between a stack and a queue. Stay tuned, it's going to be an instructive post.

Example - Cycle detection in directed graph

Problem statement: Given a directed graph (as adjacency list: List<List<int>> graph), detect if it contains a cycle. Nodes are labeled 0 to V-1, where V = graph.Count. A cycle exists if there's a path that starts and ends at the same node (following directions).

In this situation the data structure changes again. The node doesn't have a value, it just has a list of directions towards other nodes and is defined by its index. The structure holding this is a list of lists, where the index in the list represents the node and the value in the list is a list of indexes towards other nodes.

Let's try some code:

bool HasCycle(List<List<int>> graph, int node, bool[] visited=null)
{
    visited ??= new bool[graph.Count];
    if (visited[node]) return true;
    visited[node] = true;

    foreach (var neighbor in graph[node])
    {
        if (HasCycle(graph, neighbor, visited))
        {
            return true;
        }
    }

    return false;
}

List<List<int>> graph = [
    [1,2],
    [2],
    []
];
Console.WriteLine(HasCycle(graph, 0)); // Output: True

The idea here is simple: start with each neighbor of each node then recurse. If you find any node that has been visited before, you have a cycle. Or do you? The code above has a conceptual bug. Can you find it? Look at the example and tell me, is the output correct?

The answer is no. One can reach the same node multiple ways (in our case the index 2 node), but because it's a directed graph, it might not be necessarily a cycle. In our case, node 0 connects to node 1, which then connects to node 2, but node 0 also connects to 2 directly. There is no way to get from node 2 back to 0, though, so there is no cycle.

How would you solve it? The solution - in terms of code - is very simple, but one has to have seen the problem before or have a lot of time to find it. That's why I think this kind of problems are terrible for determining if you're a good developer, but I digress. Here is the working solution:

bool HasCycle(List<List<int>> graph, int node, int[] visited=null)
{
    visited ??= new int[graph.Count];
    visited[node] = 1;

    foreach (var neighbor in graph[node])
    {
        if (visited[neighbor] == 1) return true;
        if (visited[neighbor] == 0 && HasCycle(graph, neighbor, visited))
        {
            return true;
        }
    }
    visited[node] = 2;
    return false;
}

List<List<int>> graph = [
    [1,2],
    [2],
    []
];
Console.WriteLine(HasCycle(graph, 0)); // Output: False

graph =
[
    [1],
    [2],
    [0]
];
Console.WriteLine(HasCycle(graph, 0)); // Output: True

Simply replace the type of the visited array to int, mark a node as "visiting" with 1, then as "visited" with 2. You ignore visited nodes, but if you find one that is in visiting state as a neighbor, then you're in a cycle.

Note: this would be a lot more readable with a three state Enum, and if you feel like it go for it. People will appreciate making the code more readable. But it will take you some extra time to write up the Enum definition, so this is - in my eyes - another reason why these tests measure the wrong thing.

The time complexity of this algorithm is O(V+E) where V is the number of vertices/nodes and E is the number of edges. The space complexity is O(V), as we create an array of size V as part of the solution.

Example - Maximum path sum in DAG

This one is very hard to figure out, but easy to implement. You just have to have a feeling for these things to get past the more obvious gotchas.

Problem statement: 

• You are given a directed acyclic graph (DAG) with n nodes numbered from 0 to n-1.
• The graph is given as an adjacency list: graph[i] = list of nodes you can go to directly from node i.
• Each node has a value given in array values[0..n-1].
• Return the maximum sum of node values you can collect by following any path in the graph

Example:

int[] values = [1, -2, 3, 4];
int[][] graph = [[1, 2], [3], [3], []];

This problem is deceptive for multiple reasons:

• It looks like "longest path" so people think NP-hard
• But it's a DAG, so longest path is solvable in linear time
• Many people waste time trying brute force / backtracking / permutations
• Many try to keep track of visited nodes unnecessarily (not needed in DAG)
• The correct insight is subtle for many: "longest path ending at each node" is easy to compute with DP + DFS
• Negative values make greedy impossible
• Large n forbids O(n²) solutions
• You must memoize properly or you'll exceed the accepted time limit
• The DP state "maximum path ending at node X" is not the first thing most people think of

The post is long enough already, so here is the code:

int[] values = [1, -2, 3, 4];
int[][] graph = [[1, 2], [3], [3], []];

int MaxPathSum(int[] values, IList<IList<int>> graph)
{
    var n = values.Length;
    var memo = new int?[n];   // longest path ending at i

    var globalMax = int.MinValue;

    for (var i = 0; i < n; i++)
    {
        globalMax = Math.Max(globalMax, Dfs(i, values, graph, memo));
    }

    return globalMax;
}

int Dfs(int node, int[] values, IList<IList<int>> graph, int?[] memo)
{
    if (memo[node].HasValue)
        return memo[node].Value;

    var best = values[node];   // just this node

    foreach (var nei in graph[node])
    {
        // take the best path ending at nei + current node
        int candidate = values[node] + Dfs(nei, values, graph, memo);
        best = Math.Max(best, candidate);
    }

    memo[node] = best;
    return best;
}

Console.WriteLine(MaxPathSum(values, graph));

A bonus in this implementation is methods using IList and accepting arrays. You've forgotten that arrays implement IList, didn't you?

Example - Topological sort (Course Schedule)

Another very common use of DFS on Directed Acyclic Graphs (DAGs) is Topological sorting, producing a linear ordering of nodes such that for every directed edge u -> v, node u comes before node v in the ordering.

Use it when you need to process tasks, courses, or build steps in the correct dependency order (build systems, task scheduling, course prerequisites, etc.). If the graph has a cycle, a valid order is impossible.

The DFS trick is simple: we perform the same traversal as in Example 3 (cycle detection), but we also record each node after all its children have been processed (post-order). When we reverse that list we get the topological order. The three-state visited array (0 = unvisited, 1 = visiting, 2 = visited) detects cycles exactly like before.

Let’s see it in action with the classic Course Schedule problem.

Problem statement: There are numCourses courses you have to take and you are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai.  Return true if you can finish all courses (i.e. there is a valid topological order), otherwise false.

Here’s the complete solution:

bool CanFinish(int numCourses, int[][] prerequisites)
{
    // Build adjacency list: graph[u] contains all courses that depend on u
    var graph = new List<int>[numCourses];
    for (var i = 0; i < numCourses; i++)
        graph[i] = [];

    foreach (var p in prerequisites)
    {
        graph[p[1]].Add(p[0]); // p[1] -> p[0] (prereq before course)
    }

    var visited = new int[numCourses]; // 0 unvisited, 1 visiting, 2 visited
    var order = new List<int>();       // will store post-order (reverse topo)

    for (var i = 0; i < numCourses; i++)
    {
        if (visited[i] == 0 && !Dfs(i, graph, visited, order))
            return false;
    }

    // If we reached here there is no cycle -> valid topological order exists
    // order is in reverse; if you need the actual order just do order.Reverse()
    return true;
}

bool Dfs(int node, List<int>[] graph, int[] visited, List<int> order)
{
    visited[node] = 1; // visiting (gray)

    foreach (var nei in graph[node])
    {
        if (visited[nei] == 1) return false; // cycle!
        if (visited[nei] == 0 && !Dfs(nei, graph, visited, order))
            return false;
    }

    visited[node] = 2; // visited (black)
    order.Add(node);   // record finishing time
    return true;
}

var numCourses = 4;
int[][] prerequisites = [
    [1, 0],
    [2, 0],
    [3, 1],
    [3, 2]
];

Console.WriteLine(CanFinish(numCourses, prerequisites)); // true

Complexity

Time: O(V + E) - we visit every node and edge exactly once.

Space: O(V) for the visited array, recursion stack, and adjacency list.

Notice how this re-uses the exact cycle-detection pattern from Example 3. The only new thing is pushing nodes to the order list after their dependencies are fully explored. If you want the actual ordering just return order reversed at the end.th extra preprocessing.

This technique is extremely common in system-design interviews too (task dependency graphs, build pipelines, etc.).

Conclusion

Graph theory is a very large and important category in computer science, so explaining all of it simply in a post or two is impossible. But I hope I've clarified a lot of stuff related to the field, at least in regards to interview questions. DFS is one of the most versatile tools in your interview toolbox. Once you get comfortable with the recursive pattern (visit node -> recurse on children/neighbors -> backtrack), you'll start seeing it everywhere: trees, graphs, backtracking, path problems, cycle detection, and more.

Intro

  At the moment I am looking for a job, so I was forced to enter the world of technical interviews and the weird places like Hackerrank and Leetcode. They absolutely suck, but they have some interesting problems that generations of developers have tried to solve. In my mind there are two kinds of problems: the ones that can be solved with a little thinking and the ones that require some sort of a priori computer science knowledge. Since I have not had a formal software development education and since no matter how many jobs I've had, they always ask me about algorithms, but then I never have to use them, the ones requiring such esoterics always scare me.

  Compounding this is the fact that documentation about such concepts is made for people in computer science courses by people teaching computer science courses, which are usually some kind of math people at heart. 90% of the effort of understanding any of that is reading through their obtuse formalizations. So I've decided I would help myself and other fellow programmers understand these concepts in a way that can be understood.

  In my research into these coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall 

  Today I will be covering Dynamic Programming (DP), which solves optimizations with overlapping subproblems. And no, I will not be making crass jokes about the abbreviation because I am a motherfucking gentleman.

When to use Dynamic Programming

  Recognize a problem that can be solved with DP by these signs:

• it is too slow to solve with brute force
• the solution for the problem can be built from best solutions to subproblems
• the same subproblems (yielding the same result) need solving multiple times

Example - Fibonacci

  The poster problem for this category is Fibonacci numbers. It's funny, but when I first learned about this series of numbers I was in school, and I knew more math than programming. When you start with the mathematical definition of the Fibonacci function, the naive computer implementation is terrible, so learning Dynamic Programming with this seems reasonable. But after decades away from school, when presented with the problem, the implementation cannot be more different.

  Here is the general definition: a function F(x) which for 0 and 1 returns a defined number, then for any other x, it is computed as F(x-1)+F(x-2). Let's write this in C#, just so you see how silly it is:

int F(int x)
{
    if (x == 0) return 0;
    if (x == 1) return 1;
    return F(x - 1) + F(x - 2);
}

Readable, functional, faithful to the mathematical function, but completely inefficient. Let's add a counter to see how many times this function gets executed:

(int result,int count) F(int x)
{
    if (x == 0) return (0,1);
    if (x == 1) return (1,1);
    var (r1, c1) = F(x - 1);
    var (r2, c2) = F(x - 2);
    return (r1+r2, c1 + c2);
}

// F(10) returns (55, 89)
// F(20) returns (6765, 10946)
// F(30) returns (832040, 1346269)

Now let's think about the problem as a software developer. The client needs the last value of a series of numbers that start with 0, 1, and then add the last two numbers in the series to get the next one. It's an iteration function. The result, when you think about it in these terms, becomes obvious:

// loop solution
(int result, int count) F(int x)
{
    if (x == 0) return (0, 1);
    if (x == 1) return (1, 1);
    var (x1,x2) = (0,1);
    var c = 1;
    for (int i = 2; i <= x; i++)
    {
        (x1,x2) = (x2, x1 + x2);
        c++;
    }
    return (x2, c);
}

// F(30) returns (832040, 30)

So we optimized a function to run 30 times instead of 1.35 million times. Quite an improvement, and all it took was thinking like a software engineer, not like a math geek. This type of solution is called "bottom up dynamic programming" or "tabulation" and is usually the most efficient one. However, there is another solution called "top-down dynamic programming" or "memoization" which is what some computer science guys expect. Let's take a look:

var memo = new Dictionary<int, int>();

int F(int n)
{
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];

    memo[n] = F(n - 1) + F(n - 2);
    return memo[n];
}

Here we used the naive structure of the code, preserving the math semantics, but cached the results of the function for known values. This is actually the kind of stuff they expect from you, even if it's clearly less efficient! Because that's what they teach in school as an example. It's the printing of "hello, world!" and the unit test for a calculator class that only knows how to add two numbers all over again.

Yet, there is a very good reason to use memoization sometimes and that is if you plan to run the function multiple times using the same dictionary. You are basically constructing a table of key/value pairs and using that to cache the results. An even more efficient implementation - in this case - is using a List<int> rather than a dictionary, since the keys are sequential integers. Since you know you are going to need all values from 0 to n to calculate F(n), then you can already create/expand the list to have N items. 

They will also ask about complexity or the "Big O notation". If you don't know what that is, it's a fancy notation for describing the magnitude of time and space used by the algorithm. The naive implementation is O(Fibonacci(n+1)) in time, which is funny, as it describes the complexity with the function you're supposed to implement. The tabulation and the memoization versions are O(n) in time, or "linear", the complexity increases linearly with n. The space complexity is theoretically O(1) or "constant" for the naive and the tabulation version, while the memo version is O(n) because we store all n values in the dictionary with n keys..

I said theoretically, because practically, for the naive and memo versions, there is also extra overhead because of the recursive nature of the implementation. The data for each execution will be stored in the stack, which adds another O(n) in space and is also limited in size. Learn about Stack vs. Heap in programming and well as the Big O notation separately, if you want to drill down.

Theory

The definition sounds like this: Dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time. 

Two ways to do it:

• Top-down + Memoization - Start from the big problem, recurse down, but cache results in a dictionary/array so each unique subproblem is solved only once.
• Bottom-up + Tabulation - Start from the smallest subproblems, build a table iteratively up to the full problem. Usually uses less stack and is faster in practice.

The memoization approach is often easier and more natural, but every problem that can be solved with memoization can usually be solved with tabulation as well. If a problem has a correct recursive formulation with overlapping subproblems, you can always rewrite it as an iterative bottom-up solution by carefully filling a table (or multiple tables) in the right dependency order. The vast majority of DP problems taught and asked in interviews (Fibonacci, knapsack, coin change, longest common subsequence (LCS), edit distance, matrix chain multiplication, longest increasing subsequence, house robber, word break, regex matching, etc.) have clean bottom-up solutions.

Common Pitfalls & Trade-Offs

• Initialize dp correctly! (Often dp[0]=0 or 1, others int.MaxValue or -1)
• Watch for off-by-one (array size amount+1)
• Memo dict vs array: array/list is faster and uses less memory for integer keys 0..N
• Space: top-down can use O(N) stack + O(N) memo; bottom-up usually just O(N)
• When amount N is huge (>10⁵ - 10⁶), DP might not fit - look for math or greedy instead

Example - Coin change (minimum coins)

Let's take another example, the exact change coin problem. 

Problem: Given coins[] of different denominations and int amount, return the fewest coins needed to make exactly amount. Infinite supply of each coin. If impossible, return -1.

The memoization solution comes easier, because it's an iterative fix of the naive implementation:

Dictionary<int, List<int>?> memo = []; // memo: Memoization dictionary to store results for subproblems

IList<int> CoinChange(int[] coins, int amount)
{
    var result = FindMinCoins(coins, amount);
    return result ?? [];
}

List<int>? FindMinCoins(int[] coins, int remaining)
{
    if (remaining == 0)
        return [];

    if (remaining < 0)
        return null;

    if (memo.ContainsKey(remaining)) // memo: Check if the result for this amount is already computed
        return memo[remaining];

    List<int>? best = null;

    foreach (var coin in coins)
    {
        var subResult = FindMinCoins(coins, remaining - coin);
        if (subResult != null)
        {
            var candidate = new List<int>(subResult) { coin };
            if (best == null || candidate.Count < best.Count)
            {
                best = candidate;
            }
        }
    }

    memo[remaining] = best; // memo: Store the computed result in the memoization dictionary
    return best;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

The lines with "memo:" comments are the difference between the naive and memoized versions.

So what did we do here? We started with the total amount of money and tried every single coin. Once a coin is used, the amount decreases with the value of the coin. If the amount if negative, we overspent and return null for an unusable solution. If the amount is 0, then we return an empty array and stop the recursive processing. If the amount is larger than zero, we now have to solve the exact same problem, but with a smaller amount.

Let's see the tabulation solution.

IList<int> CoinChange(int[] coins, int amount)
{
    if (amount == 0) return [];

    var dp = new int[amount + 1];     // dp[i] will hold the minimum number of coins needed for amount i
    var prev = new int[amount + 1];   // to reconstruct the solution

    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;

    for (var i = 1; i <= amount; i++)
    {
        foreach (var coin in coins)
        {
            if (i >= coin && dp[i - coin] != int.MaxValue)
            {
                var candidate = dp[i - coin] + 1;
                if (candidate < dp[i])
                {
                    dp[i] = candidate;
                    prev[i] = coin;          // remember which coin we used
                }
            }
        }
    }

    if (dp[amount] == int.MaxValue)
        return [];          // impossible

    // Reconstruct the list of coins
    List<int> result = [];
    var current = amount;

    while (current > 0)
    {
        var coin = prev[current];
        result.Add(coin);
        current -= coin;
    }

    return result;
}

var result = CoinChange([1, 5, 10, 25], 30);
Console.WriteLine("["+string.Join(", ", result)+"]"); // returns [25, 5]

A lot more daunting, but simple once you "get it":

• We store everything in arrays, where the index is the amount. I guess one could use dictionaries instead, but for small amounts - like the ones used in interview questions - the size of the array is less important than the efficiency of execution of the index in a static array.
• We fill the array with int.MaxValue, so that any other value is preferable
• We use the prev array to store the coin we last used for every calculation - smart solution to allow us to reconstruct the list of coins
• when we just calculate and store the number of coins for each amount up to the desired amount.

It's just like the Fibonacci thing, only more complicated.

Conclusion

Use Dynamic Programming when a problem can be split into smaller pieces that get executed multiple times, yielding the same result each time. The top down approach is more intuitive, but the bottom up approach is usually more efficient.

Intro

  Another new feature in .NET that I absolutely love: Raw string literals.

  You probably know about normal strings: they start with a double quote and end with a double quote and every special character, including a double quote, has to be escaped with a backslash. You also know about verbatim strings: they start with @ and then a double quote and can contain any string, including new line characters, with the only exception being the double quote character which must be doubled to be escaped. Great for JSON with single quotes, not so great for XML, for example, but still better than escaping everything with slashes. You might even know about interpolated strings, starting with a $ and supporting templates. I wrote a blog post about it. It can be used with all the other types of strings.

  If you worked with markup language - used in web rich text editors and blogs and instant messengers - you might have used a special syntax for indicating "blocks of code". You do it by enclosing a line of code with backticks (`) or by using three backticks, followed by a new line, then multiple lines of code, then three other backticks to close the block. You can even use something like ```csharp to indicate that the syntax highlighting is supposed to be for C#.

Well, this feature has finally been added to C# itself, just that instead of backticks you use double quotes and you use a // lang = ... comment above it to declare the highlighting - even if Visual Studio and other editors know to recognize common structures like XML and JSON and stuff like that.

Details

This is great for so many things, but I love that it improves readability and allows syntax checking of the content. Check this out:

I specified that this is Regex, so it automatically warned me that I missed a closing parenthesis.

It's really cool for XMLs:

Although for some reason it didn't do syntactic highlighting, look how nice it looks: no doubled or escaped double quotes. You can read the XML, you can copy paste it as it is. This is a thing of beauty. Also, note that the whitespace between the content and the literal string block delimiters is ignored! This didn't happen with verbatim strings, much to my chagrin. In the example above, the first character of the resulting string is less-than (<) and the last is greater-than (>)

But wait... what happens if you want to have three double quotes in the literal string? Why? Because you can. Did you find the Achilles heel for literal strings? No! Because you can have a minimum of three double quotes to declare a literal string. You want three double quotes in the literal? Fine, start and end the literal string with four double quotes!

This leave me to the example in the first image. One can use a ton of double quotes that will not only declare a literal string, but also visually delimit it from the surrounding text. This is the future! If you have more string content than double quotes, something must be really wrong.

More reading

Raw string literal feature specification

  Intro

  Finally a technical blog post after so long, right? Well, don't get used to it 😝

  I just learned about a .NET 6 feature, improved in .NET 9, that can help organize your logging, making it both more efficient and readable in the process. This is Compile-time logging source generation, a way to define logger messages in partial classes using attributes decorating method stubs. Source code generators will then generate the methods, which will be efficient, have a readable name and not pollute your code with a log of logging logic.

  There are some constraints that you must follow:

• Logging methods must be partial and return void.
• Logging method names must not start with an underscore.
• Parameter names of logging methods must not start with an underscore.
• Logging methods cannot be generic.
• If a logging method is static, the ILogger instance is required as a parameter
• Code must be compiled with a modern C# compiler, version 9 (made available in .NET 5) or later

As a general rule, the first instance of ILogger, LogLevel, and Exception are treated specially in the log method signature of the source generator. Subsequent instances are treated like normal parameters to the message template.

Details

Here is an example:

public static partial class Log
{
    [LoggerMessage(
        EventId = 0,
        Level = LogLevel.Critical,
        Message = "Could not open socket to `{HostName}`")]
    public static partial void CouldNotOpenSocket(
        this ILogger logger, string hostName);
}

// use like this:
_logger.CouldNotOpenSocket(hostName);

There is support to specifying any of the parameters required in the logger message as method parameters, if you want a hybrid approach.

You can use both static and instance methods - as long as they conform to the rules above.

You can use other attributes to define sensitive logging parameters, a thing called Redaction, like this:

// if you have a log message that has a parameter that is considered private:
[LoggerMessage(0, LogLevel.Information, "User SSN: {SSN}")]
public static partial void LogPrivateInformation(
    this ILogger logger,
    [MyTaxonomyClassifications.Private] string SSN);

// You will need to have a setting similar to this:
using Microsoft.Extensions.Telemetry;
using Microsoft.Extensions.Compliance.Redaction;

var services = new ServiceCollection();
services.AddLogging(builder =>
{
    // Enable redaction.
    builder.EnableRedaction();
});

services.AddRedaction(builder =>
{
    // configure redactors for your data classifications
    builder.SetRedactor<StarRedactor>(MyTaxonomyClassifications.Private);
});

public void TestLogging()
{
    LogPrivateInformation("MySSN");
}

// output will be: User SSN: *****

The generator gives warnings to help developers do the right thing.

You can supply alternative names for the template placeholders and use format specifiers.

More to read

Message Templates

Intro

Welcome to sparse arrays, a JavaScript concept that completely escaped me until now. Let's dig into it.

I wanted to create a game board, an array of 8 rows, themselves arrays of 8 elements so I unthinkingly did a const row=Array(8). I used a console.table on it and it was displayed in a stupid way, but I blamed it on Google devs and moved on. I didn't understand something was amiss until I did a .forEach on a row array that had only three pieces on it and it was executed just three times. What was going on?

Explanation

Well, when you use the Array(integer) constructor you get a sparse array. It has a length, it has items, but it is not a contiguous memory space with N slots for values. The same thing happens when you omit an element from an array declaration, like [1,,2] which is a sparse array different from [1, undefined, 2]. A normal array, in this context, is called a dense array.

In other words, sparse arrays work differently in for and forEach loops! It's almost like an empty object with a length property that has array methods working for it. Think about this code for example:

const arr = { length: 8 }
arr[1]='something';

// displays 8 lines, where only the second is 'something' and the rest are undefined
for (let i=0; i<arr.length; i++) console.log(arr[i]);

// simulated forEach - displays only 2 lines: something and 8
Object.values(arr).forEach(v=>console.log(v));

The simplest way to transform a sparse array into a dense array is to iterate it, like this: [...sparseArray]. You can create a dense array with Array.from( { length:8 } ), however new Array(8) or Array(8) will return a sparse array.

If you look in the docs, sparse arrays are often used with .fill, like this: Array(8).fill(undefined), which will return an array of 8 undefined elements.

Going deeper

So, wait... now there are two types of arrays, they function differently, they must be different classes, right? Actually, no! These are just concepts that apply to Array. Let's see some code:

const x = [1]; // dense array
x.length=10; // sparse array, all slots except the first are 'empty'.
x.fill(2); // dense array, all slots are filled with the value 2
x[1]=undefined; // dense array, second slot contains undefined
delete x[3]; // sparse array, fourth slot is 'empty'
// 1 in x == true;
// 3 in x == false;

What is this madness? This is something new introduced by nasty people who just want to make everything complicated, right? Actually, no. Arrays were always sparse, from the very beginning of the language in 1995. The concept itself was formalized in 2009 for ES5, though, where it was explicitly said that for..in and for..of and forEach, map, filter, etc, will skip empty slots.

Conclusion

JavaScript arrays are misnomers and different from the previous concept of array, used in languages like C or .NET, a fixed and contiguous memory space to store elements based on a positional index. JavaScript arrays are complex objects that allow insertion and removal of items, resizing and, yes, sparsity.

You can work in JavaScript for years and years and still get blindsighted by something like this...

  Array.from is a JavaScript function that until now, I've used exclusively to transform an iterable into an array. I had never considered the powerful factory functionality that it provides, because its declared signature is deceptively simple: Array.from(arrayLike, mapFn, thisArg). So you get something that's like an array (an interable, right?) then you map it (phaw, like I don't know how to map an array!) and a thisArg probably sets the this context for the function (like I don't know how to bind a function!)

  And yet...

  The first "array-like" parameter  doesn't need to be an iterable, it can be an object with a length. Meaning that you can just do something a number of times.

  Example for creating a range: 

// Sequence generator function (commonly referred to as "range", cf. Python, Clojure, etc.)
const range = (start, stop, step) =>
  Array.from(
    { length: Math.ceil((stop - start) / step) },
    (_, i) => start + i * step,
  );

  Getting a sample from an array of string:

const sample = (arr, count) =>
  Array.from(
    { length: count },
    ()=>arr[Math.floor(Math.random()*arr.length)]
  );

  How about generating a random string?

const chars = 'abcdefghijklmnopqrstuvwxyz';
const randomString = (length) =>
  Array.from({ length }, () => chars[Math.floor(Math.random() * chars.length)]).join('');

// OR using the sample function above

const randomString = (length) =>
  sample('abcdefghijklmnopqrstuvwxyz',length).join('');

  And if you don't want an array, but something "array-like", like a NodeList?

class MyClass {}

Array.from.call(MyClass, ["foo", "bar", "baz"]);
// MyClass {0: 'foo', 1: 'bar', 2: 'baz', length: 3}

  I admit Array.from(a,b,c) is functionally equivalent to Array.from(a).map(b.bind(c)), but it's more efficient, as the array is constructed only once. The power of this function comes from its interpretation of the "array-like" first argument. It takes iterable objects and/or containing a length property, thus allowing a more concise, functional way of writing code and avoiding unnecessary loops.

Hope it helps!

  Yep, it's is that easy, thanks to code added by the Chromium devs. You just make sure the focus is on the HTTPS error page, then type "thisisunsafe". A lot more details here: thisisunsafe - Bypassing chrome security warnings.

  Is it a good idea? Probably not. Will it be remove by Google devs some time in the future? Probably yes. But sometimes you just need to access that site and don't care about other stuff.

  Hope it helps!

  A while ago I wrote a browser extension called Bookmark Explorer that no one used because it had such a banal name, but it was pretty cool. I just let it die when Google took it down for being a manifest V2 extension. I plan to modernize it and make it work for modern browsers. It is now also renamed as...

Bookmark Surfer Daedalus!

  OK, it's still a silly name, but you know how naming is the hardest part, right?

  This blog post will become the official web page for the extension.

  But what does it do? Well, it allows to easily navigate in bookmark folders. Let's say you have one of those folders with hundreds of links or you, like me, open a hundred YouTube videos that you plan to eventually watch (yeah, right!) and your main memory consumption is keeping those tabs in the background. Now all you have to do is just put all of these into bookmark folders and open the first one. From it, you can quickly go forward or backward with either mouse or key combinations. The next page in the folder will be preloaded while you read the current one, so that you switch faster.

  Features:

• right click on a link and add it to the Read Later folder without having to open it (the extension opens it in the background to get the final URL and the title of the page, then closes it immediately)
• click on extension button to get a popup with arrows forward/backward to navigate in whichever folder the current page is bookmarked in. You also get a button to move the current page to the end of the folder, so as to read it later than the others.
•  use Ctrl-Shift-K/L for backward/forward navigation. You can also change the key shortcuts in the browser.
• define patterns that determine what makes a URL unique. For example some web sites have different pages with the exact same URL, but a parameter changed, like YouTube or some blog platforms. Maybe even hashes. You can define the pattern for those domains. The normal pattern is just the domain and the path, ignoring query parameters and hashes.
• manage the bookmarks in the current folder. You can select them individually, delete them, move them to the end or the start and so on.
• see the bookmarks that you deleted - whether with the extension or some other mechanism - and choose which one to permanently remove or restore to their original location.
• notifications of pages that you bookmarked multiple times
• you can export the URLs of the selected items in an entire folder

  This extension is essential for people who read a lot on the Internet, like researchers or simply people who love information.

Intro

In the .NET world one of the most used method of accessing databases is with Entity Framework (EF), an Object Relational Mapper (ORM) that is tightly integrated with the language syntax. Using the Language Integrated Queries (LINQ) native to .NET languages, it makes data access feel like working with normal .NET collections, without much knowledge of SQL. This has its benefits and drawbacks that I will try not to rant about here. But one of the issues that it consistently creates is confusion regarding the structure of the software project, levels of abstractions and ultimately unit testing.

This post will try to explain why the repository abstraction is ALWAYS useful. Note that many people use repository as a term for abstracted data access, while there is also a repository software pattern which relates to similar things, but it's not the same thing. In here, I will call a repository a series of interfaces abstracting the implementation details of data access and ignore the design pattern completely.

History

Feel free to skip this if you are aware of it, but I have to first address how we got to the idea of repositories to begin with.

In prehistory, code was just written as is, with no structure, everything in, doing what you wanted it to do or at least hoping to. There was no automated testing, just manual hacking and testing until it worked. Each application was written in whatever was on hand, with concerns about hardware requirements more important than code structure, reuse or readability. That's what killed the dinosaurs! True fact.

Slowly, patterns started to emerge. For business applications in particular, there was this obvious separation of the business code, the persistence of data and the user interface. These were called layers and soon separated into different projects, not only because they covered different concerns, but also because the skills necessary to build them were especially different. UI design is very different from code logic work and very different from SQL or whatever language or system was used to persist data.

Therefore, the interaction between the business and the data layer was done by abstracting it into interfaces and models. As a business class, you wouldn't ask for the list of entries in a table, you would require a filtered list of complex objects. It would be the responsibility of the data layer to access whatever was persisted and map it to something understandable to business. These abstractions started to be called repositories.

On the lower layers of data access, patterns like CRUD quickly took over: you defined structured persistence containers like tables and you would create, read, update or delete records. In code, this kind of logic will get abstracted to collections, like List, Dictionary or Array. So there was also a current of opinion that repositories should behave like collections, maybe even be generic enough to not have other methods than the actual create, read, update and delete.

However, I strongly disagree. As abstractions of data access from business, they should be as far removed from the patterns for data access as possible, instead being modelled based on the business requirements. Here is where the mindset of Entity Framework in particular, but a lot of other ORMs, started clashing with the original idea of repository, culminating with calls to never use repositories with EF, calling that an antipattern.

More layers

A lot of confusion is generated by parent-child relationships between models. Like a Department entity with People in it. Should a department repository return a model containing people? Maybe not. So how about we separate repositories into departments (without people) and people, then have a separate abstraction to map then to business models?

The confusion actually increases when we take the business layer and separate it into sublayers. For example, what most people call a business service is an abstraction over applying specific business logic only to a specific type of business model. Let's say your app works with people, so you have a model called Person. The class to handle people will be a PeopleService, which will get business models from the persistence layer via a PeopleRepository, but also do other things, including a mapping between data models and business models or specific work the relates only to people, like calculating their salaries. However, most business logic uses multiple types of models, so services end up being mapping wrappers over repositories, with little extra responsibility.

Now imagine that you are using EF to access the data. You already have to declare a DbContext class that contains collections of entities that you map to SQL tables. You have LINQ to iterate, filter and map them, which is efficiently converted into SQL commands in the background and give you what you need, complete with hierarchical parent-child structures. That conversion also takes care of mapping of internal business data types, like specific enums or weird data structures. So why would you even need repositories, maybe even services?

I believe that while more layers of abstraction may seem like pointless overhead, they increase the human understanding of the project and improve the speed and quality of change. There is a balance, obviously, I've seen systems architected with the apparent requirement that all software design patterns be used everywhere. Abstraction is only useful if it improves code readability and separation of concerns.

Reason

One of the contexts where EF becomes cumbersome is unit testing. DbContext is a complicated system, with a lot of dependencies that one would have to manually mock with great effort. Therefore Microsoft came with an idea: in memory database providers. So in order to test anything, you just use an in memory database and be done with it.

Note that on Microsoft pages this method of testing is now marked with "not recommended". Also note that even in those examples, EF is abstracted by repositories.

While in memory database tests work, they add several issues that are not easy to address:

• setting up an in memory DbContext requires all of the dependencies to existing entities
• setting up and starting the memory database for each test is slow
• in order to get valid database output you need to set up a lot more than what you want to atomically test

Therefore, what ends up happening is that people set up everything in the database within a "helper" method, then create tests that start with this inscrutable and complex method to test even the smallest functionality. Any code that contains EF code will be untestable without this setup.

So one reason to use repositories is to move the testing abstraction above DbContext. Now you don't need a database at all, just a repository mock. Then test your repo itself in integration tests using a real database. The in memory database is very close to a real database, but it is slightly different, too.

Another reason, which I admit I've rarely seen be of actual value in real life, is that you might want to change the way you access the data. Maybe you want to change to NoSql, or some memory distributed cache system. Or, which is much more likely, you started with a database structure, perhaps a monolithic database, and now you want to refactor it into multiple databases with different table structures. Let me tell you right off the bat that this will be IMPOSSIBLE without repositories.

And specific to Entity Framework, the entities that you get are active records, mapped to the database. You make a change in one and save the changes for another and you suddenly get the first entity updated in the db, too. Or maybe you don't, because you didn't include something, or the context has changed.

The proponents of EF always hype the tracking of entities as a very positive thing. Let's say you get an entity from the database, you then do some business, then you update the entity and save it. With a repo you would get the data, then do business, then get the data again in order to perform a little update. EF would keep it in memory, know it wasn't updated before your change, so it would never read it twice. That's true. They are describing a memory cache for the database that is somehow aware of database changes and keeps track of everything you handle from the database, unless instructed otherwise, bidirectionally maps database entries to complex C# entities and tracks changes back and forth, while being deeply embedded in the business code. Personally, I believe this plethora of responsibilities and lack of separation of concerns is a lot more damaging than any performance gained by using it. Besides, with some initial effort, all that functionality can still be abstracted in a repository, or maybe even another layer of memory caching for a repository, while keeping clear borders between business, caching and data access.

In fact, the actual difficulty in all of this is determining the borders between systems that should have separate concerns. For example, one can gain a lot of performance by moving filtering logic to stored procedures in the database, but that loses testability and readability of the algorithm used. The opposite, moving all logic to code, using EF or some other mechanism, is less performant and sometimes unfeasible. Or where is the point where data entities become business entities (see the example above with Department and Person)?

Perhaps the best strategy is to first define these borders, then decide on which technology and design are going to fit into that.

My conclusion

I believe that service and repository abstractions should always be used, even if the repository is using Entity Framework or other ORM underneath. It all boils down to separation of concerns. I would never consider Entity Framework a useful software abstraction since it comes with so much baggage, therefore a repository much be used to abstract it in code. EF is a useful abstraction, but for database access, not in software.

My philosophy of software writing is that you start with application requirements, you create components for those requirements and abstract any lower level functionality with interfaces. You then repeat the process at the next level, always making sure the code is readable and it doesn't require understanding of the components using or the ones used at the current level. If that's not the case, you've separated concerns badly. Therefore, as no business application ever had requirements to use a specific database or ORM, the data layer abstraction should hide all knowledge of those.

What does business want? A filtered list of people? var people = service.GetFilteredListOfPeople(filter); nothing less, nothing more. and the service method would just do return mapPeople(repo.GetFilteredListOfPeople(mappedFilter)); again nothing less or more. How the repo gets the people, saves the people or does anything else is not the concern of the service. You want caching, then implement some caching mechanism that implements IPeopleRepository and has a dependency on IPeopleRepository. You want mapping, implement the correct IMapper interfaces. And so on.

I hope I wasn't overly verbose in this article. I specifically kept code examples out of it, since this is more of a conceptual issue, not a software one. Entity Framework may be the target of most of my complaints here, but this applies to any system that magically helps you in small things, but breaks the important ones.

Hope that helps!

A few years ago I wrote about this, but in less detail. Here is a more refined version of the same idea.

Intro

Unit tests are both boon and bane to developers. They allow quick testing of functionality, readable examples of use, fast experimentation of scenarios for just the components involved. But they also can become messy, need maintenance and update with every code change and, when done lazily, can't hide bugs rather than reveal them.

I think the reason unit testing is so difficult is because it's associated with testing, something other than code writing, and also that unit tests are written in a way opposite to most other code we write.

In this post I will give you a simple pattern of writing unit tests that will enhance all the benefits, while eliminating most of the cognitive dissonance with normal code. Unit tests will remain readable and flexible, while reducing duplicate code and adding no extra dependencies.

How to unit test

But first, let's define a good unit test suite.

To properly test a class, it has to be written in a certain way. In this post we will cover classes using constructor injection for dependencies, which is my recommended way of doing dependency injection.

Then, in order to test it, we need to:

• cover positive scenarios - when the class does what it's supposed to do, with various combinations of setup and input parameters to cover the whole functionality
• cover negative scenarios - when the class fails in the correct way when the setup or input parameters are wrong
• mock all external dependencies
• keep all of the test setup, action and assertion in the same test (what is normally called the Arrange-Act-Assert structure)

But that's easier said than done, because it also implies:

• setting up the same dependencies for every test, thus copying and pasting a lot of code
• setting up very similar scenarios, with just one change between two tests, again repeating a lot of code
• generalizing and encapsulating nothing, which is what a dev would normally do in all of their code
• writing a lot of negative cases for few positive cases, which feels like having more testing code than functional code
• having to update all of these tests for every change to the tested class

Who loves that?

Solution

The solution is to use the builder software pattern to create fluid, flexible and readable tests in the Arrange-Act-Assert structure, while encapsulating setup code in a class complementing the unit test suite for a specific service. I call this the MockManager pattern.

Let's start with a simple example:

// the tested class
public class Calculator
{
    private readonly ITokenParser tokenParser;
    private readonly IMathOperationFactory operationFactory;
    private readonly ICache cache;
    private readonly ILogger logger;

    public Calculator(
        ITokenParser tokenParser,
        IMathOperationFactory operationFactory,
        ICache cache,
        ILogger logger)
    {
        this.tokenParser = tokenParser;
        this.operationFactory = operationFactory;
        this.cache = cache;
        this.logger = logger;
    }

    public int Calculate(string input)
    {
        var result = cache.Get(input);
        if (result.HasValue)
        {
            logger.LogInformation("from cache");
            return result.Value;
        }
        var tokens = tokenParser.Parse(input);
        IOperation operation = null;
        foreach(var token in tokens)
        {
            if (operation is null)
            {
                operation = operationFactory.GetOperation(token.OperationType);
                continue;
            }
            if (result is null)
            {
                result = token.Value;
                continue;
            }
            else
            {
                if (result is null)
                {
                    throw new InvalidOperationException("Could not calculate result");
                }
                result = operation.Execute(result.Value, token.Value);
                operation = null;
            }
        }
        cache.Set(input, result.Value);
        logger.LogInformation("from operation");
        return result.Value;
    }
}

This is a calculator, as is tradition. It receives a string and returns an integer value. It also caches the result for a specific input, and logs some stuff. The actual operations are being abstracted by IMathOperationFactory and the input string is translated into tokens by an ITokenParser. Don't worry, this is not a real class, just an example. Let's look at a "traditional" test:

[TestMethod]
public void Calculate_AdditionWorks()
{
    // Arrange
    var tokenParserMock = new Mock<ITokenParser>();
    tokenParserMock
        .Setup(m => m.Parse(It.IsAny<string>()))
        .Returns(
            new List<CalculatorToken> {
                CalculatorToken.Addition, CalculatorToken.From(1), CalculatorToken.From(1)
            }
        );

    var mathOperationFactoryMock = new Mock<IMathOperationFactory>();

    var operationMock = new Mock<IOperation>();
    operationMock
        .Setup(m => m.Execute(1, 1))
        .Returns(2);

    mathOperationFactoryMock
        .Setup(m => m.GetOperation(OperationType.Add))
        .Returns(operationMock.Object);

    var cacheMock = new Mock<ICache>();
    var loggerMock = new Mock<ILogger>();

    var service = new Calculator(
        tokenParserMock.Object,
        mathOperationFactoryMock.Object,
        cacheMock.Object,
        loggerMock.Object);

    // Act
    service.Calculate("");

    //Assert
    mathOperationFactoryMock
        .Verify(m => m.GetOperation(OperationType.Add), Times.Once);
    operationMock
        .Verify(m => m.Execute(1, 1), Times.Once);
}

Let's unpack it a little. We had to declare a mock for every constructor dependency, even if we don't actually care about the logger or the cache, for example. We also had to set up a mock method that returns another mock, in the case of the operation factory.

In this particular test we wrote mostly setup, one line of Act and two lines of Assert. Moreover, if we want to test how the cache works inside the class we would have to copy paste the entire thing and just change the way we setup the cache mock.

And there are the negative tests to consider. I've seen many a negative test doing something like: "setup just what is supposed to fail. test that it fails", which introduces a lot of problems, mainly because it might fail for completely different reasons and most of the time these tests are following the internal implementation of the class rather than its requirements. A proper negative test is actually a fully positive test with just one wrong condition. Not the case here, for simplicity.

So, without further ado, here is the same test, but with a MockManager:

[TestMethod]
public void Calculate_AdditionWorks_MockManager()
{
    // Arrange
    var mockManager = new CalculatorMockManager()
        .WithParsedTokens(new List<CalculatorToken> {
            CalculatorToken.Addition, CalculatorToken.From(1), CalculatorToken.From(1)
        })
        .WithOperation(OperationType.Add, 1, 1, 2);

    var service = mockManager.GetService();

    // Act
    service.Calculate("");

    //Assert
    mockManager
        .VerifyOperationExecute(OperationType.Add, 1, 1, Times.Once);
}

Unpacking, there is no mention of cache or logger, because we don't need any setup there. Everything is packed and readable. Copy pasting this and changing a few parameters or some lines is no longer ugly. There are three methods executed in Arrange, one in Act and one in Assert. Only the nitty gritty mocking details are abstracted away: there is no mention of the Moq framework here. In fact, this test would look the same regardless of the mocking framework one decides to use.

Let's take a look at the MockManager class. Now this will appear complicated, but remember that we only write this once and use it many times. The whole complexity of the class is there to make unit tests readable by humans, easily to understand, update and maintain.

public class CalculatorMockManager
{
    private readonly Dictionary<OperationType,Mock<IOperation>> operationMocks = new();

    public Mock<ITokenParser> TokenParserMock { get; } = new();
    public Mock<IMathOperationFactory> MathOperationFactoryMock { get; } = new();
    public Mock<ICache> CacheMock { get; } = new();
    public Mock<ILogger> LoggerMock { get; } = new();

    public CalculatorMockManager WithParsedTokens(List<CalculatorToken> tokens)
    {
        TokenParserMock
            .Setup(m => m.Parse(It.IsAny<string>()))
            .Returns(tokens);
        return this;
    }

    public CalculatorMockManager WithOperation(OperationType operationType, int v1, int v2, int result)
    {
        var operationMock = new Mock<IOperation>();
        operationMock
            .Setup(m => m.Execute(v1, v2))
            .Returns(result);

        MathOperationFactoryMock
            .Setup(m => m.GetOperation(operationType))
            .Returns(operationMock.Object);

        operationMocks[operationType] = operationMock;

        return this;
    }

    public Calculator GetService()
    {
        return new Calculator(
                TokenParserMock.Object,
                MathOperationFactoryMock.Object,
                CacheMock.Object,
                LoggerMock.Object
            );
    }

    public CalculatorMockManager VerifyOperationExecute(OperationType operationType, int v1, int v2, Func<Times> times)
    {
        MathOperationFactoryMock
            .Verify(m => m.GetOperation(operationType), Times.AtLeastOnce);
        var operationMock = operationMocks[operationType];
        operationMock
            .Verify(m => m.Execute(v1, v2), times);
        return this;
    }
}

All of the required mocks for the test class are declared as public properties, allowing any customization of a unit test. There is a GetService method, which will always return an instance of the tested class, with all of the dependencies fully mocked. Then there are With* methods which atomically set up various scenarios and always return the mock manager, so that they can be chained. You can also have specific methods for assertion, although in most cases you will be comparing some output with an expected value, so these are here just to abstract away the Verify method of the Moq framework.

A MockManager base class

Mock managers are very useful and make for readable code and nice tests, but they can be tiresome to write. When you want to test hundreds of classes, writing a mock manager for all becomes really annoying. Luckily, you can use a base class that makes this really easy!

So let's rewrite the CalculatorMockManager class with this base class:

public class CalculatorMockManager
    : MockManagerBase<Calculator>
{
    private readonly Dictionary<OperationType, Mock<IOperation>> operationMocks = [];

    public CalculatorMockManager WithParsedTokens(List<CalculatorToken> tokens)
    {
        GetMock<ITokenParser>()
            .Setup(m => m.Parse(It.IsAny<string>()))
            .Returns(tokens);
        return this;
    }

    public CalculatorMockManager WithOperation(OperationType operationType, int v1, int v2, int result)
    {
        var operationMock = new Mock<IOperation>();
        operationMock
            .Setup(m => m.Execute(v1, v2))
            .Returns(result);

        GetMock<IMathOperationFactory>()
            .Setup(m => m.GetOperation(operationType))
            .Returns(operationMock.Object);

        operationMocks[operationType] = operationMock;

        return this;
    }

    public CalculatorMockManager VerifyOperationExecute(OperationType operationType, int v1, int v2, Func<Times> times)
    {
        GetMock<IMathOperationFactory>()
            .Verify(m => m.GetOperation(operationType), Times.AtLeastOnce);
        var operationMock = operationMocks[operationType];
        operationMock
            .Verify(m => m.Execute(v1, v2), times);
        return this;
    }
}

The first thing we notice is that the base class is a generic one, taking as a generic parameter the type of the class we want to test. Then there are no more properties for mocks, the methods setting up mocks use a GetMock<T> method instead. And finally there is no GetService method.

How does it work? Well, when GetService is called, using reflection we find the constructor parameters and find a value to use in them. By default a mock will be generated for each, which then can be accessed with the GetMock<T> method. However, there are two methods that are virtual, allowing to customize the resolution of either the constructor parameter itself or that of its mock. Moreover, you can just decorate a property of the mock manager class with an attribute, and that property value will be used as the constructor parameter of that type.

And if you really liked the idea of Mock properties, then you can define them as read only properties that call GetMock. Here are the base class and the attribute used to decorate properties as constructor parameter providers:

/// <summary>
/// Base class for mock managers
/// </summary>
/// <typeparam name="TSubject"></typeparam>
public abstract class MockManagerBase<TSubject>
    where TSubject : class
{
    protected readonly Dictionary<Type, Mock> mocks = [];
    private TSubject _service;
    private Dictionary<Type, PropertyInfo> _properties;

    public TSubject GetService()
    {
        if (_service is not null) return _service;
        var subjectType = typeof(TSubject);
        var ctors = subjectType.GetConstructors();

        //Currently supports only services with 1 ctor
        var theCtor = ctors.Single();

        var services = new ServiceCollection();
        foreach (var serviceType in theCtor.GetParameters())
        {
            var paramType = serviceType.ParameterType;
            object paramInstance = CreateInstance(paramType);
            services.AddSingleton(paramType, paramInstance);
        }

        var serviceProvider = services.BuildServiceProvider();
        _service = ActivatorUtilities.GetServiceOrCreateInstance<TSubject>(serviceProvider);
        return _service;
    }

    /// <summary>
    /// Override this to have custom values for constructor parameters
    /// </summary>
    /// <param name="type"></param>
    /// <returns></returns>
    protected virtual object CreateInstance(Type type)
    {
        var instance = GetFromProperty(type);
        if (instance is null)
        {
            Mock mock = CreateMock(type);
            mocks[type] = mock;
            instance = mock.Object;
        }
        return instance;
    }

    /// <summary>
    /// Override this to have custom Mocks for constructor parameters
    /// </summary>
    /// <param name="type"></param>
    /// <returns></returns>
    protected virtual Mock CreateMock(Type type)
    {
        var mockType = typeof(Mock<>).MakeGenericType(type);
        var mock = GetFromProperty(mockType) ?? Activator.CreateInstance(mockType);
        return mock as Mock;
    }

    private object GetFromProperty(Type type)
    {
        _properties ??= this.GetType()
            .GetProperties(BindingFlags.Public | BindingFlags.Instance)
            .Where(prop => prop.GetCustomAttribute<ConstructorParameterProviderAttribute>() is not null)
            .ToDictionary(prop => prop.PropertyType, prop => prop);
        if (!_properties.TryGetValue(type, out PropertyInfo prop)) return null;
        return prop.GetValue(this);
    }

    /// <summary>
    /// Get the mock for type <typeparamref name="T"/>
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <returns></returns>
    public Mock<T> GetMock<T>()
        where T : class
    {
        GetService(); // ensure mocks are created
        return mocks[typeof(T)] as Mock<T>;
    }
}

/// <summary>
/// Mark a property in a <see cref="MockManagerBase{TSubject}"/> as a provider 
/// for a type or the mock of a type used in constructor injection
/// </summary>
[AttributeUsage(AttributeTargets.Property, AllowMultiple = false, Inherited = true)]
public class ConstructorParameterProviderAttribute : Attribute {}

The test methods should remain unchanged, unless you need a Mock instance outside the mock manager methods, and then you use GetMock.

Here is a more complex mock manager:

public class ExampleMockManager
    : MockManagerBase<Example>
{
    [ConstructorParameterProvider]
    public ExampleDbContext Db { get; } = new MockDbContext();

    protected override object CreateInstance(Type type)
    {
        if (type == typeof(string))
        {
            return DateOnly.FromDateTime(DateTime.Now).ToString("o");
        }
        return base.CreateInstance(type);
    }

    protected override Mock CreateMock(Type type)
    {
        if (type == typeof(IFancyService))
        {
            var mock = CreateFancyMock<IFancyService>();
            return mock;
        }
        return base.CreateMock(type);
    }
}

public class Example
{
    public Example(
        string name, 
        IFancyService fancyService,
        ExampleDbContext dbContext,
        INormalService normalService)
    {
        // ...
    }
}

In this mock manager, the Db property is used to populate the ExampleDbContext constructor parameter, an override of CreateInstance will generate the string as the date of today and an override of CreateMock will create a different type of mock, but just for IFancyService, INormalService gets the regular mock. This is a contrived example, as the following rewrite does exactly the same thing in less code that is much more readable:

public class ExampleMockManager
    : MockManagerBase<Example>
{
    [ConstructorParameterProvider]
    public ExampleDbContext Db { get; } = new MockDbContext();

    [ConstructorParameterProvider]
    public Mock<IFancyService> FancyMock { get; } = new();

    [ConstructorParameterProvider]
    public string Today => DateOnly.FromDateTime(DateTime.Now).ToString("o");
}

Conclusion

This pattern now aligns test writing with code writing:

• abstract the things you don't care about in any context
• write once and use many times
• humanly readable, self documenting code
• small methods with low cyclomatic complexity
• intuitive code writing

Writing a unit test now is trivial and consistent:

1. instantiate the mock manager of the class you want to test (or write one based on the steps above)
2. compose specific scenarios for the test (with auto complete for existing already covered scenario steps)
3. execute the method you want to test with test parameters
4. check everything is as expected

The abstraction doesn't stop at the mocking framework. The same pattern can be applied in every programming language! The mock manager construct will be very different for TypeScript or JavaScript or something else, but the unit test would pretty much look the same way.

Hope this helps!

Here is the scenario:

• you have two tables: a source of recent data and an SQL Server destination table with the same structure that has to be updated with that data
• they are both on the same server (we assume that if the data source is external you have copied it into a local temporary table)
• the destination table is in active use
• the source destination may be in active use also
• the tables are large, locking them and waiting for the merge to finish is not an option
• the difference between the tables is usually small. Not so small as to be irrelevant, but small relative to the size of the tables
• we don't care about full data consistency (any intermediate state between the current and the updated one is acceptable)

There are some quirks in SQL Server that affect our task, mainly that if you try to modify 5000 rows or more of a table, then the locking will escalate from row locks to a table lock, turning it unusable during the merge. Also, for operations involving a lot of data, the log of the database will increase to accommodate that size, then the changes will be persisted and the log invalidated. This takes a lot of disk space and if anything happens during the operation, the entire operation will be rolled back, with all of the data in the log having to be restored, which also takes a lot of time, blocking the database.

The first idea is to find rows that are different, new or missing and just sync 5000 of them at a time. One can do this with a MERGE or classic INSERT, UPDATE, DELETE operations. And this works, but it has a major flaw: after the first 5000 rows have been found and synchronized, the next operation will go through them again anyway to find the next 5000 rows, and again, and again, and again. The execution time will increase exponentially with every new batch of rows.

What we actually need is to take a list of changes and apply them in batches, kind of like an artificial transaction log. The following stored procedure will take two parameters: the full schema name of the source table and the full schema name of the destination table. It will create a log of changes, take 4900 of them at a time and apply them to the destination table. The only restrictions are that the destination table has to have primary key columns and the source and destination tables have the same columns. For performance reasons, it's best that the source table also has the same primary keys or at least an index on the same columns. The usage would look like EXEC usp_MergeTables 'SomeSchemaIncludingDbo.SourceTable','MaybeSomeOtherSchema.DestinationTable'

I will explain what it does after the code:

-- this is for batched merge (del, upd, ins) of the data of a table into another (nolock/readpast for reduced locking of source and destination tables)

CREATE OR ALTER PROC usp_MergeTables(@SourceTable NVARCHAR(256),@DestinationTable NVARCHAR(256))
AS
BEGIN

SET NOCOUNT ON

IF NOT EXISTS(SELECT * 
FROM sys.schemas s
INNER JOIN sys.tables t
ON s.schema_id=t.schema_id
WHERE REPLACE(REPLACE(@SourceTable,']',''),'[','')=s.name+'.'+t.name)
BEGIN

  DECLARE @Err1 VARCHAR(100) = 'Source table '+@SourceTable+' not found!'
  ;THROW 50404,@Err1,1

END

SELECT CAST(s.name as NVARCHAR(Max)) as schemaName,CAST(t.name as NVARCHAR(Max)) as tableName,CAST(c.name as NVARCHAR(Max)) as columnName,c.is_computed,c.is_identity, 
CASE 
  WHEN tp.name IN ( 'varchar', 'char', 'varbinary' ) THEN tp.name + 
                  CASE WHEN c.max_length = -1 THEN '(max)'       
                         ELSE '(' + CAST(c.max_length AS VARCHAR(4)) + ')' END       
  --types that have an unicode character type that requires length to be halved 
  WHEN tp.name IN ( 'nvarchar', 'nchar' ) THEN tp.name + 
                   CASE WHEN c.max_length = -1 THEN '(max)'       
                         ELSE '(' + CAST(c.max_length / 2 AS VARCHAR(4)) + ')'       
                                                              END
   --types with a datetime precision 
  WHEN tp.name IN ( 'time', 'datetime2', 'datetimeoffset' ) THEN tp.name + 
                                            '(' + CAST(c.scale AS VARCHAR(4)) + ')' 
  --types with a precision/scale 
  WHEN tp.name IN ( 'numeric', 'decimal' ) 
  THEN tp.name + '(' + CAST(c.precision AS VARCHAR(4)) + ',' +
                                             CAST(c.scale AS VARCHAR(4)) + ')'
  --timestamp should be reported as rowversion 
  WHEN tp.name = 'timestamp' THEN 'rowversion' 
  --and the rest. Note, float is declared with a bit length, but is 
  --represented as either float or real in types  
  ELSE tp.name 
END as typeName,
ISNULL(( SELECT pk.is_primary_key FROM sys.indexes pk
INNER JOIN sys.index_columns ic
ON ic.object_id = pk.object_id
AND ic.index_id = pk.index_id
AND c.column_id=ic.column_id
WHERE t.object_id = pk.object_id
AND pk.is_primary_key = 1
),0) as is_primary_key
INTO #tgtColumns
FROM sys.schemas s
INNER JOIN sys.tables t
ON s.schema_id=t.schema_id
INNER JOIN sys.all_columns c
ON t.object_id=c.object_id
INNER JOIN sys.types tp
ON c.system_type_id=tp.system_type_id
AND c.user_type_id=tp.user_type_id
WHERE REPLACE(REPLACE(@DestinationTable,']',''),'[','')=s.name+'.'+t.name

IF NOT EXISTS(SELECT * FROM #tgtColumns)
BEGIN

  DECLARE @Err2 VARCHAR(100) = 'Destination table '+@DestinationTable+' not found!'
  ;THROW 50404,@Err2,2

END

IF NOT EXISTS(SELECT * FROM #tgtColumns WHERE is_primary_key=1)
BEGIN

  DECLARE @Err3 VARCHAR(100) = 'Destination table '+@DestinationTable+' has no primary keys!'
  ;THROW 50404,@Err3,3

END

DECLARE @operSql NVARCHAR(Max)
DECLARE @delSql NVARCHAR(Max)
DECLARE @updSql NVARCHAR(Max)
DECLARE @insSql NVARCHAR(Max)
DECLARE @identityInsertOn NVARCHAR(Max)=''
DECLARE @identityInsertOff NVARCHAR(Max)=''

IF EXISTS(SELECT * FROM #tgtColumns WHERE is_identity=1)
BEGIN

  SET @identityInsertOn=CONCAT(N'
SET IDENTITY_INSERT ',@DestinationTable,N' ON
')
  SET @identityInsertOff=CONCAT(N'
SET IDENTITY_INSERT ',@DestinationTable,N' OFF
')

END


SELECT @operSql = CONCAT(N'DROP TABLE IF EXISTS #oper

SELECT *
   INTO #oper
FROM (
SELECT ',STRING_AGG(CONCAT(N'ISNULL(src.[',c.columnName,N'],tgt.[',c.columnName,N']) as [',c.columnName,N']'),N', '),N',
  CASE
    WHEN ',STRING_AGG(CONCAT(N'src.[',c.columnName,N'] IS NULL'),N' AND '),N' THEN ''DEL''
    WHEN ',STRING_AGG(CONCAT(N'tgt.[',c.columnName,N'] IS NULL'),N' AND '),N' THEN ''INS''
    WHEN (
    	SELECT * FROM ',@SourceTable,N' R
    	WHERE ',STRING_AGG(CONCAT('R.[',c.columnName,N'] = src.[',c.columnName,N']'),N' AND '),N'
    	FOR XML PATH(''Row''), ELEMENTS XSINIL
      ) <> (
    	SELECT * FROM ',@DestinationTable,N' R
    	WHERE ',STRING_AGG(CONCAT('R.[',c.columnName,N'] = tgt.[',c.columnName,N']'),N' AND '),N'
    	FOR XML PATH(''Row''), ELEMENTS XSINIL
      ) THEN ''UPD''
   END as __oper__
   FROM ',@SourceTable,N' src (NOLOCK)
   FULL OUTER JOIN ',@DestinationTable,N' tgt (NOLOCK)
   ON ',STRING_AGG(CONCAT('src.[',c.columnName,N'] = tgt.[',c.columnName,N']'),N' AND '),'
) x
WHERE __oper__ IS NOT NULL

CREATE INDEX temp_id ON #oper(',STRING_AGG(CONCAT('[',c.columnName,N']'),N', '),N')
CREATE INDEX temp_oper ON #oper(__oper__)')
FROM #tgtColumns c
WHERE c.is_primary_key=1

SELECT @delSql = CONCAT(N'

DECLARE @batch TABLE(',STRING_AGG(CONCAT('[',c.columnName,N'] ',c.typeName),N', '),N',
                   PRIMARY KEY(',STRING_AGG(CONCAT('[',c.columnName,N']'),N', '),N'))

DECLARE @ROWS INT = 1

WHILE (@ROWS>0)
BEGIN

  DELETE TOP (4900) tgt
    OUTPUT ',STRING_AGG(CONCAT('deleted.[',c.columnName,N']'),N', '),N'
	INTO @batch
  FROM ',@DestinationTable,N' tgt (READPAST)
  INNER JOIN #oper src
    ON ',STRING_AGG(CONCAT('src.[',c.columnName,N'] = tgt.[',c.columnName,N']'),N' AND '),N'
  WHERE src.__oper__=''DEL''

  SET @ROWS=@@ROWCOUNT

  DELETE o
  FROM #oper o
  INNER JOIN  @batch b
  ON ',STRING_AGG(CONCAT('o.[',c.columnName,N'] = b.[',c.columnName,N']'),N' AND '),N'
  
  DELETE FROM @batch

  IF (@ROWS=0)
    SELECT @ROWS=COUNT(*) FROM #oper WHERE __oper__=''DEL''

END')
FROM #tgtColumns c
WHERE c.is_primary_key=1


SELECT @updSql = CONCAT(N'

SET @ROWS = 1

WHILE (@ROWS>0)
BEGIN

  UPDATE tgt
  SET ',(SELECT STRING_AGG(CONCAT('[',c.columnName,N'] = src.[',c.columnName,N']'),N', ')
FROM #tgtColumns c
WHERE c.is_primary_key=0 AND c.is_computed=0),N' OUTPUT ',STRING_AGG(CONCAT('inserted.[',c.columnName,N']'),N', '),N'
	INTO @batch
  FROM ',@DestinationTable,N' tgt (READPAST)
  INNER JOIN ( 
    SELECT TOP (4900) s.*
    FROM #oper o
	INNER JOIN ',@SourceTable,N' s
	ON ',STRING_AGG(CONCAT('s.[',c.columnName,N'] = o.[',c.columnName,N']'),N' AND '),N'
    WHERE __oper__=''UPD''
  ) src
    ON ',STRING_AGG(CONCAT('src.[',c.columnName,N'] = tgt.[',c.columnName,N']'),N' AND '),N'

  SET @ROWS=@@ROWCOUNT

  DELETE o
  FROM #oper o
  INNER JOIN  @batch b
  ON ',STRING_AGG(CONCAT('o.[',c.columnName,N'] = b.[',c.columnName,N']'),N' AND '),N'
  
  DELETE FROM @batch

  IF (@ROWS=0)
    SELECT @ROWS=COUNT(*) FROM #oper WHERE __oper__=''UPD''

END')
FROM #tgtColumns c
WHERE c.is_primary_key=1


SELECT @insSql = CONCAT(N'

SET @ROWS = 1

WHILE (@ROWS>0)
BEGIN

  INSERT INTO ',@DestinationTable,N'(',(SELECT STRING_AGG(CONCAT('[',c.columnName,N']'),N', ')
FROM #tgtColumns c
WHERE c.is_computed=0),N') OUTPUT ',STRING_AGG(CONCAT('inserted.[',c.columnName,N']'),N', '),N'
    INTO @batch
  SELECT TOP (4900) ',(SELECT STRING_AGG(CONCAT('s.[',c.columnName,N']'),N', ')
FROM #tgtColumns c
WHERE c.is_computed=0),N'
  FROM #oper o
  INNER JOIN ',@SourceTable,N' s
  ON ',STRING_AGG(CONCAT('s.[',c.columnName,N'] = o.[',c.columnName,N']'),N' AND '),N'
  WHERE __oper__=''INS''

    SET @ROWS=@@ROWCOUNT
	
  DELETE o
  FROM #oper o
  INNER JOIN  @batch b
  ON ',STRING_AGG(CONCAT('o.[',c.columnName,N'] = b.[',c.columnName,N']'),N' AND '),N'
  
  DELETE FROM @batch

  IF (@ROWS=0)
    SELECT @ROWS=COUNT(*) FROM #oper WHERE __oper__=''INS''

END

DROP TABLE #oper
')
FROM #tgtColumns c
WHERE c.is_primary_key=1

DROP TABLE #tgtColumns

--PRINT @operSql
--PRINT @delSql
--PRINT @updSql
--PRINT @identityInsertOn
--PRINT @identityInsertOff
--PRINT @insSql

DECLARE @sql NVARCHAR(Max) = CONCAT(@operSql, @delSql, @identityInserton, @updSql, @insSql, @identityInsertOff)
EXEC sp_sqlexec @sql

END

OK, this is a large thing, but the principles used are simple:

• first we create a table containing information about the columns of the tables: schema, table, column name, whether the column is primary key or computed, and the type name. The schema and table name are not used, but may be useful for debugging. Note that this SP doesn't check the tables have the same number and type of columns. That's on you to ensure.
• using the column information we create four strings that will contain the SQL for the following operations:
  • create an "operations table"
  • delete rows that are not needed
  • update rows that need to be updated
  • insert rows that are missing
• there are four strings mostly for debugging purposes to keep them smaller than the 8000 characters that Microsoft SQL Server Management Studio can print at a time, but they are concatenated and executed as one.
• implementation details:
  • we use FOR XML PATH('Row'), ELEMENTS XSINIL to generate a string with all the data in each row, so we don't have to compare rows column by column. We could have made this work with comparisons, but the code would have been bulky and ugly when comparing for NULL or for having values. ELEMENTS XSINIL will ensure that there is a difference between empty space and NULL.
  • a FULL OUTER JOIN is used to find (based on the primary key columns of the destination table) if rows need to be either deleted, updated or inserted. That operation is specified in the __oper__ column
  • the operations table is thus created, containing the primary key values and the operation required with two indexes: one on the primary keys and one on the operation. These indexes are not really that relevant, so one could choose to remove them.
  • a @batch table variable is used with a PRIMARY KEY on the primary key columns of the destination table, for performance reasons
  • the batching is done via a DELETE... OUTPUT operation. We delete the 4900 rows we process and we output them in the @batch table
  • for each segment we either: delete destination rows with the same primary keys for 'DEL', update destination rows with the same primary keys for 'UPD' and insert source rows with the same primary keys for 'INS'
  • before we update, we set IDENTITY_INSERT to ON and at the end to OFF, if any identity columns
  • if some rows were affected by the operation, then we continue in the same segment. If not, then we look in the operations table to see if there are still rows to be processed. No rows may be affected while there are still rows to be processed due to the locking avoidance hints
• improvements to avoid locking:
  • when we generate the operations table we use NOLOCK, which reads uncommitted values ignoring locks. This may not be what you want, but if the source table is locked for whatever reason, this ensures the merge operation is not blocked
  • when we process the batches we use READPAST, which ignores locked destination rows. This ensures that rows that can be updated will be, while the others can be done later, meaning that if you have 1 locked row, the merge operation will go around it, then wait until it is unlocked to update or delete it.

If you want to see what the generated SQL looks like, uncomment the PRINT lines and comment the EXEC one.

Now, I just wrote this stored procedure, so I may have missed some cases. Let me know if you find a situation where this doesn't work as expected. 

Hope it helps!

What is the structure of a table created from another via SELECT * INTO [Second] FROM [First] ?

A simple question, indeed, a basic one, but one that I have never asked myself until today. I honestly believed that the result is a generic table containing the same column names and types and their values and nothing else.

The answer, though, is strange. If the original column is NOT NULL, the resulting column will also be NOT NULL. If the original column has IDENTITY, the column in the second table will also have IDENTITY. And, as you know, you can't add or remove IDENTITY from existing columns without dropping and adding them back. The DEFAULT value, though, is not transferred.

The Microsoft reference page says: 

The format of new_table is determined by evaluating the expressions in the select list. The columns in new_table are created in the order specified by the select list. Each column in new_table has the same name, data type, nullability, and value as the corresponding expression in the select list.

...

When an existing identity column is selected into a new table, the new column inherits the IDENTITY property, unless one of the following conditions is true:

• The SELECT statement contains a join.
• Multiple SELECT statements are joined by using UNION.
• The identity column is listed more than one time in the select list.
• The identity column is part of an expression.
• The identity column is from a remote data source.

...

Indexes, constraints, and triggers defined in the source table are not transferred to the new table, nor can they be specified in the SELECT...INTO statement. If these objects are required, you can create them after executing the SELECT...INTO statement.

...

Specifying an ORDER BY clause does not guarantee the rows are inserted in the specified order.

...

When a computed column is included in the select list, the corresponding column in the new table is not a computed column. The values in the new column are the values that were computed at the time SELECT...INTO was executed.

So, my assumptions were wrong, but still what do you do when you want to achieve exactly that: create a new schema-less table with the same columns in terms of name and data type and value only? It's a bit ugly, but I have not found a better alternative. Just UNION ALL with a SELECT that has the same number of (nullable) columns and no rows. like this:

SELECT *
  INTO [Second]
FROM [First]
  UNION ALL
(SELECT NULL, NULL,NULL,NULL WHERE 1=0)

Assuming that the First table had four columns, this will result in a table having the same column names, types and values as the original table, but all columns will be nullable and with no identity.

Hope it helps!