The Short Address

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
Revolut

Problem

A URL shortener turns each new link's sequential row id into a compact slug. Encode a non-negative integer n into base 62 over the alphabet '0' through '9', then 'a' through 'z', then 'A' through 'Z', with the most significant digit first. The id 0 maps to the slug '0', not an empty string.

Every link needs a slug small enough to type by hand.

Example 1

Input:

n = 0

Output:

"0"

Example 2

Input:

n = 61

Output:

"Z"

Worked solution and explanation

What this problem really is

This is base conversion wearing a URL-shortener costume. Anyone can divide by 62 in a loop. What separates candidates is two quiet edges that the obvious loop gets wrong. First, while n > 0 never runs for id 0, so the very first row in the table gets an empty slug that resolves to nothing. Second, remainders come out least-significant first, so unless you flip them, 62 encodes as '01' instead of '10' and 999999 as '19c4' instead of '4c91': every multi-digit slug points at the wrong record.

Break down the requirements

Step 1: Define the base-62 character set

The alphabet is 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ: exactly 62 characters, and a digit's value is its index. The 61 -> 'Z' example confirms that uppercase comes last.

Step 2: Handle the zero id before the loop

A loop that runs while n > 0 never executes for n == 0, so it would return an empty string. Guard that case up front and return '0'.

Step 3: Extract digits via repeated modulo and division

Take n % 62 for the current digit, map it through the alphabet, then set n = n // 62. Repeat until n reaches 0.

Step 4: Reverse the collected characters

Digits come out least-significant first, so reverse the collected list once and join it. One reversal at the end beats prepending on every iteration.

The solution

Repeated division with custom alphabet
def encode_base62(n: int) -> str:
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if n == 0:
        return "0"
    digits = []
    while n > 0:
        remainder = n % 62
        digits.append(chars[remainder])
        n = n // 62
    digits.reverse()
    return "".join(digits)

Common follow-up questions