Yahoo Interview Question Software Engineer / Developers
Country: India
At least 4, from an information theoretic standpoint. 13! / 5! / 8! = 1287. When the professor picks 5 students from a group of 13, that is the number of possible outcomes. To know about each student, the professor must have enough info to distinguish between each possible permutation (13!).
Even with no information overlap, 1287^3 < 13!. 1287^4 > 13!, so the professor needs at least k = 4. Whether there actually is a combination of k=4 I am not sure, but K cannot be < 4.
I had attempted to package a fairly tough argument in an information-theoretic shell to make the argument easy to understand for people that have seen such arguments before. Similar argumentation can be used to show that sorting based on comparisons cannot be faster O(N logN) and such.
_
This argument's actually kind of tough. Here's what I'm saying. When the professor makes an observation, by the calculations I showed, he makes 1 of at most 1287 distinct observations. Now, there are 13! possible arrangements of students. So, let's say the professor *partitions* the space of 13! possible outcomes into 1287 partitions, partition K representing the outcomes that are still possible after making first observation K. Even if he can make each partition the same size, there is at least some partition that has 13!/1287 = 4838400 outcomes.
Repeating this process, after a second observation, there's still some partition of size 3760 (ceil of 4838400/1287). After a third observation, some partition still has size at least 3. After a 4th observation, he could narrow it to 1 outcome.
Note that this proof doesn't show K can be as low as 4, it just shows no K less than 4 is possible. In fact, I don't think it's possible to do K < 5, but K= 5 is easily possible. These information-theoretic arguments just give a useful lower bound.
Define a "travel companion subset" as a group of students who have the same history of standing and sitting. For any two members of a travel companion subset of size >= 2, it's clear that we can't know their individual names. The good news is that once you find a person without any travel companions, you can identify his name immediately--it will be the only name that was called for the appropriate sitting/standing positions. Proof: Let's say person 4 has no travel companions. If he had heard both the names "Al" and "Bob" during his roll calls, he would clearly would have had a travel companion (since person 4 can only call his own name), so it's a proof by contradiction.
Anyway, divide and conquer, by splitting up people using a Fibonacci pattern:
5/8 standing/sitting
2/3 3/5 (stand/sit, stand/sit)
1/1 1/2 1/2 2/3 (stand/sit, stand/sit, stand/sit, stand/sit)
After three rounds, we have uniquely identified 4 people, and then we have travel companion subsets of 2, 2, 2, and 3 people. We can split those up in two more rounds:
1/1 1/1 1/1 1/2 # 7 people uniquely identified
1/1 # last 2 people identified
what do you mean by this sentence : " He remembers the names of all the students who are standing and the ones who are sitting but doesn't remember the name of each student individually"...
Its kind of confusing, since he already knows names of all standing and sitting, does that not mean he knows all the names ?
assuming names are distinct..
- aritra February 20, 2012Say first group is {1,2,3,4,5} now replace one of the students with a new one, new group is {1,2,3,4,6} .. so now he can identify 5 and 6 both,
next replace 4 with say 7 ..
then 3 with 8 ..
then 2 with 9
then 1 with 10
next change the group to include 2 unknowns e.g. {1,2,3,11,12} swap 12 with 13 in next move and he identifies both. And since he knows everyone except 11 .. he now knows 11 too
i.e.
k identified
1 0
2 2
3 4
4 6
5 8
6 10
7 12 + 1
hence k = 7.