Problems Base course RU

Solves

measurement

Articles

TEC Technique Big O How work grows with the data: O, Ω and Θ, rules for estimating code, and where asymptotics mislead. estimated from the program text 1 problem TEC Technique Fast input and output A million numbers in tens of milliseconds instead of a second: reading it all at once, a buffer and one write of the output. O(size of the input) 1 problem TEC Technique How to benchmark honestly Repetitions, warm-up, median and minimum, timeit and testing.Benchmark—and the usual ways to fool yourself with a measurement. enough repetitions for a series to take at least a tenth of a second 1 problem TEC Technique Cache-friendly data The same algorithm, a different order of memory accesses: tiling, padded rows and laying data out by field. the same big O 1 problem TEC Technique Complexity from measurements The growth of running time from measurements: the slope, the ratio test, exponentials, and where measurement lies. O(B) per attempt 1 problem TEC Technique Amortized analysis A bound on a whole sequence of operations, not on each one: by a sum, by coins and by a potential, and where it does not help. a bound on a sequence 2 problems TEC Technique Choosing a data structure First the list of operations, then the structure: the cost of each operation in Python and Go on one map. depends on the choice 1 problem

Problems

A million temperatures A robust timing estimate A verdict from measurements How much Horspool reads Cache misses

Often together

interviews 6 in production 5 estimation 3 array 3 classic 2 contests 2 amortized 2 hash table 2 queue 2 cache-friendly 1 matrix 1 images 1