Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Type a name or a two-letter code. Use the up and down arrow keys to move through the countries, Enter to choose one and Escape to close.

Coding Interview Patterns  Module 1 – How to approach a coding round

Read constraints to pick the target complexity

Read a coding problem's constraints block in a minute, turn its limits into a target complexity and the patterns that fit it, and check the plan by timing it.

  • Beginner
  • 15 minutes
  • Examples run with Python 3.14.8 and Pyodide 314.0.7
  • By MySmartCoPilot
Free lesson, Pro answers: 15 minutes
Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

  • Estimate the operation budget from input limits and the time limit
  • Choose a target complexity class, for example O(n log n) for n up to 2 × 10⁵
  • Measure code instead of trusting folklore numbers
  • Identify the technique and the trap that limits on values, queries and test cases point to

Before you start

What you’ll learn · Before you start

What you will learn

  • Estimate the operation budget from input limits and the time limit
  • Choose a target complexity class, for example O(n log n) for n up to 2 × 10⁵
  • Measure code instead of trusting folklore numbers
  • Identify the technique and the trap that limits on values, queries and test cases point to

Before you start

On this page

Every online-assessment problem ends with a constraints block: The lines at the end of a problem statement that give the input sizes, the ranges of the values and the time limit. They say how fast a solution must be before you design one., and many people skim past it to start coding. That block is the most direct hint you will get: a line such as n ≤ 2 × 10⁵ tells you how fast the solution must be before you have thought of one. In a live round the limits are often missing, so you ask for them during the clarifying step. Below, limits are read the way you would under time pressure, mapped to a target complexity and the patterns that usually reach it, and a plan is checked by timing it rather than by trusting a rule of thumb.

Read the block before the story

Here is an original constraints block of the kind that ends a problem statement:

Constraints

1 ≤ n ≤ 2 × 10⁵. −10⁹ ≤ a[i] ≤ 10⁹. 1 ≤ q ≤ 10⁵ queries. Time limit: 2 seconds per test file. The answer can be large: print it modulo 10⁹ + 7.

Read it in this order, and say the conclusions aloud in a live round:

  1. The largest size. n can be 200,000, so an algorithm that looks at every pair makes about n²/2 = 2 × 10¹⁰ comparisons. That rules out O(n²) before you write anything.
  2. The time limit and your language. Multiply the seconds by the number of simple steps your language does per second. A common planning figure is about 10⁸ a second for compiled code and about 10⁷ for CPython; the DSA track’s lesson on growth rates measures where those figures come from. Two seconds in Python is then a operation budget: How many simple steps a solution may take: the time limit in seconds times the steps the language does in a second, about 10⁸ for compiled code and 10⁷ for CPython as planning figures. of a few times 10⁷ steps.
  3. The other numbers. The values reach 10⁹ in size, q queries come on top of n, and the modulus says the true answer is too big to print. Each of these changes the plan, as the clues below show.

Then compare the step count of each idea with the budget. Here, n log₂ n is about 3.5 million for n = 2 × 10⁵, well inside even the Python budget, so the target is O(n log n) or better, plus a cheap answer to each query.

The model below makes that comparison for every common growth rate at once. It starts at this block’s n = 200,000 and the CPython figure of 10 million steps a second; its line marks one second, half of this time limit:

Interactive · change it and see Each growth rate at n = 200,000, in CPython Pick an input size and how many simple operations the machine does a second. Each bar is the time for that many operations, on a log scale.
Running time by growth rate: growth rate against seconds (log scale).10^-910^-710^-510^-310^-1101,000100 thousand10 million1 billion100 billion10 trillion1,000 trillion100,000 trillionseconds (log scale)growth rateO(1)100 nsO(log n)1.8 µsO(n)20 msO(n log n)352 msO(n²)1.1 hoursO(n³)25 yearsO(2ⁿ)forever1 second

For n = 200 thousand at 10 million operations a second: O(n log n) takes 352 ms, O(n²) 1.1 hours and O(2ⁿ) forever. Within a second: O(1), O(log n), O(n), O(n log n).

