Data structures

Cards

1. A geohash turns a latitude and longitude into a short string. Points that share a longer _____ are in the same, smaller cell, so a database can find nearby points with a _____ query on an ordinary index. easy Fill in the blank
2. Which structure estimates how many requests each of millions of IP addresses has made, in fixed memory? easy Multiple choice
3. A search engine keeps, for each word, the list of documents that contain it. This structure is an _____. easy Fill in the blank
4. A game needs a live leaderboard for 10 million players: the top 100 and any player's rank, updated on every score. What fits best? easy Multiple choice
5. How can you track exactly which of 100 million users were active each day, in little memory? medium Flashcard
6. A Bloom filter says a key "might be present" or "is definitely not present". Which mistake can it make? medium Multiple choice
7. A Bloom filter for 100 million keys with a 1% false-positive rate needs about 9.6 bits per key. How much memory is that? medium Estimate
8. What does a count-min sketch estimate, and in which direction is it wrong? medium Flashcard
9. You need a compact "is this key in the set?" filter like a Bloom filter, but keys must also be deleted. What fits? medium Multiple choice
10. To find drivers near a rider, you look up the rider's geohash cell. Why must you also search the neighbouring cells? medium Multiple choice
11. You need the number of unique visitors per page, for billions of visits. What data structure fits, and what does it trade? medium Flashcard
12. In a _____, every parent holds a hash of its children's hashes. Two replicas compare their _____ hashes first and descend only into the subtrees whose hashes differ. medium Fill in the blank
13. When would you pick a quadtree over a fixed geohash grid? medium Flashcard
14. How does a trie make autocomplete fast enough for every keystroke? medium Flashcard
15. What is a skip list, and where is it used? hard Flashcard
16. How do you track the top 100 hashtags in a stream with millions of distinct tags, in bounded memory? hard Flashcard