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?


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.