Crawler Seen Pages
A small search startup crawls the web and must not fetch the same page twice. Keeping every URL it has seen in memory is too much: at about 100 bytes a URL, a billion URLs is 100 GB. A Bloom filter answers "have I seen this URL?" with about 10 bits per URL, so 1.25 GB for the same billion. The catch: it can say "maybe seen" for a URL it never saw (the crawler then skips a page it should have fetched), but it never says "not seen" for a URL that was added.
The same structure sits in front of disk lookups in key-value stores, to skip reading files that cannot hold a key, and in front of caches, to drop requests for keys that do not exist. See Design a Web Crawler and Design a Key-Value Store.
Your task
Write a class SeenFilter with a bit array of m bits, all 0 at the start, and k hash positions per URL:
add(url): set the bits at allkpositions ofurlto 1.mightContain(url): returntrueif allkpositions ofurlare 1, otherwisefalse.bitsSet(): return how many of thembits are 1.
The positions come from two fixed hashes of the URL, spelled out here so every solution picks the same bits. For each character from left to right, with c its character code:
h1 = (h1 × 31 + c) mod 1,000,000,007, starting fromh1 = 0h2 = (h2 × 37 + c) mod 1,000,000,009, starting fromh2 = 0
Position i, for i from 0 to k − 1, is (h1 + i × h2) mod m. Two positions of one URL may be the same bit.
class SeenFilter
Examples
new SeenFilter(16, 3)
.add("cats.io")
.add("dogs.io")
.add("owls.io")
.bitsSet()
.mightContain("dogs.io")
.mightContain("yaks.io")
.mightContain("bats.io")[null, null, null, null, 9, true, false, true]
For "cats.io", h1 = 750,493,409 and h2 = 956,570,721, so the positions are 750,493,409 mod 16 = 1, then 2, then 3. "dogs.io" sets 9, 8, 7 and "owls.io" sets 11, 5, 15: 9 bits in all. "dogs.io" was added, so it is found. "yaks.io" needs bits 2, 15 and 12; bit 12 is 0, so it was certainly never added. "bats.io" needs bits 7, 1 and 11, which other URLs happened to set: a false positive. The filter says "maybe" for a URL it never saw.
Constraints
- 1 ≤ m ≤ 100,000
- 1 ≤ k ≤ 16
- Each URL has 1 to 100 printable ASCII characters (codes 33 to 126)
- At most 2,000 calls per test
Start with brute force
A hash set of every URL is exact, but it stores the URLs: about 100 GB for a billion of them, which does not fit in one machine's memory, so every check becomes a network or disk lookup.
The Bloom filter trades exactness for size. With about 10 bits per URL and 7 hash positions, the false positive rate is roughly (1 − e−0.7)7 ≈ 0.8%, for 1.25 GB instead of 100 GB.
Hints
0 of 4 shown- Hint 1
A plain set stores the URLs themselves. What could you store instead if you were allowed to be wrong in one direction only?
- Hint 2
Store only bits. Adding a URL turns on a few bits chosen by hashing it. If any of those bits is still off later, the URL was never added; if all are on, it probably was.
- Hint 3
Compute
h1andh2once per URL, then get thekpositions from(h1 + i × h2) mod m. Take each step of the hash modulo its prime, so the numbers stay small enough for exact JavaScript arithmetic. - Hint 4
Use an array of
mbooleans or 0/1 values, and keep a counter that goes up only when a bit changes from 0 to 1, sobitsSetis O(1). Do not count a bit twice when two positions coincide.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The filter is an array of bits. Adding sets k bits picked by hashing; checking reads the same k bits. Getting k positions from two hashes, h1 + i × h2, is a standard trick that avoids computing k separate hash functions.
Trace the example, m = 16, k = 3:
- add "cats.io": positions 1, 2, 3. Bits on: {1, 2, 3}.
- add "dogs.io": 9, 8, 7. Bits on: {1, 2, 3, 7, 8, 9}.
- add "owls.io": 11, 5, 15. Bits on: {1, 2, 3, 5, 7, 8, 9, 11, 15}, so
bitsSet()is 9. - "yaks.io" needs 2, 15, 12. Bit 12 is off: definitely not seen.
- "bats.io" needs 7, 1, 11, all on: "maybe seen", though it never was.
Why there are no false negatives: adding only ever turns bits on, so the bits of an added URL stay on. That is also why you cannot delete from a plain Bloom filter: turning a bit off could erase another URL. Size it up front: with n URLs and m bits, the best k is about (m / n) × 0.69, and the filter gets worse as it fills, as the crowded test shows.
class SeenFilter {
constructor(m, k) {
this.m = m;
this.k = k;
this.bits = new Uint8Array(m); // one byte per bit, for clarity
this.count = 0;
}
positions(url) {
let h1 = 0, h2 = 0;
for (let i = 0; i < url.length; i++) {
const c = url.charCodeAt(i);
h1 = (h1 * 31 + c) % 1000000007; // stays far below 2^53
h2 = (h2 * 37 + c) % 1000000009;
}
const out = [];
for (let i = 0; i < this.k; i++) out.push((h1 + i * h2) % this.m);
return out;
}
add(url) {
for (const p of this.positions(url)) {
if (!this.bits[p]) { this.bits[p] = 1; this.count++; } // count 0 -> 1 only
}
}
mightContain(url) {
return this.positions(url).every((p) => this.bits[p] === 1);
}
bitsSet() {
return this.count;
}
}class SeenFilter:
def __init__(self, m, k):
self.m = m
self.k = k
self.bits = bytearray(m) # one byte per bit, for clarity
self.count = 0
def _positions(self, url):
h1 = h2 = 0
for ch in url:
c = ord(ch)
h1 = (h1 * 31 + c) % 1000000007
h2 = (h2 * 37 + c) % 1000000009
return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, url):
for p in self._positions(url):
if not self.bits[p]: # count 0 -> 1 only
self.bits[p] = 1
self.count += 1
def might_contain(self, url):
return all(self.bits[p] for p in self._positions(url))
def bits_set(self):
return self.countRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.