Module 1 · Foundations · Lesson 1 of 17

How to Solve and Check a Coding Problem in C#: Patterns, Tests and Measured Big-O

16 min readTechInterviewNotes Editorial TeamUpdated 13 Oct 2026Save

Learning outcome

You can run a coding interview the way strong candidates do: restate the problem, write test cases first, name the pattern, state time and space complexity, and check that claim by counting operations as the input doubles. You also know how this course's runnable examples are built, so you can reuse the harness for your own practice.

Intuition

Most interview problems are one of about ten patterns in disguise. The work is to recognize the pattern from the constraints ("sorted array", "contiguous subarray", "shortest path", "top k"), then apply a template you already trust. Complexity is not a guess you say at the end: it follows from the template, and you can check it.

flowchart LR
    A["Restate + examples"] --> B["Edge cases as tests"]
    B --> C["Brute force + its Big-O"]
    C --> D["Name the pattern"]
    D --> E["Code the template"]
    E --> F["Run tests"]
    F --> G["State and check Big-O"]

Deep dive

The interview loop (about 35-45 minutes for one problem):
1. Restate the problem and confirm input sizes and value ranges. "n up to 10^5" rules out O(n²) in practice; "n up to 20" allows exponential search.
2. Write 3-5 test cases before coding: the given example, empty or single element, duplicates, negative numbers, the largest size.
3. Say the brute force and its cost in one sentence. It shows you can solve the problem and it gives you a baseline.
4. Name the pattern that removes the waste, then code it.
5. Walk through a test by hand, then state time and extra space.
Pattern triggers used in this course:

Clue in the problem	Pattern	Lesson
"Have we seen this value before?"	Hashing	4
Sorted input, pairs or triples	Two pointers	5
Contiguous subarray or substring	Sliding window or prefix sums	3, 6
"Next greater", matching brackets	Stack / monotonic stack	7
Sorted data or a monotonic yes/no answer	Binary search	9
Levels, shortest path in steps	BFS	10, 12
Dependencies, ordering	Topological sort	13
"Top k", "k-th", merge sorted streams	Heap (`PriorityQueue`)	14
Ranges, meetings, bookings	Sort + sweep	15
Choices that branch, "all combinations"	Recursion, DP, backtracking	Recursion/DP course

Big-O in practice: count the work per element. A loop inside a loop over the same data is usually O(n²). A loop whose inner pointer never moves backwards is O(n) in total even if it is nested (Lessons 6 and 7 prove this by counting). Sorting costs O(n log n). Extra space counts what you allocate, not the input.
Checking complexity: run the solution at n, 2n, 4n and count a basic operation. Doubling counts suggest linear growth; quadrupling suggests quadratic growth; slightly more than doubling is consistent with n log n; a fixed number of extra steps for a fixed input-size multiplier suggests logarithmic growth. These finite samples are checks, not proofs of asymptotic bounds. Counting is deterministic. Wall-clock time is noisy (CPU caches, JIT, other processes), so timing is a sanity check only.
How the examples in this course work:
- Check.Eq(name, actual, expected) prints PASS or FAIL for each test case, and Check.Summary() prints the totals.
- Big.Growth resets Big.Ops, runs your code at several sizes and prints the ratio as n doubles. You put Big.Ops++ on the operation you want to count.
- Big.Time prints the median of 5 timed runs per size. The examples build with TieredCompilation off so timings are not distorted by the JIT recompiling hot code during measurement.

The harness is short enough to read in full:

// Test and complexity harness used by every lesson in this course.
// Check.Eq prints PASS/FAIL per test case. Big.Growth counts basic operations
// (deterministic, same on every machine) and prints how the count grows when n doubles.
using System.Collections;
using System.Diagnostics;

public static class Check
{
    static int _pass, _fail;

    public static void Eq(string name, object? actual, object? expected)
    {
        string a = Fmt(actual), e = Fmt(expected);
        bool ok = a == e;
        if (ok) _pass++; else _fail++;
        Console.WriteLine(ok ? $"PASS {name} -> {a}" : $"FAIL {name} -> {a} (expected {e})");
    }

    public static void Summary() => Console.WriteLine($"tests: {_pass} passed, {_fail} failed");

    public static string Fmt(object? o) => o switch
    {
        null => "null",
        string s => s,
        IEnumerable e => "[" + string.Join(",", e.Cast<object?>().Select(Fmt)) + "]",
        _ => o.ToString()!
    };
}

public static class Big
{
    // Lessons increment Big.Ops inside the loop they want to measure.
    public static long Ops;

