Google Interview Question for Software Developers


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

- Aditya August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- A September 07, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- A September 07, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anon March 22, 2017 | Flag
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:
- 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.

- Chris August 05, 2016 | Flag Reply
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.

- Arun Vadivel August 05, 2016 | Flag Reply
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])

- vivek.doudagiri August 05, 2016 | Flag Reply
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.

- Johnny August 05, 2016 | Flag Reply
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.

- Nisheeth August 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 24, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 24, 2016 | Flag
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;
	}

- divm01986 August 08, 2016 | Flag Reply
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 .

- Anusha kowdeed August 24, 2016 | Flag Reply
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

- piotrekg2 August 25, 2016 | Flag Reply
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;
}

- Anon September 03, 2016 | Flag Reply
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);
    }

- josbimosbi January 02, 2017 | Flag Reply
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()[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)

- Nitish Garg January 03, 2017 | Flag Reply
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));
			}
		}
		
	}

- zacattack November 02, 2018 | Flag Reply
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.

- srini.som April 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Just use quicksort.

- frestuc August 05, 2016 | 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