CareerCup

This still uses "N" passes/iterations. Is it possible to do this in less than N passes for N people?

It only does three passes. One pass to initialize the array, one pass to increment it for each person, and one pass to find the max. It's O(N). The naive approach is basically N-squared, where you take try all N rotations and count all N people during each pass. Do you understand what I'm doing differently here?

Thanks for the reply. I am a bit lost here. Can you quickly mockup your method with an example? algo/code/step1,step2, etc

@xankar, To keep things simple, let's simplify the problem to say that the original seating arrangement is ABCDE, but our players are finicky about where they sit:

A: wants seat 3
B: wants seat 2
C: wants seat 4
D: wants seat 1
E: wants seat 3

Hopefully you can see how this maps to desired rotations from our original seating arrangement:

A: wants to move 2 clockwise
B: wants to move 0 clockwise
C: wants to move 1 clockwise
D: wants to move 2 clockwise (actual rotation)
E: wants to move 3 clockwise(actual rotation)

After we compute each person's desired shift, we update this data structure:

0 clockwise: 1 vote (from B)
1 clockwise: 1 vote (from C)
2 clockwise: 2 votes (from A, D)
3 clockwise: 1 vote (from E)
4 clockwise: 0 votes

Note that our data structure doesn't keep track of the voters; it's just the counts.

At the end we iterate through our vote tallies and find that 2-clockwise makes the most people happy (2).

Once you understand this scenario, it's a pretty small mental leap to account for the original seating arrangement being something other than ABCDE.

Nice solution. It's efficient, and your comments strike a nice balance of explaining things that aren't immediately obvious, without being overly verbose.

I think the above code will not work for all cases. for example, consider what happens when the input is "EABCD" with the preference array now changed to {4,1,2,3,4} The answer should be 1.Since in one pass it rotates to "ABCDE" where 4 are happy.
Also, bestPassesNum should point to the index to yield correct answer. Its pointing to the maximum number.
I've made some modifications.please let me know if its wrong.

import java.util.Arrays;

public class Example {

    public static void main(String[] args) {

        // A=1, B=2, C=3, D=4, E=4

        // 1 2 3 4 5 -- slots
        // 4 1 2 3 4 -- peoplePrefs
        // E A B C D

        int[] slots = new int[] { 1, 2, 3, 4, 5 };

        int[] preferences = new int[] { 4, 1, 2 , 3, 4 };

        int[] passes = new int[slots.length];
        
        int distanceToPreference = 0;
        
        // find a distance from the initial position of slots for each preference
        for (int i = 0; i < preferences.length; i++) {
            if (preferences[i] == i + 1) {
                // the stay on desired position
                distanceToPreference = 0;
            } else {
                // distance from the desired position to the end of array
                distanceToPreference = slots.length - preferences[i];

                if (preferences[i] >= i) { //CHANGE1
                    // distance from the start of array to the desired position
                    distanceToPreference += (i + 1);
                }
                distanceToPreference= (distanceToPreference% slots.length); //CHANGE 2
            }
            
            // one more preference is happy on the distance 'distanceToPreference'
            passes[distanceToPreference]++;
        }

        System.out.println("passes: " + Arrays.toString(passes));
        
        int bestPassesNum = 0;
        int result = 0;
        for (int i = 0; i < passes.length; i++) {
            if (bestPassesNum < passes[i]) {
                bestPassesNum = passes[i];
                result = i;//CHANGE 3
            }
        }
        
        System.out.println("we need " + result + " passes");
    }
}

@laxman601, I think you should try to collapse the following lines of code to one or two lines of code, and avoid all the special casing. If you can use zero-based indexing, then this idiom is fairly common:

desired_rotation = (desired_chair + num_chairs - chair) % num_chairs

If you are dealing with a language that computes modulus correctly for negative numbers (e.g. in Python, -5 % 7 == 2, which is correct, but JS is stupid about it and gives you the mathematically awkward answer of -5 ), then go with this:

desired_rotation = (desired_chair - chair) % num_chairs

if (preferences[i] == i + 1) {
                // the stay on desired position
                distanceToPreference = 0;
            } else {
                // distance from the desired position to the end of array
                distanceToPreference = slots.length - preferences[i];

                if (preferences[i] >= i) { //CHANGE1
                    // distance from the start of array to the desired position
                    distanceToPreference += (i + 1);
                }
                distanceToPreference= (distanceToPreference% slots.length); //CHANGE 2
            }

The Banker's algorithm solves a much more complicated problem. Read the question again and then read the wikipedia article on the Banker's algorithm.