Lesson 40.2 · Designing Data Structures
Frequencies, History and Randomness
LFU groups keys by use count with a pointer to the minimum. Time-based and snapshot stores keep sorted histories per key and binary search them. O(1) random choice uses an array plus an index map, deleting by swapping with the last element.
14 min
Think of it like this
A library that tracks how often each book is borrowed (LFU), keeps every past edition with its publication date (time-based store), and draws a random book by picking a random shelf number (random set).
1.Three more combinations
LFU: key → (value, freq), freq → LinkedHashSet<key> (insertion order breaks ties by recency), and minFreq. On access, move the key to the next frequency bucket; if the old bucket was the minimum and is now empty, minFreq++. Inserting a new key resets minFreq to 1.
Time-based / snapshot stores: key → list of (time, value) appended in increasing time, then a binary search (or TreeMap.floorEntry) for the latest version at or before a time.
Random set: an ArrayList for O(1) random access and a HashMap value → index. To delete in O(1), move the last element into the deleted slot and update its index.
Feeds (Twitter): each user's tweets are a list; the news feed merges the followed users' lists with a heap, taking the 10 newest (K-way merge, Module 19).
Remember
- Buckets + minFreq for LFU.
- Append-only histories + binary search.
- Swap-with-last for O(1) delete.
Common mistakes
- Forgetting to reset minFreq to 1 after inserting a new key.
- Deleting from the middle of an ArrayList (O(n)).