abc Interview Question for Applications Developers


Country: India
Interview Type: In-Person




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

Divide the initial array into 4 pieces. One side will have 2 equal parts and the other side will have 2 non-equal parts. Use the equal side to tell the weight of the normal marble. Now binary search the unequal side of the array by splitting the current portion in half and moving to the half that's weight doesn't logically make sense given the normal marble weight. Once you have a single marble selected, that should be the odd one out.

This is an O(lgn) time algorithm and O(1) space.

- jbaum517 August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you.but how is the time complexity calculated here..? Can u plz help me with that

- Divya Bolla August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, so think about what this algorithm is doing. We are constantly splitting the input in half. The time here is a question of how many times does it take us splitting the input in half to have 1 number remaining (aka 2^0 numbers remaining).

We start with an array of size size = n = 2^k.
Then we split the array in half, size = 2^(k-1)
Then again, size = 2^(k-2)
continue..
until size = 2^0 = 2^(k-k) = 1

It took us K steps to go from 2^K to 2^0. What is K in terms of N?

2^K = N, therefore, K = lg2(N)

- jbaum517 August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

since weigh balance is used we should consider splitting the group into 3 not 2 . 12 marbles should be split into three groups 4(g1) ,4(g2) , 4(g3) and weighed in the balance a below.

Assume g3 contains a heavier marble:
Case : (compare g1 and g2) If the g1 and g2 are weighed the balance will remain same so discard g1 , g2 and continue the same process with g3

Case where g1 is compared to g3 : weight balance will lean towards g3 heavier side so discard g1, g2 and and continue the same process with g3.

so Complexity becomes O(logN) where N is number of marbles and base of log is 3 not 2.

- vasa.v03 December 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

3

- xxx August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3

- Selvan August 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

2 < log_3(12) < 3, so at least 3 steps
btw, log_3(24) < 3, and we are able to find if the odd marble is heavier or lighter


1:
(1, 2, 3, 4) < (5, 6, 7, 8) => x in (1, 2, 3, 4) and lighter or x in (5, 6, 7, 8) and heavier

1.1:
(1, 2, 3, 5) < (4, 10, 11, 12) => x in (1, 2, 3) and lighter
1.1.1:
1 < 2 => 1 is odd marble and lighter
1.1.2:
1 > 2 => 2 is odd marble and lighter
1.1.3:
1 = 2 => 3 is odd marble and lighter

1.2:
(1, 2, 3, 5) > (4, 10, 11, 12) => x is 4 and lighter or x is 5 and heavier

1.2.1:
1 > 4 => 4 is odd and lighter
1.2.2:
1 = 4 => 5 is odd asd heavier

1.3:
(1, 2, 3, 5) = (4, 10, 11, 12) => x in (6, 7, 8) and heavier

1.3.1:
6 < 7 => 7 is odd and heavier
1.3.2:
6 > 7 => 6 is odd and heavier
1.3.3:
6 = 7 => 8 is odd and heavier

2:
(1, 2, 3, 4) > (5, 6, 7, 8) is simular as 1

3:
(1, 2, 3, 4) = (5, 6, 7, 8)

3.1:
(9, 10, 11) > (1, 2, 3) => x in (9, 10, 11) and heavier

3.1.1:
9 > 10 => 9 is odd and heavier
3.1.2:
9 < 10 => 10 is odd and heavier
3.1.3:
9 = 10 => 11 is odd and heavier
3.2:
(9, 10, 11) < (1, 2, 3) => x in (1, 2, 3) and lighter

3.2.1:
9 > 10 => 10 is odd and lighter
3.2.2:
9 < 10 => 9 is odd and lighter
3.2.3:
9 = 10 => 11 is odd and lighter
3.3:
(9, 10, 11) = (1, 2, 3) => 12 is odd

3.3.1:
12 < 1 => 12 is odd and lighter
3.3.2:
12 > 1 => 12 is odd and heavier

- afazulzyanov August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3 steps pf weighing required
1 .devide group of 12 stones to group of 6
2 .find the highest weighing group
3.devide the most weghted group to group of 3
4.find most weighted among these two groups having 3 stones
5.in that three stones weigh about any two stones if they are equal the third stone have higher weight. else stone in weigh scale have higher weight.

- sj August 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

one correction :find it is higher or lower weight ,for that weigh between 6 vs 6 and
not position of each side.weigh 3 vs 3 on each find the group of equal weight.from this we can find unknown stone have high weight or less weight

