Many people hate 'Mount Fuji' style interview questions. Questions such as:
"How many barbers are there in your home town?"
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!
- Devise a winning strategy when you know that the initial state of the switch is off.
- 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?
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.