Return to Answer

##Review

At reading the problem I thought it needed to be a lossless compression algorithm to generate a unique id.

The most basic compression is run length encoding on the bits that make the url. Or a dictionary compression on bit patterns such as Lempel, Ziv, Welch compression AKA LZW or LZ compression. However there is some storage overhead and for short URLs you will have trouble getting a smaller url than the original.

##Random id?

Your solution stores the original url mapped to a random index. There is no need for a compression or even a hash as all you need is a unique id per URL.

To generate an unique id you need only the number line. JS Number can generate 9e15 unique ids, that's a new id every millisecond for the next quarter million years (twice that if you include negatives).

You can also compress the id by converting the id to base 36 (the max base for Number.toString(radix)) thus the longest encoding is "2gosa7pa2gv" and the shortest is "0" and you need store only one 64bit double for the short url.

See Example

##Bug?

Your function returns a different short url for the same long url.

##Example

• Simple index encoding, there is room for lots of optimization in storage.

• Produces safe urls using only a-z0-9 to encode.

• There is a limit as it does rely on the hashing function (Chance of a clash) of the JS engine.

• Checks if a url has already been encoded

You can avoid the JS hash functions (and possible clash), by using an array or set of arrays (if number of urls high) but that comes with a huge CPU cost of locating the URL if the data set is big will require a linear search of the stored urls when encoding. Decoding will still be fast as the encoded url contains the index of the original url

const PREFIX = 'http://tinyurl.com/';
const urls = {
 short: new Map(), // can be array use id to index
 long: new Map(), // can be array and use find rather than has and get
 value: 0,
 get id() { return urls.value++ },
};
function encode(url) {
 if (urls.long.has(url)) { return PREFIX + urls.long.get(url).id.toString(36) }
 const urlEntry = { url, id: urls.id };
 urls.long.set(url, urlEntry);
 urls.short.set(urlEntry.id, urlEntry);
 return PREFIX + urlEntry.id.toString(36);
}
function decode(url) {
 return urls.short.get(parseInt(url.split(PREFIX)[1], 36)).url;
}

Review

At reading the problem I thought it needed to be a lossless compression algorithm to generate a unique id.

The most basic compression is run length encoding on the bits that make the url. Or a dictionary compression on bit patterns such as Lempel, Ziv, Welch compression AKA LZW or LZ compression. However there is some storage overhead and for short URLs you will have trouble getting a smaller url than the original.

Random id?

Your solution stores the original url mapped to a random index. There is no need for a compression or even a hash as all you need is a unique id per URL.

To generate an unique id you need only the number line. JS Number can generate 9e15 unique ids, that's a new id every millisecond for the next quarter million years (twice that if you include negatives).

You can also compress the id by converting the id to base 36 (the max base for Number.toString(radix)) thus the longest encoding is "2gosa7pa2gv" and the shortest is "0" and you need store only one 64bit double for the short url.

See Example

Bug?

Your function returns a different short url for the same long url.

Example

• Simple index encoding, there is room for lots of optimization in storage.

• Produces safe urls using only a-z0-9 to encode.

• There is a limit as it does rely on the hashing function (Chance of a clash) of the JS engine.

• Checks if a url has already been encoded

You can avoid the JS hash functions (and possible clash), by using an array or set of arrays (if number of urls high) but that comes with a huge CPU cost of locating the URL if the data set is big will require a linear search of the stored urls when encoding. Decoding will still be fast as the encoded url contains the index of the original url

const PREFIX = 'http://tinyurl.com/';
const urls = {
 short: new Map(), // can be array use id to index
 long: new Map(), // can be array and use find rather than has and get
 value: 0,
 get id() { return urls.value++ },
};
function encode(url) {
 if (urls.long.has(url)) { return PREFIX + urls.long.get(url).id.toString(36) }
 const urlEntry = { url, id: urls.id };
 urls.long.set(url, urlEntry);
 urls.short.set(urlEntry.id, urlEntry);
 return PREFIX + urlEntry.id.toString(36);
}
function decode(url) {
 return urls.short.get(parseInt(url.split(PREFIX)[1], 36)).url;
}