Google Interview Question for Software Developers

• 2

Country: United States

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

Can be done in O(n) # of swaps:

Algorithm:

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

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

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

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

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

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

It's clearly O(n) but not guaranteed n+1. Depending on luck the the newly vacated spot could be the last one.

ex)
5 4 3 2 1 x
x 4 3 2 1 5
1 4 3 2 x 5
1 4 3 2 5 x
1 x 3 2 5 4
1 2 3 x 5 4
1 2 3 4 5 x

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

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:
- 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.

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

Since the requirement is to sort in minimal moves, use selection sort or cycle sort.

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

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])

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

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.

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

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.

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

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.

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

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.

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

//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;
}

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

As said by Aditya we can use Cycle sort that sorts with minumum number of moves .

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

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

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

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;
}

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

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);
}

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

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()
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)

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

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));
}
}

}

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

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.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

Just use quicksort.

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.

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.