Problems Base course RU

Solves

frequencies

Articles

DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems DS Data structure Fenwick tree Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index. O(log n) per prefix sum and per update 2 problems STR Algorithm Huffman code The optimal prefix code for character frequencies: the two rarest trees are glued together until one is left. O(n log n) 2 problems SYS Data structure Count-Min Sketch Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards. O(d) per item and per query 2 problems

Problems

Frequent words in one pass How many bits the text takes Tolstoy's anagrams Two estimates A gift with a purchase

Often together

classic 3 in production 3 hashing 2 array 2 interviews 2 compression 2 hash table 1 membership 1 security 1 databases 1 prefix sums 1 range queries 1