Finishes within a second O(n log n) and faster
O(n²) takes 1.1 hours
O(n log n) takes 352 ms
The numbers as a table
Time for n = 200 thousand
Growth rateOperationsTime
O(1)1100 ns
O(log n)17.61.8 µs
O(n)200 thousand20 ms
O(n log n)3.5 million352 ms
O(n²)40 billion1.1 hours
O(n³)8,000 trillion25 years
O(2ⁿ)too many to countforever

At these values O(n log n) takes 352 ms and O(n²) takes 1.1 hours. Switch to 100 million steps a second, the compiled figure, and they take 35 ms and 6.7 minutes: a faster language never rescues the square. Lower n to 3,000 and O(n²) needs 900 ms, inside a second even in CPython.

Key idea

Turn the limits into a budget, the seconds times the steps a second, and compare each idea’s step count with it before you write any code.

Checkpoint

Check: Reading the limits in order

  1. Question 1 of 2 The time limit is 2 seconds and you write CPython, at the planning figure of about 10⁷ simple steps a second. About how many steps may your solution take?

    Type a number.

    A hint

    Multiply the seconds by the steps a second.

    Show the answer: Question 1 of 2

    Answer: 20000000 steps

    2 seconds × 10⁷ steps a second = 2 × 10⁷ steps, a few times 10⁷ as the lesson puts it. Every idea is then compared with that budget.

  2. Question 2 of 2 For n = 200,000, about how many comparisons does an algorithm that looks at every pair once make?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: About 2 × 10¹⁰

    Each of the n items meets the n − 1 others, and each pair is counted once, so about n²/2 = 2 × 10¹⁰ comparisons: hundreds of times any budget of a few seconds.

A target for each size

This list is an estimate, not a law: it assumes a budget of roughly 10⁸ simple steps, about a second of compiled code. Python has about a tenth of that, which moves each boundary down (for O(n²), from about 10,000 to about 3,000).

  • n up to about 10: O(n!) fits, so you can try every order, with backtracking.
  • n up to about 20: O(2ⁿ · n) fits, so you can try every subset, with bitmasks or backtracking.
  • n in the hundreds: O(n³) fits: three nested choices, such as interval dynamic programming.
  • n in the thousands: O(n²) fits: every pair, or a two-dimensional table.
  • n from 10⁵ to 10⁶: aim for O(n log n): sorting, heaps, binary search.
  • n of 10⁷ and more: aim for O(n) or better: one pass, hashing, two pointers, or a formula.

The patterns named here each have a module of their own later in this track. Reading the limits first tells you which modules to think about, and which ones you can rule out without trying them.

The boundaries in that list need not be remembered: a few lines work them out. This program finds, for each growth rate, the largest n whose step count fits 10⁷ and 10⁸ steps, by doubling n until it fails and then searching between the last two sizes:

The largest n each growth rate allows Python · budget.py
# The largest n that each growth rate allows within a budget of simple steps, worked out
# rather than remembered: about a second of CPython (10**7 steps) and of compiled code (10**8).
import math

BUDGETS = [10**7, 10**8]
GROWTH = [
    ("n!", math.factorial),
    ("2^n * n", lambda n: 2**n * n),
    ("n^3", lambda n: n**3),
    ("n^2", lambda n: n**2),
    ("n log n", lambda n: n * math.log2(n)),
    ("n", lambda n: n),
]


def largest_n(steps, budget):
    """The largest n with steps(n) <= budget: double n until it fails, then binary search."""
    high = 1
    while steps(high * 2) <= budget:
        high *= 2
    low, high = high, high * 2  # steps(low) fits the budget and steps(high) does not
    while high - low > 1:
        middle = (low + high) // 2
        if steps(middle) <= budget:
            low = middle
        else:
            high = middle
    return low


print(f"{'growth':10}{'10^7 steps':>14}{'10^8 steps':>14}")
for name, steps in GROWTH:
    sizes = "".join(f"{largest_n(steps, budget):>14,}" for budget in BUDGETS)
    print(f"{name:10}{sizes}")

Output

growth        10^7 steps    10^8 steps
n!                    10            11
2^n * n               19            22
n^3                  215           464
n^2                3,162        10,000
n log n          526,172     4,523,071
n             10,000,000   100,000,000

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 budget.py

