CareerCup

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") ) ; 
	}
}

The things that come to my mind while designing a URL shortener service is -
1. First the functional part, we need to design a system which can shorten a given url into some specified length. Generally the purpose of url shortening is to send url in mobile smses which have a fixed length.
2. Scalability? Do we want system to be distributed
3. Do we expect short urls to expire and to be re-used.

To start with a basic design, I can generate a hash of the url, check if the hashed string already present in some distributed DB. We are book-keeping our records. If it is present then return otherwise hash it again. To access the short-url for same string again and again, we can keep a inverse index.