This is a first attempt on a series with focus on solving commonly asked programmer interview questions, in this first episode we’ll do prime factorization.

Screencast

And yes, I’ve been made aware of that 21 is not a prime, not easy to code and talk at the same time. :-)

What the interviewers are looking for

It’s not all about the final solution, the interviewers are interested in how you break down larger problems into smaller more comprehensible ones. How you go about solving problems with logical thinking. If the interviewers are any good they’ll try to make you feel comfortable and develop a solution together if you get stuck, the idea is not to grill someone at the whiteboard.

Breaking it down

There’s three partials problems to solve, or four perhaps if we count in to realize that we’re done.

1. Divide with the lowest possible prime as many times as possible.
2. Write a method to find the next prime.
3. Write a method to check if a number is a prime.
4. Realize we are done when the division gives us 1.

Sometimes the candidate will try to give us a recursive solution because they think that’s what we want to see, it’s not, going down that path usually only complicates things. If the interviewers are fishing for a recursive solution, they’ll probably ask something like:

Do X without using a loop

where X could be to reverse a string for instance. It’s always a good idea to write down test cases and test the solution by hand at the whiteboard.

Code

Here’s the program I developed during the screencast with a couple of optimizations added that I got pointed out when publishing the screencast:

using System;
using System.Collections.Generic;
using System.Linq;

public class Program {
    public static void Main(string[] args) {

        var number = int.Parse(args[0]);
        var remaining = number;
        var currentPrime = 2;    
        var result = new List();
    
        do {  
            while (remaining % currentPrime == 0) {
                result.Add(currentPrime);
                remaining /= currentPrime;
            }  
        
            currentPrime = nextPrime(currentPrime);
        } while (remaining > 1);
    
        Console.WriteLine(string.Format(
            "{0}s prime factors are: {1}", 
            number, 
            string.Join("*", result.ToArray())));
    }

    private static int nextPrime(int currentPrime)
    {
        var lastPrimeInArray = Primes.Last();
        if (lastPrimeInArray != currentPrime)
            return Primes.First(x => x > currentPrime);
           
        var nextPrime = currentPrime + 2;
        while (!IsPrime(nextPrime)) nextPrime+=2;
        Primes.Add(nextPrime);
        
        return Primes.Last();
    }

    private static bool IsPrime(int nextPrime)
    {
        for (int i = 2; i < nextPrime / 2; i++)
            if (nextPrime % i == 0) return false;
        return true;
    }

    // TODO: Load first 1000 primes from a file
    private static List Primes = new List { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
}

Bare in mind, it’s been quite some time since I solved these kind of puzzles, don’t be harsh. :-)

Is this a good interview question?

In my experience it helps to seed out some bad programmers. It can most certainly seed out some candidates with potential as well, but we reasoned that it’s simply worth it rather than hiring a really bad programmer. In the end it’s up to the interviewers to steer and adapt the audition to fully explore the candidates skill set, everyone doesn’t perform well under stress and it’s important to be agile during the interview process.

I don’t think that these kind of tests alone is enough to make a decision weather a candidate should get a job as a programmer or not. We usually combined an algorithmic problem with a business/architectural problem and tried to solve that as well, after all we were in the business of developing enterprise applications and not programming puzzles.

Challenge

Feel free to provide your own solution and suggest optimizations. You don’t have to be a programmer to solve these kind of puzzles, you can do it with a pen and paper. We did this on the whiteboard, so the code didn’t even need to compile. It’s fun!

And as always, until next time, have a nice day!