Google Interview Question
Country: United States
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]);
}
}
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};
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.
seems like modified insertion sort.
- czhao86 November 14, 2014