Software Engineering Interview Questions Part 2

There was also recently an article that was doing the rounds with the 20 most craziest interview questions, quoting allegedly real questions from interviews at places like Google, Facebook, Goldmans etc. Here are a few, along with my attempts to answer them..

Facebook: Twenty five racehorses, no stopwatch, five tracks.  Figure out the top three fastest horses in the fewest number of races.
This needs a few assumptions before we begin: 1) each track only races 5 horses, and races cant be started at the exact same time - preventing effectively just running all the horses at once; 2) horses run the lap in a consistent time (e.g. if horse A beats horse B in one race, and horse B then beats horse C, then A will also beat horse C)
  1. Race 5 races, each with 5 horses in it (so all horses have raced) (5 races)
  2.  Race 1 race with the winners of the first 5 races (6 races)
  3. Find the winner of race 6 and from that horse's original race take the horses that came second and third (2 horses); take the second place horse of race 6 plus the horse that came second in his original group (2 horses); take the third place horse of race 6 (1 horse) - Race these 5 horses, this will give the second and third fastest horses (we already know the number 1 fastest horse is the winner of race 6)
Total races: 7

Goldman Sachs: Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale. What’s the fewest number of times you have to use the scale to find the heavier ball?
Answer: 2
  1. Arbitrarily split the balls in to three piles, 3-3-2
  2. weigh the two sets of 3 balls (first weighing)
  3. If the two sets of three balance (weigh the same) then we know the heavier ball is one of the balls in the set of 2, so weigh those two (second weighing), and you will see immediately which is heavier
  4. If the two sets of three do not balance, then take the heavier set and weigh any two of those balls - if the first two balls you weigh are the same then you know the third ball in the set of 3 is the heaviest. If they do not weigh the same then you will immediately see the heaviest ball

Google: You are climbing a staircase. Each time you can either take one step or two. The staircase has n steps. In how many distinct ways can you climb the staircase?
The trick to this question, as with a lot of complex sounding questions(things that start with "there are 100 prisoners.." or "there is a village with 1,000 married couples") is to break "n" (or the number provided" to a much lower number.

In this case, lets start off with n=2 (we will skip n=1) - in this instance its easy to do the mental arithmetic to work out the number of permutations: it can be 1,1 or 2. So therefore there are 2 different permutations. Obviously, in this case, whilst n=2, permutations(lets call it x)=2, but its safe to assume n=x will not be consistent as n increases.

So let's increase n, this time, n=3. Again, simple mental arithmetic and we can work out possible permutations: 1,1,1;  1,2 and 2,1. So again there are 3 permutations (x=3).
We will continue our approach to see if we can see a pattern emerging.

n=4: possible permutations: 1,1,1,1;  2,2;  2,1,1;  1,2,1;  1,1,2, so x=5
n=5: possible permutations: 1,1,1,1,1;  2,2,1;  2,1,2;  1,2,2;  1,1,1,2;  1,1,2,1;  1,2,1,1;  2,1,1,1;  So x=8

We could continue this process untill we could see a pattern emerging, although as n increases, the number of permutations increases so might need a pencil and paper if you wanted to carry on. Fortunately, it seems to be heading in the direction of the Fibonnaci sequence! So to find the number of permutations for n steps we just need to find the nth position in the fibonnaci sequence (still not that simple!)

I have not validated that these answers are correct, but this is what I came up with! Leave a comment if you think I have done something wrong somewhere along the way.