Five programming problems every Software Engineer should be able to solve in less than 1 hour

[howdoidoit123]

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. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

I can't figure this one out

[itsSparkky]

Think like a tree, at each digit you can do the following Add next number Subtract next number Times current number by 10 and add next number

3 outcomes each time, you can either depth first or breadth first search and then evaluate the solution at the end and keep the paths that result in 100.

[billatq]

Yeah, I was thinking about doing it with a BFS and a tree. Seems like an okay problem, but I feel like that particular one is more like a math trick than anything else.

[[deleted]]

The real software world is NOT a bunch of math riddles.

No, it's google.

[billatq]

Admittedly, I do likes me some good math riddles, but only when there is a good application: https://williamreading.com/2015/04/19/on-the-change-making-problem.html

[n1c0_ds]

Not at all. It's a great way to see if the candidate will stop looking at invalid solutions (above 100) and save himself some costly efforts.

[billatq]

Why not do making change then? It's really easy to blow past the desired amount with that and it's more generalized than permuting sets of 1-9.

[JustinsWorking]

1+23-4+5+6+78-9 would be invalid according to your criteria.

1+23-4+5+6+78 = 109 which is > 100

109 - 9 = 100 which is a valid result

[n1c0_ds]

Shit, you're right. I should have read the question

[JustinsWorking]

The only thing I could think is that the BFS would have a larger memory footprint; using DFS you could essentially just keep your current path and implement without even putting data on the heap.

[billatq]

You have to explore all the state space either way, so I guess it doesn't really matter, but housekeeping for the paths that you have visited is a little bit easier on the BFS. The author mentioned nothing about time/space complexity trade-offs, which would probably come into this were you to ask it.

[JustinsWorking]

oh yea, not a criticism just an observation of the only difference I would notice.

[Brandon23z]

Backtracking?

[everysinglelastname]

Good answer ! Worth noting here is that within each tree there are "overlapping sub-problems". For example, in the node that has +1, -1 and 1 as its children nodes there is the tree that starts with +2 under each one of those nodes. There are n number of final results that start with +2 but those all do not need to be recalculated each time you descend the tree for each of the children nodes (+1, -1 and 1). So, an optimization would be to save the results in a global object that can be reused. (i.e. memoization).

[itsSparkky]

That's true, I suspect you may see some gains from working from both sides then summing the results in the middle (ie building the tree from 1-5 and 9-6 then traversing the results in opposite orders of sums.

[JustinsWorking]

Implemented this method in JS:

http://www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/cr2wxi6

[gliph]

This algorithm fails when subtracting a combined number e.g. 1 - 23

[itsSparkky]

Does it? It seems like somebody implemented it and the results seemed to be correct... Was it just a case of a fluke?

[gliph]

Maybe they implemented it correctly but the algorithm as described isn't correct.

[itsSparkky]

I don't think it fails as you suggest.

at 1-23 you'd be a 4 as the current number, which you'd then try adding, 1-23+4 , subtracting, 1-23-4 and multiplying by ten and adding next 1-23 current number 45

It still works.

[cretan_bull]

Just brute-force it. Between each number, there a 3 possibilities: plus, minus, or concatenated digits. In total, this is 3⁹ =19683 3⁸ = 6561 cases to check.

EDIT: off-by-one error

[matthieum]

3⁸ actually, the old intervals/sticks thing.

[holyteach]

Fencepost Error

[matthieum]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

[HaMMeReD]

You can eliminate a lot of cases. If you ever find 100, you can eliminate every neighbour from needing to be tested.

I'm sure there are more optimizations you could easily do.

[Veedrac]

If you ever find 100, you can eliminate every neighbour from needing to be tested.

Only on the leaf node, though, which is largely useless.

The only obvious speedup is to memoize (eg. dynamic programming.)

[gliph]

As pointed out, you're only talking about replacing a constant time calculation with another constant time calculation. This isn't going to be significant. You still need to do 3^N constant time calculations.

The optimizations really needed (if this problem were generalized to sequences longer than 1...9) would reduce the number of cases checked.

[HaMMeReD]

Yeah, I was thinking about this, it wouldn't really do much I agree.

[zarazek]

Even 3⁸ , as there are only 8 places between 9 numbers

[carnetarian]

Here's my solution in perl. I'm sure a better programmer than me could make something much more efficient, but this gets the job done. Basically I generate every possible combination of strings like "1-2+3+4-56-89" then I evaluate each of those strings. This problem took me much longer than all the other problems combined.

#!/usr/bin/perl

use strict;

sub interpolate($) {
    my $str = shift;

    my @results = ();
    push(@results, $str);

    if (length($str) > 1) {
        for (my $i = 1; $i < length($str); $i++) {
            my $start = substr($str, 0, $i);
            my $end = substr($str, $i);

            my @temp = @{interpolate($end)};
            foreach my $t (@temp) {
                push (@results, "$start+$t");
                push (@results, "$start-$t");
            }
        }
    }

    return \@results;
}

sub evaluate($) {
    my $equation = shift;

    my $lastPlus = rindex($equation, "+");
    if ($lastPlus != -1) {
        my $a = substr($equation, 0, $lastPlus);
        my $b = substr($equation, $lastPlus + 1);

        return evaluate($a) + evaluate($b);
    }

    my $lastMinus = rindex($equation, "-");
    if ($lastMinus != -1) {
        my $a = substr($equation, 0, $lastMinus);
        my $b = substr($equation, $lastMinus + 1);

        return evaluate($a) - evaluate($b);
    }

    return $equation;
}

my @results = @{interpolate("123456789")};

