[Solution] Implement a URL shortener | Microsoft Interview Question
This problem was asked by Microsoft.
Implement a URL shortener with the following methods:
shorten(url)
, which shortens the url into a six-character alphanumeric string, such as zLg6wl
. restore(short)
, which expands the shortened string into the original url. If no such shortened string exists, return null. Hint: What if we enter the same URL twice?
Idea behind the solution
A Bijection function is being asked, which means it can map one value to another without "duplicated mappings" (2 different values mapping to the same value).
Although a simple hash function could be used, it is hard to determinate the odds of having a really big url to map to the same short url, it is easier to store the big url in a cache/database and generate an ID for it, and than transform this ID to the shorten url, so with the shorten url we transform back to the ID and get the real ID from the DB.
Basically it is needed to transform a base 10 number into a base 62 number (every letter, capital letter and numbers = 62 in total). Read more about his approach here.
Please check the main.js snippet for the solution.
This solution originally posted at: Github by @Murillo2380
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.