Its table backs the list up: about 10 items for O(n!), about 20 for O(2ⁿ · n), a few hundred for O(n³), 3,162 and 10,000 for O(n²), and roughly half a million to four and a half million for O(n log n).

Checkpoint

Check: A target class for each size

  1. Question 1 of 2 According to the table the budget program printed, what is the largest n for which n² simple steps fit in 10⁷ steps?

    Type a number.

    Show the answer: Question 1 of 2

    Answer: 3162 items

    3,162² = 9,998,244 fits in 10⁷ and 3,163² = 10,004,569 does not, so O(n²) reaches about 3,000 items in a second of CPython and 10,000 in a second of compiled code.

  2. Question 2 of 2 Constraints: 1 ≤ n ≤ 20, and you must pick some of the n items. Which target does that suggest?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: O(2ⁿ · n), trying every subset

    2²⁰ is about a million subsets, and checking each one costs about n more steps: about 2 × 10⁷ in all, which fits. 20! is about 2.4 × 10¹⁸, far too many. A limit this small is often a hint that trying every subset is intended.

Measure instead of trusting rules of thumb

A planning figure is a guess about someone else’s computer. When it matters, measure. Here are the two correct solutions of the step-goal streak from the first lesson of this module, timed on their worst case, a streak that covers every day:

The brute force and the one-pass streak, timed Python · streak_timing.py
# The two correct streak solutions from the first lesson of this module, timed as n grows.
import time


def brute_force(steps, goal):  # start a streak on every day: O(n^2) when the streak is long
    best = 0
    for start in range(len(steps)):
        length = 0
        while start + length < len(steps) and steps[start + length] >= goal:
            length += 1
        best = max(best, length)
    return best


def one_pass(steps, goal):  # O(n)
    best = run = 0
    for count in steps:
        run = run + 1 if count >= goal else 0
        best = max(best, run)
    return best


def best_ms(solution, steps, runs=3):
    """The fastest of a few runs, in milliseconds: slower runs were disturbed by other programs."""
    fastest = float("inf")
    for _ in range(runs):
        start = time.perf_counter()
        solution(steps, 7000)
        fastest = min(fastest, time.perf_counter() - start)
    return fastest * 1000


print("Every day meets the goal, the worst case for the brute force.")
print(f"{'n':>9}  {'brute force':>12}  {'one pass':>10}")
brute_ms = {}
for n in [500, 1_000, 2_000, 100_000]:
    steps = [9000] * n
    if n <= 2_000:  # beyond that the brute force takes too long to wait for
        brute_ms[n] = best_ms(brute_force, steps)
    brute = f"{brute_ms[n]:9.1f} ms" if n in brute_ms else f"{'(skipped)':>12}"
    print(f"{n:>9,}  {brute}  {best_ms(one_pass, steps):7.2f} ms")
estimate = brute_ms[2_000] * (100_000 / 2_000) ** 2 / 1000  # O(n^2): 50 times the n, 2,500 times the time
print(f"Estimated brute force at n = 100,000: about {estimate:,.0f} s, against a 10 s limit for Python.")

Output

Every day meets the goal, the worst case for the brute force.
        n   brute force    one pass
      500        7.5 ms     0.02 ms
    1,000       33.2 ms     0.05 ms
    2,000      146.9 ms     0.10 ms
  100,000     (skipped)     6.28 ms
Estimated brute force at n = 100,000: about 367 s, against a 10 s limit for Python.

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 streak_timing.py

Your numbers will differ from the recorded ones, and from run to run, but the shape should be the same. If one row looks out of line, run it again: other programs on the computer disturb short timings.

  • Doubling n roughly quadruples the brute force’s time, because it is O(n²) on this input. The one-pass version roughly doubles, as O(n) should.
  • The estimate for n = 100,000 is minutes, against HackerRank’s 10-second limit for Python. Even a limit ten times as long would not be enough.
  • The one-pass version handles 100,000 days in a few milliseconds in CPython, so in Python the language was never the problem; the algorithm was.