- sj August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

so total 4 steps

- sj August 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

3 try

Solution is little tricky (not a mathematical solution but a logical solution)---

Divide 12 balls in 3 sets of 4. Batch 1, Batch 2, Batch 3

1. Measure Batch 1 & Batch 2 (batch 1 on left side and batch 2 on right side)

2 a. left side goes up - If different ball is light then its in batch 1, if ball is heavy then its in batch 2. Take 3 balls from batch 1 and 2 ball from batch 2 place them on left side, take 4th ball from batch 1 and place it on right side along with 4 balls from batch 3.

3 a. Left side still goes down - Ball is light and its one of the 3 balls that are placed on left side. take two of them and measure. lighter one will be different if they weight same then 3rd ball is different

3 b. Right side goes down - Either two balls placed on left side from batch 2 are heavy or 4th ball placed on right side from batch 1 is light. Measure the 2 balls from batch 2. If they are same then its the 4th ball from batch 1 which is light, if t they are not same then take the heavy one. That's different

3 c. If both side remains same then different ball is in 2 balls left from batch 2 and its heavy. Measure them and take the heavy one

2 b. Left side goes down - then the above logic will still hold true

2 c. Both side weight same - Different ball is in batch 3. Take 3 balls from batch 3 and 3 balls from batch 1 and weight them.

3 a . Batch 1 balls goes down then it means ball is heavy and its one of the 3 balls from batch 3. Take two balls from batch 3 and measure and take the heavy one. If they weight same take 3rd ball

3 b. Batch 1 goes - same logic hold true

3 c. Both batches weight same - Its the 4th ball from batch 3 which is different. Measure it against any other ball to find if its heavy or light

- Dalip December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3 try

Solution is little tricky (not a mathematical solution but a logical solution)---

Divide 12 balls in 3 sets of 4. Batch 1, Batch 2, Batch 3

1. Measure Batch 1 & Batch 2 (batch 1 on left side and batch 2 on right side)

2 a. left side goes up - If different ball is light then its in batch 1, if ball is heavy then its in batch 2. Take 3 balls from batch 1 and 2 ball from batch 2 place them on left side, take 4th ball from batch 1 and place it on right side along with 4 balls from batch 3.

3 a. Left side still goes down - Ball is light and its one of the 3 balls that are placed on left side. take two of them and measure. lighter one will be different if they weight same then 3rd ball is different

3 b. Right side goes down - Either two balls placed on left side from batch 2 are heavy or 4th ball placed on right side from batch 1 is light. Measure the 2 balls from batch 2. If they are same then its the 4th ball from batch 1 which is light, if t they are not same then take the heavy one. That's different

3 c. If both side remains same then different ball is in 2 balls left from batch 2 and its heavy. Measure them and take the heavy one

2 b. Left side goes down - then the above logic will still hold true

2 c. Both side weight same - Different ball is in batch 3. Take 3 balls from batch 3 and 3 balls from batch 1 and weight them.

3 a . Batch 1 balls goes down then it means ball is heavy and its one of the 3 balls from batch 3. Take two balls from batch 3 and measure and take the heavy one. If they weight same take 3rd ball

3 b. Batch 1 goes - same logic hold true

3 c. Both batches weight same - Its the 4th ball from batch 3 which is different. Measure it against any other ball to find if its heavy or light

- Dalip December 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't use a algorithm or standard written logic. I sort of did this the way that Dalip did it. However, I was not aware of the question not allowing 1 marble being weighed.

I would weigh 2 marbles individually. That would give me the possibility of 2 of the same weights. For instance/example, 2oz but if I were to get two of the same results that would mean that the majority of the marbles were that weight because only 1 is heavier or lighter.

I would then multiply 2oz by the 11 = 22oz. I would then weigh the whole group of marbles after performing this math. If I measured 23oz then the one marble is 1oz lighter than the other marbles. If I measured 25oz then the marble is 1 oz heavier than than the other marbles.

This is probably wrong and I missed something in my logic but it made sense to me at the time.

- Mike h. March 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

3 tries.

Divide 12 balls in 3 sets of 4. say A, B, C
weight A against B, if both are equal, then defected marble is in C otherwise if A > B defected marble is in B(weigh count 1)

suppose B has defected ball:
take 3 marble from each B and A or C, if both has same weight that means 4th ball from B is defected.(weigh count 2)
if weight of 3 balls from B are not equal to A balls, then weight any two ball from B if weight are different then we found defected ball otherwise 3rd ball is defected.(weigh count 3)

