When A ‘Mount Fuji’ Question Is Not Really A ‘Mount Fuji’ Question (Are You As Smart As You Think You Are)

Mount FujiMany people hate 'Mount Fuji' style interview questions. Questions such as:

"How many barbers are there in your home town?"

or

"How would you move Mount Fuji?"

That last one being the most well known of these types of questions and the one from which the rest get their name. These questions were initially popularized by Microsoft, but many of the most well-known tech companies have used them since. They have recently fallen a bit out of favour, but you're still likely to come across some if you do few tech interviews here and there.

There is a good reason why many people don't like these types of questions. Most of the time, they don't really have a good answer. The question is designed to put a person under pressure (when they can't immediately see a way to tackle the problem) and see how they handle it, as well as see if they can come up with a creative solution on the spot. Some developers tend to enjoy that kind of challenge, others seem to loath it which is why opinions about these questions are highly polarised. While I personally don't think these questions are the be-all-end-all, I do believe they have their value, but that is not what I want to talk about.

You see the people who hate these questions, hate them with a passion. Whenever an interview contains a 'Mount Fuji' or two and people do badly, they know exactly where to cast the blame. "It was all because of the stupid Mount Fuji questions. I was never good at those, plus I wouldn't want to work for a company that would ask them anyway." That's the excuse you give to yourself. Makes you feel better about failing – which is actually not a bad rationalisation as far as rationalisations go. But, there is an issue with this thinking because sometimes, a question that sounds like a 'Mount Fuji' question isn't really one at all and with all the hate we direct towards them we might end up missing it completely. So, what excuse do we give ourselves then, hmmm :)?

What I want to do is present a couple of these 'Non-Mount Fuji' questions here. While they might seem like one of 'those' at first, they are actually very reasonable questions, relevant, with concrete solutions. In my opinion, very decent interview fodder as well, but you're likely to fail them just as badly as any 'Mount Fuji' problem if you haven't practiced, so let's have a look.

Here is the first:

There is a village full of people. One day the priest gathers all the villagers together and declares that their God has told him that some among the villagers are sinners. All sinners will be marked with a sign on their forehead so that all other people will be able to see if a person is a sinner or not, but noone will know if there is a mark on their own forehead. Furthermore, the mark will not be visible in the mirror and one person is forbidden from telling another if they are a sinner. The villagers must work out which among them are sinners at which point all sinners are to leave the village. The village has been given one week and if at the end of the week, there are still sinners present, the whole village will be destroyed.

The villagers go about their own business during the day, however the whole village gathers in the square at the end of every day so that everyone can see if there are still any sinners left among them. After the third such gathering all the sinners pack up their stuff and leave the village.

How many sinners were there? How did you arrive at that number?

This is a deductive reasoning question. We tend to use this kind of reasoning all the time when writing software, so the question is highly relevant to the software development profession. This question has many different forms and is pretty common, so you may have heard it before. If you have you should be able to answer it easily right :)?

Here is the second:

You are one of several recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:

You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.

I have setup a "switch room" which contains a light switch, which is either on or off. The switch is not connected to anything.

Every now and then, I will select one prisoner at random to enter the "switch room". This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.

Each prisoner will visit the "switch room" arbitrarily often. More precisely, for any N, eventually each of you will visit the "switch room" at least N times.

At any time, any of you may declare: "we have all visited the 'switch room' at least once". If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!

  1. Devise a winning strategy when you know that the initial state of the switch is off.
  2. Devise a winning strategy when you do not know whether the initial state of the switch is on or off.

This is a distributed coordination problem. The reasoning used to solve this one is relevant when it comes to both distributed computing and concurrency. Infact, I 'stole' this question from Chapter 1 of the "The Art of Multiprocessor Programming", which is a great book I've been browsing recently (it really is a very interesting book and I will likely be going through it in a lot more detail, don't worry though, you'll read about it right here when that happens :)). In my opinion this is an even better question than the last, it feels more 'computery' for whatever reason. More than that, once you've worked it out, the solution can pretty easily be expressed in code to validate your reasoning (which is exactly what I did). Infact, with a little bit of creative thinking, even the first question can be validated through some code. If you can express something in code it's a winner as far as I am concerned.

So What Do We Do With These?

Brain

What I want you to do is use this as an opportunity to practice. It doesn't really even matter if you're likely to ever get this kind of question in an interview; these are good questions to give the old programming brain a bit of a workout. Not only is this an opportunity to problem-solve, but it can also be an opportunity to write some quick, interesting code. After going through this exercise, if you ever do see these kinds of questions in an interview, you'll hopefully be able to distinguish them from the 'hated Mount Fuji' ones :).

So, get your thinking caps on and try to solve these questions – then post your solutions in the comments below. The first person to get everything right gets a prize, actually I lie, there is no prize, but apparently incentives don't work anyway, so it doesn't matter. What you will get is a decent mental workout and the satisfaction of solving an interesting problem. Don't worry if you can't get it though, you'll get better with practice as long as you give it a go. Anyway, I won't leave you in the lurch, I'll post my solutions to both of those questions in a few days, including the code I wrote to validate the second one (I might even write some code for the first one if I get time). If you're really brave, then also post how long it took you to work out the answer (it doesn't really matter, getting these right at all would be a very decent effort, but if you want to show everyone how much of a genius you really are, this is your chance :)). I am really looking forward to seeing what you come up with.

Images by Molas and "lapolab"

  • root

    I think the second problem has a solution of the following form (not sure if this is the best way to handle it but still):
    1. Everyone enters the room but leaves the switch in the ‘off’ position. They count the times they have entered the room, and when they reach N, they will put the switch to “ON”. If anyone find the switch on “ON”, they declare.
    2. I suppose they could just count the times they enter the room, and when they hit N, they leave (so they have no use of the switch in this case, because everyone would have to hit N).

    I suppose that the problem was actually saying that “for each N visits, each of you would have visited the room at least one time” , not “N times” because that would be impossible.
    Or maybe I misunderstood.

    About the first problem, I’m not sure I get the constraints, because it seems to me that people would be able to tell the sinners from the first night (for instance one person could check everybody and make a list of the sinners, or they could pair up and check each other…)

    • http://www.skorks.com Alan Skorkin

      I think you misunderstood the problem a little bit the whole thing about N was basically to say that every prisoner will enter the room at some point and potentially more than once, it is probably easier to ignore the N all together, looking at it now, it probably confuses the problem a little bit.

      For the first problem, you missed the constraint that noone can tell another person if that person is a sinner or not, so there is no way for anyone to find out if they are a sinner unless they are able to deduce it somehow.

      • Victor

        Ah, well you have to make a few things clearer; it was not clear from the problem that one could not tell another if they were *not* a sinner, only that they could not tell if they *were* a sinner…

        Also, for the result, do you expect a hard number? like 5 or 2 or a percentage? Or is that a trick question?

        • Victor

          Ah, I obviously didn’t read further :) Don’t even bother answering my question, a couple of people have already provided the right solution!

        • Victor

          PSPS

          I guess the answer is: it doesn’t matter?

  • http://geographika.co.uk geographika

    “Furthermore, the mark will not be visible in the mirror and one person is forbidden from telling another if they are a sinner. ”

    Can a villager tell another villager they aren’t a sinner?

    • http://www.skorks.com Alan Skorkin

      No they can not.

  • root

    Ok, I just wrote a long comment answering the second question, and when I hit the “Submit” button, I got a big nice 404 error,
    So to be short:
    - I suppose the text of the problem meant “when the total number of visits hits N, everyone has visited at least once” , because the way it looks now “for N visits, everyone visited the room N times” means everyone visited the room together
    - for the second question, part 1: each visitor visits the room and doesn’t touch the switch. they keep count of the number of visits to the room. the first one to make N visits turns the switch to ‘ON’. The following visitors can see that the switch is “ON” and make the claim to leave.
    - part 2: each one counts to N visits and then leaves the room, regardless of the switch

    for the first question, it’s not really clear to me what are the constraints, because they could just do it in the first night (for instance one person could check everybody, or they could check each other in pairs…)

    • http://www.skorks.com Alan Skorkin

      Sorry about that 404, I really need to consider moving to some better hosting. It’s less about the money and more about finding the time to do all the leg work of actually finding a decent host and then installing all the relevant bits (LAMP stack etc), then moving the blog over, making sure everything still works. I am hoping if I moan long enough, some hosting company will come along and help me out by doing it all for me :). Anyways, sorry about that little bitch-session.

      As I said in response to your first comment, it is probably better to ignore the whole N think all together it really does make it confusing. I should have taken it out and just said, that any prisoner can visit the room any number of times and in any order, but all prisoners are guaranteed to visit eventually.

    • sunny

      u must be a bad developer….since you didnt save long comment before submit, is that how you treat your code also….bad boy

  • http://softwareramblings.com Stephen Doyle

    My solution to the prisoner problem:
    - Group elects a leader. Leader is responsible for making the “we have all visited the switch room” declaration.
    - Leader will turn switch off if it is on. Each time he/she switches it off, he/she increments a count. When count is the same a the number of prisoners (assuming initial switch state is off) or greater than the number of prisoners (assuming initial switch state is on) then all prisoners will have visited the room.
    - All other prisoners will turn the switch on if it is off. They will only do this once. All other times they visit the room they do not alter the state of the switch.

    Haven’t figured out how to handle an unknown initial switch state yet.

    • http://www.skorks.com Alan Skorkin

      Hey Stephen,

      That’s correct, electing the leader is the thing to do, this would usually be the case in a problem involving multiple machines (distributed coordination). It is a lot easier when one machine is the master and the others are slaves (leader and followers), which is what makes this problem relevant in my opinion. The second part is solved along similar lines, some of the people in the comments below have the right idea.

    • malymato

      My solution to problem when the initial state of switch is not known:

      1. Every prisoner can turn the switch only once – when visiting the room for the first time
      2. The first one who enters the room becomes a “counter”, permanently watching for the change of the state of the switcher, turning switch for the first time
      3. Everyone else who enters the room turns the switch
      4. When the counter = number of prisoners, every prisoner has visited the room

  • nickels

    I would hire the person who told me flat out,
    “You’re not going to move Mt. Fuji. Its not going to happen”
    Because at the end of the day being realistic about a problem and communicating realistic boundaries is as important as blowing sunshine upwards.
    I’ve seen some spectacular failures and endless schedule delays from people not having the guts to state reality or management failing to listen to reality.

    • http://www.skorks.com Alan Skorkin

      That would be a decent initial answer, but the interviewer would likely then ask you ignore whether it is possible or not and describe how you would do it if you had to. Think of it this way, if someone gives you a business requirement which you know is impossible, but you need to do your due diligence anyway if only to be able to point at all the things you did try and how unsuccessful they were. I’ve had to do this more than once in my work.

      • nickels

        Thats a CYA strategy, not a bad idea, but leads to trouble. Better to stick to one’s guns if you really believe it, imho.

  • http://www.dan-menard.com Dan M

    First and foremost: Thanks for posting these! My brain appreciates the workout. Now, on to my results:

    I can’t solve the first problem. There’s something about it that I’m totally blind to, and after staring blankly at it for about 10 minutes with no progress, I’ve given up :)

    The second problem, however, took me about 25 minutes to solve. Here is my solution:

    For part 1, where the switch is known to start at off, the group chooses one “leader” during the initial meeting, and that leader makes a mental note of how many prisoners there are in total, including himself. To keep nomenclature simple, let’s call the other prisoners “followers”.

    When a follower enters the switch room, he will do nothing if the switch is off. If the switch is on, the follower will switch it off the first time only; any subsequent visit where the switch is on, he’ll leave it on.

    Whenever the leader walks into the switch room, he will do nothing if the switch is on. If the switch is off, he will flip it on, and keep track of how many times he has done this. Once he has flipped the switch on X times, where X is the total number of prisoners including himself, he can safely alert the warden that everyone has visited the room.

    This works because it allows the leader to keep a count of how many unique visits there have been to the room, since each follower will only take action one time, and never before the leader has started the count by flipping the switch on for the first time.

    For part 2, the plan is very similar except for two changes:

    First, instead of only flipping the switch from on to off once, each of the followers flips the switch from on to off twice before never touching it again.

    Second, instead of declaring victory after X flips, where X is the total number of prisoners, the leader waits until he has flipped the switch from off to on 2X-1 times.

    This works because there can only be up to 1 on-to-off flips before the leader’s first visit. If there is a pre-leader flip, the leader will reach 2X-1 flips after all prisoners have flipped the switch exactly twice. In the case where there is not a pre-leader flip, the leader will reach 2X-1 flips when all the followers have flipped the switch exactly twice, except for one follower who has flipped the switch exactly once.

    I’m curious to know if there are more efficient solutions than mine, and if there is a way to do it without a leader. Also, my plan will fall apart if any of the prisoners makes an error, maliciously interferes with the plan, or dies. Is there an alternate solution that has any tolerance for failure?

    • http://www.skorks.com Alan Skorkin

      Hi Dan,

      I am glad you found these interesting. The thing to do with the first one, is make some assumptions with the most specific case of the problem. If there is only one sinner, will they be able to work it out on their own. After you get that one, what would happen if there were 2 sinners. After that you can pretty much generalise and come up with a solution.

      Your solution to problem 2 is correct, both parts. I came up with these exact solutions the first time around as well, I do believe there is a more efficient way of doing the second one, but I would like to validate it with some code before I say anything. It will likely be in my post which will solve both of these problems.

  • Julian Birch

    At the risk of looking extremely stupid:

    If there was one sinner, he’d be able to figure it out on the first day.
    So, if everyone comes back on the second day, there’s got to be more than one.
    If you were a sinner, and could see one other on the second day, you’d know there was exactly two and would leave.
    Extension of this reasoning leads me to conclude the answer is 3. Annoyingly, I guessed the answer, but spent several minutes convincing myself of it.

    2)

    Split the prisoners into two groups. Call all but one signallers, the other is the monitor.
    Signaller Strategy: If I’ve never switched the light on, and it’s off, switch it on. Otherwise leave it alone.
    Monitor Strategy: Always switch the light off. Keep count of how many times you’ve seen the light on. When that is the number of signallers, inform the warden.

    Wasted five to ten minutes trying to come up with a symmetric solution, it was pretty obvious once I let go of that assumption.

    • http://www.skorks.com Alan Skorkin

      Hey Julian,

      Your reasoning is correct, this is exactly the way to do it. Your solution to the second one is also correct. I also wasted about 5 minutes trying to think of a solution where any of the prisoners can declare :).

      • Thomas Eyde

        The whole reasoning on the sinner issue seems to be dependent on the sinners knowing they are in fact sinners. But nothing in the problem statement says that. Anyway, if a sinner knows he is one, he also knows he must leave town. Meeting up at the gathering is not necessary, the sinner count is still unknown and it doesn’t matter if all left town on the third or any other day.

        So what did I miss?

    • Andre

      I tought the light switch wasn’t connected to anything.

  • Tom Theisen

    This is highly relevant to me because i have an interview tomorrow.

    Question 1) I think the answer is 3. If there were only 1 sinner, he would look around, see no one else marked, and realize he was the sinner on the first day. Generally, if it has been n days, all the sinners will simultaneously realize they are sinners. Because when day n+1 comes, if a villager sees only n sinners, he will then know he is also one. The same process will be occurring with all the other sinners simultaneously.

    Question 2) Assuming a known off starting position, Prisoner A switches it to on, and Prisoner B declares the end when he sees the switch is on. Without that assumption, the best I can do is say that each prisoner should switch the switch each time they see it, and declare the end when they return to find it changed. This is vulnerable to a pathological case where each prisoner visits an even number of consecutive times though. Assuming the choice of prisoner is really random though, the probability this continuing approaches zero.

    I think I’ve spent 13 minutes on these, counting the time to type them.

    • http://www.skorks.com Alan Skorkin

      Hey Tom,

      Your answer to the first one is correct, but the second one is not quite right, you can have a look at some of the other comments which get both parts of that question correct, or alternatively, I will post my solutions in a couple of days.

      • Thomas Eyde

        I still don’t understand. It’s not given that the sinner knows he is one. And as all other people can see the mark, the sinner need more information just seeing other sinners.

  • Bananas

    1. Everyone leaves…

    The last sinner in the village either thinks all the sinners are gone, in which case everyone else leaves, and then so does he (if he realizes he’s a sinner). Or he thinks he’s a sinner, in which case he leaves.

    2.1 One person is allowed to turn the light off, you are only allowed to turn the light on once if the light is off when you go there.
    Whomever turns the light off counts the number of times it was on.
    2.2 idk

    • http://www.skorks.com Alan Skorkin

      Your answer to the first one is not quite right. Part 1 of the second one is correct though.

  • Steven

    I think this is correct. Haven’t tested it:
    All prisoners except one are ‘up-flippers’: if (switch_is_off && toggle_count (prisoner_count – 1)*2-1) declare_all_visited().

    • http://www.skorks.com Alan Skorkin

      That’s basically it yeah.

  • Steven

    For the unknown initial position prisoner problem: All prisoners except one are ‘up-flippers’: if (switch_is_off && toggle_count is less than 2) {toggle(on). ++toggle_count.}
    One prisoner is a ‘down-flipper’: if(switch_is_on) {toggle(off). ++visitor_count.} if(visitor_count is greater than (prisoner_count – 1)*2-1) declare_all_visited().

    Since the initial position of the switch can cause an off-by-one error, we ask each up-flipper to toggle twice. This assures that each prisoner has visited at least once.

    • http://www.skorks.com Alan Skorkin

      You’re also right about this one :)

  • Kemal

    ###########
    Problem 1:
    ###########
    -Answer: Three sinners.

    -Time: The solution took me one minute, but I’ve seen variations of this
    problem before.

    -Reasoning: If there was one sinner, he would see that no other people are sinners, and leave immediately. If there are N sinners, each sees N-1 sinners at the first meeting. Each waits until the (N-1)th meeting, to see if they all leave. When they don’t, each sinner realizes that they themselves are the Nth sinner. So, after the Nth meeting, they and all the other N-1 sinners leave.

    ############
    Problem two:
    ############
    -Time: about 30 minutes

    -Solutions:

    Case 1: the switch starts in the off state.
    ————————————————–
    Say there are N men. They designate one man to be the census taker. He initializes a count at 0.

    Every time a man goes into the room:
    -If he is NOT the census taker: if the switch is off, he turns it on. After his first visit, he never toggles the switch again.
    -If he is the census taker: if the switch is off, he turns it on and adds 1 to his count. If his count is N, he goes to the warden and demands release.

    This solution works because each time the census taker finds the switch off, he knows there has been a new visitor (starting with himself).

    Case 2: the switch starting state is unknown.
    ——————————————————
    Same rules as Case 1, but with two changes:
    -Non-census-takers toggle from on->off twice, not once.
    -The designated census taker demands freedom when his count reaches 2*N-2

    To see why this works, consider the two possible starting states:

    1. The switch starting state is “off”. See “Case 1″, above. Stopping at N is sufficient, so stopping at 2*N-2 is also sufficient.

    2. The switch starting state is “on”. The first man to to toggle the switch to “off” will not be counted. Hence, only one of his toggles will be counted. Both toggles from each of the other N-2 non-census-takers will be counted. That is 2*(N-2) + 1 = 2*N – 3 toggles. Since the census taker also counts himself, that is 2*N – 2 toggles total. Once the count reaches this level, he knows that everyone has visited at least once; in fact, everyone except the first visitor has visited at least twice.

    • http://www.skorks.com Alan Skorkin

      You’re quite right on all counts, and very good job on the analysis of the second case of problem 2 (i.e. spotting 2N-2).

  • http://www.dan-menard.com Dan M

    Kemal, good catch on the second prisoner case being 2*N-2; I mistakenly assumed 2*N – 1, forgetting that the census-taker doesn’t need to count himself twice.

    Also, for the first problem, I assumed it was possible that there were no sinners. Without that assumption the problem makes a lot more sense :)

    • http://www.skorks.com Alan Skorkin

      Althought your solution would still work fine 2N-1, just not as efficient :). And you’re right, you definitely have to assume there is at least one sinner which is why their god must have started the whole problem in the first place :).

  • Alex

    For problem 1, everyone is saying 3, and basing it on the sinner seeing 2 other sinners, and at the end of 3 days, leaving.

    I don’t think this works.

    If the last sinner leaves at the end of day 3, because “I don’t see any more sinners, I must be the last one”, what’s to prevent a non-sinner from thinking the same thing on day 4? What’s to prevent the last one to leave (on day 3) from thinking he’s a non-sinner, and “the sinners have left, we’re all safe, hooray!” ?

    • http://www.skorks.com Alan Skorkin

      Hi Alex,

      This does work, because each sinner doesn’t leave at the end of every day, all sinners leave together at the end of the third day since that’s how long they needed to deduce that each one of them was a sinner based on the continued presence of the others.

      • Thomas Eyde

        You’re saying they need that long to deduce the answer, but how? If I am a sinner, I will in this case see two sinners every day. If I fail to recognize myself as a sinner, and no one tells me there are three sinners, how can we arrive at a solution?

        However, if I ask two sinner to count how many sinners they see, and they see the same number as me, then I know I am a sinner too. But we can all do that exercise on the first day, and the actual number can be anything.

        • Peeteriz

          It the ‘game’ is still going on in day three, then you know that there are more than two sinners on the island (otherwise they would have left yesterday).
          If you see only two sinners but know that there are more than two, then you have found out that you are a sinner as well.

          • http://student.johnpdaigle.com J. Paul Daigle

            The sinner question doesn’t really set the constraints clearly. The constraint isn’t that one villager can’t tell another villager about who is or isn’t a sinner, the constraint is that the villagers may not communicate any information at all about the number or identity of sinners except by leaving the village. The input information is that there is at least one sinner.

            If the villagers are allowed to count and communicate, then the problem could be solved on day one by dividing the villagers into groups of and having each villager communicate the number of sinners they see.

  • Caleb

    Answer one: everybody. Villagers aren’t very good logicians, so on the third night they crack under the pressure and split.

    Maybe I’m just rationalising my failure to deduce the correct answer (*sigh*), but in my experience the real challenge of working in a technical field has little to do with the actual ability to reason. Given enough time and energy, any logical problem that can be solved will be solved. Said in another way, a given set of postulates–taken together with the rules of inference–contains all possible consequences of these postulates. A proof just articulates an inevitable consequence of the givens.

    The truly difficult parts of working in a technical field are the human aspects of ambiguous situations and interpersonal relationships. A 30-page essay on why the content management system your boss chose to purchase is technically inferior will be ignored at best, and would probably antagonize your boss if it’s actually read. Technologically superior products are not guaranteed to achieve market penetration–I’m sure we’ve all used products that were better than the competition, but folded anyway. One recent example from my own experience is Lala.com

    And the examples pile up: it’s rarely possible to spend the time necessary to thoroughly research all available options before making a decision on whether or not to adopt the hot new scripting language of the moment. Your marketing staff won’t care that their decade-old contact management system is impossible to update and requires specialty hardware–it works for them and they don’t want to retrain on a new system.

    To me, these are the challenges. Especially because techies have to be thinking rationally and analytically about the project du jour while they’re engaged in the human aspect of business, such as selling the project to upper management.

    Take with a grain of salt because I’m not in the interviewer’s chair, but personality and charisma count for a lot in my book.

    • http://www.skorks.com Alan Skorkin

      Haha, I like your answer, regardless of its incorrectness :).

      I agree with everything you say, personality and communication skills definitely count for a lot in software, but I do believe that ability to reason is important as well especially in some of the more complex areas of software development (i.e. not business webapp development ).

  • rollingstone

    Kemal, dont you mean
    “-If he is the census taker: if the switch is ON, he turns it OFF and adds 1 to his count. If his count is N, he goes to the warden and demands release.”

  • kedi_xed

    To question one:
    ‘one person is forbidden from telling another if they are a sinner’

    As the villagers are gathered together, someone could simple state the rule that no-one talk to those with a mark on their head all day. If you haven’t been spoken to all day, then you must leave. This could possibly mean that all sinners have left by the second day, and that the number of sinners cannot be deteremined.

    However, if the statement above were to say:
    ‘one person is forbidden from indicating to another if they are a sinner’
    Then it would be a more difficult problem.

    • http://www.skorks.com Alan Skorkin

      It’s the second one, so it is the more difficult problem :), although you can still reason it out as many of the people in the comments above have done.

  • http://www.shaunrowland.com/ Shaun Rowland

    I only had time to think about problem 1, so here are my thoughts:

    The key here is that everyone knows that sinners will see N – 1 sinners and non-sinners will see N sinners. Villagers just need to figure out if they see the smaller number. When I approached this problem the first time, I came up with a quick solution to simply figure out how many sinners there were with any given random set of villagers and their random “sin status” using this information. I think this follows the rules in general – you have everyone count up the number of sinners they see and then share their totals. Those who have a total of N are non-sinners, while those with a total of N – 1 are sinners. There are only two possible values villagers will come up with when totaling the number of sinners they see, so you can figure out N and N – 1. I was pretty satisfied with this basic fact (though obvious), but it doesn’t solve the actual problem. We know that sinners packed up and left _after_ the third meeting. They did not just count things up like this at the first meeting, but instead waited it out like the villagers they are, unless I missed something about the rules. For example, what if there were 100 sinners? This would never work and the village would be destroyed. That didn’t happen, so they were lucky. I think they should have been destroyed for taking 3 meetings to figure this out though.

    Everyone can simply assume they’ve been counted as a sinner. Perhaps they are not all clear on their God’s rules :-) Therefore, they can assume they see N – 1 sinners, but maybe they see N sinners and were good (and will get Christmas presents or something). What to do? We know if someone sees no other sinners, he is the sinner. N = 1, and he sees N – 1. Because there is at least one sinner, that’s the only conclusion he can make. He leaves _before_ the first meeting. It took 3 meetings to figure this out in the inefficient villager “we hope there are fewer than 8 or so sinners or we’re dead” way. The sinners didn’t figure this out until after the 3rd meeting. This means it takes 3 days to realize they are a sinner:

    - If someone left before meeting 1, there was 1 sinner.
    - If someone left before meeting 2, there were 2 sinners.
    - If someone left before meeting 3, there were 3 sinners.
    - The sinners realize they are hosed on the 3rd meeting. They leave on day 4 after the 3rd meeting, just to spend some extra time with their more well behaved friends. Why did they almost bring such wrath?

    You can only figure out that you need to leave if meeting number M is N – 1. Of course, if N is 1, then you can leave before meeting (no meeting required).

    M = N – 1
    3 = N – 1
    N = 4

    I assume the first meeting is after they get the bad news which requires the formulation of an algorithm that’s almost surely bound to doom any village that I am familiar with. This seemed like a one by off problem to me anyway…

    • http://www.skorks.com Alan Skorkin

      Hi Shaun,

      Haha, that’s some awesome analysis :).

  • Lundy

    Why do they need three nights? If at the meeting, everyone counts how many sinners they see individually (if you can’t say it out loud, write it on a piece of ballot paper, and all numbers read out by the chief). Assuming you could remember your own number, you would immediately know if you are a sinner or not after the first night. If 10 villagers, 3 sinners, you would have 7 counts of 3, and 3 counts of 2. The 3 would leave. I can’t figure out why it would take them 3 nights?

    • http://www.skorks.com Alan Skorkin

      The villagers are not allowed to share their observations with other villagers in any way, which includes writing it on a piece of paper or reading it out loud.

  • TomP

    I may be thick, but I think the sinners problem does not have an iterative answer, but is simply a case of a solution existing if there is exactly one sinner, and no solution if there is more than one. The only case where a sinner gains information about their own state is when they see no other sinners.

    I do not see how the progression of time adds information to the problem space. If you start out with X sinners, any given villager will see either X or X-1 sinners, but without knowing how many sinners there are, a villager has no way to know whether they are a sinner or not, and the passage of an extra day does not add to the information a villager has.

    Please explain my error.

    • rix0r

      If there really were just X-1 sinners, the sinners would’ve left a day earlier. Hence, there cannot be X-1 sinners so there must be X sinners (and the observer must be one of them).

      The absence of reaction across a number of “decision points” is what extra information is added. It’s easiest if you count up from the bottom.

      1. It’s time for the first trial. Let’s say one person is seeing 0 sinners: since there must be at least one sinner, he is the one. He packs up and leaves.

      2. Now let’s say there are 2 sinners and it’s time for the second trial; two people both see 1 sinner. Since they know the other person is not alone, they know it must be both the guy they can see and themselves who are sinners. How do they know the other guy is not alone? Because if he were, he would’ve been able to deduce that on day 1 and left.

      3. And so on: on day 3, the 3 actual sinners would spot 2 other sinners and since there can’t be 2, there must be 3, etc.

      Of course, as soon as you have one sinning villager who can’t figure this out, you’re screwed :).

      • Thomas Eyde

        What if I see two sinners on day one and am the third one. How will an additional day or two help me? I can reason there has to be more than one, but nothing more. If there are more than one, no one will leave, and my observations will be the same on any day.

  • Pingback: Dew Drop – June 3, 2010 | Alvin Ashcraft's Morning Dew

  • wallygold

    I don’t know about the elegance of these solutions but here goes my attempt:

    a) (Start position off). Give only one person, A, the authority to turn the switch off. Everyone else turns the switch on the first chance they get and never again. A can keep count of how many times someone else turned it on.

    b) (Start position unknown). One person, A, switches the switch every time he goes into the room. All the other people turn the switch on the first time they find it off AFTER seeing the switch in two different positions. Every time A comes back to find it on after leaving if off he knows that someone he hasn’t counted has been in the room.

    Ok, now to go read the other comments. I came up with the first solution relatively quickly. I thought about the second actively for a while (can’t really say how long to be honest: maybe 10 minutes maybe 20 minutes) then I went to watch some tennis (Nadal vs Almagro). Two sets in that idea occurred to me.

  • David

    @TomP,

    Does this work as a fuller answer to the sinners problem?

    1) Suppose there is one sinner. On the first day, he will look around and see no other marks. He will therefore know he is the only sinner and leave. Assuming each villager is able to follow this logic, then if no-one has left after the first day, everyone can logically conclude that there are at least two sinners.

    2) Suppose there are two sinners. Each of those sinners will see exactly one other sinner, and if each has thought through Point 1, then on the second day each will (a) know that there have to be at least two sinners, and (b) only see be able to one other sinner, so each can conclude that they have to be a sinner, and by this logic both should leave. (On the first day, each sinner would wait, because of the possibility that the other sinner is the only sinner.) Conversely, if no-one has left after the second day, everyone can conclude that there are at least three sinners.

    3) Suppose there are 3 sinners. Each of those would see two other sinners. They would then know that there are either 2 or 3 sinners, depending on whether or they themself are a sinner. By the third day they would know that, because of Point 2 above, there can’t be only two sinners, so they would leave. Conversely, if no-one has left after the third day, everyone can conclude that there are at least four sinners.

    Since the sinners all leave on the third day, there are therefore 3 sinners.

    • http://www.shaunrowland.com/ Shaun Rowland

      I am confused by the 3 argument. The sinners don’t leave on the third day. They leave after the third meeting. The third meeting is at the end of the third day. The problem states that they leave after the third gathering. It seems to me that you are stating they leave after the second gathering. Your sinners don’t show up to the third gathering. The problem states that after they are told, they go about their business and meet at end of the day (the gathering) to see if they should leave following your logic, which I also agree with. After the third of said gatherings, they pack up and leave. There has to be 4 sinners they way I read this.

      • David

        Fair point. The question says ” the whole village gathers in the square at the end of every day so that everyone can see if there are still any sinners left among them”, so I should have referred to gatherings rather than days. Ie, they look around during the gathering, perform do their thinking, and leave at the end.

    • http://www.dan-menard.com Dan M

      Thank you for explaining this in detail. It finally makes sense to me :)

    • Thomas Eyde

      Ah, now I see. Thank you David. Well explained. And sorry, all, for my previous irritating comments.

      • http://www.skorks.com Alan Skorkin

        No worries, I am glad you sorted it out, there were some good comments to this post :).

        • Scott

          This IS a Mount Fuji problem. Why?

          Because this relies on people behaving rationally, logically, and for the interest of other people. All things we know people don’t do.

          We’ve already established that these people are sinners, and that they have to leave the village – the comfort of their lives – and for what alternative? Maybe they’ll die out there, so they may as well stay. Maybe they’ll decide that these rotten villagers deserve to be destroyed, especially that damn priest that damned them to be expelled from the village.

          Though, technically you’ve short-circuited that by saying the sinners DO in fact pack up and leave :)

    • http://www.joshcheek.com Josh

      Finally a decent answer, thank you.

      Also, I’d be incredibly insulted if anyone asked me a question like this in an interview.

  • David

    By the way, I hadn’t worked it out until after I saw the earlier solutions.

  • Peter

    I’m with TomP, I don’t see the logic in presenting the progression of 1, 2, 3 sinners.

    On day one, meeting one, N sinners see N-1 sinners. But they don’t know if they’re seeing N-1 or N, they have to assume one or the other.

    And the saints (non-sinners) see N sinners, but don’t know if they are actually seeing N-1 sinners or not, because no one can indicate in any way to anyone else their status as sinner.

    So what is it about meeting three that is different than meetings one and two that makes all the sinners leave? Why don’t all the saints leave, assuming they are the Nth sinner because they don’t know if they’re seeing N-1 or N sinners?

    I think most of the analysis so far is dependent on the progression from 1, 2, 3, and sinners leaving because they assume they’re sinners, while totally neglecting the saints who are just as likely to leave because they assume they’re sinners as well. And the progression from 1 to 2 to 3 isn’t valid, because we would start with N sinners at meeting one, not 1 sinner at meeting one, and 2 sinners at meeting two, etc.

    My idea for a solution is a toss-up between doing some sort of binary search by splitting the group successively smaller, or maybe because people can tell each other that they are saints (not sinners) through some loophole in 11th commandment “Thou shalt not tell the sinner if they are a sinner.”

    • aaron

      Another way to think about it:

      Sinners see N-1 sinners.
      Saints see N sinners.

      Someone starts counting 1, 2, 3… and when they get to the number of sinners you see, you must leave. Since N-1 < N, all the sinners will leave one step before all the saints would have.

      Rather than counting, they met at the square each day.

      This one stumped me because I was assuming the sinners were unreliable and might not leave on their count, etc. I also missed the part about there being at least one sinner. Hopefully in an interview that would have been clarified rather quickly.

      • Lulu

        The main thing is to identify what the quiz/question is about. In the case of the sinners, it’s obviously a test of deductive reasoning, like what the article has stated. Then you will know what to assume and what questions NOT to ask the interviewers. It will absolutely piss the interviewers off if you start bombarding them with irrelevant questions like “how would you know if everyone’s smart enough to figure it out? what if someone got sick and can’t attend the gathering? What if the sinners refuse to leave?”

        Also, it’s also important to note that the answer is not the most crucial part but how you work towards the answer. You can tell a lot about the interviewees in the process.

  • http://www.franciscosoto.net bobby

    For the first one:
    How about, the whole town picks one random dude from the crowd, and he sorts everyone depending on what he can see about them. Everyone know knows what he is, but do not know what they are, and he knows what everyone is, but not himself.

    At this point, he picks a guy from each group to represent it as a whole, and he asks one of these representatives, (let choose the sinner), to take his place and sort him out. At this point, the first one knows what he is because if he is in the same group as the third one, he’s not sinner, if he is in the group of the third one he knows he’s not a sinner, and now the one sorting also knows what he is, as he knows where he put the first one. If in the group of the third one, then he knows himself does not belong in that group, or he first one is in the contrary group to the third guy, the second knows he’s in the same group as the first.

    At this point, the three guys know what they are, and at least one of them is a sinner, so the whole town should follow the representative in his group, if he goes out of town, then they know they should go to.

    (It’s a bit of a mess to explain with words, not sure if I was clear)

  • http://www.franciscosoto.net bobby

    I was typing as I was thinking, so I repeated a few sentences and I can’t edit, I am sorry.

  • http://www.franciscosoto.net bobby

    And there are a few special cases in case everyone is a sinner or not sinner, etc. But these are easy to work out.

  • http://www.franciscosoto.net bobby

    And I just realized I answered the wrong question, I read the thing and assumed things. Feel free to not include my answer or these additional comments. !

  • Alex Yap

    I think the first question only works if the following condition is added: “No villager can communicate with another villager using any means.”
    If there is any communication, then information from the whole group can be used to instantly figure out who are the sinners. For example, here is a solution that works just as quickly regardless of the number of sinners:

    The village chief tells everyone, “as soon you see don’t see any more sinners, just break out and party”. Then he selects a random villager to just say if he sees odd or even number of sinners in the village. Everyone else can see if this randomly selected villager is a sinner. So the logic is:

    For everyone else:
    1. If the selected villager is NOT a sinner, and what you see does not match what he says, then you are a sinner. So you leave.
    2. If the selected villager is a sinner, and what you see matches what he says, then you are a sinner. So you leave.

    At this point, the selected villager may or may not be the only sinner left. If he sees everyone else starting to party, then he’s not a sinner. If everyone is standing still, he knows he’s the last sinner so he leaves.

  • Pingback: Ali Razeen » Blog Archive » The Introduction of Puzzles

  • Pingback: Ali Razeen » Blog Archive » Puzzle: The Village and Sinners

  • http://ertw.com/blog/ Sean

    It took me a while to follow the reasoning for the sinner question. What helped was setting an arbitrary number of villagers and then putting it all on a spreadsheet, including each person’s thoughts:

    https://spreadsheets.google.com/pub?key=0AvDAAxZ4Y8OedFZiVU1hdUdtZVgyclJ0V2xXd3NMUmc&hl=en&output=html

  • padua

    When asked a Microsoft interview question, refuse to answer.

    Then ask them “give me an example in english of a double-positive that is a negative”

    When they go blank, put your arms akimbo and say ” yeah-yeah” with a sneer.

  • Kane McGovern

    Can all of the villagers just commit a sin before the end of the week, then all leave at once? ;)

  • http://www.ghostmonk.com Nicholas

    Interestingly enough, the wording of the first question implies there must be 4 sinners. It’s a pedantic trick maybe, but because you say “some”, this implies more than 1.

    On the first day, if there were only 3 sinners, each sinner would assume there must only be 2 sinners, and that each of the other 2 sinners would see only one other and deduce that they are the second. Thus the 2 would pack up and leave in the same day. However, upon returning the second day, each of the three sinners would realize that there must be another, and that other is him/her.

    By extension this logic would continue to the 3rd day making 4 sinners in all.
    The wording of the problem is better if you say “At least 1 sinner”

  • Robert

    The real question is: do you really want to work for a company that has no freakin idea how to hire developers? If they are so bad that they waste your time with silly questions they looked up on the internet, then do you really want to spend the best part of the next year working for goofballs? If they’re that childish in the interview how do you think they’ll treat you once you’ve dropped your job and gone to them as your only source of income?

    • http://www.skorks.com Alan Skorkin

      Hi Robert,

      You’ve somewhat missed the points of the this post, puzzle question certainly can be useless, but in many cases they only appear to be so, deductive reasoning, concurrency, back of the envelope calculation are all skills that all developers need. Many questions that test for this sound like puzzle questions. I recommend you read my latest post, Here Is The Main Reason Why You Suck At Interviews there is a whole section about it in there.

  • Jose

    Hi!

    I think the answer for the first question is: all of them.

    Why? This is what happens:
    1- First day: everyone goes to the square. A person can see all of the people who are sinners, except him/herself.
    2- Second day: everyone goes to the square to see if the sinners have left. No sinner has left. Everyone assumes THEY’RE the sinner, so it’s best to leave for the sake of the village.
    3- Third day: there’s no one.

    Is that right?

    • Lulu

      No the question is only the sinners left, not everyone. LOL.

      This is how it works:

      Conditions: They could see everyone at the end of the day but they can’t communicate at all.
      Results: All and only sinners left on the 3rd day.

      The answer: There are 3 sinners.
      1. If there was only 1 sinner, he will see everyone else WITHOUT the mark and deduce that he’s the one and left on the first day.
      2. If there were 2 sinners, each of the sinners will see 1 mark among everyone but they are not sure if they carry the mark. They will know at the end of day one because with 1 mark, it will be case 1 and the person would have left on day 1. The fact that no one leaves on day 1 means 2 people saw 1 mark on other’s head.
      Then day 3 uses the same deduction: 3 sinners, each sees 2 marks and no one leaves on the first and second day.

      Possible question: It could more than 3 sinners, how would they know?
      Well, ‘coz each person can only have 1 mark and they can SEE EVERYONE ELSE.

  • wad

    I seriously don’t get the 2/b.

    Why does the initial state matters, after all? The very first prisoner would turn it off or on (depending which state the leader is counting). If he is not the leader, then he doesn’t even have to know that he was the first one or not, jut follow the standard rule. The leader has to know if he is the first one to avoid

  • Roland

    I realize I’m very late to this discussion, but wouldn’t a faster solution for the sinners problem be as follows (assuming that at least 1 person is NOT a sinner):

    At the first nightly meeting, each person writes down the number of sinners he/she sees and these counts are collected [by the priest perhaps]. The highest number recorded [N] will be the count of the number of sinners in the village, which corresponds to the count observed by all non-sinner. This number is announced by the priest and each person who had counted N-1 sinners will know to leave.

    This would accomplish the filtering on the 1st day without one villager telling another about the observed mark.

    Seems like this way of solving the problem results in an order of magnitude less complexity than the other published results.

    Also it would seem that since we are guessing at the method used by the villager, there is no way of identifying the number of sinners in the original problem as it was stated, as if they had followed this method, 1 day would have been sufficient. (perhaps they spent the extra time packing?)

    Or did I miss a constraint?

    Great post/comments btw!

  • Roland

    I realize I’m very late to this discussion, but wouldn’t a faster solution for the sinners problem be as follows:

    There are N villagers. At the first nightly meeting, each person writes down the number of sinners he/she sees and these counts are collected [by the priest perhaps].
    One of three scenarios may occur:

    *Scenario 1 (trivial): Each villager counts N-1 sinners. In that case all villagers are sinners and must leave on that day.

    *Scenario 2 (trivial): Each villager counts 0 sinners. There are no sinners in the village (The priest lied, which did not brand him a sinner however).

    *Scenario 3: Some villagers count X sinners and others count X+1 (where X<N). In this case, all villagers who only counted X are themselves sinners and will leave on that day.

    This would accomplish the filtering on the 1st day without one villager telling another [directly] about the observed mark.

    It seems like this way of solving the problem results in an order of magnitude less complexity than the other posted solutions.

    Lastly, it would seem that since we are guessing at the method used by the villager, there is no way of identifying the number of sinners in the original problem as it was stated, as if they had followed this method, 1 day would have been sufficient. (perhaps they spent the extra time packing?)

    Or did I miss a constraint?

    Great post/comments btw!

  • Taker of noncensus

    For problem 2, in your replies to a few comments you said that the N thing can be ignored. That is not true — the N thing is important.

    Suppose we only knew this: ‘Each prisoner will visit the “switch room” arbitrarily often.’ In such a case, the warden could arrange that the census taker will visit the switch room once at a time when it’s too early to answer, and never visit again. If the warden doesn’t know who the census taker is then the warden picks a bunch of people at random so the warden has a bunch of chances of winning instead of being sure of winning.

    We do need this: ‘More precisely, for any N, eventually each of you will visit the “switch room” at least N times.’ Now we are guaranteed that the census taker will eventually get the full count.

  • Bue

    Found a solution for the second question. (finally)
    “Devise a winning strategy when you know that the initial state of the switch is off.”
    Before they are locked up, they count how many people there is in the prison. Then they choose one person as a counter. Then everybody, except the counter, turn the switch on if it’s off and do nothing if it’s on. They can only turn on the switch once. The counter counts how many times he turns the lights off and when the count is the amount of people in the prison (besides himself), then he will declare that everybody have ben in the room at least once and win.

    “Devise a winning strategy when you do not know whether the initial state of the switch is on or off.”
    Using the same strategy here would result in a one man uncertainty. If the initial state is on, then the finish count would be the amount of people + 1 (excluding the counter). If the initial state is off, then finish count would be the amount of people (excluding the counter).
    This can be solved if everybody turn on the lights two times. Then the finish count would be the amount of people (excluding the count) times two.

    example with 3 people and 1 counter
    Case 1: The initial state is off. 3 people turn on the switch twice and the counter declares that everybody have been in the room on count 6.

    Case 2: The initial state is on (So the count starts at 1). 2 out of 3 flips the switch twice (so the current count is 5). Then counter can’t declare that everyone have been in the room before the last person enters the room and turn the switch on.

    Couldn’t solve the one with the sinners without assuming that they knew the amount of sinners though. It’s not forbidden to tell people that they are not sinners right?

    Well, I enjoyed the questions but I totally forgot about the rest of your post. *Bookmarked*

  • http://www.joshcheek.com Josh

    What if there were more sinners than days until destruction? What if one of the sinners wasn’t smart enough to figure this out? These are actually both riddles, not logic problems, because while they do have a correct answer, and while it is an algorithm, the algorithm is a trick that you pretty much have to have heard ahead of time, or do problems like this frequently, in order to figure it out.

    I’m with Robert, I think these interview questions reveal a disrespectful interviewer. Also I don’t really want to work at a place where my coworkers qualifications are that they happen to be good at riddles.

  • Pingback: Ali Razeen » The Introduction of Puzzles

  • Pingback: The Paltering Grounds - When A ‘Mount Fuji’ Question Is Not Really A ‘Mount Fuji’ Question (Are You As Smart As You Think You Are)

  • Frank

    1st problem:
    This could be like the basketball test.
    Since they cannot tell each other who is a sinner, they could segment the village into groups.
    ‘clean’ groups are resolved and the ‘unclean’ are combined and segmented again. rinse. repeat.
    Since the people in a group can only say if others in their groups are clean/unclean, they are not telling anyone they are sinners.
    You keep doing this until a group of sinners is left.

    2nd problem:
    One idea I have is that if you enter the room for the first time, you have to set the switch to ‘off’, if you enter it a second (or N) time, you have to set it to ‘on’ (or leave it at that setting).
    The idea is that someone that has not yet visited the room N times will ‘reset’ the count. When all have been there twice (or N), it would stay at ‘on’.
    But that would require everyone to have been sent there at least n times before people are sent there a n+1 time.
    Ok, no result but that is how I might approach it.

  • SteveD

    These questions are not “Mt Fuji” questions at all. They’re worse! With a Mt Fuji question, there is no way to know the real answer, if there even is one. The point (such as it is) is to see the thought processes of the answerer.

    However, the two questions you posted, are simply “Aha!” questions. Either you realize (or already heard) the trick to them, or you don’t. Once you know the trick, there’s not much additional work to do.