Arrays and searching 0/120

Lesson 9 of 9

Data structure design: caches, stacks and queues

Keep two views of the same items in sync so every method meets its time limit: a random-pick set, an LRU cache, a timestamped store and an LFU cache.

4,085 words · 19 min read

Part 1 of 9 Designing a structure

What is a data-structure design problem?

A data-structure design problem asks for a class instead of one function. The statement lists the methods, what each one returns and, in three of this lesson's four problems, how fast each call must run: O(1)O(1) on average. The judge then calls the methods in some order, up to 200,000 times in each problem here, and checks every return value. Let's start with an example.

Design a class RandomizedSet that holds a set of integers. insert(val) adds val and returns true, or returns false if val is already stored. remove(val) deletes val and returns true, or returns false if val is missing. getRandom() returns one stored value, each stored value with the same probability. Every method must run in O(1)O(1) time on average.

LeetCode creates the object and calls the methods in the order given. The output lists what each call returns, with null for the constructor.

Constraints

  • −231≤-2^{31} \le val ≤231−1\le 2^{31} - 1
  • At most 2×1052 \times 10^5 calls in total
  • getRandom is only called when the set holds at least one value

Sample · Input

["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]

Output

[null,true,false,true,2,true,false,2]

Before thinking about structures, let's read the sample call by call. insert(1) returns true. remove(2) returns false, because 2 was never inserted. insert(2) returns true, so the set holds 1 and 2 and the first getRandom() may return either; the output shows one possible run. remove(1) returns true, the second insert(2) returns false because 2 is already stored, and the last getRandom() must return 2, the only value left.

A hash set and an array each manage part of the job in O(1)O(1). A hash set inserts and removes in O(1)O(1) on average, but its members have no positions 0, 1, 2 to choose among, so picking a random member means walking the set. An array picks values[k] for a random index kk in one step, but finding val to remove it is a scan. With 10510^5 values stored, 10510^5 removals of a value that is not there each read every slot:

105×105=1010 slot reads10^5 \times 10^5 = 10^{10} \text{ slot reads}

At a judge's rough rate of 10810^8 simple steps a second, that is around 100 seconds.

Keep two views of the same items

Each structure is fast for part of the job, so we store the same items in both. A design built this way keeps two views of the same items: one finds an item by its key, and the other keeps the position, order or count the remaining methods ask about. The price is bookkeeping: every method that adds, moves or removes an item updates both views before it returns, so the next call finds them in agreement.

We build four designs this way: the set above, a cache that evicts the key used longest ago, a store that answers by timestamp, and a cache that evicts the key used the fewest times.