Google Interview Question for SDE1s


Country: United States




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

We can use something like a min-heap. Where the node value is the number of connections handled by the server. Each server can maintain a list of clients it is serving.

In addition to this we can have a HashMap to store the <client,server> pair to retrieve the server.

- DigitalFire May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ur idea is very good, can u explain in terms of sudo code...i mean the classes and implementation

- nr May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We can have each node for each server and can have a name field to denote server. The value of a node can be Number of connections currently being handled by the server. We can increase the node value of min-heap when the request is directed to any server and decrease when the request is served.

Here comes the problem.
1) How will you avoid race conditions
synchronising would be very bad idea, since it will badly affect the request serving

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

I don't think synchronization is a problem. This is an in-memory calculation and the time spent will be much smaller than the network call to the chosen server.

- galli August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Min-heaps do not support increase-key. We would have to delete-min and re-insert the key after each round, which is both O(log n).

- galli August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I had implemented load balancer by using the algorithm Round Robin algorithm for load balancing servers and it was implemented with Cirular Linked List..

- Aresh May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I would ask more questions to the interviewer, if it is dumb load balancer a round robin will work like Aresh mentioned, otherwise we'll have to have a policy by which we will decide the request goes to which server. like random, scatter and gather, sticky session, based on some parameter.
Look at this page for some ideas: http :// horicky.blogspot.com/2010/10/scalable-system-design-patterns.html

- vj May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did read the link.. i dont think this much knowledge was expected.......Interviewer wanted me to come up with my own design for load balancer and write code for it

- nr May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

There are many different kinds of load balancers. The question isn't meaningful without more context. You should mention what kind of load balancer you're interested in. What problem will this load balancer solve?

- eugene.yarovoi May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think, interviewer would would expect to know so much about load balancer...interviewer wanted to know some basic data structure that can be used and code based on tht

- nr May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

simplest, round robin
increment index modulo count

- Anonymous May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the real issue/challenge is to break up a task into estimatable loads or tasks to be distributed.

- Anonymous May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nah...

supposing this is a server, wouldn't be better to have a self organizing array?

Such as if you have a request for a server, you can always return the list's first element and then auto organize the list...

But if you have two request at the same time, you can treat those requesting threads as readers threads and give them the first element while you auto organize your data structure internally for the next requests...

this way you always return the server as fast as possible and doesn't need a synchronized area...

although I think the round robin could work well to because is simple enough to don't be a bottleneck if your request are not that big.
If they are, you can always organize your servers as a tree, delegating forward the request.

- raulkist May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You should ask some clarification questions before answering.
Are the machines identical?
Do they have same "max connection limit"?
All the incoming requests to the load balancer takes same time to complete, i.e., fixed?

Lets say, we've three machines A,B,C. Now, the job of load balancer is to make sure the load is uniformly distributed across all the machines and same time it doesn't overload the machines. This means, the load balancer should consider the max processing power of each machine (i.e., the max connections that a machine can support). Typically its not same for each machine, the hardware configuration will vary between machines (or each machine may run additional processes).
Above data are almost static., we've to consider an another important runtime parameter, the time taken for a request (or number of active connections on a machine), also must to be to balance the load.
The naive approach is to use round robin method (just distribute one request to each machine circularly). Otherwise maintain the above mentioned details in a bucket and distribute the load. When we reach the bucket capacity, keep the incoming requests on hold (may be in a queue) instead of overloading the machines (that will crash the all machines).

Hope it helps!

- devsathish May 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is some code for a min heap. The key is the comparable strategy, is this case minimum usage and incriminating that usage upon getting the top of the heap. The rest should be straight forward.

Kind regards

public class MinHeap<V> {

	public class Node<E> implements Comparable<Node<E>> {

		private E value;
		private int usage;

		public Node(E val) {

			this.value = val;
		}

		public void incrementUsage() {

			usage++;
		}

		@Override public int compareTo(Node<E> o) {

			return usage - o.usage;
		}

	}

	private Node<V>[] nodes;
	private int size;

	public MinHeap(int s) {

		this.nodes = (Node<V>[]) new Node[s];
	}

	public void insert(V val) {

		Node<V> node = new Node<V>(val);
		nodes[++size] = node;
		swim(size);
	}

	public V getAndIncrementMin() {

		Node<V> v = nodes[1];
		v.incrementUsage();
		swap(1, size);
		sink(1);
		return v.value;
	}

	private void swim(int k) {

		while (k > 1 && greater(k, k / 2)) {
			swap(k, k / 2);
			k = k / 2;
		}
	}

	private void sink(int k) {

		while (2 * k <= size) {
			int j = 2 * k;
			if (j < size && greater(j, j + 1))
				j++;
			if (!greater(k, j))
				break;
			swap(k, j);
			k = j;
		}
	}

	private void swap(int a, int b) {

		Node<V> temp = nodes[a];
		nodes[a] = nodes[b];
		nodes[b] = temp;
	}

	private boolean greater(int i, int j) {

		return nodes[i].compareTo(nodes[j]) > 0;
	}
}

- Ally B June 08, 2013 | 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