4
\$\begingroup\$

The task

is taken from leetcode

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.

My solution

const url = {};
const ALPHANUMERIC = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
const PREFIX = 'http://tinyurl.com/';
/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
function encode(longUrl) {
  let id = createIdOfSize(6);
  while(url[id]) {
    id = createIdOfSize(6);
  }
  url[id] = longUrl;
  return PREFIX + id;
};

function createIdOfSize(n) {
  let i = n;
  let id = '';
  while(i-- > 0) {
    id += ALPHANUMERIC[(Math.random() * ALPHANUMERIC.length) | 0];
  }
  return id;
};
/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
function decode(shortUrl) {
  return url[shortUrl.split(PREFIX)[1]];
};

/**
 * Your functions will be called as such:
 * decode(encode(url));
 */
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Bug: I thought about that too. But since the code passes their test, I assume it wasn't important. \$\endgroup\$ – thadeuszlay May 24 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.