    // Runs work(n) for each size, counts Ops, prints the ratio when n doubles.
    // Ratio ~2 => O(n); ~4 => O(n^2); slightly above 2 => O(n log n); ~1 => O(1) or O(log n) (see the count).
    public static void Growth(string label, int[] sizes, Action<int> work)
    {
        Console.WriteLine($"ops growth: {label}");
        long prev = 0; int prevN = 0;
        foreach (int n in sizes)
        {
            Ops = 0;
            work(n);
            string ratio = prevN > 0 && prev > 0 ? $"  x{(double)Ops / prev:0.00} for n x{(double)n / prevN:0}" : "";
            Console.WriteLine($"  n={n,13:N0}  ops={Ops,15:N0}{ratio}");
            prev = Ops; prevN = n;
        }
    }

    // Wall-clock doubling test (median of 5 runs). Machine-dependent: read the ratio, not the ms.
    public static void Time(string label, int[] sizes, Func<int, Action> setup)
    {
        Console.WriteLine($"time growth (median of 5, varies per run): {label}");
        double prev = 0;
        foreach (int n in sizes)
        {
            Action run = setup(n);
            run(); // warm-up
            var t = new double[5];
            for (int i = 0; i < 5; i++) { var sw = Stopwatch.StartNew(); run(); t[i] = sw.Elapsed.TotalMilliseconds; }
            Array.Sort(t);
            string ratio = prev > 0 ? $"  x{t[2] / prev:0.0}" : "";
            Console.WriteLine($"  n={n,13:N0}  {t[2],9:0.000} ms{ratio}");
            prev = t[2];
        }
    }

    public static int[] RandomArray(int n, int max, int seed = 42)
    {
        var r = new Random(seed);
        var a = new int[n];
        for (int i = 0; i < n; i++) a[i] = r.Next(max);
        return a;
    }
}

Code example: one problem, three complexities

"Does the array contain a duplicate?" solved with nested loops, by sorting, and with a HashSet<int>.

// L01: one problem, three complexities. "Does the array contain a duplicate?"
// Each version is tested, then its growth is measured by counting operations.

static bool DupNested(int[] a)            // O(n^2) time, O(1) extra space
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
        {
            Big.Ops++;
            if (a[i] == a[j]) return true;
        }
    return false;
}

static bool DupSorted(int[] a)            // O(n log n) time, O(n) space for the copy
{
    var s = (int[])a.Clone();             // do not mutate the caller's array
    Array.Sort(s);
    for (int i = 1; i < s.Length; i++)
    {
        Big.Ops++;
        if (s[i] == s[i - 1]) return true;
    }
    return false;
}

static bool DupHashSet(int[] a)           // O(n) average time, O(n) space
{
    var seen = new HashSet<int>(a.Length);
    foreach (int x in a)
    {
        Big.Ops++;
        if (!seen.Add(x)) return true;    // Add returns false when x is already present
    }
    return false;
}

Func<int[], bool>[] all = [DupNested, DupSorted, DupHashSet];
string[] names = ["nested", "sorted", "hashset"];
for (int k = 0; k < all.Length; k++)
{
    Check.Eq($"{names[k]} [1,2,3,1]", all[k]([1, 2, 3, 1]), true);
    Check.Eq($"{names[k]} [1,2,3,4]", all[k]([1, 2, 3, 4]), false);
    Check.Eq($"{names[k]} []", all[k]([]), false);
    Check.Eq($"{names[k]} [7]", all[k]([7]), false);
}
Check.Summary();

// Worst case for all three: no duplicates, so every version scans everything.
Big.Growth("nested loops (no duplicate)", [1_000, 2_000, 4_000], n => DupNested(Enumerable.Range(0, n).ToArray()));
Big.Growth("hashset (no duplicate)", [1_000, 2_000, 4_000], n => DupHashSet(Enumerable.Range(0, n).ToArray()));
Console.WriteLine($"nested comparisons for n=4,000: n(n-1)/2 = {4_000L * 3_999 / 2:N0}");

Big.Time("nested", [2_000, 4_000, 8_000], n => { var a = Enumerable.Range(0, n).ToArray(); return () => DupNested(a); });
Big.Time("sorted", [200_000, 400_000, 800_000], n => { var a = Enumerable.Range(0, n).Reverse().ToArray(); return () => DupSorted(a); });
Big.Time("hashset", [200_000, 400_000, 800_000], n => { var a = Enumerable.Range(0, n).ToArray(); return () => DupHashSet(a); });

Output (.NET 10, Release)

Text

PASS nested [1,2,3,1] -> True
PASS nested [1,2,3,4] -> False
PASS nested [] -> False
PASS nested [7] -> False
PASS sorted [1,2,3,1] -> True
PASS sorted [1,2,3,4] -> False
PASS sorted [] -> False
PASS sorted [7] -> False
PASS hashset [1,2,3,1] -> True
PASS hashset [1,2,3,4] -> False
PASS hashset [] -> False
PASS hashset [7] -> False
tests: 12 passed, 0 failed
ops growth: nested loops (no duplicate)
  n=        1,000  ops=        499,500
  n=        2,000  ops=      1,999,000  x4.00 for n x2
  n=        4,000  ops=      7,998,000  x4.00 for n x2
