Oracle Interview Question Java Developers
Country: India
Interview Type: In-Person
Its n-1.
Assume there are n players in a tennis singles tournament having the rule that as soon as someone loses a match, he is out. Now to find a winner, n-1 players must lose a match. Now see the analogy between this example and the question
As per your argument, that as soon as a person loses a match, he is out of the tournament, there will be approx. log n games. An example is Wimbledon, in which 128 players play in 7 rounds to find the winner.
A similar analogy would be trying to find out the tallest among a group of people, being able to ask only if person A is taller than person B, and being answered truthfully either yes / no
@Sandeep, your logic is wrong, I agree that for 128 players there will be 7 rounds but there will be 127 matches : 64 in first, 32 in second, 16 in third, 8 in fourth, 4 in fifth, 2 in sixth and 1 in seventh round.
You can see the question in this way as well : if a coin is rejected that it can not be the lightest one, it must have been weighted against atleast one coin lighter than itself.
How to find min-weight (coin) in a given set of '10' distinct weights (coins) in minimum number of weighing's if provided with a balance. (no labels shown on coin resembling the weight). Generalize for 'n' distinct weights.
^-- I hate problems that are stated ambiguously.
"How to find the min-weight (coin)" => implies there's a coin in the set that weights less than the others coins in the set. Stated alternately, this implies there are two different types of coins (i.e. two possible weights for each specific coin in the set) and nine of the ten coins are of heavier variety while the remaining one is of lighter variety. But it's not clear that's what's being asked at all...
"... Given a set of '10' distinct weights (coins)" => ambiguous. could mean there are ten coins in the set each of which has a distinct weight (i.e. each coin in the set of ten has a different (i.e. distinct) weight) or there are ten coins in the set which each has a weight which could be the same or different. (would seem like an imprecise or unusual connotation of the word 'distinct'. Reading on...
"Generalize for n distinct weights" => here we use the term 'distinct' again. It's still unclear what the problem statement is. Are we saying there are n different types of coins each with a distinct weight and the task is to deduce the minimum weight coin from a set of m coins (e.g. m == 10). Or, is the question to scale the answer as the set size of coins is increased to n coins (saying nothing about how many different coin types (i.e. distinct weights) there are?
So...
Assume a set comprising C coins total.
The set of C coins comprises coins chosen from another set T whose members are archetypes (e.g. T might comprise pennies, nickles, dimes, quarters). Each member of T has a distinctly different weight.
What is the size of set C and the size of set T? Are there any assumptions about the composition of C given T? Or, is C simply chosen from random from T?
The answer is n-1.
But proving this is the trickier part.
This is one proof that I would have given. Convert the given problem to a graph problem. The players are treated as nodes and a comparison between 2 players is treated as an edge. Now, the problem boils down to graph connectivity. To have a connected graph, there should be a minimum of n-1 edges. If we have less than n-1 edges, it guarantees that the graph is not connected.
PS: While less than n-1 edges guarantees that the graph is not connected, greater than n-1 edges does not guarantee connectivity. I will leave it to you to figure out why.
I think the ans would be log n ( like if n=8, u can keep 4 on one pan and 4 on another pan of the balance. You get the less weighing 4 and again split it into 2 on each pan..finally u compare the two smallest ones by placing one on each pan and you get ur ans.) tell me if there is a better way
Selection algorithm.
This is finding the smallest ( can also generalize it to kth smallest) number in a set of number using a comparator.
I also got 9. Weigh 2 different coins each time to get 5 coins from the 10 that weigh less in each weighing, and then repeat with 4 of these 5 coins, and then repeat with the 2. Since there's an odd number, the final coin that was left out will need to be weighed.
Generalizing this method should require a proof by induction since this method relies on using an algorithm. I'm out of time atm, but it should be a simple proof (induct on powers of 2, i.e. if 2^i is the smallest power of 2 contained in n holds, say 2^(i+1) is now the smallest power of 2 and try to see if the hypothesis works). I suspect that the n-1 solution is correct as well, but I haven't worked the details yet.
The answer is 4.
This can be derived from: 2^n = 4
2^3 is 8
and 2^4 is 16, so we have to go with n=4.
So we will have following weights:
2^0, 2^1, 2^2, 2^3
That is:
1, 2, 4, 8
Now imagine yourself if you can derive all the numbers between 1 to 10 or not from it.
I can prove that it is possible to do it in n - 1 weighings, but proving it is the minimum is escaping me.
- Wesley Cho April 08, 2012The coins must be weighed in pairs, since there is no useful information that can be guaranteed to be gotten by weighing 3 or more coins at once.
Lemma: 2^i coins requires 2^i - 1 weighings. Proof: For i = 0, done. Suppose it holds for i. 2^(i + 1) coins can be paired mutually exclusively into 2^i pairs for weighing, resulting in 2^i coins left. Those coins require 2^i - 1 weighings by inductive hypothesis, so the # of weighings required = 2^i + 2^i - 1 = 2^(i + 1) - 1.
For n = 1, there are no weighings required - so n - 1 = 0.
Suppose that for all n with 2^i as the highest power of 2 contained in n, n coins require n - 1 weighings.
Now suppose that 2^(i + 1) is the highest power of 2 contained in n. Then we may say that m = n - 2^(i + 1) < 2^(i + 1) (if not, then n >= 2^(i + 1) + 2^(i + 1) = 2^(i + 2), a contradiction to the assumption).
By inductive hypothesis, the # of coin flips for the min weight coin out of the m remaining coins is m - 1.
By lemma, the coin flips for the min weight coin out of the 2^(i + 1) coins is 2^(i + 1) - 1.
Since we are left with two coins, we must make 1 additional weighing to determine the lightest coin, so we made (m - 1) + (2^(i + 1) - 1) + 1 = (n - 2^(i + 1) - 1) + 2^(i + 1) = n - 1 weighings.