How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Shopify.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Shopify during technical interviews.

Implement URL Shortening Codec | Shopify Coding Question

Quick Overview

This question evaluates understanding of hashing, encoding, state management, and collision-handling strategies for creating a consistent mapping between long and short URLs, testing competencies in data structures, algorithms, and simple system design within the Coding & Algorithms domain.

Implement URL Shortening Codec

Company: Shopify

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a small in-memory URL-shortening component in a pair-programming interview. Expose two methods: `shorten(long_url: str) -> str`, which returns a short URL under a fixed host such as `https://short.example/`, and `expand(short_url: str) -> str`, which returns the original long URL. The same long URL should return the same short URL during one process lifetime, and two different long URLs must never decode to the wrong original URL. You may choose an incrementing ID, random token, hash-based token, or another scheme, but be ready to explain collision handling and trade-offs. Assume no external database or network calls. Follow-ups may include persistence, preventing predictable URLs, concurrent requests, invalid input, and time or space complexity.

Quick Answer: This question evaluates understanding of hashing, encoding, state management, and collision-handling strategies for creating a consistent mapping between long and short URLs, testing competencies in data structures, algorithms, and simple system design within the Coding & Algorithms domain.

Implement an in-memory URL shortening codec by processing a sequence of operations in order. Support two operations: - `shorten(long_url)`: return a short URL under the fixed host `https://short.example/` - `expand(short_url)`: return the original long URL Use this deterministic scheme so outputs are testable: 1. Every new long URL gets the next non-negative integer ID, starting from 0. 2. Convert that ID to Base62 using the alphabet `0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ`. 3. The short URL is `https://short.example/` + that Base62 code. Rules: - If the same long URL is shortened multiple times, it must return the same short URL during the same run. - Two different long URLs must never map to the same decoded result. - `expand` should return an empty string `""` if the short URL has the wrong host or was never generated earlier. - `shorten("")` is invalid and should return `""` without creating a mapping. Write a function that receives all operations and their values, and returns the result of each operation in order.

Constraints

1 <= len(operations) == len(values) <= 200000
Each operation is either `shorten` or `expand`
0 <= len(values[i]) <= 2000
Use the fixed host `https://short.example/`
Base62 alphabet must be exactly `0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ`

Examples

Input: (["shorten", "expand"], ["https://example.com/page", "https://short.example/0"])

Expected Output: ["https://short.example/0", "https://example.com/page"]

Explanation: The first new URL gets ID 0, which encodes to `0`. Expanding that short URL returns the original URL.

Input: (["shorten", "shorten", "shorten", "expand", "expand"], ["https://a.com", "https://a.com", "https://b.com", "https://short.example/0", "https://short.example/1"])

Expected Output: ["https://short.example/0", "https://short.example/0", "https://short.example/1", "https://a.com", "https://b.com"]

Explanation: Repeated shortening of the same long URL must return the same short URL. The second distinct URL gets the next ID.

Input: (["expand", "shorten", "expand", "shorten", "expand"], ["https://short.example/zzz", "", "https://other.example/0", "https://valid.com", "https://short.example/0"])

Expected Output: ["", "", "", "https://short.example/0", "https://valid.com"]

Explanation: Unknown short URLs, empty long URLs, and wrong-host short URLs all return empty string. The first valid shortened URL still gets code `0`.

Input: (["shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "shorten", "expand"], ["https://u0.com", "https://u1.com", "https://u2.com", "https://u3.com", "https://u4.com", "https://u5.com", "https://u6.com", "https://u7.com", "https://u8.com", "https://u9.com", "https://u10.com", "https://short.example/a"])

Expected Output: ["https://short.example/0", "https://short.example/1", "https://short.example/2", "https://short.example/3", "https://short.example/4", "https://short.example/5", "https://short.example/6", "https://short.example/7", "https://short.example/8", "https://short.example/9", "https://short.example/a", "https://u10.com"]

Explanation: Base62 continues after `9` with `a`, so ID 10 maps to code `a`.

Hints

Use two hash maps: one from long URL to code, and one from code to long URL.
A counter gives unique IDs; convert each new ID to Base62 to build deterministic short URLs.

Quick Overview