CareerCup

TinyUrl is to shorten the long urls which is more handy.
we can do that using hash table/database to do this.
1. Hash the long url which user gives, and store this new along with user given url.
2. when user give shortened url generated in step 1, system will retrieve original url matching the shortened url in hashtable.

Need to design for a large sysmet which will hold millions of URL's

Database to be used to solve scalability problem.

Stronger hash function will do a better job if it is to hold millions of URL's but it will not be a tinyurl anymore

General working of TinyUrl is:
If same long url is given multiple times (or multiple users), different tiny urls need to be given.


So, we can start with a 3 character combination and increase the number of character combinations when they are exhausted. Add the character combination as a key and the long url as value in the hashtable. So when the tinyurl is given, the value against this in the hash table is fetched in constant time.

Please do comment your opinions.

Redirect Part:

When you click on a link of any tiny url, an HTTP Request is sent to their server with the full URL, like http // bit.ly / b9 (not a real one).

They read the path part (here b9), which maps to their Database.

In the Database, they find the real URL. Then they issue a redirect, which is a HTTP 302 response and the target URL in the header.

Encoding Part:

One of the most popular URL shortening services simply take the ID in the database of the URL and then convert it to Base 62[a-zA-Z0-9].

import static org.testing.AssertJUnit.assertEquals ;

public class TinyURL {
	private static final String ALPHABET_MAP = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ;
	private static final int BASE = ALPHABET_MAP.length() ;

	public static String encode ( int IndexNum ) {
		StringBuilder sb = new StringBuilder() ;
		
		while ( IndexNum > 0 ) {
			sb.append ( ALPHABET_MAP.charAt ( IndexNum % BASE ) ) ;
			IndexNum /= BASE ;
		}
		return sb.reverse().toString() ;
	}

	public static int decode ( String str ) {
		int Num = 0 ;

		for ( int i = 0, len = str.length(); i < len; i++ ) {
			Num = Num * BASE + ALPHABET_MAP.indexOf ( str.charAt(i) ) ;
		}
		return Num ;
	}

	public static void main ( String[] args ) {
		//System.out.println ( "Encoding for 123 is " + encode(123) ) ;
		//System.out.println ( "Decoding for b9 is " + decode ("b9" ) ) ;

		assertEquals ( "b9", encode(123) ) ;
		assertEquals ( 123, decode("b9") ) ; 
	}
}