CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Redo the numbers (20 minutes)

A crawler fetches 3 billion pages per month, 300 KB each, kept for 2 years. Give pages per second, peak, storage per month and total.

Done when: you write about 1,157 per second, 2,315 peak, 900 TB per month and 21.6 PB.

Hint

3,000,000,000 / 2,592,000 seconds in 30 days is about 1,157.

Easy 2: Trace a URL (20 minutes)

Write the eleven workflow steps in your own words, and mark which two are checks that can stop a page or URL.

Done when: eleven steps, with Content Seen? and URL Seen? marked.

Hint

Both checks come after a step that produces something new.

Easy 3: Thread count (20 minutes)

A worker takes 0.4 s per page and waits 2 s between pages of the same host. How many threads give 600 pages per second?

Done when: you write 2.4 s per page, 0.417 pages per second per thread, and 1,440 threads.

Hint

0.4 + 2 = 2.4 seconds per page per thread.

Medium

Medium 1: Draw the frontier (30 minutes)

Draw the front queues, back queues, router, mapping table and selectors. Mark where priority and politeness are enforced.

Done when: a diagram with at least eight labelled parts and the two roles marked.

Hint

Back queues each hold one host.

Medium 2: Bloom filter sizing (30 minutes)

For 10 billion URLs and a 0.1 per cent false positive rate, estimate bits per URL (about 14.4 bits) and total size.

Done when: you write about 14.4 bits per URL and about 18 GB.

Hint

Bits per element is about -ln(p) divided by (ln 2) squared.

Medium 3: Trap rules (30 minutes)

List five rules to limit spider traps, such as a URL length cap, with the cost of each.

Done when: five rules, each with a side effect, such as skipping legitimate long URLs.

Hint

Think about URL length, depth, pages per site and repeated path segments.

Hard

Hard 1: Mini crawler (90 minutes)

Write a crawler for a small local test site you control. It must obey robots.txt, keep one queue per host with a delay, skip seen URLs and duplicate content, and stop after 500 pages.

Done when: it fetches the site with no repeats, respects the delay in a log, and handles a planted trap.

Hint

Use a local test server so no real site is hit.

Hard 2: Re-crawl policy (60 minutes)

Design a re-crawl schedule using update history. Pages that changed in the last 3 visits are visited daily, and stable ones weekly or monthly. Show the load on a million pages.

Done when: a table of classes with page counts, visit intervals and fetches per day.

Hint

Count pages in each class, then divide by the interval.

Hard 3: Mock interview (60 minutes)

Answer "design a web crawler" aloud in 35 minutes and mark yourself on the four steps. List two missed topics.

Done when: a recording, a score on each step, and two named gaps.

Hint

Use the four-step framework as a checklist.