## BMO Harris Bank Interview Question for Software Developers

• 0
of 0 votes

Team: Anti-money laundering
Country: United States
Interview Type: In-Person

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

Are we looking for a heavy weight or light weight ball? I am assuming light weight here.

Minimum number of times to find the ball that is not equal weight is 2

Make two groups of 3 balls and one group of 2 balls

For e.g.
Group 1 and Group 2 has 3 balls
Group 3 has 2 balls

a) Weigh Group 1 and Group 2
b) If Weight (Group1) == Weight(Group2) then Group3 has the light weight ball
b1) Weight balls in Group3 to find the light weight ball
c) Else either Group1 or Group2 has the light weight ball
c1) Choose two balls from light weight group and weigh again
c11) If Weight(ball1) == Weight(ball2) then left out ball (Ball3) is the light weight ball
c12) Else either ball1 or ball2 is the light weight ball

So, the minimum number of times to use a scale is 2 times - using three-group technique.

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

So I though about this for a while, and here's what I ended up with.

First, observe that since we have a balance that allows us to compare two sets of balls then there are 3 possible outcomes:
1. The left side of the balance is heavier
2. The right side of the balance is heavier
3. The two sides are equal in weight

Now, we can think about the implications of each of the 3 outcomes.
1. The heavier ball is on the left side.
2. The heavier ball is on the right side.
3. The heavier ball is not on either side i.e. is in the set of balls not involved in the measurement

One of these 3 must occur and in all 3 cases we can eliminate the possibility that the ball is in the other 2 groups. So every time we take a measurement, we can remove 2 of the 3 groups that we separated the balls into. Now, if we assume that we divide the balls into equal groups each time, then we see that since we are left with 1/3 of the balls after each measurement, then the number of measurements necessary to reduce it to 1 ball would be ceiling(log_3(n)) where n is the original number of balls.

Now, we can consider the case where we can have groupings of different sizes, as we must if the number of balls isn't divisible by 3. In order for the conditions above to hold, the two groups on the scale must have the same number of balls; otherwise the conclusions are invalid. So, we have the condition that at least 2 of the 3 groups must have an equal number of balls. Since at each measurement its possible that we end up with the largest group, then the necessary number of further measurements at each step is log_3(max(n_i)) where n_i is the list of the number of balls in each group at step i. Thus, we see that its in our best interest to keep max(n_i) low at each point which means picking numbers as close to equal as possible. Obviously the closest we can come to equal is split exactly in thirds, so we see that if we follow the optimal strategy for each value of n we have the following relation:

num_measurements = ceiling(log_3(n))

0-3 => 1 measurements
4-9 => 2 measurements
10-27 => 3 measurements
....

This is our answer for the worst case number of measurements for each given number of balls.

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

I believe the problem is missing one important factor. The order in which the "odd" ball is picked...

If first or second, weight two balls. If 3rd-8th, weight 6 balls initially. Hence, it depends on chance of having odd ball in hand

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

Also, if the odd ball is one of the first four balls, two attempts is very likely

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

The two problems with knowledge of whether the different ball is heavier or lighter and without aforementioned knowledge are completely different. If it is known that the different ball is lighter (or heavier), the answer is obviously 2 turns of weighing.

Assuming that the different ball is lighter:

1) Start by picking 6 balls at random and place 3 on either side of a scale
2) If the the first weighing is equal, it will take only 1 weighing to determine which of the remaining 2 balls is different (k
3) If the first weighing is unequal, and we know that the ball is lighter, so we pick 2 balls at random from the lighter side.
4) If the second weighing from the pile of 3 balls is equal, then the left out ball is lighter.
Or else, the lighter ball is found from the weighing.

If, on the other hand, it is unknown that the different ball is heavier or lighter, it will take 3 tries to figure out the different ball.

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