TinyURL, by LeetCode
Fun beginner's problem by LeetCode, here it is https://leetcode.com/problems/encode-and-decode-tinyurl/#/description:
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 the
encode and decode methods for the TinyURL service. 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.
Simple solution: keep two hash-tables, one mapping long URLs to short URLs, and another one the other way around (short to long). Use a random number generator to generate the short version. Mix that all up, and voila!
public class Codec
{
private Hashtable longToShort = new Hashtable();
private Hashtable shortToLong= new Hashtable();
// Encodes a URL to a shortened URL
public string encode(string longUrl)
{
if (longToShort.ContainsKey(longUrl)) return (string)longToShort[longUrl];
string shortUrl = (new Random()).Next().ToString();
longToShort.Add(longUrl, shortUrl);
shortToLong.Add(shortUrl, longUrl);
return shortUrl;
}
// Decodes a shortened URL to its original URL.
public string decode(string shortUrl)
{
return (string)shortToLong[shortUrl];
}
}
Technically your solution has a bug because of random number usage :) Example:
ReplyDeleteencode('foo') -> state {{'foo' => '2'}, {'2' => 'foo'}}
encode('bar') -> state {{'bar' => '2'}, {'2' => 'bar'}}
decode('2') -> 'bar'
I decided to not use random numbers and use a simple incremented variable. The advantage of this approach is that it's easy to use an array/vector instead of expensive hashtable to map short URLs to lone ones. This way short URLs require less space for storage. The disadvantage of this approach is that it might be a security requirement to not use easy to predict values. In such case your solution can be used a starting point - it just need to handle collisions properly.
BTW, this problem is actually a great starting point for a design interview, since follow-up questions can include: "How would you make it scalable?".
My simple solution:
class Solution {
private:
vector long_urls;
unordered_map reverse_index;
public:
// Encodes a URL to a shortened URL.
string encode(string longUrl) {
auto existing = reverse_index.find(longUrl);
size_t hash;
if (existing != reverse_index.cend()) {
hash = existing->second;
} else {
long_urls.push_back(longUrl);
hash = long_urls.size()-1;
}
return to_string(hash);
}
// Decodes a shortened URL to its original URL.
string decode(string shortUrl) {
return long_urls[stoi(shortUrl)];
}
};
Thank you for posting!