Google Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

This is more like a design problem other than a coding problem. I guess the key points to cover is

1. web servers to handle URL shortening request and to handle URL access request
2. database to store the mapping from URL to tiny url
3. caching to reduce the response delay and the hit on database
4. capacity: how much traffic is supposed to be served on average, at peak?
5. scalability: how to survive huge amount of requests?
6. availability: how to survive any system failure: server crash, database crash, cache crash
7. security: how to handle malicious requests?

Seems a lot to discuss here

- nixfish October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hashing. The big URL will the input to your hashing function. Maintain multiple buckets (partitioning) to achieve scalability. Length of the url may be an attribute to partition it.

- devsathish October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why would you want to use length as a factor in partitioning?

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the length will be varied in a wide range so the number of buckets will be a lot. How about the startting character of the link. Like facebook, then f.

Or may be part of the link, like .com or .org.

- binhngoc17 November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tinyurl uses base 36 encoding. If you want more robust use base 64 (0-9 a-z A-Z)

- gixxer6er October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can any1 throw light on scalability and reliability

- Anonymous October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Posting a possible solution to the problem to get comment and feedback. Solution uses an Hashmap to store the real URL and the tiny URL where the tiny URL is the key and the real URL is the value. The tiny URL is generated by counting through characters the same way you count through numbers. A single character can give you 256 entries.

static final String  fixedURLPart = "fixedURLPart";
static Hashmap<String,String> urlMap = new Hashmap<String, String>;

// Generates the Tiny URL
String generateTinyURL(String inURL){
	String tinyURL =  fixedURLPart + getNextString();
	urlMap.put( tinyURL, inURL );
	return(tinyURL);
}

// Returns the URL
String getRealURL(String tinyURL){
	return(urlMap.get(tinyURL));
}

// Should be able to generate 2,560,000,000 tiny URLs with this.
// This will take up 9.54MB.  Can increase number to increase scale.
static char[] charList = new char[10000000]; 
static int i = 0;

// Generates the unique string for each tiny URL
String getNextString(){

	if(charList = null){
		charList = new char[1];
		charList[0] = (char)0;
	} else {
		int savedi = i;
		while(i < charList.length){
			if(charList[i] < 255)
				charList[i] = (char)((int)charList[i] + 1);
				break;
			else{
				charList[i] = (char)0;
				i++;
			}
		}
		i = savedi;
	}
	return(new String(charList));

}

- CodeSpace October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have completely missed what the question is about.

- Critic. October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please educate me.

- CodeSpace October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

That is not a critic's job. But, anyway, since you asked...

Try answering the following questions:

How will the user actually use the tiny url?

How many users can you sustain at a time?

How easily can you scale with an increasing user base?

What happens if the machine running the above piece of code crashes?

What happens if you reboot the machine, and the user then decides to use the tinyurl?

Would you restart generation of the tinyurls, after the process is restarted?

This is a scalable system design question (multiple machines, failure scenarios, persisting data reliably etc).

You cannot just answer with code like this.

- Critic aka teacher. October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the feedback. This is good to know. My solution only focuses on implementing the core URL generation mechanism which was my initial interpretation of the question. I agree it does not answer the scalability question.

- CodeSpace October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Even without considering scalability, you are doing nothing about persistence (like your machine reboots etc), not considering possible multi-threaded issues etc.

Also, the ids you generate are completely predictable, which may or may not be a good thing.

And once scalability comes into picture, your code will probably have to be thrown out, as you cannot expect to run that code on all machines.

- Critic October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice way of answering Critic...sarcasm intended.

- Anonymous January 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: Lol?

- Critic. January 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need memcached - ofcourse you need to pretend that you are going to build it from scratch. basically a hashkey % noof servers.

- Viv October 17, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More