Encode and Decode TinyURL - Practice Coding Problems

Encode and Decode TinyURL - Problem

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design a class to encode a URL and decode a tiny URL. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the URLShortener class:

URLShortener() Initializes the object of the system.
String encode(String longUrl) Returns a tiny URL for the given longUrl.
String decode(String shortUrl) Returns the original long URL for the given shortUrl.

Input & Output

Example 1 — Encode URL

$ Input: operation = "encode", url = "https://leetcode.com/problems/design-tinyurl"

› Output: "http://tinyurl.com/4e9iAk"

💡 Note: The system generates a short code and returns the tiny URL. The exact code depends on the implementation approach.

Example 2 — Decode URL

$ Input: operation = "decode", url = "http://tinyurl.com/4e9iAk"

› Output: "https://leetcode.com/problems/design-tinyurl"

💡 Note: The system looks up the short code and returns the original long URL that was previously encoded.

Example 3 — Encode Same URL Twice

$ Input: operation = "encode", url = "https://google.com"

› Output: "http://tinyurl.com/xyz123"

💡 Note: Encoding the same URL multiple times should return the same short URL to avoid duplicates.

Constraints

1 ≤ url.length ≤ 10⁴
url is guaranteed to be a valid URL.

Visualization

Tap to expand

Understanding the Visualization

Input

Long URL or short URL with operation

Process

Generate short code or lookup original URL

Output

Short URL or original long URL

Key Takeaway

🎯 Key Insight: Use bidirectional hash maps to achieve O(1) encode and decode operations

Asked in

a Amazon 45 M Microsoft 38 G Google 35 f Facebook 32

The key insight is to maintain bidirectional mappings between long and short URLs using hash maps. The counter-based approach is simplest with O(1) operations. Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Base62 Encoding with Hash	O(1)	O(n)	Use Base62 encoding of hash values for deterministic short codes
Random Code with Hash Map	O(1)	O(n)	Generate random short codes and use hash maps for storage
Counter-Based Sequential Encoding	O(1)	O(n)	Use a simple counter to generate sequential short codes

Base62 Encoding with Hash — Algorithm Steps

Hash the long URL using a hash function
Convert hash to Base62 string
Store mapping and handle collisions

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash

Generate hash from long URL

Encode

Convert hash to Base62 string

Resolve

Handle collisions with counter suffix

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_URLS 1000
#define MAX_URL_LEN 500

typedef struct {
    char longUrl[MAX_URL_LEN];
    char shortUrl[MAX_URL_LEN];
} URLPair;

static URLPair urls[MAX_URLS];
static int urlCount = 0;
static char chars[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

// Simple hash function
unsigned long simpleHash(char* str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

void base62Encode(unsigned long num, char* result) {
    if (num == 0) {
        result[0] = chars[0];
        result[1] = '\0';
        return;
    }
    
    char temp[20];
    int i = 0;
    while (num > 0) {
        temp[i++] = chars[num % 62];
        num /= 62;
    }
    
    // Reverse the string
    int j = 0;
    for (int k = i - 1; k >= 0; k--) {
        result[j++] = temp[k];
    }
    result[j] = '\0';
}

int codeExists(char* shortUrl) {
    for (int i = 0; i < urlCount; i++) {
        if (strcmp(urls[i].shortUrl, shortUrl) == 0) {
            return 1;
        }
    }
    return 0;
}

char* encode(char* longUrl) {
    // Check if already encoded
    for (int i = 0; i < urlCount; i++) {
        if (strcmp(urls[i].longUrl, longUrl) == 0) {
            return urls[i].shortUrl;
        }
    }
    
    unsigned long hashValue = simpleHash(longUrl);
    char code[20];
    base62Encode(hashValue, code);
    
    sprintf(urls[urlCount].shortUrl, "http://tinyurl.com/%s", code);
    
    // Handle collision
    int counter = 0;
    char originalShort[MAX_URL_LEN];
    strcpy(originalShort, urls[urlCount].shortUrl);
    
    while (codeExists(urls[urlCount].shortUrl)) {
        counter++;
        sprintf(urls[urlCount].shortUrl, "%s%d", originalShort, counter);
    }
    
    strcpy(urls[urlCount].longUrl, longUrl);
    urlCount++;
    
    return urls[urlCount-1].shortUrl;
}

char* decode(char* shortUrl) {
    for (int i = 0; i < urlCount; i++) {
        if (strcmp(urls[i].shortUrl, shortUrl) == 0) {
            return urls[i].longUrl;
        }
    }
    return "";
}

char* solution(char* operation, char* url) {
    if (strcmp(operation, "encode") == 0) {
        return encode(url);
    } else {
        return decode(url);
    }
}

int main() {
    char operation[20];
    char url[MAX_URL_LEN];
    
    fgets(operation, sizeof(operation), stdin);
    operation[strcspn(operation, "\n")] = 0;
    
    fgets(url, sizeof(url), stdin);
    url[strcspn(url, "\n")] = 0;
    
    char* result = solution(operation, url);
    printf("%s\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Hash function and Base62 conversion are constant time operations

✓ Linear Growth

Space Complexity

O(n)

Store n URL mappings plus collision chains

⚡ Linearithmic Space

52.0K Views

High Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Base62 Encoding with Hash — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler