← Back to C# interview home

Guides Guide 2 Reference

Constraints and Complexity

The constraint list is not fine print. It is the interviewer telling you which complexity they expect, and often which pattern to use. Read it first.

Candidates skip straight to the examples. The constraints are more useful. “n ≤ 20” means exponential is fine and they want backtracking. “n ≤ 10⁵” means anything quadratic will fail. Reading the bound turns a guess into a decision.

Contents

  1. The operations budget
  2. Input size to expected complexity
  3. Reading a constraint as a hint
  4. Counting the operations in your own code
  5. What the growth rates really mean
  6. The space budget
  7. How to state a complexity

The operations budget

A judge or an interviewer usually has one second of runtime in mind. C# is compiled to machine code by the JIT, so it buys roughly 10⁸ simple operations, close to Java. Budget a few times less when each step allocates, hashes a string, or goes through LINQ.

So the working rule is: estimate the operation count as a function of n, plug in the largest n in the constraints, and check it lands under about 10⁸. That is the whole method.

This matters in a real interview more than people expect. If n = 10⁵ and your solution is O(n log n), that is about 1.7 million operations, comfortably fine. If it is O(n²), that is 10¹⁰, which takes minutes even in C#. You can tell the interviewer your approach will not work before writing it. That is exactly the judgement they want to see.

Input size to expected complexity

This is the list to memorise. Find the largest n in the constraints and read across.

The two most useful lines. n ≤ 20 almost always means subsets or bitmask, because 2²⁰ is about a million and 2³⁰ is a billion. And n = 10⁵ almost always means sort it or use a hash map, because n² is 10¹⁰ and n log n is under 2 million. Spot these two at a glance and you save five minutes.

Reading a constraint as a hint

Constraints tell you more than the complexity. Several phrasings map almost one to one onto a pattern.

Ask about the constraints that are missing. If the statement never says whether values can be negative, whether the input is sorted, or how large n gets, ask. Each of those changes the answer. Interviewers score the question as a plus, not as ignorance.

Counting the operations in your own code

Three rules cover almost every case.

The nested loop that is not quadratic

public static class NotQuadratic
{
    /// <summary>Two pointers in nested loops, but only O(n) work in total.</summary>
    /// <param name="nums">The values.</param>
    /// <returns>How many times the inner loop moved left.</returns>
    /// <example>NotQuadratic.Moves([1, 2, 3, 4]) returns 3.</example>
    public static int Moves(int[] nums)
    {
        int left = 0;    // 0 is the first index. left only ever moves forward.
        int total = 0;   // 0 moves so far

        // right is the outer index. Invariant: left <= right, and left never goes back.
        for (int right = 0; right < nums.Length; right++)
        {
            while (left < right && nums[left] < nums[right])
            {
                left++;      // one step forward. At most n steps across the WHOLE loop.
                total++;
            }
        }
        return total;
    }
}
left right both pointers only move this way left moves at most n times, right moves n times: O(n) total
Figure G2.1 — Count pointer moves, not loop nesting. Each pointer crosses the array once.

Reading the figure. Green cells are behind left and will never be looked at again. Blue cells sit between the two pointers. Amber is where right is now. Grey cells are still ahead. The arrow below shows the only direction either pointer moves.

Count pointer moves, not loop nesting. Here left starts at 0, only increases, and never passes n. So the inner while runs at most n times across the whole outer loop, not n times per pass. Total: O(n). This amortised argument is the same one behind the sliding window, monotonic stacks and cyclic sort. Interviewers ask about it directly, so have the sentence ready.

The single loop that is quadratic

O(n²): linear calls in the body 
public static class DedupSlow
{
    /// <summary>Keeps first sightings, newest
    /// first. O(n^2).</summary>
    /// <param name="items">The values.</param>
    /// <returns>Distinct values, reversed.</returns>
    /// <example>DedupSlow.Run([1, 2, 1, 3])
    /// returns [3, 2, 1].</example>
    public static List<int> Run(int[] items)
    {
        var output = new List<int>();
        foreach (int item in items)
        {
            if (output.Contains(item))  // O(n)
            {
                continue;
            }
            output.Insert(0, item);     // O(n)
        }
        return output;
    }
}
O(n): a set, then one reverse 
public static class DedupFast
{
    /// <summary>Same result. O(n).</summary>
    /// <param name="items">The values.</param>
    /// <returns>Distinct values, reversed.</returns>
    /// <example>DedupFast.Run([1, 2, 1, 3])
    /// returns [3, 2, 1].</example>
    public static List<int> Run(int[] items)
    {
        var seen = new HashSet<int>();
        var output = new List<int>();
        foreach (int item in items)
        {
            if (seen.Add(item))   // O(1) avg
            {
                output.Add(item); // O(1)
            }
        }
        output.Reverse();         // O(n), once
        return output;
    }
}

No nesting in sight, and the left one is O(n²). The lesson: look inside the loop body, not just at the loop headers. List.Contains, Insert(0, ...), RemoveAt(0), ranges such as s[i..], LINQ Min, Max, Sum, Count(), and string += are all linear.

Recursive cost

The gap between the second and fourth lines is why quickselect beats a full sort for finding one element. It recurses into one half instead of both.

Dynamic programming has a shortcut

For any DP, the time is number of states × work per state. Two nested indices with an O(1) step is O(n²). Two indices with an O(n) inner scan is O(n³). You can read the complexity straight off the state, before writing a line. In C#, the table size also tells you the memory: new long[n + 1, m + 1] is 8 bytes per cell.

What the growth rates really mean

Concrete numbers, so the symbols have weight. Each figure is an operation count.

Three readings worth keeping.

The space budget

Memory limits are usually 256 MB. C# stores value types inline, so an int[] of 10⁶ items is about 4 MB. Every class instance costs a header of about 16 to 24 bytes on top of its fields. A million small objects is where memory goes.

Rough sizes for 10⁶ elements on a 64-bit runtime:

The lesson: prefer arrays of value types and value tuples to lists of small arrays or small classes. It is faster and several times smaller.

Conventions for what counts as extra space:

How to state a complexity

Say four things, in this order. It takes fifteen seconds and closes the question cleanly.

  1. The time, with the reason. “O(n log n). The sort dominates, and the sweep after it is linear.”
  2. The space, and what is in it. “O(n) for the dictionary. O(1) extra if you do not count the output.”
  3. What the variables mean. “n is the number of intervals, not the length of the timeline.”
  4. Worst or average case. “Average O(n). Worst case O(n²) if the hash degrades.”
Do not quote a bound with a bare letter. “O(k)” means nothing until you say what k is. Problems with two inputs need both: string matching is O(n + m), not O(n). Sloppiness here is one of the easiest ways to look less careful than you are.
Amortised is not average. Amortised O(1) means a long run of calls averages out, guaranteed, as with List.Add. Average case O(1) means it usually holds, as with a Dictionary lookup, and an adversary could break it. Using the right word is a small, visible signal.

The five things to carry forward

← Guide 1 — The C# Toolkit Guide 3 — The Interview Script →