Five Programming Problems

Introduction

Recently I stumbled upon this blog post on ShiftedUp. The writer briefly explains that he encountered many cases of job applications for Software Engineer positions, made by people who actually have no idea of what programming means.

Then he proposes 5 coding problems to solve in less than one hour, using whatever programming language you are comfortable with. So I decided to take the challenge! The language used is JavaScript, but the examples can be written easily in any other language.

Problem 1

“Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.”

function forSum(list) {

    var i, result = 0;

    for(i = 0; i < list.length; i++) {
        result += list[i];
    }

    return result;
}

function whileSum(list) {

    var result = 0;

    while(list.length) {
        result += list.pop();
    }

    return result;
}

function recursiveSum(list)
{
    if(!list.length) return 0;

    return list.pop() + recursiveSum(list);
}

Ok, that was quick! Bring it on!

Problem 2

“Write a function that combines two lists by alternatingly taking elements.”

Just for sake of simplicity I’m assuming that both lists have the same number of elements.

function alternateMerge(list1, list2)
{
    var merged = [];

    while(list1.length && list2.length) {
     	merged.push(list1.shift());
        merged.push(list2.shift());
    }

    return merged;
}

Problem 3

“Write a function that computes the list of the first 100 Fibonacci numbers.”

Wow, feels like going back to University!

function fibonacci(n)
{
    n < 2 ? n : fibonacci(n-2) + fibonacci(n-1);
}

var result = [],
    i = 1;

for (i = 1; i <= 100; i++) {
    result.push(fibonacci(i));
}

This version uses the recursive version of the Fibonacci formula, but if you look carefully you will notice that it’s not so efficient because every time the i counter is increased, the fibonacci function has to compute, with every iteration, the results of the previous calls¹.

For example, if we consider the recursive step for n

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

and the recursive step for n-1

fibonacci(n-1) = fibonacci(n-3) + fibonacci(n-2)

by sostitution we can see that

fibonacci(n) = fibonacci(n-2) + fibonacci(n-3) + fibonacci(n-2)

In this case we are doing fibonacci(n-2) more than once, and continuing with the computation we will have more duplication. To solve this problem we can optimize the calculation by using a technique called memoization, in order to cache the answers of previous computations and return them back when needed. Let’s see an example:

function memoization(f) {
    var cache = {}
    return function(x) {
        if (typeof cache[x] === 'undefined') {
            cache[x] = f(x);
        }
        return cache[x];
    }
}

fibonacci2 = memo(fibonacci);

My second attempt however was to use the loop version:

var result = [],
    i;

var a = 0,
    b = 1,
    tmp;

for(i = 1; i <= 100; i++){
    tmp = a + b;
    a = b;
    b = tmp;

    result.push(tmp);
}

Much better! It is faster than the previous implementation, however the results are not completely correct, because after the 78th iteration we lose the precision of the Number type since JavaScript, unlike other languages, doesn’t support Big Integers. The largest exact integer value is 9007199254740991 and is defined by Number.MAX_SAFE_INTEGER.

By the way, if you are interested in Fibonacci algorithms and you are eager to know which one is the fastest, take a look at the JSperf site http://jsperf.com/fibonacci-y-combinator/5

Problem 4

“Write a function that given a list of non negative integers, arranges them such that they form the largest possible number.”

The example provided by the author is [50, 2, 1, 9]. The function should somehow rearrange the list and return the number 95021, which is the largest among all the possibilities.

Here the things start to get tricky! My first intuition was trying to compare lexicographically each element of the array using the sort function. Let’s see how it works:

function rearrange(list)
{
    var result;

    list.sort().reverse();

    result = parseInt(list.join(""), 10);

    return result;
}

console.log(rearrange([50, 2, 1, 9]));

At first we simply sort the list in ascending order, getting [1, 2, 50, 9]. Note that the numbers are sorted as strings, so “50” is smaller than “9” simply because “5” is smaller than “9”.

The next steps are reversing the array, joining its values and returning a proper number, which in this case is exactly 95021.

However this solution is not perfect! Let’s take for example the list [5,50,56], the number returned by the rearrange function is 56505, but the largest number is 56550. So how can we solve this problem definitively?

After a couple of attempts, I realized that string concatenation was the way to go. Let me first explain the idea: when sorting the array we have access to the compare function that defines the sort order depending on the two arguments (returning a negative number says that the first argument is smaller, a positive number says otherwise). For example

