CareerCup

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

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.

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

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.

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

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

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.

Just use quicksort.