The Link Shrinker

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Equativ

Problem

Return the short code our link shortener assigns to url: the first six hex characters of the URL's MD5 digest, recorded in code_map (short code to URL) before it comes back. If a different URL already holds that code, the code is instead the shortest longer prefix of the same digest that no other URL holds.

Long addresses have aliases - you give them out, you keep the map.

Example 1

Input:

url = "https://example.com/very/long/path", code_map = {"bab008":"https://example.com/very/long/path"}

Output:

"bab008"

Example 2

Input:

url = "https://google.com", code_map = {"bab008":"https://example.com/very/long/path"}

Output:

"99999e"

Worked solution and explanation

What this really is

This is deterministic content hashing wearing a service-design costume. The real question: can you turn a URL into a short code that the same URL always regenerates, without consulting the map to remember what you handed out before? A content hash gives you that for free, because the digest is a pure function of the URL. Two traps separate candidates. The first is mechanical: hashlib.md5() wants bytes, not a str, so hashing the raw URL throws TypeError before any code exists. The second is the one that ships: resolving a collision by overwriting, which silently hands a different link's code to the new URL.

Walking it

Step 1: Hash the encoded URL

Call url.encode() to get UTF-8 bytes, then hashlib.md5(...).hexdigest() for a 32-char lowercase hex string. It is deterministic by construction: identical input, identical digest, every time.

Step 2: Take the 6-char prefix

Slice the first 6 hex characters as the code. That is 16^6, roughly 16 million codes, which is why real collisions are rare enough that the visible tests never hit one.

Step 3: Resolve a genuine collision

Before storing, check whether the code is already in the map under a DIFFERENT URL. If so, lengthen the prefix one hex char at a time (digest[:7], digest[:8], ...) until no other URL holds it. A code already mapped to the SAME url is not a collision: the loop stops and the URL keeps its code, even an extended one it was given earlier.

Step 4: Store and return

Write code_map[code] = url into the passed dict and return the code string. Mutate in place; do not build a fresh dict.

The solution

MD5 short code with collision extension
import hashlib


def url_shortener_encode(url: str, code_map: dict) -> str:
    digest = hashlib.md5(url.encode()).hexdigest()
    length = 6
    code = digest[:length]
    while code in code_map and code_map[code] != url:
        length += 1
        code = digest[:length]
    code_map[code] = url
    return code
Naive: hash the str
hashlib.md5(url).hexdigest() raises TypeError because MD5 only accepts a bytes-like object. You fail before producing a code.
Correct: encode first
hashlib.md5(url.encode()).hexdigest() feeds it UTF-8 bytes, so you get 'bab0087156...' and slice 'bab008'.

Common follow-up questions