## Yahoo Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
3
of 5 vote

assuming names are distinct..
Say 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.

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

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.

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

How is it so ? Please can you explain!!!

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

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.

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

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

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

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 ?

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

13C5 or 13!/(8!*5!)

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

who told you that?

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.