## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

27 27 (27)
9 9 (9)
3 3 (3)
1 1 (1)

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

Love the simplicity of this answer ! If anyone is wondering what's the complexity , then it's O(logn) [ base 3 , not base 2 ] .

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

Yes. The generic solution takes logN with base 3. Original problem is nine balls. This is twisted, but can be solved with same formula.

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

Nice idea, but implementing it is not that trivial.

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

f(n) = log3(n) + (n is power of 3 ? 1 : 0);
f(3) = f(2) = 1;

f(1) = f(0) = 0; //trivial

Not sure, why dynamic programming needed. Looks to me like, O(1) computation.

ex: f(27) = 1 + f(9); //divide into 9,9,9, compare 2 9's
f(9) = 1 + f(3); //divide into 3,3,3, compare 2 3's
f(3) = 1;
formla gives f(27) = log3(27) + 0

ex: f(12) = f(4) + 1 //4,4,4
f(4) = f(3) + 1; //2,2
f(3) = 1;

formula gives f(12) = log3(12) + 1 = 3;

(Please verify if f(n/3) needs to be considered in forumla instead of log3(n) before accepting)

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

[5 Tries]

1) split into three groups 27 each
2) weigh the two groups of 27 each.
3a) If both are equal the lighter ball is on the 3rd group of 27
3b) If they are unequal the lighter group on the balance should have the lighter ball
4)Pick up the suspected group , Split into two groups of 13 each and weigh them, so 13 13 1
5a) If they are equal the one extra ball is the lighter one
5b) If they are unequal pick the subgroup which contains the lighter ball
6) Split the subgroup of 13 into 6 6 1 and weight 6 and 6 against each other
7a) If they are equal the 1 extra ball is the lighter ball
7b) If they are unequal so we have the group of 6 which contains the lighter ball
8) Split the group of 6 into 3 3, one of that should be ligher pick the group of 3
9) Split the 3 into 1 1 1, weight 1 1 against each other.
10a) If both are equal the third ball is the lighter one.
10b) If they are unequal , the one which weights low is the lighter ball

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

Wrong. Maximum it takes 4 tries

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

Always work with thirds. Going off the previous answer where you now have a suspected group of size 27. Break this into three groups of 9.compare two groups. If same it's in the third, otherwise take the lighter group of 9. The lighter group of 9 is solved similarly again with thirds, comparing two groups of 3 and taken a culprit group of 3 containing lightest group. A group of three just needs a comparison of two items, again comparing two groups that are a third of the population. This answer takes at most 4 comparisons

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

``````public static int find_lighter(int a[],int start, int end){

if(start == end) //exit condition
return start;
//divide this array into three.
int parts = (end+1-start)/3;

//store start and index of each part into temporary variable to avoid creation of new //arrays.
int firstStart = start;
int firstEnd = firstStart + parts-1;

int secondStart = firstEnd +1;
int secondEnd   = secondStart +parts -1;

int thirdStart = secondEnd+1;
int thirdEnd =  a.length-1;

//calculate sum
int sum1 = sum(a,firstStart,firstEnd);
int sum2 = sum(a,secondStart,secondEnd);
int sum3 = sum(a,thirdStart,thirdEnd);

if(sum1 == sum2){
//sum3 has the lighter
return find_lighter(a,thirdStart,thirdEnd);
}
else if(sum1 > sum2){
//sum2 has the lighter
return find_lighter(a,secondStart,secondEnd);
}else{
//sum1 has the lighter
return find_lighter(a,firstStart,firstEnd);
}
}
public static int sum(int a[],int start, int end){

int sum = 0;
for(int i=start;i<=end;i++){
sum = sum + a[i];
}
return sum;
}``````

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

What do you mean by using dynamic programming??

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

Briefly, it means Solving the problem by splitting it in sub problems. Store results for partial solution. Use stored results for taking next decision.

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

I have an idea about dynamic programming. I was asking in context of this question. As the optimal solution is to divide the group into 3 sub-groups and again checking those and choosing another suitable sub-group and then searching in that group. So, this looks like a ternary search(like binary search but just dividing the input into 3 parts).

So, basically we are just dividing the input into sub-problems. What part of the above algorithm known as dynamic programming. And if this is a DP algorithm, then even binary search is a DP algorithm.

Please bear with me, I am very confused.

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

DP means if you have solution to sub-problems,add those results to fins solution to the main problem.

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

first knew 'dynamic programming' by this problem. I looked up in wiki and implemented. would you correct me if there is something weird?

``````#include <stdio.h>
#include <string.h>
#include <math.h>

static int s_weight_subtotal;

int get_weight(int weight[], int start, int len)
{
int i;

if(len==1)
return weight[start];

i = log(len)/log(3)-1;

if(!s_weight_subtotal[i][start]) {
s_weight_subtotal[i][start]	= get_weight(weight, start, len/3) + get_weight(weight, start+len/3, len/3) + get_weight(weight, start+(len*2/3), len/3);
}

return s_weight_subtotal[i][start];
}

int find(int weight[], int start, int len)
{
if(len==1)
return start;

if(get_weight(weight, start, len/3) < get_weight(weight, start+len/3, len/3)) {
return find(weight, start, len/3);
}
else if(get_weight(weight, start+len/3, len/3) < get_weight(weight, start+(len*2/3), len/3)) {
return find(weight, start+len/3, len/3);
}
else {
return find(weight, start+(len*2/3), len/3);
}
}

void dump_weight_subtotal(void)
{
int i, j;
for(i=0; i<3; i++) {
printf("[%d] ", i);
for(j=0; j<81; j++) {
if(s_weight_subtotal[i][j]!=0)
printf("(%d: %d), ", j, s_weight_subtotal[i][j]);
}
printf("\n");
}
}

int main(int argc, char* argv[])
{
memset(s_weight_subtotal, 0x00, sizeof(s_weight_subtotal));

int weight;
for(int i=0; i<81; i++)
weight[i] = 90;
weight = 12;

int idx = find(weight, 0, 81);
printf("lightest: idx=%d, value=%d\n", idx, weight[idx]);

dump_weight_subtotal();

return 0;
}``````

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

Python:
O(n) subproblems each taking O(1) time = O(n) time
O(n) space for the DP array

``````def findcompares(num):
arr = [0 for x in range(num+1)]

arr = 0; arr = 0; arr =1; arr = 1;

for i in range(4,num+1):
thevals = helper(i)
arr[i] = max(arr[thevals], arr[thevals], arr[thevals])+1

return arr[num]

def helper(num):
r = num%3
d = num/3

if r==0:
return d,d,d
if r==1:
return d,d,d+1
if r==2:
return d,d+1,d+1``````

print findcompares(81)

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

use modified merge logic,during the joining only return array values with distinct values

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

You can change the BALL_MAX define for any divisible by 3. Try 81*81*81 for example.

time: O(log3(n)) best case, worst case is O(n)
space: O(n)

``````#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define BALL_MAX (81)
#define MIN(_a, _b) (((_a) < (_b)) ? (_a) : (_b))
#define BALL_OFFSET(_ball, _len, _off) (_ball + ((_len / 3) * (_off)))

static long iterations;

inline size_t min3(size_t a, size_t b, size_t c)
{
return MIN(MIN(a, b), c);
}

size_t weight(size_t *ball, size_t len)
{
size_t i;
size_t ret = 0;
for (i = 0; i < len; ++i)
ret += *(ball + i);
return ret;
}

bool find_lightest_ball(size_t *ball, size_t len, size_t *min_val /* OUT */)
{
iterations++;
if (len == 3) {
*min_val = min3(*ball, *(ball + 1), *(ball + 2));
return true;
} else if (len == 9) {
size_t w1, w2, w3;
w1 = weight(BALL_OFFSET(ball, len, 0), len / 3);
w2 = weight(BALL_OFFSET(ball, len, 1), len / 3);
w3 = weight(BALL_OFFSET(ball, len, 2), len / 3);

if (w1 == w2 && w2 == w3)
return false;
else if (w1 < w2)
return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val);
else if (w2 < w1)
return find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val);
else
return find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
} else {
return find_lightest_ball(BALL_OFFSET(ball, len, 0), len / 3, min_val) ||
find_lightest_ball(BALL_OFFSET(ball, len, 1), len / 3, min_val) ||
find_lightest_ball(BALL_OFFSET(ball, len, 2), len / 3, min_val);
}
}

int main(int argc, char *argv[])
{
size_t i, ball[BALL_MAX];
size_t w, w2, l_i;
size_t min_ball_val;

srand(time(NULL));

w = rand() % 100 + 1;
for (i = 0; i < BALL_MAX; i++)
ball[i] = w;

l_i = rand() % BALL_MAX;
while ((w2 = rand() % 100) >= w);

ball[l_i] = w2;

for (i = 0; i < BALL_MAX; i++)
printf("ball #%u: %u\n", i+1, ball[i]);

find_lightest_ball(ball, sizeof(ball) / sizeof(*ball), &min_ball_val);
printf("lightes ball: %u\n", min_ball_val);
printf("number of iterations: %ld\n", iterations);

return 0;
}``````

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

#include <stdio.h>
#include <stdlib.h>
//(1. Num of left ball is odd )take out 1 ball each time randomly, ,if balance
//between 2 sides, randow ball is target; if not, find the smaller one
//group to recursive; (2.Num of left ball is even). Compare both size, using smaller one group
//to recursive.
int recursion_cal(int a[]);
int main()
{

int i=0;
int a;
for (i=0;i<81;i++)
a[i]=2;
a=1;

return recursion_cal(a);

//return 0;
}
int recursion_cal(int a[])
{
int pos_rand_ball;
int size_a=sizeof(a)/4;//how many items in array A.

if (size_a%2==0)//even
{
int i=0;
int group_A[size_a/2];
int tot_group_A=0;
int group_B[size_a/2];
int tot_group_B=0;
for( ;i<size_a;i++)
{
tot_group_A=tot_group_A+a[i];
tot_group_B=tot_group_B+a[size_a/2+i];
group_A[i]=a[i];
group_B[i]=a[size_a/2+i];
}
recursion_cal(tot_group_A<tot_group_B?group_A:group_B) ;
}
else
{
int i=0;
int group_A[size_a/2];
int tot_group_A=0;
int group_B[size_a/2];
int tot_group_B=0;
pos_rand_ball=rand()%size_a;
int temp[size_a-1];
for(;i<pos_rand_ball;i++)
{
temp[i]=a[i];

}
for(;i<size_a-pos_rand_ball;i++)
temp[pos_rand_ball+i-1]=a[pos_rand_ball+i];
for(;i<sizeof(temp)/4;i++)
{
tot_group_A=tot_group_A+temp[i];
tot_group_B=tot_group_B+temp[sizeof(temp)/8+i];
group_A[i]=temp[i];
group_B[i]=temp[sizeof(temp)/8+i];
}
if (tot_group_A==tot_group_B)
{printf("the position of abnormal ball is %d",pos_rand_ball );
return pos_rand_ball;
}
else
recursion_cal(tot_group_A<tot_group_B?group_A:group_B) ;
}

}

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

There are 81 balls, not 80.

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.