Google Interview Question


Country: United States




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

seems like modified insertion sort.

- czhao86 November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method worked for me. As czhao86 said it's a modified insertion sort. First iterate the array to find the index of the empty spot (it's indicated by Integer.MIN_VALUE). then swap it with the very first position in the array i.e. list[0]. Use modified insertion sort and make sure the 0th position remains the empty parking spot at the end of each pass.

private void sInsertionSort(int[] list)
	{
		// say int[] list = {Integer.MIN_VALUE, 8, 7, 6, 5, 1};
		for(int i=1; i<list.length; i++)
		{
			int next = list[i];
			int j = i;
			while(j > 0 && list[j-1] > next)
			{
				list[0] = list[j];
				list[j] = list[j-1];
				list[--j] = next;
				list[0] = Integer.MIN_VALUE;
			}
		}

		for(int i=0; i<list.length; i++)
		{
			System.out.println(list[i]);
		}
	}

- OmPranav November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

maybe
Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm to let n-1 cars in P1 and P2 park in the same slots
or
Rearrange an array using swap with 0.

You have two arrays src, tgt, containing two permutations of the numbers 0..n-1. You would like to rearrange src so that it equals tgt. The only allowed operations is “swap a number with 0”, e.g. {1,0,2,3} -> {1,3,2,0} (“swap 3 with 0”). Write a program that prints to stdout the list of required operations.

Practical application:

Imagine you have a parking place with n slots and n-1 cars numbered from 1..n-1. The free slot is represented by 0 in the problem. If you want to rearrange the cars, you can only move one car at a time into the empty slot, which is equivalent to “swap a number with 0”.

Example:
src={1,0,2,3}; tgt={0,2,3,1};

- Anonymous November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm going to assume the empty spot at the start is the one that's going to be empty at the end.

Each car has a desired spot. Create a directed graph with each car pointing to the one in the spot it wants to go to. Every node has a single out edge and a single in edge. This means if we follow forward from any one car we eventually get a cycle. So choose a car, move the car that's in its spot out of the way, and put that car in place. Then look at the car that you've moved and where it wants to go. Move that car out of its way. Continue. Eventually this process terminates because we're cycling through. Either we've done all the cars or we haven't. If not, go to one of those cars. Repeat until done.

Process is O(N), assuming you have the desired order in place (and let's be honest, if you didn't have the desired order yet, you would work it out before trying to implement a sort by moving cars).

If the empty spot is actually somewhere that a car wants to end up, all the better. Move that car there. Then new empty spot, move the car that wants to be there. When this process stops, you're back at the base case I assumed above.

- j November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems like regular sort (qsort for example) solution where empty slot is temp buffer for switching two elements. Do I miss something?

- Pavel December 30, 2014 | 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