Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 63 ยท Practice and Review

Competitive Programming Interview Questions

Twenty-four competitive programming questions with short answers: complexity limits, greedy proofs, modular math, DP, graphs, and debugging, with runnable Python.

Interviews and team-selection rounds for contest programmers rarely ask you to solve a brand new problem in the first five minutes. They ask short questions about technique: "How do you know a greedy is correct?", "Why do we take answers modulo 1,000,000,007?", "What does n = 2 * 10^5 tell you?". Good answers show that you understand why a method works, what it costs, and when it breaks.

This page collects twenty-four such questions, grouped by topic, with answers short enough to say out loud in about a minute. Each answer points to the lesson that explains the idea in depth. A strong answer has three parts: the fact, the reason, and the trade-off. "Binary search is O(log n)" is a fact; "...because every check halves the candidate range, but only if the predicate is monotone" is an answer.

Complexity and limits

1. How do you choose an algorithm from the constraints?

Read the largest input size and map it to an operation budget. A judge does roughly 10^8 simple operations per second in a compiled language and far fewer in Python, so n = 10^5 allows O(n log n), n = 5000 allows O(nยฒ), n <= 20 allows O(2^n) or O(n ยท 2^n), and n <= 10^18 forces O(log n) math. The constraints are the biggest hint in the statement. See Reading a Problem Statement and Estimating Time and Memory.

2. Why is Python risky in contests, and how do you cope?

Python executes around 10^7 simple operations per second, so a solution that passes in C++ at 10^8 steps will time out. Cope by choosing a better algorithm first, then by using built-ins that run in C (sorted, sum, max, slicing, str.join), fast input with sys.stdin, and by avoiding deep recursion. See Python for Contests.

3. A solution is O(nยฒ) with n = 10^5. What now?

That is about 10^10 steps, far too many. Look for what the inner loop recomputes: a running sum (prefix sums), a window (two pointers), a minimum over a range (sparse table or segment tree), or a monotone choice (sort, then sweep). The usual goal is to bring the inner work down to O(1) or O(log n).

4. What is the difference between time limit and memory limit problems?

Time is usually the tight resource, but memory bites on large tables: a Python list of 10^7 integers takes roughly 80 MB for the pointers alone, and a 5000 x 5000 DP table has 25 million cells. Roll the DP array (keep only the previous row) or switch to array/NumPy when memory is the limit.

Python Turn constraints into a plan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy and searching

5. How do you prove a greedy algorithm is correct?

With an exchange argument (take any optimal solution and swap its first differing choice for the greedy one without making it worse) or a stays-ahead argument (show after every step the greedy partial answer is at least as good as any other). If you cannot prove it, test it against a brute force on thousands of small random inputs. See Greedy Algorithms and How to Trust Them.

6. Give an example where a plausible greedy fails.

Coin change with coins {1, 3, 4} and amount 6: greedy takes 4 + 1 + 1 (three coins), but 3 + 3 uses two. The same pattern appears in knapsack and in "take the shortest interval first". When the greedy choice can block two better later choices, you need DP.

Python Greedy coin change versus DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

7. When can you binary search on the answer?

When there is a monotone predicate: if answer x is feasible then every larger (or every smaller) value is feasible too. You binary search the boundary and test each candidate with an O(n) or O(n log n) check, for a total of O(n log range). Typical phrases are "minimize the maximum" and "maximize the minimum". See Binary Search on Answer for Contests.

8. What are the most common binary search bugs?

An infinite loop from lo = mid with a floor midpoint, an off-by-one in the final answer (lo versus lo - 1), a predicate that is not truly monotone, and bounds that are too small. Fix them by choosing one invariant ("lo is infeasible, hi is feasible") and keeping it.

9. How do two pointers count subarrays with "at most k" of something?

Move the right end forward, and move the left end only forward while the window is invalid. For every right end, the number of valid subarrays ending there is the window length. "Exactly k" equals "at most k" minus "at most k - 1". See Two Pointers and Sliding Windows in Practice.

Math

10. Why do problems ask for the answer modulo 1,000,000,007?

True answers (counts of arrangements, paths, subsets) get astronomically large, and returning them modulo a prime keeps every number in the machine word and makes division possible: for a prime p, b has an inverse b^(p-2) or pow(b, -1, p). The prime is arbitrary but standard. See Modular Arithmetic.

11. How do you divide under a modulus?

Never use //. Multiply by the modular inverse: a / b mod p = a * pow(b, -1, p) mod p, valid when gcd(b, p) = 1. Python's pow accepts a negative exponent with a modulus since version 3.8. In other languages use Fermat's little theorem with fast exponentiation.

12. How do you compute n choose k modulo a prime for many queries?

Precompute factorials and inverse factorials up to the largest n once, then answer each query as fact[n] * inv_fact[k] * inv_fact[n-k] % p in O(1). See Counting and Combinatorics.

Python Binomials under a prime modulus

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

13. How does a sieve help, and what does it cost?

