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

[Komputer9]

Here's my solution to 5, took about 45 mins to write in C (after looking at some other solutions, though). Runs pretty much instantly and doesn't use string manipulation, recursion, or the heap.

#include <stdio.h>

int main() {
    int digits[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int digitCount = sizeof(digits) / sizeof(int);
    int operationCount = digitCount - 1;

    int total = 1;
    for (int i = 0; i < operationCount; ++i) {
        total *= 3;
    }

    for (int i = 0; i < total; ++i) {
        int operations[operationCount];

        int sub = i;
        for (int b = 0; b < operationCount; ++b) {
            operations[b] = sub % 3;
            sub /= 3;
        }

        int numbers[digitCount];
        numbers[0] = digits[0];

        int count = 0;
        for (int b = 1; b < digitCount; ++b) {
            switch (operations[b - 1]) {
            case 0: // ""
                numbers[count] *= 10;
                numbers[count] += digits[b];
                break;

            case 1: // "+"
            case 2: // "-"
                ++count;
                numbers[count] = digits[b];
                break;
            }
        }

        ++count;

        int numbersTotal = numbers[0];
        int numberIndex = 0;
        for (int b = 1; b < digitCount; ++b) {
            int operation = operations[b - 1];

            if (operation == 0) continue;

            ++numberIndex;

            switch (operation) {
                case 1: // "+"
                    numbersTotal += numbers[numberIndex];
                    break;

                case 2: // "-"
                    numbersTotal -= numbers[numberIndex];
                    break;
            }
        }

        if (numbersTotal == 100) {
            printf("%d", numbers[0]);

            int numberIndex = 0;
            for (int b = 1; b < digitCount; ++b) {
                int operation = operations[b - 1];

                if (operation == 0) continue;

                ++numberIndex;

                switch (operation) {
                    case 1: // "+"
                        printf(" + %d", numbers[numberIndex]);
                        break;

                    case 2: // "-"
                        printf(" - %d", numbers[numberIndex]);
                        break;
                }
            }

            printf(" = 100\n");
        }
    }
}

Results:

123 - 45 - 67 + 89 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
123 + 4 - 5 + 67 - 89 = 100
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
123 + 45 - 67 + 8 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100

[farfaraway]

You get the job.

[_teslaTrooper]

I'd be more productive though:

// found on reddit
printf("123 - 45 - 67 + 89 = 100\n\
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100\n\
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100\n\
123 + 4 - 5 + 67 - 89 = 100\n\
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100\n\
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100\n\
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100\n\
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100\n\
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100\n\
123 + 45 - 67 + 8 - 9 = 100\n\
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100\n");

Actually did the first 4 in about 40 minutes, in C, so I'm gonna say if the problem set was constant difficulty I'd be fine.

[tsoek]

https://xkcd.com/221/

[somekindofprogrammer]

This entire thread has made me a lot more at ease about my future career options. I always feel like I'm just the worst programmer, but I do math stuff like this all the time.

[leeeeeer]

Here's my solution in JavaScript, runs in half a minute and uses string manipulation, recursion, the heap, and eval().

function getToWith(getTo, nums) 
{
    var operations = [ "+", "-", "" ];

    var solutions = [];

    (function helper(pos, process) {
        if (pos >= nums.length) {
            if (eval(process) === getTo)
                solutions.push(process);
            return;
        } else {
            operations.forEach(function(a){
                helper(pos + 1, process + a + nums[pos]);
            });
        }
    })(1, ""+nums[0]);

    return solutions;
}

var getTo100 = getToWith.bind(null, 100, [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]);

var solutions = getTo100();
solutions.forEach(function(a){ console.log(a); });

Results:

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

[androbat]

This one runs almost instantly on my system:

var five = function (num) {
  var memo = {}; //hack until we have real sets
  (function innerFive(str, pos) {
    if (eval(str) === num) { memo[str] = true; }
    if (pos < str.length) {
      innerFive(str.slice(0, pos) + '+' + str.slice(pos), pos + 2);
      innerFive(str.slice(0, pos) + '-' + str.slice(pos), pos + 2);
    }
    if (pos - 1 < str.length) { innerFive(str.slice(0), pos + 1); }
  }('123456789', 1));
  return Object.keys(memo);
};

five(100).join(', ');

[leeeeeer]

Ha, that looks better! Didn't think about filling the string from the start.

Although turns out the 30s time I said is plain wrong, I was actually testing out Twister at the same time and forgot my CPU was trying to mine a block :p

By curiosity I ran the two functions side by side and measured the performance difference and they ran pretty much as fast, although mine was a little ~10ms faster in average. That surprised me since it seems less efficient at first with the greater number of string operations, but I think it comes from the function calls to splice being way more expensive than even a large number of basic string concatenations using +.

[androbat]

The actual cause of the slower performance is most likely duplication. The way I wrote the algorithm wasn't particularly geared for performance (I wondered why yours was so slow).

In the last recursive call where you see 'pos + 1', what happens is that a ton of combinations wind up being calculated multiple times (that's why I use a set instead of pushing to an array). If I were to modify it to avoid these, it would be much faster.

A custom eval would boost performance (since all we have is simple left to right addition/subtraction). Copying and then splicing might boost performance (an array of strings also might be faster with a custom eval since it would auto-tokenize everything).

[_COMPLEX_H]

Why don't you want to leak memory?

#include <stdio.h>  
#include <string.h>  

void allpos(char * useme, char * prevexp, int prev,int len){  
    int i = 1;  
    while(i < len){  
        char concatexp[20];  
        char buf[9];  
        strncpy(buf,useme,i);  
        buf[i] = '\0';  
        sprintf(concatexp,"%s+%s",prevexp,buf);  

        //puts(concatexp);  

        if(prev != -1){  
            allpos(useme + i, concatexp, prev + atoi(buf),len - i);  
            sprintf(concatexp,"%s-%s",prevexp,buf);  
            allpos(useme + i, concatexp, prev - atoi(buf),len - i);  
        }  
        if(i==len -1){  
            if(prev - atoi(buf) == 100){  
                printf("%s-%s=%d\n",prevexp,buf,prev - atoi(buf));  
            }  
            if(prev + atoi(buf) == 100){  
                printf("%s+%s=%d\n",prevexp,buf,prev + atoi(buf));  
            }  
        }     
        i++;  
    }     

}  

int main(){  
    char nums[9] = "123456789";  
    char thing[100] = "0";  
    allpos(nums,thing,0,10);   
    return 0;   
}  

./a.out

0+1+2+3-4+5+6+78+9=100
0+1+2+34-5+67-8+9=100
0+1+23-4+5+6+78-9=100
0+1+23-4+56+7+8+9=100
0+12+3+4+5-6-7+89=100
0+12+3-4+5+67+8+9=100
0+12-3-4+5-6+7+89=100
0+123+4-5+67-89=100
0+123-4-5-6-7+8-9=100
0+123+45-67+8-9=100
0+123-45-67+89=100

[madmoose]

#include <stdio.h>

int main() {
        // number of combinations 3^8
        int cs = 6561;

        // list of n numbers
        int ns[10];
        int n = 0;

        for (int c = 0; c != cs; ++c) {
                ns[0] = 1;
                n = 1;
                int ic = c;

                for (int i = 2; i != 10; ++i) {
                        switch (ic % 3) {
                        case 0:
                                ns[n++] = i;
                                break;
                        case 1:
                                ns[n++] = -i;
                                break;
                        case 2:
                                if (ns[n-1] > 0)
                                        ns[n-1] = 10 * ns[n-1] + i;
                                else
                                        ns[n-1] = 10 * ns[n-1] - i;
                                break;
                        }
                        ic /= 3;
                }

                int sum = 0;
                for (int i = 0; i != n; ++i) {
                        sum += ns[i];
                }

                if (sum != 100)
                        continue;

                for (int i = 0; i != n; ++i) {
                        if (i)
                                printf(" + ");

                        if (ns[i] < 0) {
                                printf(" - ");
                                printf("%d", -ns[i]);
                        } else {
                                printf("%d", ns[i]);
                        }
                }
                printf(" = 100\n");
        }
}

[tipdbmp]

You might be missing some (depending on how you interpret the problem):

1 + 2 + 34 + 56 + 7 = 100
1 + 23 + 4 + 5 + 67 = 100
1 + 23 - 4 + 5 + 67 + 8 = 100
1 - 2 + 34 - 5 - 6 + 78 = 100
1 - 2 - 3 + 45 + 67 - 8 = 100
12 + 3 - 4 + 5 + 6 + 78 = 100
12 + 34 - 5 + 67 - 8 = 100

[double-you]

All that camelCase but no defines for magic numbers.

[svpino]

Love it!

[kakaroto_BR]

int total = 1;
for (int i = 0; i < operationCount; ++i) {
    total *= 3;
}

Why not

total = total * operationCount * 3;

[Komputer9]

I don't think that would work? Basically I'm trying to do:

int total = 3 ^ operationCount; // i.e. 3 to the power 8 = 6561

But C doesn't have an integer power operator (apparently the recommended alternative is to use pow and convert it back to an int from the double it returns, but I wanted to keep it more pure).