Problems Base course RU

Built on

hash table

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 GRA Technique Storing a graph Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.

neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists

2 problems 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 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

Is there such a street piece Two books for a gift card A shared shopping list A storm of retries Frequent words in one pass Orders by deadline Tolstoy's anagrams A ring from its pieces Merge edits without a server Triangles of imports The fifteen puzzle in the fewest moves

Often together

array 4 interviews 4 in production 4 classic 3 databases 2 queue 2 measurement 2 hashing 1 membership 1 frequencies 1 security 1 graph 1