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 Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

In-Memory URL Shortener: Encode and Decode

Quick Overview

This question evaluates a candidate's ability to design a class-based data structure with paired encode and decode operations that maintain a consistent mapping in memory. It tests object-oriented design and hash map usage for achieving constant-time lookups, commonly asked in coding interviews to assess system design fundamentals at the data-structure level.

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory URL shortener that can encode a long URL into a short URL and decode that short URL back to the original long URL. Design a class `Codec` (or the equivalent in your language) that supports two operations: - `encode(long_url)` — take a long URL string and return a short URL string. - `decode(short_url)` — take a short URL previously returned by `encode` (on the same object) and return the exact original long URL. ### Contract - For any URL `u`, `decode(encode(u))` must return a string equal to `u`. - A single `Codec` instance handles many `encode`/`decode` calls; you may keep state in memory across calls. - Every short URL must begin with the fixed prefix `http://short.url/` followed by a short key you choose (for example `http://short.url/0` or `http://short.url/a4Bz`). - `decode` is only ever called with a short URL that this same instance previously produced. - It is acceptable — but not required — for repeated `encode` of the same long URL to return either the same or a different short URL. Both are correct as long as the round-trip contract holds. ### Constraints - `1 <= len(long_url) <= 10^4`. - `long_url` is a valid URL made of printable ASCII characters and contains no spaces. - At most `10^4` total calls are made to `encode` and `decode`, in any order. - All `encode`/`decode` calls operate on the same `Codec` instance. ### Example ``` codec = Codec() s = codec.encode("https://example.com/path?id=42&ref=home") # s == "http://short.url/0" (the exact key is up to your implementation) codec.decode(s) # returns "https://example.com/path?id=42&ref=home" ``` ### What to implement Provide the `Codec` class with `encode(self, long_url: str) -> str` and `decode(self, short_url: str) -> str`. Aim for `encode` and `decode` to each run in expected `O(1)` time per call, and keep the short keys compact.

Quick Answer: This question evaluates a candidate's ability to design a class-based data structure with paired encode and decode operations that maintain a consistent mapping in memory. It tests object-oriented design and hash map usage for achieving constant-time lookups, commonly asked in coding interviews to assess system design fundamentals at the data-structure level.

Implement an in-memory URL shortener with a `Codec` that supports two operations: - `encode(long_url)` returns a short URL that must begin with the fixed prefix `http://short.url/` followed by a short key you choose. - `decode(short_url)` returns the exact original long URL for a short URL this same instance produced. The round-trip contract is the whole point: `decode(encode(u)) == u`. A single `Codec` instance handles many calls and may keep state in memory. **How this console tests you.** Since the short key is up to you, you are given a list of `operations` and must return a list of result strings. Each operation is a two-element list of strings: - `["encode", long_url]` — encode `long_url`; append `"OK"` if the short URL starts with `http://short.url/`, else `"FAIL"`. Each produced short URL is remembered in encode order. - `["decode", k]` — `k` is the 0-based index (given as a string) among the encode operations; decode that short URL and append the recovered original long URL. The `solution` driver is already wired for you — implement the `Codec` class it calls. **Example.** `operations = [["encode", "https://example.com/path?id=42&ref=home"], ["decode", "0"]]` returns `["OK", "https://example.com/path?id=42&ref=home"]`.

Constraints

1 <= len(long_url) <= 10^4.
long_url is a valid URL of printable ASCII characters with no spaces.
At most 10^4 total encode/decode calls, in any order, on the same Codec instance.
decode is only ever called with a short URL this instance previously produced.
Every short URL must begin with the prefix 'http://short.url/'.

Examples

Input: ([["encode", "https://example.com/path?id=42&ref=home"], ["decode", "0"]],)

Expected Output: ["OK", "https://example.com/path?id=42&ref=home"]

Explanation: Encode one URL (short URL has the required prefix so 'OK'), then decode encode-op #0 to recover the exact original URL.

Input: ([],)

Expected Output: []

Explanation: No operations: the result list is empty.

Input: ([["encode", "http://a.com"], ["encode", "http://b.com"], ["encode", "http://a.com"], ["decode", "0"], ["decode", "1"], ["decode", "2"]],)

Expected Output: ["OK", "OK", "OK", "http://a.com", "http://b.com", "http://a.com"]

Explanation: Encoding the same URL twice is fine; each short URL must independently round-trip, so decode #0 and #2 both yield 'http://a.com'.

Input: ([["encode", "http://x.io/1"], ["decode", "0"], ["encode", "http://y.io/2"], ["decode", "1"], ["decode", "0"]],)

Expected Output: ["OK", "http://x.io/1", "OK", "http://y.io/2", "http://x.io/1"]

Explanation: Encodes and decodes interleave; a previously encoded short URL can be decoded again later (decode #0 appears twice).

Input: ([["encode", "https://ex.com/p?a=1&b=2#frag"], ["decode", "0"]],)

Expected Output: ["OK", "https://ex.com/p?a=1&b=2#frag"]

Explanation: URLs with query strings and fragments must survive the round-trip unchanged.

Hints

Keep a counter and a dictionary. On encode, use the current counter value as the key, store key -> long_url, bump the counter, and return 'http://short.url/' + key.
On decode, strip the fixed 'http://short.url/' prefix to recover the key, then look it up in your dictionary.
Because keys are generated fresh each time, encoding the same URL twice yields two independent keys that both round-trip correctly — that is allowed by the contract.
Both encode and decode are O(1) expected: a hash-map insert and a hash-map lookup.

Quick Overview