Get started

Python Interview Prep Quiz: Idioms, Pitfalls and LRU Cache

A final Python interview practice test: 15 questions and three programs on fast input, sliding windows, pitfalls, LRU caches, hash maps, stacks and intervals.

  • Course: Python study plan
  • Module: Interview idioms
  • Kind: Checkpoint — cleared at 70%
  • Reading time: 30 min
  • Runtime: CPython 3.11

Final checkpoint — Interview idioms is the checkpoint that closes the Interview idioms module: a graded quiz and whole-program exercises, passed at 70%.

Instructions

The last checkpoint of the Python plan. It covers the round and the file template, the idiom sheet, the twelve pitfalls, the hash map, dynamic array, LRU cache and heap by hand, clean-solution habits and the theory drill — and, being the last one, it reaches back across the whole track: collections, generators, classes, exceptions, the standard library and the cost model.

How it works. Fifteen questions and three programs; 70% on the questions and every program accepted clears the module. With every other module complete, that also completes the plan.

Before you start, make sure you can answer these from memory:

  • Why sys.stdin.buffer.read().split() beats input() in a loop, and when it does not matter.
  • Which shape "longest subarray with at most k distinct" is, and the idiom for it.
  • Why [[0] * n] * m is wrong, and why a mutable default argument is shared.
  • What makes get, put and eviction all O(1) in an LRU cache.
  • Why a hash map resizes at a load factor, and what that does to the cost of put.
  • What -7 // 2 and -7 % 2 are, and why.
  • The one-sentence answers for the GIL, a generator and is versus ==.

The three programs are the classics interviewers set: a sliding-window rate limiter over a stream of timestamps with a deque, an RPN evaluator with a stack, an operator table and per-line error handling, and an interval merger with sorted keys, a coverage total and bisect queries.

Common questions

Which pattern is "longest subarray with at most k distinct" values?

A sliding window. Advance the start index while the window holds more than k distinct values, tracking counts in a dict or Counter and deleting a key when its count reaches zero; each element enters and leaves once, so the scan is O(n).

What makes get, put and eviction all O(1) in an LRU cache?

A dict maps each key to a node in a doubly linked list ordered by use, so a node can be found, unlinked and moved to the tail in O(1), and the least recently used entry is always at the head. OrderedDict.move_to_end and popitem(last=False) do exactly that.

What are -7 // 2 and -7 % 2 in Python?

-4 and 1. Floor division rounds towards negative infinity, and the remainder takes the divisor's sign, so that (a // b) * b + a % b == a always holds.

Why does sys.stdin.buffer.read().split() beat input() in a loop?

It reads the whole input in one call as bytes, with no per-line call and no decoding, and int() accepts the byte tokens directly. It matters for large inputs such as 10⁵ lines; for a few lines, input() is fine and clearer.

Exercises

A sliding-window rate limiter

Read limit window on the first line, then non-decreasing integer timestamps one per line until EOF. A request at time t is allowed when fewer than limit requests were allowed in the interval (t - window, t]; keep the allowed timestamps in a deque, dropping those at or before t - window from the front. Print t=<t> allow or t=<t> deny per request, then allowed <a> denied <d>.

Input: the limit and window, then timestamps. Output: one line per request, then the totals.

2 10
1
2
3
11
12
13

prints

t=1 allow
t=2 allow
t=3 deny
t=11 allow
t=12 allow
t=13 deny
allowed 4 denied 2

An RPN evaluator

Read one reverse-Polish expression per line until EOF: integer tokens and the operators +, -, *, / (division truncates towards zero, as int(a / b)). Evaluate each with a stack and a dict from operator to function, and print = <value>, or error: stack underflow when an operator lacks two operands, error: division by zero, error: bad token <token> for anything else, or error: leftover operands when more than one value remains. Handle each error with a specific exception, not a bare except.

Input: one expression per line. Output: one line per expression.

2 1 + 3 *
4 13 5 / +
10 6 9 3 + -11 * / * 17 + 5 +
1 +
1 0 /
1 2
1 x +

prints

= 9
= 6
= 22
error: stack underflow
error: division by zero
error: leftover operands
error: bad token x

Merge intervals with bisect queries

Read n, then n lines a b (inclusive integer intervals, in any order), then q and q query points one per line. Merge overlapping or touching intervals after sorting by start, and print merged [a,b] [c,d] ..., covered <sum of (end - start) over the merged intervals>, then for each query t=<x> covered or t=<x> free, found with bisect_right on the merged starts.

Input: the intervals, then the queries. Output: two summary lines, then one line per query.

3
1 3
2 6
8 10
3
5
7
10

prints

merged [1,6] [8,10]
covered 7
t=5 covered
t=7 free
t=10 covered

In this module: Interview idioms

← The Python theory drill — thirty questions, thirty answers