big corp's interview question

A friend of mine who is working for a major IT corporation was asked a variant of the following question during his interview:

There is a village of people at the top of a hill, one night a prophet comes and tells the villagers that the next morning, at least one of them will have a white dot on their forehead. As soon as a villager knows for sure that he/she has a white dot on their forehead, they must leave the village in the morning. The villagers are not allowed to communicate at ALL with each other, and can not see their own foreheads. They may only see the foreheads of all of the other villagers. On the first morning, none of the villagers leave. On the second morning, none of the villagers leave. On the third morning, the exact number of villagers with white dots on their foreheads leave the village. How did these villagers know to leave?

The MAXIMUM time for hired personnel who was asked this question and had correct answer was 5 minutes. Personally, I was able to do it in about 2.

have fun~

Find more posts tagged with

Comments

johnnyg5646

only 3 people in the villiage?

bighornsheep

johnnyg5646 wrote:

only 3 people in the villiage?

explain your reasoning, why would 3 people mean that the villagers would know?

sprkymrk

Actually, I would contend that it was a false prophet.

one night a prophet comes and tells the villagers that the next morning, at least one of them will have a white dot on their forehead.

On the first morning, none of the villagers leave. On the second morning, none of the villagers leave.

If what a prophet says does not come to pass, he's a false prophet.

RTmarc

bighornsheep wrote:

johnnyg5646 wrote:

only 3 people in the villiage?

explain your reasoning, why would 3 people mean that the villagers would know?

Process of elimination. By the third day the third villager would have known that if the other two people did not leave, it must be himself.

Mishra

I would have to say that nobody left because no one had a dot on their head... The question just eludes to the fact that someone might have left.

Or everyone left becasue by the third day, everyone thought it was them with the white dot.

Ye Gum Noki

That is without question, the stupidest interview question I have ever heard. Worse, even that the ridiculas "What are some of your weaknesses?"

Guh!!!!

BigTone

Did they look in a puddle or a reflection of window or sometihng?

Vogon Poet

It is standard procedure to give abductees 3 days to get their affairs in order before they are called back to the mothership.
Beware of prophets that chain smoke.

Kaminsky

My response would have been "ermm.. pardon me for asking but is there a drugs problem in this company?"

What the hell sort of interview question is that? When I got it wrong, and then they explained it to me for the "ahhh..." moment, I would have got up and slapped them for being elitist pratts and then gone and got a real job. I mean, imagine working there after that interview!

Plantwiz

I'm curious at the hostile responses....whatever happened to the thrill of being challenged?

This isn't much different the the King/Queen for a day interview question or the Why are man hole covers round and not square? In some cases it's not about the answer, but the way you handle the odd-ball question

With Employers hands being tied on asking certain questions...they've had to come up with questions that can appear a waste of the applicants time, but really can show much more of their potential and a bit of their personality.....something that is far more important in many team environements then just how well you can troubleshoot. (a lot of people can troubleshoot).

davenport

Plantwiz wrote:

Why are man hole covers round and not square?

I thought it was so they couldn't fall in the hole.

sprkymrk

Plantwiz wrote:

I'm curious at the hostile responses....whatever happened to the thrill of being challenged?

We're mad because we don't know the answer and BigHornSheep won't tell us.

Plantwiz wrote:

Why are man hole covers round and not square?

Well, since the manholes themselves are round, it wouldn't make any sense for a manhole cover to be square now, would it?

bighornsheep

sprkymrk wrote:

Plantwiz wrote:

I'm curious at the hostile responses....whatever happened to the thrill of being challenged?

We're mad because we don't know the answer and BigHornSheep won't tell us.

hmm..I was really hoping more people would at least try this one, I'm assured that these problems or "riddles" are extremely popular among the top list l33t IT companies because it's meant to do two things, test your head knowledge and logic to figure out the problem, and to test your personality/emotional traits when faced with a roadblock under pressure.

The problem is meant to be seen and understood as "hopeless" or "stupid" or "what is this" "why am I being asked this crap" kind of question so they can see how you would react when things "arent what you would expect"...can one stretch their comfort zone, in other words.

Having said this, there is NO DOUBT that this question makes sense if you have some sort of math background, or at least willing to break down the issues and points in a way that "makes sense".