Two habits come from this. First, choose the complexity class before you worry about the language: no time limit makes up for a class that is too slow. Second, before you submit in an online assessment, build the largest input the limits allow (here, 100,000 days that all meet the goal) and time your own solution on it. Sample tests are usually small, so they seldom tell you that a solution is too slow.

Key idea

Time your solution on the largest input the limits allow: when n doubles, about four times the time means O(n²) and about twice means O(n), and no time limit rescues a class that is too slow.

The time limit is per language on some platforms. HackerRank’s environment page lists 10 seconds for Python, 4 for Java and Go, and 2 for C and C++. A longer limit does not make an interpreted loop as fast as compiled code, so for loop-heavy plans in Python, budget with the smaller Python figure.

Not affiliated

Based on public information about HackerRank. MySmartCoPilot is not affiliated with HackerRank, and HackerRank’s real time limits may differ from what this lesson describes.

Checkpoint

Check: Measuring instead of guessing

  1. Question 1 of 2 You time your solution at n = 50,000 and n = 100,000. The second run takes about four times as long. What does that suggest?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: The solution is O(n²) on this input

    For O(n²), doubling n multiplies the work by four; for O(n), by two. The timing program showed both shapes: the brute force roughly quadrupled from 1,000 to 2,000 days, the one-pass version roughly doubled.

  2. Question 2 of 2 An O(n²) solution takes 0.2 seconds at n = 2,000. Estimate its time at n = 100,000, in seconds.

    Type a number.

    A hint

    n grows 50 times, and the time of an O(n²) solution grows with the square of that.

    Show the answer: Question 2 of 2

    Answer: 500 seconds

    100,000 / 2,000 = 50, and 50² = 2,500, so 0.2 × 2,500 = 500 seconds. The timing program makes the same estimate from its own run at 2,000 days.

Clues hidden in the limits

Besides the size, other limits point at a technique. None of these is a rule, but each is worth a second look:

The statement says What it often means
Values up to 10⁹ An array with one slot per value is out: sort, or use a hash map
A sum of up to 2 × 10⁵ values of 10⁹ each The total, 2 × 10¹⁴, overflows a 32-bit integer; use 64-bit integers in Java, C++ and Go (Python’s integers have no limit)
q queries on top of n items Scanning for every query costs n × q; prepare once so that each query is O(1) or O(log n)
k ≤ 20 for a small set of choices 2ᵏ subsets is about a million: bitmasks over the k choices
“Print the answer modulo 10⁹ + 7” The answer is a huge count: usually counting with dynamic programming or combinatorics
Up to 10⁴ test cases, with the sum of n at most 2 × 10⁵ The total is bounded, so O(n log n) per test is fine; resetting a big array for every test is not

The overflow line is easy to check: a Java int holds values up to 2,147,483,647, according to the Java Language Specification, far below 2 × 10¹⁴. The last line hides a classic slip. If each of 10⁴ test cases clears an array of 10⁶ counters, the clearing alone costs 10¹⁰ steps, though every test case is small; clear only what the test case used.

In a live round

Say the reading out loud, in one or two sentences: “n is up to two hundred thousand, so comparing every pair is about two times ten to the ten steps. I need O(n log n) or better, so I’m thinking about sorting or a hash map.” It shows the interviewer your plan, and it is the problem-solving signal the rubric in the first lesson looks for.

Scientific Notation Calculator Multiply limits such as 2 × 10⁵ by 2 × 10⁵ and compare the result with your budget. Python Online Compiler Build the largest input the limits allow and time your own solution on it.

Checkpoint

Check: Clues in the other limits

  1. Question 1 of 2 n ≤ 10⁵ values, each between 0 and 10⁹. You need to know how often each value appears. What do the limits rule out?

    Choose one answer.

    Show the answer: Question 1 of 2

    Answer: A list with one counter per possible value, because it would need 10⁹ slots

    A list indexed by value needs a slot for every possible value, a billion of them. A hash map or a sort needs memory only for the values that actually occur.

  2. Question 2 of 2 A Java solution adds up to 2 × 10⁵ values of up to 10⁹ in an int. What goes wrong?

    Choose one answer.

    Show the answer: Question 2 of 2

    Answer: The total can reach 2 × 10¹⁴, far past the int maximum of 2,147,483,647, so it overflows

    2 × 10⁵ values of 10⁹ add up to 2 × 10¹⁴, which overflows a 32-bit int. Use a 64-bit long in Java, C++ and Go; Python's integers have no limit.