suppose C has defected ball:
take 3 marble from each C and A or B, if both has same weight that means 4th ball from C is defected.(weigh count 2)
if weight of 3 balls from C are not equal to A balls, then weight any two ball from C if weight are different then we found defected ball otherwise 3rd ball is defected.(weigh count 3)

- Anand May 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer is one.
It's asking for minimum number of tries, not maximum.

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

The answer is one.
It's asking for minimum number of tries, not maximum.

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

Devide in three groups 5-5-2, in this scenario best case will be 2 tries and worst will be 3 tries

- manoj.mk05 August 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't know why people are saying 4 , the correct ans is ""3"":
1. at first divide the 12 marbles into 3 pieces of 4.
2. put 4 pieces one side and 4 on other side of the weight scale,
case 1: the wieghts are equal:
1.1 it means the lighter one is from the 4 not in weight scale.
from that 4 marbles,put 2 marbles on both side of the scale
1.2 the one which is lighter has the light marble
1.3 put the one marble on each scale, and you'll get the lightest marble.
case 2: the weights are not equal:
strt from 1.2

- ibrahim April 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test

- sdf April 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can achieve the same answer (3) by splitting into two groups each having 6 marbles.
Try-1 6 & 6
Try-2 Get the lowest weighing group and split into 3-3
Try 3 From the lowest weighing group pick 2 marbles and weigh, if both are same then 3rd is lowest. Else which is least weighing marble in the balance is the marble.

So answer is 3.

- Mahathi Kondamudi October 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

4
Divide the initial array into 3 pieces:A B and C.
first: if A=B, then the odd one is in C.
C(a,b,c,d)
second if a=b,then: if a=c,the odd one is d
else the odd one is c
third if a!=b,then: if a=c, the odd one is b
else the odd one is a.
if A!=B
if A=C, the odd one is in B
else, the odd one is in A.
return the the steps 2nd and 3rd above.
so I think I need 4 steps to find the odd one.

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

you see that if A!=B, then you would need another step, then the answer would be 5. Check it out.

- Anonymous August 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Correct answer is 4

1. divide 12 marbles into group of 4.
2. now you have 3 groups - 4 marbles in each group. let;s call group A, B and C
3. Weigh group A vs B
case 1. A > B
4. Weigh A vs C
case 1.1 A > C - meaning group A has the defected marble. We also learned that defected marble in heavier.
5. Now divide group A' marble into group of 2 and weigh the two groups and so on until you find the defected marble. so far total attempts are 4
case 1.2 A == C - meaning group B has the defected marble and since A > B, defected marble in lighter. follow the above procedure. total attempts to discover defected marble in this case is 4
case 1.4 A < C - will it ever come here.. think about it

case 2. A < B
follow the above procedure

case 3 A== B - meaning C has the defected marble
pick 2 marbles from A and 2 from C. If they are equal then remaining 2 marbles will have the defected one. in that case pick 1 marble from A and 1 from remainining 2 from group C. weigh them if they are equal then last one is culprit.. if not equal then the current one is culprit.

so the correct answer is 4.

- Anonymous August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It asks for the minimum number. Look at your case 3, the number of times weighed is three (you just have to identify odd one out, not whether it is lighter or heavier). It would require some luck for this to occur, but it is the minimum number. I would give this as the response, and qualify it to say that 4 times would always result in an answer

- pyxis828 January 23, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. divide 12 marbles into group of 4.
2. now you have 3 groups - 4 marbles in each group. let;s call group A, B and C
3. Weigh group A vs B
case 1. A > B
4. Weigh A vs C
case 1.1 A > C - meaning group A has the defected marble. We also learned that defected marble in heavier.
5. Now divide group A' marble into group of 2 and weigh the two groups and so on until you find the defected marble. so far total attempts are 4
case 1.2 A == C - meaning group B has the defected marble and since A > B, defected marble in lighter. follow the above procedure. total attempts to discover defected marble in this case is 4
case 1.4 A < C - will it ever come here.. think about it

case 2. A < B
follow the above procedure

case 3 A== B - meaning C has the defected marble
pick 2 marbles from A and 2 from C. If they are equal then remaining 2 marbles will have the defected one. in that case pick 1 marble from A and 1 from remainining 2 from group C. weigh them if they are equal then last one is culprit.. if not equal then the current one is culprit.

so the correct answer is 4.

- wick August 09, 2015 | 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