## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

Each person has a distance that they wish to be rotated. Calculate this distance as a positive number in the clockwise distance, so it will be a number from 0 to 4. Initialize an array from 0 to 4 with counts of zero, and the array will represent the number of people that are happy with each rotation distance. For each person, increment the appropriate slot in the array. At the end, iterate through the array to see which one has the largest count.

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

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

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

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?

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

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

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

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

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.

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

``````public class PassesForPreferences {

public static void main(String[] args) {

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

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

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

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

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) {
// distance from the start of array to the desired position
distanceToPreference += (i + 1);
}
}

// one more preference is happy on the distance 'distanceToPreference'
passes[distanceToPreference]++;
}

System.out.println("passes: " + Arrays.toString(passes));

int bestPassesNum = 0;
for (int i = 0; i < passes.length; i++) {
if (bestPassesNum < passes[i]) {
bestPassesNum = passes[i];
}
}

System.out.println("we need " + bestPassesNum + " passes");
}
}``````

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

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

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

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.

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

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

@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
}``````

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

#include<stdio.h>
#include<math.h>
int flag;
main()
{
int pref,allot,i,n;
char A;

printf("Enter Preference from A to E\n");
for(i=0;i<5;i++)
{
printf("\n%c =",65+i);
scanf("%d",&pref[i]);
}
printf("Enter Current Situation\n");

scanf("%s",A); //BCDEA

for(i=0;i<5;i++)
{
n=A[i];
n-=65;
allot[n]=i+1;
}
for(i=0;i<5;i++)
{
printf("%d ",pref[i]);
}
printf("\n");
for(i=0;i<5;i++)
{
printf("%d ",allot[i]);
}
printf("\n");
for(i=0;i<5;i++)
{
int t=pref[i]-allot[i];
if(t<0)
t+=5;

flag[t]++;

}
printf("\n");

for(i=0;i<5;i++)
if(flag[i]>=3)
{
printf("%d\n",i);
break;
}

return 0;
}

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

Is it not a deadlock problem.

Use Banker's Algorithm. It does exactly this thing

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

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.

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.