An LRU Cache removes the item that has not been used for the longest time when the cache reaches its capacity.

A common implementation uses:

• Hash Map for O(1) lookup.

• Doubly Linked List for O(1) insertion and removal.

Time Complexity:

• Get: O(1)

• Put: O(1)

2️⃣0️⃣0️⃣ How Would You Design a URL Shortener?

Answer:

A URL shortener converts a long URL into a short, unique URL.

Example:

Long URL: https://example.com/products/category/item/12345

Short URL: https://short.ly/aB92x

A basic system can use:

1. Generate a unique ID for each URL.

2. Convert the ID into a short Base62 string.

3. Store the mapping between the short code and original URL.

4. When the short URL is requested, look up the original URL.

5. Redirect the user to the original URL.

Important Design Considerations:

• Unique short IDs

• Database design

• Caching

• Scalability

• High availability

• Expiration of URLs

• Analytics and click tracking

🔥 Double Tap ❤️ For More