Practise: the two closest readings

The exercise gives a problem with its own constraints block. Read the limits first and say which complexity you are aiming for; the long sample test stops a function after 200,000 executed lines, as a full-size hidden test would stop an O(n²) one. The tests run in your browser, with a first hint ready:

Exercise · Easy · Python

Find the two readings closest in time

A sensor logs a reading now and then, and the log keeps the time of each reading in seconds. Write closest_gap(times), which returns the smallest number of seconds between any two readings. The times are not in order, and two readings can share a time (the gap is then 0).

The statement comes with this constraints block:

  • 2 <= len(times) <= 200,000
  • 0 <= times[i] <= 10**9
  • Time limit: 2 seconds
closest_gap([40, 7, 25, 31])  # 6: the readings at 25 and 31
closest_gap([5, 90, 5])       # 0: two readings at the same time

Before you write code, read the limits as the lesson does and say which complexity you are aiming for. Comparing every pair passes the short sample tests, but the last test has 20,000 readings and stops a function after 200,000 executed lines, so it fails there, as it would fail the full-size hidden tests of a real assessment.

Starter code · closest.py

def closest_gap(times):
    """The smallest number of seconds between any two of the readings."""
    # Replace this line with your code.
    return 0
The sample tests · test_closest.py
import random
import sys

from closest import closest_gap

LINE_LIMIT = 200_000


class TooSlow(Exception):
    pass


def run_limited(times):
    """Call closest_gap, but stop it after LINE_LIMIT executed lines: a time limit that is the same everywhere."""
    executed = 0

    def count_lines(frame, event, arg):
        nonlocal executed
        if event == "line":
            executed += 1
            if executed > LINE_LIMIT:
                raise TooSlow
        return count_lines

    sys.settrace(count_lines)
    try:
        return closest_gap(times)
    except TooSlow:
        raise AssertionError(f"too slow: more than {LINE_LIMIT:,} lines ran; every pair is too many at this size") from None
    finally:
        sys.settrace(None)


def test_example():
    """the example from the prompt"""
    assert closest_gap([40, 7, 25, 31]) == 6


def test_shared_time():
    """two readings at the same time are 0 seconds apart"""
    assert closest_gap([5, 90, 5]) == 0


def test_two_readings():
    """the smallest input the limits allow"""
    assert closest_gap([1_000_000_000, 0]) == 1_000_000_000


def test_closest_pair_not_neighbours_in_the_log():
    """the closest pair is far apart in the log"""
    assert closest_gap([100, 50, 0, 75, 101]) == 1


def test_input_unchanged():
    """the caller's list is not changed"""
    times = [40, 7, 25, 31]
    closest_gap(times)
    assert times == [40, 7, 25, 31]


def test_many_readings():
    """20,000 readings within the line limit"""
    rng = random.Random(2026)
    times = rng.sample(range(0, 10**9, 1_000), 20_000)  # all different, all multiples of 1,000
    times[-1] = times[123] + 7  # one pair just 7 seconds apart
    assert run_limited(times) == 7
A hint

The values go up to 10**9, so an array with one slot per second is out, and 200,000 readings rule out every pair. If the times were in order, which readings could be the closest pair? Only certain neighbours need comparing.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Now work through the lesson’s questions. They start where your answers are weakest, rise in difficulty as you get them right, and show the working after every answer:

Practice that adapts to you

Practise this lesson

