Google Interview Question Software Engineer / Developers
Could you explain a little more? All elements less than the pivot should be on the left and more than the pivot on the right; how could we use the empty place as the pivot?
Also, are we assuming the cars in the final order are sorted?
I don't think the cars in the final order are sorted. The final order may be 6 5 4 3_ 2 1, ect. The problem does not mean the final order have to be in sorted order
how do I explain this to you?
think the following:
car: a, b, c, d, e
new order is: b, e, d, c, a
it equivalent to:
sort 5, 1, 4, 3, 2 to 1,2,3,4,5
get the idea?
(If assume that the final order is sorted?)
1. We could shift the _ (empty place) at the end.
2. Use quicksort on the rest of that array. We use the empty slot at the end to move the pivot in the correct position. Note, that after putting the pivot in the correct position, we again see to that the _ (empty place) is at the end.
3. When the array is sorted we move the _ (empty place) back to where ever it belongs in the final position.
(nlgn solution)
(If assume that the final order could be anything?)
1. Go through first array and save key value pairs (key = value at index i ; value = i) in a hashtable.
2. Now lets start arranging the cars in thier position according to array 2;
for each element in array 2 (when we encounter a _ ignore it, only numbers),
find its orginal position using the hash table, also find the the the position of the empty place. Using these positions see to that the correct car is in position i in the first array. Note that this change would update some values in the hash table too (like new position of the empty place).
At the end the empty place will be in the position we want it to be. (I hope this method makes sense!).
(n solution)
a little more explanation on projecting this problem to quick sort:
1. observe that: if you maintain the order of cars, shifting the empty slot from one place to any other place takes O(n)
2. in this problem, you always swap a car with the empty slot. Similarly, in quicksort, the swap operation always involves the pivot element;
Shoudln't shifting the empty slot take O(1) time? As in,
1 2 3 4 5 _ to _ 2 3 4 5 1 is 0(1)? Would'nt taking car 1 out and parking it in in the last place be just one operation?
Give the '_' slot a value between the element below and above it in the proposed sort order. Then sort using a sort algorithm (depending on size of array, different sorting algorithms would be used).
you didn't get the point.
the point is, any swap operation is restricted to have the empty slot as one of the two operands.
consequently, quick sort is the best candidate.
Assuming we are given the initial order(I) and the final order(F).
Our algorithm should formulate the steps to transform I to F.
reorder(I, F, n, p) { // I = intial order, F = final, n = no. of elements, p = pivot
for(i = 1; i <= n; i++) {
if(I[i] = F[i]) continue;
j = find(I, F[i]); //find the index of element F[i] in the array I.
swap(I, i, pivot); // swap the elements I[i], I[pivot]
swap(I, j, i);
pivot = j;
}
}
Same approach.. Java code here. Complexity is again n^2
public static int[] rearrangeParking(int exist_order[],int new_order[] ) throws Exception
{
int blankSlot = -1;
for(int i=0;i<exist_order.length;i++)
{
if(exist_order[i] == 0)
{
blankSlot = i;
break;
}
}
int carFoundAt = -1;
for(int i=0;i<exist_order.length;i++)
{
//expected is not same as original
if(exist_order[i]!=new_order[i])
{
//use blank space
exist_order[blankSlot] = exist_order[i];//park this car in the blank slot
exist_order[i] = 0; // current slot is blank now
blankSlot = i;
//find the new_order[i] car in the current parking lot
carFoundAt =-1;
for(int j=0;j<exist_order.length;j++)
{
if(exist_order[j] == new_order[i])
{
carFoundAt = j;
break;
}
}
if(carFoundAt!=-1)// this car found at the parking slot
{
//take car to its new position
exist_order[blankSlot] = exist_order[carFoundAt];//park the car in the blank slot
blankSlot = carFoundAt;
exist_order[blankSlot]=0;
}
else
{
throw new Exception("Specificed order is incorrect, car:"+new_order[i]+" not found");
}
}
}
return exist_order;
}
@geniusxsy
Please provide the quicksort-style pseudocode. In the CLR quicksort implementation (ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/LectureNotes/lec4.pdf), the pivot is *not* always one of the swap operands:
int partition(int[] a, int low, int hi){
int pivot = a[low];
int i = low;
for (int j = low+1; j <= hi; j++) {
if (a[j] <= pivot){
i++;
swap(a[i],a[j]);
}
swap(a[i],pivot);
return i;
}
O(n) with O(n) space complexity seems like the best we can do.
No sorting needed folks. Firstly, move the _ to the correct position by having the car that is presently there move to current _. Using the given example, this means:
1 2 3 4 5 _ 6
2 3 1 4 _ 5 6 ->
2 3 1 4 5 _ 6
Now that _ is in the right place, forget about it:
2 3 1 4 5 6
Go through the lots one by one. If a car is in the wrong place, swap out the wrong car and replace with the right one. After going through the lots, you should of course have the right order, after an O(n) number of swaps.
But how to do swaps? Say you have cars X and Y. Move X to _, move Y to X's old position, then move X to Y's old position. O(1) swap. So O(n) time for the whole deal.
i do have to say although i agree with most of what you said, i have to say that because a swap between a car and an empty space is ideal, if we ever get to a point where the empty space in initial config and final config are at the same place, we take a random car that is not in the right position to swap with the empty spot. Then we start the algorithm up accordingly.
So for example, if final config if [1 2 3 4 _] and starting config is [3 1 2 _ 4]:
3 1 2 _ 4 -> 3 1 2 4 _ -> (now we have the empty spaces aligned, which is a problem. but don't start swapping between two cars since this will take 3 steps per swap. swap a random car (#3 let's say) that is not in position with the empty space) -> _ 1 2 4 3 -> (then proceed as usual) 1 _ 2 4 3 -> 1 2 _ 4 3 -> 1 2 3 4 _
I will try to present my understanding..I Could be wrong...
suppose there are 5 slots in both p1 and p2. 4 cars with the same Id come to p1 and 4 come to p2. They might occupy different spots in their respective lots. we need to rearrange the cars in a particular lot(p1 or p2)so that they occupy the same spot in the both p1 and p2.
If this is the question i don't think the solution is very tough..But i doubt that this is the question..
If anyone understands this question, could you elaborate, a bit? I'd def have to ask my interviewer for more info.
- Anonymous December 31, 2009