SwadhyAI Notes

All Low-Level Design notes

Machine coding · not HLD

URL shortener

You paste a long URL. The service hands back a short code. Later someone opens that code and lands on the original address. In this machine-coding round you implement that encode and decode loop, a store port (an interface a HashMap can satisfy this afternoon), and what happens when two codes collide.

Collisions at a billion links, regional failover, and starting with Kafka answer the wrong interview. Those belong on the related System Design note: URL shortener .

This afternoon vs later

This machine-coding round

shorten and resolve, uniqueness via , an injected generator, and a HashMap fake store.

Optional follow-ups

Custom alias and TTL (time-to-live) if they ask after the first two methods work.

Related System Design note

KGS (key generation service), edge Redis, Cassandra, 302 vs 301 (temporary vs permanent redirect), and click analytics off the hot path. Open that note when they ask scale.

What actually happens

The paste-and-open story is two methods and a mapping. UrlShortener.shorten(url) returns a code. resolve(code) returns the long URL. A Store port saves that pair. An IdGenerator, or a hash plus a collision policy, creates the code. Codes must be unique.

If you hash the URL, a collision needs a retry or a counter suffix. If you use a counter plus base62 (digits and letters, 62 symbols), uniqueness is easier and the generator must be atomic. Either way, on the store is the race story.

The store is a repository. Tests use a map fake. The encoder does not know HashMap versus a future SQL adapter; that boundary is the design. See API design and HLD vs LLD.

Simple rule of thumb

Once the two methods are clear, you still have to pick how codes are minted, and what to leave on the table.

Prefer a counter plus base62 with an atomic generator. Hash plus a bounded retry is fine if they ask you to start from the URL. Do not open with load balancers or Kafka; stay on shorten, resolve, and the store port until they ask about a billion links (see the System Design note in the hero).

How to explain this in an interview

Name encode, decode, and uniqueness first. plus retry, or an atomic counter, is the uniqueness sentence. Mention the related System Design note only when they ask scale.

Mint, then claim

The rule above is the policy. The sequence below is the mechanism: mint a code, then claim it on the store.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.
Read the diagram definition
sequenceDiagram
    participant C as Caller
    participant S as UrlShortener
    participant G as CodeGenerator
    participant St as ShortLinkStore

    C->>S: shorten(longUrl)
    S->>G: next(longUrl)
    G-->>S: "x7K9m"
    S->>St: putIfAbsent(code, longUrl)
    alt inserted
        S-->>C: code
    else collision
        S->>G: next again / suffix
        S->>St: putIfAbsent
    end

The shortener asks the generator for a code, then claims it with . If the insert succeeds, return the code. If it collides, ask again (or suffix) and claim again, inside a bounded loop.

Concurrency

Counter generator: AtomicLong (a Java atomic counter) so two threads shortening different URLs get different codes. Hash generator: retry loop on the claim. Two threads shortening the same URL may still get two codes unless you also key the store by long URL. Say whether identical destinations share a code. That is a product decision, not an accident of HashMap.

Who owns what

  1. 01

    UrlShortener

    Owns shorten and resolve, validates the URL, and retries on collision.

  2. 02

    CodeGenerator

    Mints the next code (counter or hash) and must be atomic for counters.

  3. 03

    ShortLinkStore

    Claims uniqueness with putIfAbsent and finds the long URL on resolve.

  4. 04

    Clock (follow-up)

    Supplies time for TTL follow-ups; skip it until shorten and resolve work.

Java API sketch

The types above become this Java sketch. The encoder still talks only to the generator and the store port.

java
interface CodeGenerator {
  String next(String longUrl);
}

interface ShortLinkStore {
  boolean putIfAbsent(String code, String longUrl);
  Optional<String> find(String code);
}

class CounterBase62 implements CodeGenerator {
  private final AtomicLong seq = new AtomicLong(1);
  public String next(String longUrl) {
    return Base62.encode(seq.getAndIncrement());
  }
}

class UrlShortener {
  private final CodeGenerator codes;
  private final ShortLinkStore store;

  String shorten(String longUrl) {
    validate(longUrl);
    for (int i = 0; i < 8; i++) {
      String code = codes.next(longUrl);
      if (store.putIfAbsent(code, longUrl)) return code;
    }
    throw new CouldNotAllocateCode();
  }

  Optional<String> resolve(String code) {
    return store.find(code);
  }
}

Forty-five minutes, then the seam test

With the API on the board, this is how you spend the round and prove the race without leaving the process.

Numbers to know

  1. 0–8Sketch the port: shorten, resolve, and ShortLinkStore so tests can fake the map.
  2. 8–20Implement a counter plus base62 generator, using AtomicLong so codes stay unique.
  3. 20–32Prove collision retry: a scripted generator returns aaa, then aab.
  4. 32–40Validate URLs at the edge; add a custom alias only if time remains.
  5. 40–45When they say a billion links, name the related System Design note.

Tests that prove the seams

Use an InMemoryShortLinkStore on a ConcurrentHashMap (a thread-safe map). A fake generator returns "aaa" then "aab". First shorten succeeds as aaa. The second colliding shorten gets aab. resolve("aaa") is the first long URL.

java
@Test
void collisionRetries() {
  ShortLinkStore store = new MapStore();
  CodeGenerator gen = new ScriptedGenerator("aaa", "aaa", "aab");
  UrlShortener s = new UrlShortener(gen, store);
  assertEquals("aaa", s.shorten("https://a.example"));
  assertEquals("aab", s.shorten("https://b.example"));
}

Invalid cases, follow-ups, and what still breaks

The happy path is mint-then-claim. These are the cases that fail in the room, wait for a follow-up, or stay a product sentence after the code works.

Invalid cases

  • Load balancers belong on the System Design note, not this encode/decode round.
  • Math.random() codes with no collision plan are not a uniqueness strategy.
  • Reject blank or non-http URLs at the edge; do not store garbage.
  • A taken custom alias is a domain error when returns false; do not overwrite.
  • resolve on an unknown code returns Optional.empty, never a null long URL.

What the follow-up changes

  • Custom aliases: validate charset [a-zA-Z0-9], claim the name, and reject duplicates.
  • TTL: store an Entry plus Clock, the same expiry story as the in-memory KV page.
  • Analytics: a long adder is enough if they insist; do not start ClickHouse.
  • Scale: open the related System Design note; stay off Kafka in this round.

Still fails when

  • Same URL, two threads: they may mint two codes unless you also key by destination (see Concurrency).
  • Kafka in sentence one: that is the System Design interview, not this afternoon's class.

Trade-offs

  • Sharing one code for the same URL is a product decision, not a HashMap accident.
  • A HashMap fake is enough here; Cassandra waits for the related System Design note.

Wrap-up

You have the API, the race, and the clock. Use the links, then stop when uniqueness has a test.

You're done when

Collision has a retry: when fails, the shortener asks the generator again within a bounded loop. Uniqueness comes from that claim plus the generator, not from hope. A HashMap is a fine in-process store for this round. Load balancers and regional failover belong on the related System Design note.