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.
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:
- 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.
- 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.
- 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:
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).
The numbers as a table
| Growth rate | Operations | Time |
|---|---|---|
| O(1) | 1 | 100 ns |
| O(log n) | 17.6 | 1.8 µs |
| O(n) | 200 thousand | 20 ms |
| O(n log n) | 3.5 million | 352 ms |
| O(n²) | 40 billion | 1.1 hours |
| O(n³) | 8,000 trillion | 25 years |
| O(2ⁿ) | too many to count | forever |
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
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 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
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
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
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 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
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
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
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.
Checkpoint
Check: Clues in the other limits
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,0000 <= 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.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
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.
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
Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.
-
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"?
-
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?
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
- time.perf_counter() (Python Software Foundation)
- Time complexity of operations on built-in types (Python Software Foundation)
- Numeric types: int, float, complex (Python Software Foundation)
- The Java Language Specification, Java SE 25: integral types and values (Oracle)
- Execution environment (HackerRank)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress