1Show the Level 1 solution
2**A.**
31. **Functional** (verb: upload).
42. **Non-functional** (adjective: fast).
53. **Functional** (verb: follow).
64. **Non-functional** (adjective: durable).
75. **Non-functional** (adjective: available).
86. **Functional** (verb: search).
910**B.** One good question per letter (others are fine too):
11- **Scope:** "Is it just tracking the order status, or the rider's live location on a map as well?"
12- **Count:** "How many orders a day, and how many riders sending location at the same time?"
13- **Access pattern:** "How often does the rider's app send its location, and how often do customers refresh?"
14- **Latency:** "How fresh must the rider's position be on the customer's map: 1 second, 10 seconds?"
15- **Exactness:** "Is it OK if the map is a few seconds behind? Must order status changes (like 'delivered') be exact?"
Show the Level 2 solution
1. Seconds in 30 days = 30 × 24 × 3,600 = 2,592,000. New links per second = 100,000,000 ÷ 2,592,000 ≈ **39 per second** (call it about 40).
2. Redirects = 100 × 39 ≈ **3,900 per second** on average (call it about 4,000).
3. Links in 5 years = 100 million × 12 × 5 = 6 billion. Storage = 6 billion × 500 bytes = **3 TB** (3 × 10¹² bytes).
4. 62⁵ = 916,132,832 (about 0.9 billion), **not enough** for 6 billion. 62⁶ = 56,800,235,584 (about 56.8 billion), enough with lots of room. So **6 characters**.
1Show the Level 3 solution
2Tested solution (Python 3):
34```python
5import string
67ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase # 62 characters
8910def to_base62(n):
11 if n == 0:
12 return ALPHABET[0]
13 out = []
14 while n > 0:
15 n, r = divmod(n, 62)
16 out.append(ALPHABET[r])
17 return "".join(reversed(out))
181920class Shortener:
21 def __init__(self, base_url="https://sho.rt/"):
22 self.base_url = base_url
23 self.next_id = 1
24 self.code_to_url = {}
25 self.url_to_code = {} # so the same long URL gets the same short code
2627 def shorten(self, long_url):
28 if not long_url.startswith(("http://", "https://")):
29 raise ValueError("not a valid URL")
30 if long_url in self.url_to_code:
31 return self.base_url + self.url_to_code[long_url]
32 code = to_base62(self.next_id)
33 self.next_id += 1
34 self.code_to_url[code] = long_url
35 self.url_to_code[long_url] = code
36 return self.base_url + code
3738 def resolve(self, code):
39 return self.code_to_url.get(code) # None means "404 Not Found"
40```
4142All five checks pass. The full file with the checks is in `code/ch01_url_shortener.py`.
4344*Note:* counter-based codes are guessable (code 1, 2, 3...). That's a trade-off to name in the interview (see Q8).
1Show the Level 4 solution
2**A. The bug:** the code never checks whether the random code is **already taken**. When it is, the dictionary entry is **overwritten**.
341. Alice shortens her page and gets code `aB3x9Q`. She shares it.
52. Months later, Bob shortens a different page. The random generator happens to produce `aB3x9Q` again.
63. `code_to_url["aB3x9Q"] = bob_url` replaces Alice's entry. No error is raised.
74. Everyone clicking Alice's link now lands on Bob's page. Alice's link is lost for good.
89"56.8 billion codes" sounds safe, but the chance of a clash grows with every link stored. With 1 billion links already saved, each new random code has about a 1 in 57 chance (1.8%) of hitting an existing one. That's a lost link roughly every 57 new links.
1011**The fix:** check before you write, and pick again if the code is taken.
1213```python
14def shorten(long_url):
15 while True:
16 code = "".join(random.choice(ALPHABET) for _ in range(6))
17 if code not in code_to_url:
18 code_to_url[code] = long_url
19 return code
20```
2122In a real database, make `code` the **primary key** (or add a unique constraint), so the database itself rejects a duplicate even if two servers try the same code at the same moment. Then retry with a new code. The tested demo in `code/ch01_url_shortener.py` uses 2-character codes so the clash shows up fast: the buggy version lost 27 of 500 links, the fixed version lost none.
2324**B.** Mistakes in the opening:
251. **No clarifying questions.** It jumps straight into a design (1.5).
262. **Over-engineering.** Three microservices and Kafka before knowing the scale (1.13).
273. **Buzzwords without reasons.** "Cassandra because it scales" with no link to the requirements (1.11).
284. **A risky choice with no trade-off.** Hashing with MD5 and cutting it short can make two URLs share a code. The collision problem isn't mentioned.
295. **Silence.** Two minutes of silent drawing (1.12).
306. **An unjustified scale claim.** "A billion users" was never agreed with the interviewer (1.5).
1Show the Level 5 (sketch) solution
21. **Functional:** create a paste, read a paste by link, optional expiry. **Non-functional:** fast reads, highly available, pastes never lost before expiry, unguessable links for private pastes. **SCALE questions:** max paste size? pastes per day? read/write ratio? how long are pastes kept? public or private?
32. **Numbers (assumed):** 1 million new pastes a day ≈ 12 writes a second; 10 reads per write ≈ 120 reads a second; average paste 10 KB ≈ 10 GB a day ≈ 3.65 TB a year.
43. **API:** `POST /pastes {content, expires_in}` → `{url}`; `GET /pastes/{id}` → content, or 404.
54. **Data model:** metadata table `pastes(id PK, created_at, expires_at, size, storage_key)`; the text itself in object storage (Chapter 11), because pastes can be large and are read as a whole.
65. **High-level design:** load balancer → app servers → metadata database plus object storage, with a cache or CDN for popular pastes. **Write:** app makes an ID, uploads content to object storage, saves metadata. **Read:** check cache → metadata → fetch content from object storage (or straight from the CDN).
76. **Deep dive:** unique, unguessable IDs (random IDs with a uniqueness check, Chapter 10), or expiry cleanup (lifecycle rules in object storage plus a cleanup job for metadata).
87. **Trade-offs:** "Content in object storage **because** pastes can be large and the database stays small. **The cost** is a second system and an extra read. **Unless** pastes are tiny, then keep them in the database." And: "Random IDs **because** pastes may be private. **The cost** is a uniqueness check on every write. **Unless** all pastes are public, then a counter is simpler."