P is for Programming

Google Interview Questions and Answers

December 1, 2010

I came across a very interesting article this morning regarding common Google Interview questions.  While I don’t plan on working for Google (not saying I wouldn’t like to – I just don’t think I’ve got the kind of experience they’re after) I do enjoy challenging interview questions and I thought I would see how I fare with them.

I tried to do the questions without resorting to Google (no pun intended), so if my answers seem idiotic keep that in mind.  You’ll notice that I only looked at the Software Engineer questions.

So without further ado…

The questions

Why are manhole covers round?

I’ve heard this one before.  In fact, this is such a common interview question that I’m pretty sure this never gets asked.  Manhole covers are round for 2 reasons – so that the cover can’t actually fall into the manhole and so that they’re easier to move (roll them).

What is the difference between a mutex and a semaphore?  Which one would you use to protect access to an increment operation?

Both mutexes and semaphores are used to control access to a shared resource – most often in multithreading scenarios.  A mutex is used when only one thread or process is allowed to access a resource and a semaphore is used when only a certain set limit of threads or processes can access the shared resource.  Essentially a mutex is a semaphore where the limit is set to 1.

Which one would I use to protect access to an increment operation?  Well, if I’m using C# I would say neither – just use Interlocked.Increment – but in the general scenario I would use a mutex.

A man pushed his car to a hotel and lost his fortune.  What happened?

He lost an epic game of Monopoly.  (Heard this one before I think)

Explain the significance of “dead beef”.

I think there might be some cultural difference that makes this question more difficult to me than it should be – I’ve never heard of “dead beef”.  If I had to venture a guess I would say that it’s similar to a sunk cost – something that is done and cannot be changed.

Write a C program which measures the speed of a context switch on a UNIX/Linux system.

Finally, some code!  I’ve never attempted something like this before, so I’m fairly confident I’m going to fail miserably – but that’s half the challenge in my opinion.  I’m not going to use C (I haven’t done C programming in almost 5 years) – I’ll stick with C#.

I guess there are 2 challenges to measuring a context switch – performing a context switch and measuring the time it took.  I guess the easiest way to perform a context switch would be to use a lock and simply have 2 threads constantly loop over the lock.  The easiest way to measure it would be to use the Stopwatch class.  The challenge here would be to try and minimize the overhead with the lock and the actual measurement with the Stopwatch.  As I said – I think I’ve got this completely wrong but I’ll give it a go.

static void Main(string[] args)
{
    new Thread(ThreadCall).Start();
    ThreadCall();

    Console.WriteLine("Ticks per second: {0}", Stopwatch.Frequency);
    Console.WriteLine("Average ticks per context switch: {0}", times.Average());
    Console.ReadLine();
}

private static readonly object @lock = new object();
private static IList<long> times = new List<long>();
private static Stopwatch stopwatch = null;

private static void ThreadCall()
{
    while (true)
    {
        lock (@lock)
        {
            if (stopwatch == null)
            {
                if (times.Count > 1000000)
                {
                    break;
                }
                stopwatch = Stopwatch.StartNew();
            }
            else
            {
                times.Add(stopwatch.ElapsedTicks);
                stopwatch = null;
            }
        }
    }
}

Well, it measures something which is a good start.  We actually avoid the overhead of instantiating the stopwatch since the actual measurement will only run between the instantiation of the stopwatch and where we add the measurement to the list.  There is the obvious overhead of the null check.

Running this in release mode gave the following output:

Like I said – it measures something, but I don’t think it’s the correct answer.  If this is correct my cpu can do about 460 000 context switches per second.

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

I think this is probably my favourite question so far.  The question doesn’t really state how random the result should be, but I guess the more random it is the better.  I’m going to try the implementation in C# again, although if I’m feeling up for it I might do a Ruby implementation later on.

public class Randomizer
{
    private Random random = new Random();

    public int GivenFunction()
    {
        return random.Next(1, 6);
    }

    public int MagicFunction()
    {
        var bigRandom = GivenFunction() * 100000
            + GivenFunction() * 10000
            + GivenFunction() * 1000
            + GivenFunction() * 100
            + GivenFunction() * 10
            + GivenFunction();

        return (bigRandom % 7) + 1;
    }
}

That’s easy enough – but how random will the results be.  To test it, I ran both the ‘given function’ and my ‘magic function’ a million times and counted the results.  So I pretty much counted the number of 1’s, 2’s, 3’s all the way to 5 for the given function and 7 for the other function.  These are the results:

Which is actually very.. random!  I’m quite impressed with the results given my rather naive implementation.  This could obviously be optimized.

This is about all I can handle for now, I might try some more of the questions in a future post.  Happy coding.

Tags: C#