list.sort(function(a, b) {
    return a - b;
});

is the default implementation and sorts the array in ascending order, in this case it leaves our example array as it is. Instead we are searching for a comparison function that returns [56, 5, 50] or, in other words, a function that satisfies the following conditions

function(5, 50) {
    return +1; // 5 is > than 50
}

function(50,56) {
   return -1; // 50 is < than 56
}

function(5,56) {
    return -1; // 5 is < than 56
}

Let’s check if string concatenation could work. We join the first argument with the second and the second with the first, then we compare the result.

In the first function 550 is larger than 505. In the second function 5056 is smaller than 5650. Finally in the third function 556 is smaller than 565.

We did it! Let’s build the function:

list.sort(function(a,b) {
    var a = a + "";
    var b = b + "";

    return (a + b) > (b + a) ? -1 : 1;
});

Problem 5

“Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100”

That’s look difficult! Let’s try to break down the problem a little bit: we need to find all the lists of operands (+, - or nothing) to put between the numbers from 1 to 9 such that the result is always 100:

1[+|-|'']2[+|-|'']3[+|-|'']4[+|-|'']5[+|-|'']6[+|-|'']7[+|-|'']8[+|-|'']9 = 100

I didn’t have any intuitions on this one, so I decided to try a brute force approach. The number of operands is 3 and the spaces between the numbers are 8, which means 3^8 = 6561 combinations, feasible for a brute force solution using a for cycle. Let’s start by defining our initial data

var numbers = [1,2,3,4,5,6,7,8,9];
var target = 100;
var combinations = Math.pow(3,numbers.length-1);    // 6561

Now think about it, we have to compute 6561 different combinations of how the 3 operands can be placed in the 8 spaces between our numbers. To simplify our lives we can assign each operand to a number, in the following way

// o stands for operands
var o = { 0 : "", 1 : "-", 2 : "+" };

0 is nothing, 1 is the minus operator and 2 is the plus operator.

Now the previous sentence can be rewritten. We have to find all the combinations of 0, 1 and 2 from 00000000 to 22222222, which essentially are valid numbers in base 3², translate back those numbers in the corresponding operands, placing them between our numbers array and evaluate if the result is equal to 100.

Before this however we need to ensure that the strings smaller than 8 digits are properly padded with zeros, for example the number 4 in base 3 is 11, but we need it in the form 00000011.

Here’s the complete solution!

var numbers = [1,2,3,4,5,6,7,8,9];
var target = 100;
var combinations = Math.pow(3,numbers.length-1);

var solutions = [];
// o stands for operands
var o = { 0 : "", 1 : "-", 2 : "+" };
var i;

for(i = 0; i <= combinations; i++)
{
    var tmp = i.toString(3);    // translates the index in base 3

    var p = ("00000000" + tmp).substr(-8,8).split("").map(function(v){ return parseInt(v) });

    var try = "1"+o[p[0]]+"2"+o[p[1]]+"3"+o[p[2]]+"4"+o[p[3]]+"5"+o[p[4]]+"6"+o[p[5]]+"7"+o[p[6]]+"8"+o[p[7]]+"9";

	if(eval(try) === 100)
	{
        solutions.push(nums);
    }
}

The interesting part is in the for cycle.

1. We translate the index of the cycle in base 3 using the toString(3) method;
2. We pad the resulting string with the required zeros, then using split we convert it to an array of strings (of chars to be precise) and finally we apply map to convert them back into numbers;
3. We translate each number of the array into the corresponding operand and we place them between our numbers from 1 to 9;
4. Finally we use eval to evaluate the expression and to check if the result is equal to 100.

These are the solutions printed by the program:

[
    '123-45-67+89',
    '123-4-5-6-7+8-9',
    '123+45-67+8-9',
    '123+4-5+67-89',
    '12-3-4+5-6+7+89',
    '12+3-4+5+67+8+9',
    '12+3+4+5-6-7+89',
    '1+23-4+56+7+8+9',
    '1+23-4+5+6+78-9',
    '1+2+34-5+67-8+9',
    '1+2+3-4+5+6+78+9'
]

Conclusions

To be honest it took me more than hour to solve and code all the problems, especially because the numbers 4 and 5 are not as easier as the previous three. Moreover I’m thinking that there exists a more efficient solution for the problem 5, if this is your case, please get in touch with me on Twitter.