The sieve of Eratosthenes marks composites in O(n log log n) time and O(n) memory, giving all primes up to n. A smallest-prime-factor sieve also factorizes any number up to n in O(log n). See Number Theory Toolkit.

14. What is linearity of expectation, and why is it so useful?

E[X + Y] = E[X] + E[Y] holds even when X and Y are dependent. To get the expected value of a complicated count, split it into indicator variables, find each one's probability, and add them. No need to enumerate outcomes. See Probability and Expected Value.

Data structures

15. When do you use prefix sums, and when a Fenwick tree?

Prefix sums answer range-sum queries in O(1) after O(n) preprocessing, but only if the array never changes. If values are updated between queries, use a Fenwick tree or segment tree: both give O(log n) per update and query. See Prefix Sums and Difference Arrays and Fenwick and Segment Trees for Contests.

16. How does a monotonic stack find the next greater element in O(n)?

Keep indices in a stack whose values decrease. When a new value arrives, pop every smaller value: the new one is their next greater element. Each index is pushed and popped once, so the total work is O(n) even though there is a loop inside a loop. See Monotonic Stacks, Heaps and Deques in Contests.

17. What is lazy deletion in a heap?

Python's heapq cannot remove an arbitrary item cheaply. Instead you leave stale entries in the heap, and when you pop one that no longer matches the current state (for example an old distance in Dijkstra), you discard it. Every push is paid for by at most one pop, so the complexity stays O(log n) per operation.

Python Next greater element with a monotonic stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Graphs and DP

18. BFS or Dijkstra? What about 0-1 BFS?

BFS gives shortest paths when every edge costs the same. Dijkstra handles non-negative weights in O((V + E) log V). If weights are only 0 and 1, a deque-based 0-1 BFS (push zero-cost moves to the front) does it in O(V + E). Negative weights need Bellman-Ford, which is O(VE). See Graph Problems: Modeling and Traversal and Shortest Paths in Practice.

19. How do you decide the state of a DP?

Ask: "what is the minimum information I need about the past to make the remaining choices?" That information is the state. Then write the transition, the base cases, and the iteration order so that every state is computed after the states it depends on. Count the states times the transition cost to get the complexity. If it is too large, shrink the state or add a speedup from DP Speedups.

20. Why do 2D DP tables often need only two rows?

If row i depends only on row i - 1, keep two rows (or one row, updating in the right direction). Memory drops from O(nm) to O(m). In 0/1 knapsack you iterate capacities downwards so each item is used once; iterating upwards gives the unbounded version.

Debugging and habits

21. Your solution gets Wrong Answer on test 3. What do you do?

Re-read the statement for missed constraints, then write a slow, obviously correct brute force and compare them on random small inputs with a fixed seed. Shrink the first failing case by hand until you can trace it on paper. See Stress Testing with a Brute Force and Verdicts and Debugging.

22. What are the classic edge cases to check?

n = 1, all equal values, already sorted and reverse-sorted data, negative numbers, zero, the maximum values (for overflow in C++ and Java), and answers that need 64-bit or modular arithmetic. Also check // and % with negative numbers. See Edge Cases and Common Pitfalls.

23. Why shouldn't you compare floating-point numbers with ==?

Binary floating point cannot represent most decimals exactly, so 0.1 + 0.2 == 0.3 is False. Compare with a tolerance (abs(a - b) < 1e-9), or, better, avoid floats by keeping fractions as integer numerators and denominators.

24. How do you manage time in a live contest?

Read all problems quickly, solve in order of difficulty as you estimate it, never sit on one stuck problem for more than a set time, and always test the samples and two edge cases before submitting. Afterward, upsolve the problems you missed. See Templates and Habits.

Python Why floats and negative modulo surprise people

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A problem has n up to 2 * 10^5 and a 1-second limit. Which complexity is the realistic target?

    At 2 * 10^5, O(nยฒ) would be about 4 * 10^10 steps. O(n log n) is a few million, which fits even in Python.
  2. 2. Why is division under a prime modulus done with a modular inverse?

    Integer division does not commute with taking a remainder. Multiplying by b^(-1) mod p gives the right residue when gcd(b, p) = 1.
  3. 3. What is the best way to gain confidence in a greedy you cannot prove?

    Samples are few and often friendly. A brute force over thousands of random small cases finds counterexamples quickly.
  4. 4. Why is a monotonic stack O(n) overall despite the inner while loop?

    The inner loop's total iterations across the whole run equal the total number of pops, which is at most n.

Summary

  • Constraints tell you the target complexity; map n to a budget before you code.
  • Prove greedy ideas with exchange or stays-ahead arguments, or hunt for counterexamples with a brute force.
  • Binary search on the answer needs a monotone predicate and one clear invariant.
  • Under a prime modulus, multiply by inverses; precompute factorials for binomials.
  • Pick structures by whether data changes: prefix sums for static data, Fenwick or segment trees for updates.
  • Debug with a brute force, small cases, and edge-case checklists; manage the clock deliberately.

Next, keep the essentials on one page in the Competitive Programming Cheat Sheet.