11 questions about 4 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 11 Constraints: 1 ≤ n ≤ 2 × 10⁵, time limit 1 second. Which target fits?

    Choose one answer.

    Show the answer: Question 1 of 11

    Answer: O(n log n) or better

    n² is 4 × 10¹⁰ at the largest n, hundreds of times a budget of about 10⁸ simple steps. n log₂ n is about 3.5 million, which fits easily, even in Python.

  2. Question 2 of 11 At about 10⁸ simple steps a second, roughly how many seconds do 10¹⁰ steps take?

    Type a number.

    Show the answer: Question 2 of 11

    Answer: 100 seconds

    10¹⁰ divided by 10⁸ is 10², so about 100 seconds, against typical limits of a few seconds. That is the cost of an O(n²) algorithm at n = 10⁵.

  3. Question 3 of 11 A block says: n ≤ 3,000, time limit 1 second, print the answer modulo 10⁹ + 7. You write Python. Which reading is right?

    Choose one answer.

    Show the answer: Question 3 of 11

    Answer: O(n²) is about 9 × 10⁶ steps, within a second even in CPython, and the modulus hints at counting

    Read the size first: 3,000² is about 9 × 10⁶ steps, which the budget table says fits a second of CPython. Then the other numbers: the modulus says the true answer is a huge count, usually from dynamic programming.

  4. Question 4 of 11 For n up to about 10, which kind of algorithm fits the budget?

    Choose one answer.

    Show the answer: Question 4 of 11

    Answer: O(n!), trying every order, with backtracking

    10! = 3,628,800 fits a budget of 10⁷ and 11! = 39,916,800 fits 10⁸, so trying every order is possible for about 10 items.

  5. Question 5 of 11 n ≤ 5,000 and a time limit of 2 seconds, in a compiled language. Which plan is acceptable?

    Choose one answer.

    Show the answer: Question 5 of 11

    Answer: Every pair of items, O(n²), about 2.5 × 10⁷ steps

    For n in the thousands, O(n²) fits: here 2.5 × 10⁷ steps against a budget of about 2 × 10⁸ for two seconds of compiled code. O(n³) does not.

  6. Question 6 of 11 Why does the same list of targets move each boundary down for Python?

    Choose one answer.

    Show the answer: Question 6 of 11

    Answer: CPython does about a tenth of the simple steps a second, so each class fits a smaller n

    The planning figures are about 10⁸ simple steps a second for compiled code and 10⁷ for CPython. The budget table shows the effect: n² fits 10,000 items in 10⁸ steps and 3,162 in 10⁷.

  7. Question 7 of 11 Why build and time the largest input the limits allow before you submit in an online assessment?

    Choose one answer.

    Show the answer: Question 7 of 11

    Answer: Sample tests are usually small, so they seldom tell you a solution is too slow

    Sample tests are small, so a too-slow solution passes them. Timing your own code on the largest input the limits allow, such as 100,000 days that all meet the goal, shows the problem before the hidden tests do.

  8. Question 8 of 11 One row of your timing table is far out of line with the others. What should you do first?

    Choose one answer.

    Show the answer: Question 8 of 11

    Answer: Run it again; other programs on the computer disturb short timings

    Timings depend on the computer and on what else it is doing. Keeping the fastest of a few runs, as the program does, and running an odd row again separate noise from the shape of the curve.

  9. Question 9 of 11 Constraints: n ≤ 10⁵ numbers and q ≤ 10⁵ queries, each asking for the sum of a range of positions. What should the plan be?

    Choose one answer.

    Show the answer: Question 9 of 11

    Answer: Prepare once, so that each query costs O(1) or O(log n)

    Scanning for every query costs n × q = 10¹⁰ steps. Preparing once (running totals, for example, which a later module of this track teaches) makes each query a constant amount of work.

  10. Question 10 of 11 A problem says "print the answer modulo 10⁹ + 7". What does that usually tell you?

    Choose one answer.

    Show the answer: Question 10 of 11

    Answer: The answer is a very large count, usually found by counting with dynamic programming or combinatorics

    Asking for the remainder lets the platform check a count far too large to print in full. It is a hint to count the possibilities rather than list them.

  11. Question 11 of 11 Up to 10⁴ test cases, and the sum of n over all of them is at most 2 × 10⁵. Which plans fit a budget of about 10⁸ steps?

    Choose every answer that is right.

    Show the answer: Question 11 of 11

    Answer:

    • O(n log n) work for each test case
    • O(n) work for each test case

    The sum of n is bounded, so work that grows with n adds up to the work for one big test. O(n²) per test fails, because one test case may have n = 2 × 10⁵. Clearing 10⁶ counters 10⁴ times is 10¹⁰ steps, however small the tests are.