What is the question REALLY? Yes, how the villagers know to leave, another way of saying this is, how many villagers are there? Note, by change of variable, you're making sense out of the question in a solvable way, how the villagers know to leave, is an intepreted form of the question you're solving. However, although the changing of the question is natural, you're making a default assumption that villagers are following their command from the prophet to leave when they know. Subtle, but worthy to take note.

From the assumptions, you can further investigate that the people who leave are the people with white dots, and also the other way around. (people leave <=> people have white dot) So how many people leave? Can it be ANY "numer"? No, it has to be a positive integer, meaning that it's > 0 but < less the number of people in the village. You cant have 1000 people leave if the village only has 999. There is yet another assumption constructed from the information given, prophet said that there's at least 1 (ie. >= 1 ie > 0 if variable is positive integer, and it is from above)

It is hard reasonably solve or conclue that it's (0 + k) or (# of people in village - k)
So let's test the extreme values, maybe EVERYONE have the dots and they all leave? Let's look at the information again, they can ONLY leave if they know for sure, so what happens on the 3rd day that didnt happen on 1st and 2nd day? If they can't communicate, there's no way to exhaust any possibilities at all...so that means that on the 1st, 2nd, 3rd, 4th....day the same number of people leave, and from assumption above, the number of people who leave are the number of people with white dots, so in other words, NOBODY has white dots, and we have a contradiction, the range is actually from 0 to x where x is the number of people n the village, but by sqeeuze theorem, x is actually 0, so you could also justify that perhaps there's simply NOBODY in the villager, so thus no one has the dots.

Sie

Your stating that either no people were in the village or no people had dots?

Your question states:

How did these villagers know to leave?

Which to me would imply that atleast one person left......?
And with it being plural I would assume it meant more than one?

Thou to assume only ever makes an 'ass out u and me'

(Thats not implying anyone is an ass just a phrase i heard)

bighornsheep

Sie wrote:

Your question states:

How did these villagers know to leave?

Which to me would imply that atleast one person left......?

Actually, this is not my question, read the original post, I was simply explaining MY answer which is supposedly acceptable. Your explaination of the implication is the basis of the formal proof. You assume that perhaps there is one or more..but you realize that this can not work..either there is none, or it is everybody, but it can not be everybody because it's a closed system, so therefore it must be none, but none what? there are no candidates for having white dots? or nobody has white dots?

http://en.wikipedia.org/wiki/Contradiction#Proof_by_contradiction

Sie

I wasnt implying it was your question, i guess the question would have been a better wording for it.

Maybe its just me reading it wrong., I still think for it to be noone the question should not read 'How did these villagers know to leave".

However if it is not no one then I dont know what the answer is.

However looking at the question again the prophet states that atleast one will have a dot. This then implys atleast one person had a dot and atleast one person then left if the correct number of people with dots left.

If only one person lived in the village he would have left on the first morning knowing it must have been him pointing to there being more than one person in the village.

So thios shows that there is more than one person in the village and atleast one had a dot.

Hmm....

Mishra

I got it right! sweet

bighornsheep

Sie wrote:

However looking at the question again the prophet states that atleast one will have a dot. This then implys atleast one person had a dot and atleast one person then left if the correct number of people with dots left.

No, that's not the correct understanding of the implication, your understanding and phrasing of the implication is assumming that the words of the prophet is true. It this case, by construction of the proof by contradiction, his/her words as a prophet is not true.

The construction is as follows:
a=at least 1 person has a dot
b=person with dot leaves

a => b
b is true, but a isnt.

Sie

sprkymrk wrote:

If what a prophet says does not come to pass, he's a false prophet.

In that understanding Sprkymrk was right.

What we dont know is what the answers - either right or wrong show for each person. Different answers can be taken in different ways and different questions can be interpretted in different ways.

I dont believe in situations like this you can be 100% wrong in your answer whatever you say aslong as you can justify and explain your answer.

sprkymrk

bighornsheep wrote:

Sie wrote:

However looking at the question again the prophet states that atleast one will have a dot. This then implys atleast one person had a dot and atleast one person then left if the correct number of people with dots left.

No, that's not the correct understanding of the implication, your understanding and phrasing of the implication is assumming that the words of the prophet is true.

Then if we can't assume that the information given to us in the scenario is true, there is no correct way at all to answer the question. For even in your answers/explanations you are making assumptions as well.

