Amazon Interview Question
Software Engineer / DevelopersCountry: United States
How about this approach?
Generate a random string of fixed length based on the character set that is URL-safe.
For ex: Suppose we want to generate a 6-char length string, generate 6 random characters from a URL-safe character set. Once you generate the random string, say h6Tu6M, use it to build a short-form URL like: shrt.ul/h6Tu6M.
Use a mapping table(say a hashtable) to map the short URL to the long URL.
Ex: h6Tu6M => domainwithlongname/with/lengthy/resource/path In this step we also need to ensure that the randomly generated string is not already in use. In case a duplicate is generated, try creating another random string.
The app which is hosted at: h t t p : shrt.ul/ can look up the short resource path h6Tu6M and redirect the user to the actual resource h t t p://w w w .domainwithlongname/with/lengthy/resource/path
There is another solution to this problem.
1) Create a database with Row/Column the rows and colums are numbered from aaa-ZZZ
2) Have a trie with leaf node storing the database RowColumn value, for example if the URL is stored in aBP row and Dqr column then the leaf will store the aBPDqr.
3) Now for the input url find if the input url is in the trie, if its found return the six character database value or else create an entry into the first empty location of database and store the RowColumn value in the trie structure and return the tiny URL with the six character database value that represents unique row and column.
The advantage is there is no guess work regarding how well your hashing function has generated a hash code and whether two different URL's can result in same hash code.
1. Get a tiny domain name like bit.ly, goo.gl, or is.gd
2. Create a URI to shorten the website with the actual URL, e.g., h t t p: / / w w w.myverylongwebsitename.com/blab/blah/blah/ becomes h t t p : / / goo.gl/mVLwsnWx. You can do this by using a good hash function that generates a unique and short string for the website.
3. Implement h t t p: / / goo.gl/mVLwsnWx as a HTTP redirect to the actual website.This can be implemented as a RESTful service, so when you do HTTP.GET h t t p : / / goo.gl/mVLwsnWx, the service redirects you to the actual website.
create a table of
- klec@speroteck.com July 26, 2013ID | URL
01| index.php
02| store.php
03| about.php
....
for short url use ID converted to Base36
to get full url we:
1. get short url from request,
2. convert it to lower case
3. decode to decimal
4. get full url