Interview questions

Fresher · How do you turn a problem’s input limits into a target time complexity?

Start from the largest size and the time limit. Multiply the seconds by a planning figure for your language to get a budget, roughly a hundred million simple steps a second when compiled and ten million in CPython, then compare each idea’s step count with it. For n = 2 × 10⁵ and 2 seconds, every pair is about 2 × 10¹⁰ comparisons, far over the budget, while n log₂ n is about 3.5 million, so the target is O(n log n): sorting, a heap or binary search. As a guide, about 10 items allow O(n!), about 20 allow O(2ⁿ · n), the thousands allow O(n²) and 10⁷ needs O(n). Then read the other limits, such as values up to 10⁹ or extra queries, and time the plan on the largest input before trusting it.

Follow-ups usually test whether you can use the reading, not just recite it. Pick your replies to the three below; each option says what it gets right or misses:

Checkpoint

Interview round: three follow-up questions

  1. Question 1 of 3 In a live round the interviewer gives no limits at all. What is the strongest first move?

    Choose one answer.

    Show the answer: Question 1 of 3

    Answer: Ask for the largest input size and any time limit, then say which target that gives and why

    In a live round the limits are often missing, so you ask for them while clarifying. "n is up to two hundred thousand, so every pair is about two times ten to the ten steps; I need O(n log n)" is the sentence to aim for.

  2. Question 2 of 3 Up to 10⁴ test cases share one input, with the sum of n at most 2 × 10⁵. Your Python code clears a list of 10⁶ counters at the start of every test case. What do you say?

    Choose one answer.

    Show the answer: Question 2 of 3

    Answer: The clearing alone is 10¹⁰ steps; clear only the counters each test case used

    The bounded sum makes O(n log n) per test case fine, because the work adds up to that of one big test. Work that does not grow with n, like clearing a big array, is paid 10⁴ times: 10¹⁰ steps.

  3. Question 3 of 3 A platform gives Python 10 seconds and C++ 2 seconds. Your O(n²) Python solution for n = 10⁵ takes minutes. Would a C++ port pass?

    Choose one answer.

    Show the answer: Question 3 of 3

    Answer: No; 10¹⁰ steps take far more than 2 seconds even compiled, so the class has to change

    Choose the complexity class before you worry about the language: no time limit makes up for a class that is too slow. The one-pass streak handled 100,000 days in milliseconds in CPython itself.

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

  1. Fresher to mid

    In a live round the interviewer states a problem but gives no input limits. Which limits do you ask for, how do you turn the answers into a target complexity, and what do you do if the interviewer says "as large as you like"?

    Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups

  2. Mid to senior

    Your O(n log n) Python solution takes 1.6 seconds on the largest input you built, n = 10⁶, and the limit is 1 second. How do you decide whether the complexity class or the constant factor is the problem, and what do you change before you switch languages?

    Model answer, Pro. First step and follow-ups

Key takeaways

  • Read the constraints block before the story: the largest size, the time limit, then the other numbers.
  • Multiply the time limit by your language’s rate (planning figures: about 10⁸ simple steps a second compiled, 10⁷ in CPython) and compare each idea’s step count with that budget.
  • Sizes map to targets: about 20 means exponential is allowed, a few thousand means O(n²), 10⁵ and up means O(n log n) or better.
  • Limits on values, queries, counts and test cases each hint at a technique, and at a trap.
  • Measure on the largest input the limits allow. The complexity class decides far more than the language does.

Terms in this lesson

constraints block
The lines at the end of a problem statement that give the input sizes, the ranges of the values and the time limit. They say how fast a solution must be before you design one.
operation budget
How many simple steps a solution may take: the time limit in seconds times the steps the language does in a second, about 10⁸ for compiled code and 10⁷ for CPython as planning figures.

References

Related tools

Report a problem with this lesson

Quick answers and tool search

Type to search tools or to get a quick answer, for example 18% of 2500. Use the up and down arrow keys to move through the results, Enter to choose, and Escape to close.