Loading page…
Practice problem · medium
A product list page lets a shopper switch tag filters on and off, such as sale or in stock. The page caches each result list under the set of filters that are on.
The page keeps one working set of filters and edits it in place, because that is the cheapest thing to do. A teammate stored that working set itself as the cache key. After a few clicks the cache gave wrong answers.
You count the cache hits correctly.
Write filter_cache_hits(commands, tags).
commands[i] is "add", "remove" or "search". For "add" and "remove", tags[i] is a tag number, from 1 to 100,000. For "search", tags[i] is 0 and is ignored."add" turns a tag on, and does nothing when it is already on. "remove" turns a tag off, and does nothing when it is not on."search" looks up the set of tags that are on now. The same tags in any order are the same set, and the empty set is a valid set.1, when that set was searched before. Otherwise it is a miss, 0. Every search then stores its set in the cache."search", in order.Input: commands = ["add", "add", "search", "remove", "search", "add", "search"], tags = [1, 2, 0, 2, 0, 2, 0]
Output: [0, 0, 1]The trace edits the working set and looks it up at each search.
| Step | Command | Working set after | Searched before | Answer |
|---|---|---|---|---|
| 1 | add 1 |
{1} | ||
| 2 | add 2 |
{1, 2} | ||
| 3 | search |
{1, 2} | none | 0, then {1, 2} is stored |
| 4 | remove 2 |
{1} | ||
| 5 | search |
{1} | {1, 2} | 0, then {1} is stored |
| 6 | add 2 |
{1, 2} | ||
| 7 | search |
{1, 2} | {1, 2}, {1} | 1 |
Input: commands = ["search", "add", "remove", "search"], tags = [0, 5, 5, 0]
Output: [0, 1]The first search looks up the empty set, a miss. The tag 5 goes on and off, and the second search finds the empty set again.
Input: commands = ["add", "add", "search", "remove", "remove", "add", "add", "search"], tags = [1, 2, 0, 1, 2, 2, 1, 0]
Output: [0, 1]The second search sees the tags 2 and 1, in the opposite order. It is the same set as {1, 2}, so it is a hit.
1 ≤ commands.length = tags.length ≤ 100,0001 ≤ tags[i] ≤ 100,000 for "add" and "remove", and tags[i] = 0 for "search"Comparing the current set with every set searched before costs one comparison for each stored set. With about 30,000 searches that reach about 19,000 different sets, the comparisons add up to about 3 × 10^8 set comparisons. A table finds a stored set in one step on average.
The bound of 8 tags means that building a key from the working set costs a few steps. It is a small cost for each search.
filter_cache_hits · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.