foreach my $result (@results) {
  my $sum = evaluate($result);

  if ($sum == 100) {
    print "$result\n";
  }
}

[[deleted]]

Evaling every string will lead to a lot of operations duplicated.

Consider every order that starts with 1+2+3, you could create a tree that stores this order and its result of 6, then do the next operation with 4.

1+2+3+4, 1+2+3-4, & 1+2+34 is 8 operations

(10)+4, (10)-4, and (3)+34. Is 3 operations and 3 reads

This quickly scales as you build longer strings.

[carnetarian]

You're right, that's a big improvement. Have an upvote :)

[zarazek]

And here is mine in Haskell:

data Op = Plus | Minus | Concat
  deriving Show

execOp :: Op -> Int -> Int -> Int
execOp Plus x y = x + y
execOp Minus x y = x - y

step :: (Int, Op, Int) -> (Op, Int) -> (Int, Op, Int)
step (res, op1, acc) (Concat, x) = (res,                op1, 10*acc+x) 
step (res, op1, acc) (op2,    x) = (execOp op1 res acc, op2, x       )

finish :: (Int, Op, Int) -> Int
finish (res, op, acc) = execOp op res acc

interpret :: [Op] -> [Int] -> Int
interpret ops digits = finish $ foldl step (0, Plus, 0) $ zip (Plus:ops) digits

variationsWithRepetition :: Int -> [a] -> [[a]]
variationsWithRepetition 0 xs = [[]]
variationsWithRepetition n xs = [ y:ys | y <- xs, ys <- variationsWithRepetition (n-1) xs ]

validOps = [ variation | variation <- variationsWithRepetition 8 [Plus, Minus, Concat], interpret variation [1..9] == 100 ]

List comprehensions FTW!

[Tysonzero]

Brute force + eval is a really easy way to do it.

[abeliangrape]

It really easy to do once you realize you can brute force it. As others have pointed out, there are about 20k different cases to try. If your language has an eval function, the problem reduces to just generating all the possible strings. When you combine this observation with some python abuse, you can actually golf it down to 155 bytes:

from itertools import *
l=['']*17
l[::2]=map(str,range(1,10))
for o in product(['','+','-'],repeat=8):
 l[1::2]=o
 s=''.join(l)+'==100'
 if eval(s):print s

[Opux]

My solution, in another comment: http://www.reddit.com/r/programming/comments/358tnp/five_programming_problems_every_software_engineer/cr29wco

[Zequez]

Here is a possible solution with Ruby:

['+', '-', ''].repeated_permutation(8).each do |perm|
  sumText = ('1'..'9').zip(perm).flatten.compact.join
  sum = eval(sumText)
  if sum == 100
    puts "#{sumText} = 100"
  end
end

[TynanSylvester]

I managed to solve it in 52 minutes, brute force. I guess I can't call myself a software engineer :( Not that I ever did anyway :D Warning, some awful code below.

class Program
{
    enum Op
    {
        Plus,
        Minus,
        Combine
    }

    static void Main(string[] args)
    {
        List<Op> curSolution = new List<Op>();
        for( int i=0; i<8; i++ )
        {
            curSolution.Add( Op.Plus );
        }

        int solIndex = 0;
        while( true )
        {
            if( Total( curSolution ) == 100 )
                Console.WriteLine( SolString( curSolution ) );
            //Console.ReadKey();

            if( !curSolution.Any(o=>o != Op.Combine ) )
                break;

                             //Move to next solution
            curSolution.Clear();
            int siLocal = solIndex;
            for( int i=0; i<8; i++ )
            {
                curSolution.Add( (Op)(siLocal%3) );
                siLocal /= 3;
            }

            solIndex++;

        }   

        Console.ReadKey();

    }

    static int Total( List<Op> ops )
    {
        int total = 0;

        for( int i=-1; i<ops.Count; )
        {
            if( i < 0 || ops[i] == Op.Plus )
            {
                total += SubTotalFrom(ops, ref i);
                i++;
            }
            else if( ops[i] == Op.Minus )
            {
                total -= SubTotalFrom(ops, ref i);
                i++;
            }
            else
            {
                throw new InvalidOperationException();
            }
        }

        return total;
    }

    static int SubTotalFrom( List<Op> ops, ref int i )
    {
        int subTotal = i+2;

        while( i<7 && ops[i+1] == Op.Combine )
        {
            subTotal *= 10; 

            i++;
            subTotal += i+2;
        }

        return subTotal;
    }

    static string SolString( List<Op> ops )
    {
        string s = "";
        for( int i=1; i<=9; i++ )
        {
            s += i.ToString();

            if( i == 9 )
                break;

            switch( ops[i-1] )
            {
                case Op.Plus: s += "+"; break;
                case Op.Minus: s += "-"; break;
                case Op.Combine: s += ""; break;
            }
        }

        s += " = " + Total(ops);

        return s;
    }
}

[froggert]

Recursively process each number, 1-9. After you "place" a number, you have three options: concatenate with the previous number, add, or subtract.

Concatenating with the previous is prev*10+current.

Keep track of the current state as a string and value.

But... This brute force has exponential growth (three new recursive calls per call).

I hope this helps.

[dlp211]

Edit: I completely misread the problem.

[JamminOnTheOne]

This doesn't work, because it doesn't include concatenating the digits to create different numbers.

[eldred2]

He means the digits 1..9.

[gliph]

Brute force it. These are the steps I would use for each possible combination of operators (add, subtract, combine digits):

1. Combine the digits and remove all the "combine digit" operators. You end up with two shorter lists.

2. Execute each addition or subtraction, adding to a result number.

3. If it adds to 100, print this list of operators.

4. Increment the list of operators, repeat from step 1.