Google Interview Question
Software DevelopersCountry: United States
Note that you still need to be able to find the correct box, so you'll want to maintain a hashmap or something similar mapping from box # to location.
In fact, you can do it in guaranteed <= n + 1 swaps. Simply clear one space with an incorrect box, then move the correct box # to that space. The correct box just vacated a space for another box, so move the new box there and repeat.
Example with n = 5:
2 5 3 1 4 x
x 5 3 1 4 2
1 5 3 x 4 2
1 5 3 4 x 2
1 x 3 4 5 2
1 2 3 4 5 x
Note that you still need to be able to find the correct box, so you'll want to maintain a hashmap or something similar mapping from box # to location.
In fact, you can do it in guaranteed <= n + 1 swaps. Simply clear one space with an incorrect box, then move the correct box # to that space. The correct box just vacated a space for another box, so move the new box there and repeat.
Example with n = 5:
2 5 3 1 4 x
x 5 3 1 4 2
1 5 3 x 4 2
1 5 3 4 x 2
1 x 3 4 5 2
1 2 3 4 5 x
imagine a crane and ,loading docks as the question sugest:
1) minimize moves, assuming sorted order means that the empty dock is at the end and not in the midle somewhere after sort, it is easy:
- start with i = 1
- while i <= n-1
- if box in dock i is not box i, take that box and move it to the empty dock n+1
- get box i and move it to dock i, thereby freeing dock j
- while j is not n+1: get box j and move it to dock j, asign new empty dock to j
- increment i
2) minimize distance of move
I doubt there is a perfect solution in polynominial time. I see no common subproblem, greedy choice etc. It reminds me to the rubik cubes problem. I guess best one can do is somehow try to minimize, but I wouldn't be able to come up with a solution in the remaining time without hints.
I think the problem can be solved in the polynomial time of N+1 or N+floor[N/2] and quick sort is costly in this problem since swapping two boxes using the third box takes more number of moves.
I could find three cases for the problem:
Case 1: If all the boxes are sorted
Case 2: Take box in the dock_1 and move it to the empty space(dock_(n+1)) then check the correct correct box (box_1) and move to the dock_1. Now a dock (dock_i) will be freed by box_1, check for the box_i then move it to dock_i. (In this case we are assuming that the box_i is not on the dock_(n+1)). Repeat this until all the boxes are arranged. If this is the case for all the boxes it would take N+1 time to sort all the boxes
Case 3: Take box in the dock_1 and move it to the empty space(dock_(n+1)) then check the correct correct box (box_1) and move to the dock_1. Now a dock (dock_i) will be freed by box_1, check for the box_i then move it to dock_i. Now let us assume that we have the box_i in the dock_(n+1), move the box_i to dock_i then continue the case 3 or case 2 (this case would take N+floor[N/2])
I think that the main insight here is that we need an in-place sorting algorithm. The fastest comparison based sorting algorithm that can be performed in-place is quicksort, with an expected performance of nlogn. On average quicksort will perform nlogn comparisons and hence will perform nlogn swappings at most. the extra space can be used for the swapping part. So the algorithm is to choose at random a box as a pivot. partition the set based on this box (using the extra space for swaps). perform this recursively for the two subsets.
Can be done in N+1 moves and O(n^2) time complexity. Suppose there are 10 boxes and docks.
1) Look for the box_1, and put it in dock_n+1
2) This frees up , say dock_7, look for box_7, which frees up box_10. Now look for box_10
Basically that would result in N moves and 1 extra move to move box_1 from dock_n+1 to dock 1 @ the end.
The idea is correct and can be implemented in O(n) time but you might need more (at most 3N/2) moves. That's because when you move box_1 from dock_n+1 to dock_1, it is not necessary that all boxes are at the correct positions. You will then have to repeat your algorithm starting with a box that is not at its place (instead of box_1). E.g. suppose that you have box_2, box_1, box_4, box_3 at decks 1,2,3,4. Then you will need 4+2 moves.
The idea is correct and can be implemented in O(n) time but you might need more (at most 3N/2) moves. That's because when you move box_1 from dock_n+1 to dock_1, it is not necessary that all boxes are at the correct positions. You will then have to repeat your algorithm starting with a box that is not at its place (instead of box_1). E.g. suppose that you have box_2, box_1, box_4, box_3 at decks 1,2,3,4. Then you will need 4+2 moves.
//Time complexity: O(N^2) I think. Space: O(1). Using cyclic swaps.
public int[] sortArray(int[] arr){
if(arr==null||arr.length<=1){
return arr;
}
int empty=arr.length-1;
for(int i=0;i<arr.length;i++){
int next=i;
while(arr[next]!=next+1 && arr[next]!=0){
arr[empty]=arr[arr[next]-1];
int next_i=empty;
arr[arr[next]-1]=arr[next];
empty=next;
arr[empty]=0;
next=next_i;
}
}
return arr;
}
Given a permutation p this can by done in exactly (2 * number of cycles in permutation p + sum [length(c)] for cycle c in all cycles of permutation p) moves. Here is the algorithm:
while p contains a cycle C:
move arbitrary element A from C to the empty dock
move all other elements of C one by one to their final positions
move a back to its final position
This can be done in exactly sum(L(i)+1) for each cycle i, where L(i) is the length of the cycle i. Code:
int sort(int *a, int n) {
int res = 0;
REP(i, 0, n) if (a[i] != i+1) {
int hold = a[i]; res++;
int cur = hold-1;
int pos = i;
while (a[hold-1] != -1) {
while (a[cur]-1 != pos) cur = a[cur] - 1;
a[pos] = a[cur]; res++;
a[cur] = -1;
pos = cur;
cur = hold-1;
}
a[hold-1] = hold; res++;
}
return res;
}
public int moveMinimumSwapCrane(int input[], int len) {
int space = -1;
int swap = 0;
Map<Integer, Integer> ktv = new HashMap<>();
for (int i = 0; i < len; i++) {
ktv.put(input[i], i);
}
ktv.put(space, len);
for (int idx = 0; idx < len; idx++) {
int seeker = input[idx];
// at position 1 if we have 2 than it is at correct position.
if (seeker == idx + 1)
continue;
move(idx, ktv.get(space), ktv, input);
swap = swap + 1;
int pos = idx;
while (pos != len) {
int expVal = pos + 1;
int newPos = ktv.get(expVal);
move(newPos, pos, ktv, input);
swap = swap + 1;
pos = newPos;
}
}
return swap;
}
void move(int fromIdx, int toIdx, Map<Integer, Integer> ktv, int input[]) {
int val = input[fromIdx];
input[fromIdx] = input[toIdx];
ktv.put(input[toIdx], fromIdx);
input[toIdx] = val;
ktv.put(val, toIdx);
}
def min_moves(arr):
empty = len(arr) - 1
d0 = dict()
d1 = dict()
for i in xrange(len(arr) - 1):
if i + 1 != arr[i]:
d0[arr[i] - 1] = i
if i != arr[i]:
d1[arr[i]] = i
d = None
if len(d0) <= len(d1):
d = d0
else:
d = d1
moves = 0
while d:
moves += 1
if empty not in d:
key, val = d.items()[0]
d[key] = empty
empty = val
else:
temp = empty
empty = d[empty]
del d[temp]
return moves
a = [2,1,3,4, None]
b = [2,1,4,3, None]
print min_moves(a)
print min_moves(b)
you guys think this will work?
public static void sort(int[] boxes) {
// map of BoxId to LocationId
HashMap<Integer, Integer> dockMap = new HashMap<>();
// add BoxID-DockID pairs
for (int i = 1; i <= boxes.length; i++) {
dockMap.put(boxes[i-1], i);
}
dockMap.put(-1, boxes.length + 1);
int emptyIndex = boxes.length + 1;
for (int i = 1; i < dockMap.size(); i++) {
// case where current Box is on wrong dock
// swap with empty location
if ((int) dockMap.keySet().toArray()[i] != dockMap.get(i)) {
// move out of place box to empty dock
int currentBox = (int) dockMap.keySet().toArray()[i];
dockMap.put(currentBox, emptyIndex);
// update empty dock
dockMap.put(-1, i);
// update location of empty dock
emptyIndex = i;
//find location of correct box
int targetDock = dockMap.get(i);
// replace empty index with correctBox
dockMap.put(i, i);
// set new empty dock
dockMap.put(-1, targetDock);
// update location of empty dock
emptyIndex = i;
}
}
for(int i = 0 ; i< dockMap.size() ; i++){
if(dockMap.get(i) !=null){
System.out.println("Dock : " + i + " Box : " + dockMap.get(i));
}
}
}
private final Character BLANK_SPOT = '_';
public void performOrdering(Character[] inputOrder) {
Map<Character, Integer> letterPositionMap = new TreeMap<>();
for(int index = 0; index < inputOrder.length; index++) {
letterPositionMap.put(inputOrder[index], index);
}
Integer expectedPosition = 0;
for(Character letter : letterPositionMap.keySet()) {
if(letter.equals(BLANK_SPOT)) continue;
Integer currentPosition = letterPositionMap.get(letter);
if(!currentPosition.equals(expectedPosition)) {
Character charAtExpectedPosition = inputOrder[expectedPosition];
if(charAtExpectedPosition.equals(BLANK_SPOT)) {
//move current iteration letter to expected spot
inputOrder[expectedPosition] = letter;
//move blank spot to current iteration
inputOrder[currentPosition] = BLANK_SPOT;
//update index of letter in map
letterPositionMap.put(letter, expectedPosition);
//update index of blank spot in map
letterPositionMap.put(BLANK_SPOT, currentPosition);
} else {
//move letter from expected spot to blank spot
Integer blankSpotLocation = letterPositionMap.get(BLANK_SPOT);
inputOrder[blankSpotLocation] = inputOrder[expectedPosition];
//move current iteration letter to expected spot
inputOrder[expectedPosition] = letter;
//move blank spot to current iteration
inputOrder[currentPosition] = BLANK_SPOT;
//update index of letter in map
letterPositionMap.put(letter, expectedPosition);
//update index of blank spot in map
letterPositionMap.put(BLANK_SPOT, currentPosition);
//update index of letter at expected spot in map
letterPositionMap.put(charAtExpectedPosition, blankSpotLocation);
}
}
expectedPosition++;
}
for(Character ch : inputOrder) {
System.out.print(ch + " ");
}
}
Try this. It follows the idea of hashMap that was mentioned before. It should be done in O(N) operations with each operations requiring two swaps at max.
Can be done in O(n) # of swaps:
- Aditya August 08, 2016Algorithm:
swap dock #1 with the dock # of box in it, using the auxillary space, unit you get box #1 in dock #1.
after that go to the next dock and repeat the same procedure till you rech last dock