Programming Interview Questions: Recursion

/0 Comments/in , , /by

In this screecast we solve two commonly asked interview questions; faculty and traversing binary trees.

Screencast

What’s recursion?

A recursive function is simply a function that repeatedly calls itself and the trick is to realize when to stop calling ourselves to avoid infinite loops that result in stack overflows.

If the interviewers ask you to write down an algoritm that gives you the n:th fibonacci number, calculate faculty or traverse a binary tree they probably want you to provide both an iterative and recursive solution. We don’t address fibonacci in the screencast, but the formula for the n:th number is simply the sum of the previous two, i.e.

f(n) = f(n-1) + f(n-2)

Is this a good interview question?

Here’s the recursive methods I developed during the screencast to calculate faculty and to sum the value of all the nodes in a binary tree:

    private static int sum(Node node) {
        if (node == null) return 0;
        return node.Value + sum(node.Left) + sum(node.Right);
    }
    
    private static long faculty(int n) {
        if (n == 1) return 1;
        return n * faculty(n - 1);
    }

As you can see the answers are usually very simple but it’s not unusual to see candidates try to make things more complicated than they need to be. Just keep it simple.

Interviewers tend to ask these kind of questions even if functional programming is a very small part of the day to day work. It’s always good to be prepared by training on some simple problems similar to the ones covered here. After one or two exercises you’ll get the hang of it and it won’t be a problem if they throw these kind of questions at you during the interview.

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

Programming Interview Questions: Prime Factorization

/0 Comments/in , /by

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!