ops growth: hashset (no duplicate)
  n=        1,000  ops=          1,000
  n=        2,000  ops=          2,000  x2.00 for n x2
  n=        4,000  ops=          4,000  x2.00 for n x2
nested comparisons for n=4,000: n(n-1)/2 = 7,998,000
time growth (median of 5, varies per run): nested
  n=        2,000      0.924 ms
  n=        4,000      3.079 ms  x3.3
  n=        8,000     12.782 ms  x4.2
time growth (median of 5, varies per run): sorted
  n=      200,000      3.647 ms
  n=      400,000      7.305 ms  x2.0
  n=      800,000     15.635 ms  x2.1
time growth (median of 5, varies per run): hashset
  n=      200,000      1.635 ms
  n=      400,000      3.675 ms  x2.2
  n=      800,000      9.393 ms  x2.6

Code walkthrough

All 12 test cases pass for all three versions, including the empty array and a single element. Edge cases are tests, not afterthoughts.
Nested loops on 4,000 distinct values did 7,998,000 comparisons, exactly n(n-1)/2. Each doubling of n multiplied the count by x4.00: O(n²).
The HashSet version did 4,000 operations for n = 4,000 and doubled with n (x2.00): O(n) average, because HashSet<int>.Add is O(1) on average and returns false when the value is already present.
The timings agree with the counts but are noisier: in the captured run the nested version went x3.3 then x4.2, and the HashSet version x2.2 then x2.6 (larger sets fall out of the CPU cache). Read timing ratios as a rough check; trust the operation counts.
DupSorted clones the array before Array.Sort. Sorting the caller's array in place would be a side effect the interviewer will ask about. The clone is why its extra space is O(n).

Complexity

Version	Time	Extra space	Notes
Nested loops	O(n²)	O(1)	Fine for n ≤ a few thousand
Sort, then compare neighbors	O(n log n)	O(n) for the copy (O(log n) if you may sort in place)	`Array.Sort` is an introsort
`HashSet<int>`	O(n) average	O(n)	Worst case degrades with a bad hash (Lesson 4)

Failure modes

Coding before agreeing on the input size. You may build an O(n log n) solution when O(n²) was fine, or the reverse.
Testing only the happy path. Empty input, one element, all equal and negative values catch most bugs.
Stating "O(n)" for code that calls List.Contains or IndexOf inside a loop (that is O(n²), Lesson 2).
Mutating the caller's input (sorting in place) without saying so.
Quoting milliseconds from one run as proof of complexity. Use growth ratios or operation counts.

Interview angle

"How do you know your solution is O(n)?" Answer: "Each element is added to the set once and each Add is O(1) on average, so the loop is O(n) average with O(n) extra space. The worst case depends on the hash function. I checked it by counting operations at n, 2n and 4n: the count doubled each time. The sorting version trades the hash set for O(n log n) time and works when hashing is not available."

Practice questions

An input has n ≤ 10^5. Is an O(n²) solution acceptable?

Answer: Usually not: 10^10 basic steps is far too slow. Aim for O(n log n) or O(n).

You double n and the operation count goes x4. What complexity does this suggest?

Answer: Quadratic growth, O(n²); confirm it by analyzing the algorithm rather than treating one ratio as proof.

Why does the sorting version clone the array?

Answer: To avoid mutating the caller's data. The trade-off is O(n) extra space.

Name three edge cases for "find a duplicate".

Answer: Empty array, one element, and a duplicate at the very end (or all elements equal).

Revision checklist

Restate, confirm sizes, write tests first.
Brute force with its Big-O, then the pattern.
State time and extra space, average vs worst case.
Check growth by counting operations at n, 2n, 4n.
Do not mutate inputs silently.

Course: Recursion, Dynamic Programming and Backtracking in C#
Course: Time and Space Complexity in LINQ
Cheat sheet: .NET Collections Big-O Cheat Sheet
Lesson: Big-O for .NET developers: time and space in LINQ

References

Analogy

Everyday picture

A doctor's checklist

A good doctor does not jump to a prescription. They ask questions, take measurements, match symptoms to a known condition, then apply the standard treatment and check that it worked. Restating, testing, naming the pattern and measuring growth is the same discipline.

Quick reference

Growth ratios when n doubles

x1 (or a constant increase per 1000x): O(1) or O(log n).
x2: O(n).
a bit more than x2: O(n log n).
x4: O(n²).
x8: O(n³).