Problems Base course RU

Found in

databases

Articles

DS Data structure Bloom filter Says “surely not” or “maybe yes” about set membership, at about 10 bits per item. O(k) 2 problems DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems SYS Algorithm Consistent hashing Spreads keys over servers so that adding a server moves only its share. O(log(N·v)) to find a server 1 problem SYS Data structure CRDT Data whose copies are edited independently and merged in any order: counters, sets, text. O(1) per operation for a counter and a set; insertion into text O(1) on average 2 problems TEC Technique Coordinate compression Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks. O(n log n) to compress 2 problems

Problems

The floors of an index How many pages has the index Two swapped keys Loading in order

Often together

in production 4 interviews 3 range queries 3 classic 3 hashing 2 search tree 2 tree 2 searching 2 contests 2 replication 2 distributed systems 2 membership 1