Assumption #1 - There is a village.
Assumption #2 - There is a hill.
Assumption #3 - There was a prophet.
Assumption #4 - He spoke to the villagers.
Assumption #5 - There were villagers.
Assumption #6 - They did not communicate with each other.
Assumption #7 - On the first morning no one left.
Assumption #8 - On the second morning no one left.
Assumption #9 - On the third morning some villagers left.
etc., etc., ad nauseum.

So if we cannot assume that the scenario presented us was indeed factual and contained the necessary information in order to solve the puzzle, any and all answers could be correct by simply stating that we arrived at our answer by changing pieces of the scenario until our answer became correct. The tail wagging the dog.

How did these villagers know to leave?

My answer then is that they knew to leave because they told one another they had white dots. I simply choose NOT to assume that they did NOT communicate with each other.

mwgood

bighornsheep wrote:

...one night a prophet comes and tells the villagers...

Hmm. For the prophet to "tell" the villagers - 2 or more must actually exist. Otherwise, there is no telling and there are no villagers.

plettner

My answer is (and I'm sticking by it) that there were only three villagers. Two villagers on the first day saw that one had a dot and knew they did not need to leave. The villager with the dot was unable to confirm he had a dot.

On the second day, one villager without a dot saw two villagers with dots and knew he did not need to leave. Unable to communicate with the other 2, they remained.

On the third day the final villager saw the other 2 still had dots and knew he was to expect a dot. Each of the other villagers realsied they all dots and left.

bighornsheep

wow...very interesting array of answers....

About the list of assumptions, with the exception of 3 and 4, the rest are asserted statements that could be true or false but baring no effect on the construction of the proof.

3 and 4 are certainly assumed because it is part of constructing that the prophet's words are not true, and none of the villagers have white dots.

Anyway, this was sort of for fun for the Friday boredom...if we're all clashing about the answer or whether there is an answer, I think it will be circular, because I dont know what the model answer is.

RTmarc

plettner wrote:

My answer is (and I'm sticking by it) that there were only three villagers. Two villagers on the first day saw that one had a dot and knew they did not need to leave. The villager with the dot was unable to confirm he had a dot.

On the second day, one villager without a dot saw two villagers with dots and knew he did not need to leave. Unable to communicate with the other 2, they remained.

On the third day the final villager saw the other 2 still had dots and knew he was to expect a dot. Each of the other villagers realsied they all dots and left.

I agree.

mrhaun03

If there are no villagers, the my question is who the hell was the prophet talking to assuming there actually is a prophet. I say the prophet was smoking opium and got lost.

sprkymrk

bighornsheep wrote:

About the list of assumptions, with the exception of 3 and 4, the rest are asserted statements that could be true or false but baring no effect on the construction of the proof.

3 and 4 are certainly assumed because it is part of constructing that the prophet's words are not true, and none of the villagers have white dots.

My point was that you told another poster he shouldn't have assumed what the prophet said was true. I assert that we had to assume the entire scenario was true in order to come up with a correct answer. If we were not supposed to assume that what the prophet said was true, how can someone construct a correct response?

If I told you I had 10 bananas and ate 4, then asked you how many I had left, you would say 6. But wait, you ASSUMED I really ate 4 bananas, which is not the case. I only ate 2, so I had 8 left.

In all, I agree with mrhaun03:

If there are no villagers, the my question is who the hell was the prophet talking to assuming there actually is a prophet.

bighornsheep

I agree, your bananas example is an example of modus ponens, in a similar sense, this question is likewise solvable.

Sie wrote:

However looking at the question again the prophet states that atleast one will have a dot. This then implys atleast one person had a dot and atleast one person then left if the correct number of people with dots left.

I was pointing out the fact Sie didnt word the implication correctly, the prophet stating that there is at least one person with white dot has no implication on there being at least one person had a dot, nor how many people left. The implication made is based on assumption that the prophet said a true statement, which he didnt.

I dont think I want to go on explaining my response anymore, if you really want to know how I know the answer, try and read my explaination again, or send me a PM, the bottom line is, this is a classic example of tautology, and the answer is, no body in the village (ie. none of the villagers) have white dots. You dont know anything beyond this, you dont know if there was a village, and you dont know how many villagers there are...