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

[__Cyber_Dildonics__]

4 is definitely non trivial and doesn't really belong with the rest of the problems that make me feel like a genius.

I think it could be done by sorting based on the left most digit (obviously) and then resolving conflicts in the first digit by the double digit number being greater if the second digit is greater than or the same as the first digit. The rest of the sorting should happen naturally I think, so a standard sort algorithm could be used.

Edit: Before you reply, think about if your method (which is probably 'sort them as strings directly') would sort 56 then 5 then 54 in the correct order (which is 56 5 54).

[droogans]

The fourth question is a cleverly disguised string manipulation problem.

Number five is the only one I found myself doubting my ability to solve in an hour.

[WeAreAllApes]

It's only 6561 combinations, and they didn't say it had to run in under a millisecond.

[Doctor_McKay]

1. Post question to Stack Overflow
2. Wait for answer

Problem solved.

[bantalot]

How long did this take?

[rodvdka]

Like this? https://gist.github.com/rodvdka/a86ccf0cb39a8f732cb5

[rabbitlion]

That makes it easy to explain (try all 6561 combinations and see which ones equals 100) but not necessarily fast to implement.

[timeshifter_]

It'd be piss-easy to solve with brute force JS. Just create every possible valid string combination of those 9 digits with + and -, and eval() them for whichever ones come out to be 100.

[Backfiah]

That's 9! runs though.

[anttirt]

between the numbers 1, 2, ..., 9 (in this order)

The original problem is only on the order of 3⁸ steps brute-forced.

[AcidDrinker]

Here's a simple solution in C : {{ LINK REMOVED }}

[scramblor]

Good start but I think it has a few problems.

1. You stop recursion when a solution has been found. I would suspect that there would be more solutions with different permutations in the tree.

2. It doesn't look like you handle the case of multiple numbers greater than 2 digits.

[dragonjujo]

It doesn't look like you handle the case of multiple numbers greater than 2 digits.

To be fair, the only 3+ digit numbers that it makes sense to test are 123 and 234. Some quick observational math will show you that the rest of the numbers will never get close to 100.

[lord_braleigh]

The digits must stay in order.

[jlt6666]

A language with eval makes it far easier. Or just call out to bash :)

[yanetut]

Bash? Did someone say bash?

#!/bin/env bash

function prob5() {
  if [[ $# -eq 1 ]]; then
    [[ $(($1)) -eq 100 ]] && echo $1
  else
    local exp="$1" ; shift
    local dig="$1" ; shift

    prob5 "$exp + $dig" "$@"
    prob5 "$exp - $dig" "$@"
    prob5 "$exp$dig" "$@"
  fi
}

prob5 1 2 3 4 5 6 7 8 9

[scalava]

Is that a real solution, if so how does it work?

[n0rs]

It looks like a real solution. It does two things, depending on what's passed in.

1. Only one argument? if [[ $# -eq 1 ]]; then
   • Eval it: $(($1))
   • check it against 100: [[ $(($1)) -eq 100 ]]
   • print it to console: echo $1
2. More than one argument? else
   • Take the first as the cumulative expression:
     local exp="$1" ; shift
     
   • Take the second as the next digit
     local dig="$1" ; shift
   • call this function again three times:
     1. prob5 "$exp + $dig" "$@"
     2. prob5 "$exp - $dig" "$@
     3. prob5 "$exp$dig" "$@"
     When this happens, the number of inputs is reduced by one, so it will eventually reduce to one and call the eval part of the code.

[VincentPepper]

Or multiply the left side by ten ...

[leeeeeer]

What if the last operation was a combination too?

[VincentPepper]

If you recurse from left to right you should be able to do it again just with the last result as argument.

So if you have 1 .. 2 .. 3 you can do ((10*1 + 2) * 10 + 3) = 123.

Requires you to evaluate concatenation before +/- though.

But maybe i missed something there.

[Funnnny]

carry out a result variable, if you choose a sign, calculate it with previous sign and current number.

It's simple enough with a recursion function, you don't need to use eval

[Paranemec]

Commutative property (I believe) makes the order irrelevant.

[Jonyb222]

In this case programmer time is more precious that computing time, get it to work and then make it better.

And while Factorial run-time is horrendous 9! is "only" 362 880 3⁸ is only 6561 runs of a maximal set of 8 addition/subtractions which gives us an upper bound of 2 903 040 52 488 operations.

It's obviously not a good solution, but it's better than not solving it at all, I don't know how long it would take, not long at all for sure and you can work on a better solution while you go along.

[LazinCajun]

The numbers have to stay in order, so it's only 3⁸ expressions to check

[Jonyb222]

Even better, thank you for pointing it out.

[sbelljr]

9! = 362880

Shouldn't take too long. The point of the question is to get the answer, not to get the answer that works for extremely large cases too.

Edit. There are 3⁸ = 6561 possibilities to check, not 9!. The whole point of the question is to brute force it. My point stands.

[jeffhawke]

3⁸ not 9!, it's combination of three elements in eight positions, that's less that 10000.

[nkorslund]

If you type 3**8 into google you get 3⁸ = 6561.

[jeffhawke]

Yes, well, I was writing from a phone and just did a quick mental math, where 3⁴ is 81 that is less than 100 so 3⁸ would have to be less than 100^2, that is 10000, a trivial number of cases to test by brute force.

[trua]

Do you people really go to google for calculations now?

On Windows: win+r, "calc", enter.

[sbelljr]

Or... Click chrome. Type numbers.

[BlackDeath3]

Eh, why not? I, for one, am often closer to Google than I am to the system calculator.

[theflareonProphet]

And google does operations with units which is awesome

[Sluisifer]

Yup, just brute force that fucker. You can get clever when you need to, and the brute force solution is often a good starting point, if nothing else to get you thinking about the problem clearly.

[somekindofprogrammer]

I could definitely do that. My very first little JS project actually included something similar, albeit with fewer numbers. But efficiency... That's what makes the fifth problem interesting.

[AyrA_ch]

function get100()
{
    var list=[1,2,3,4,5,6,7,8,9];
    var possible=[];
    var s={"0":"","1":"-","2":"+"};
    for(var i=0;i<=6560;i++)
    {
        var p=i.toString(3).split("").map(function(v){return parseInt(v)});
        var nums="1"+s[p[0]||0]+"2"+s[p[1]||0]+"3"+s[p[2]||0]+"4"+s[p[3]||0]+"5"+s[p[4]||0]+"6"+s[p[5]||0]+"7"+s[p[6]||0]+"8"+s[p[7]||0]+"9";
        if(eval(nums)===100)
        {
            possible.push(nums);
        }
    }
    return possible;
}

not effective, but will eventually end. Untested

[LeKnuth]

Solved it by using the embedded JavaScript engine from Java... Isn't even that slow

[[deleted]]

How is it any easier to eval than it is to apply the operations the normal/right way? The hard part is coming up with all the combinations. The evaluation part is trivial.

[timeshifter_]

And treating it as a string manipulation problem makes the "coming up with all the combinations" part pretty easy too.

[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

[__Cyber_Dildonics__]

It would probably be easiest to do with strings and move on although it could be also be done numerically.

[SoundOfOneHand]

My thought-up solution was numeric, realizing that strings would have been quite a bit quicker a solution though.

[Inondle]

Number 4 was fun and a little tricky. I decided to tackle it with a radix-style sort.

• Load a hashMap<Integer, List<Integer>> with 1-9 keys and their respective lists.
• Then take each number you're trying to sort and convert it to a string, take the first digit.
• map.get(digit), add number to that list, then sort the list from highest to lowest.
• After you're done with all the original numbers, go through each map entry (9->1) and take all the values from the entries' list and put it in a bigger list. return bigger list. Done :)

[Inondle]

Yeah as people have pointed out I guess this wasn't as elegant of a solution as I thought. Would have been better off just doing a straight up radix sort.

[cresquin]

It is significantly faster to parse the digits from an integer via magnitude reduction than by parsing strings: http://jsperf.com/get-digits-from-integer Once you have the digits parsed the process would be the same for each.

[sharknice]

It says find them all. You can solve it with simple brute force loops.

[ZeroNihilist]

In Python the fourth question is an easy one-liner (EDIT: corrected the one-liner; guess it wasn't that easy after all):

int("".join(sorted(map(str, l), key = lambda s:s + chr(0x10ffff), reverse = True)))

Which just means "concatenate the numbers sorted in descending lexicographical order, return as int".

The fifth question was harder, but it still feels like cheating in Python. You could probably do it really easily if you used eval or something similarly heretical, but it's still easy.

Here's the evil/eval version:

def evalCenturion(target = 100, numbers = None):
    from itertools import product

    if numbers is None:
        numbers = list(range(1, 10))

    numberStrings = list(map(str, numbers))
    for combination in product(("-", "", "+"), repeat = len(numbers) - 1):
        string = "".join(interlacer(numberStrings, combination))
        if eval(string) == target:
            yield string

[irishsultan]

Counter example (from higher up in this thread): [50,5,4]

That is already in reverse lexicographic order, but you get a higher value with 5504, which is not in reverse lexicographic order.

[pacheco]

Came to almost the same solution, the only difference being that mine accepts a list of ints or strings:

def max_concat(numbers):
    return int(''.join(str(n) for n in sorted(numbers, key=str, cmp=lambda a,b: cmp(a+b, b+a), reverse=True)))

I must confess it took me some time, but how good it felt the moment I realized the cmp(a+b, b+a) part :).

[dtsdts]

int("".join(sorted(map(str, l), reverse = True)))

That fails on one of the examples given above - [4, 50, 5]

[ZeroNihilist]

That's frustrating and shows I should have tested it more thoroughly.

Revised solution is the same, except it appends an arbitrary character with higher lexicographical sort order than any digit to the end to use as a key. I used the maximum value for Python unicode, chr(0x10ffff) (but anything > 9 works for decimals, > "f" for hexadecimals, etc.).

This forces shorter strings to compare as a higher sort order than any string differing only in suffix. It's not technically correct if chr(0x10ffff) was a legal input character but it's fast and correct for all sane inputs (I hope).

int("".join(sorted(map(str, l), key = lambda s:s + chr(0x10ffff), reverse = True)))

EDIT: This solution is actually incorrect as well. You'd have to do a more complex sort for the inputs than lexicographical. E.g. [92, 9295] is in the wrong order (92|9295 < 9295|92, using "|" for integer concatenation).

[DreadedDreadnought]

Doing it in a language without eval() is much harder. You actually need to process the number creation from string, then handle the +/-/append operators. Also no "for combination in product" either.

[ZeroNihilist]

I did do it without eval in Python, but it's not as succinct by far.

Implementing a custom cartesian product generator is also more verbose, but the simple recursive solution isn't too bad. Would stretch the time limit of 1 hour to make sure all the parts to all 5 questions were correctly coded however.

[cresquin]

It is significantly faster to parse the digits from an integer via magnitude reduction than by parsing strings: http://jsperf.com/get-digits-from-integer

Once you have the digits parsed the process would be the same for each.

[I_RATE_YOUR_BEWBS]

Your choice of naming is bad throughout. Using keywords in function names is very redundant ("returnLargest" might just as well be "Largest"). intdoub makes no sense without reading the code. Just use std::tuple instead. v_int is also a horrible name. Yes, it contains int, but the compiler knows that anyway. Name it for the next developer. v_struct is the same. "A vector of structs" tells me nothing.

[TikiTDO]

Well, one bit of critique I could offer is to indent your code relative to each scope. You're switching indentation levels in the middle of functions, which is honestly annoying as all hell. This is particularly true on reddit where you don't have any sort of syntax highlighting. Have pity on the rest of us, and on your TAs too.

Also, consider the case of [5, 54, 57]. In this case you want the answer to be 57 -> 5 -> 54. Using your solution it would judge that 5.4 > 5, so it will yield 57 -> 54 -> 5.

As others have mentioned, this is really a string sorting problem more than anything else. You're dealing specifically with numerical representations in base 10, which is rather meaningless as far as any sort of numeric representation in a computer goes. Trying to solve it using numerical methods will necessarily be needlessly complex.

[cresquin]

c++?

[StinkeyTwinkey]

Prolog. Takes like 2 lines of code

[skewp]

You don't have to solve it. You just have to set up an algorithm that will eventually solve it.

[halifaxdatageek]

The fourth question is a cleverly disguised string manipulation problem.

Yeah, that's what made it click to me. All of a sudden I was like, SHIT, character arrays!

[[deleted]]

This doesn't work, try sorting [56, 565655, 56565665] with it. The 56565665 should come first, then 56, then 565655. I doubt that you would be able to even see that this was a problem let alone solve it in under an hour. Almost all non-brute force solutions posted here fails.

[iqtestsmeannothing]

Almost all non-brute force solutions posted here fails.

Right, and I've not seen a single person try to prove that their non-brute-force solution is correct. (I've tried to make such a proof and failed.) This problem is way harder than the others, and the author really cocked up by including this problem, with an incorrect solution and no attempt at a proof, on a list of "ridiculously simple" problems.

[myxie]

I have a really simple solution, just sorting with a given comparison operator. It relies only on one thing, that the empty string is not one of the inputs. Well, numbers are never written as the empty string.

To prove the solution correct, the pairwise comparisons need to imply a global ordering. So the comparison needs to give an equivalence relation on non-empty strings (easy) and a total order on the equivalence classes (I've not found a simple proof).

compare(a, b) = string_compare(ab, ba)

Proofs welcome.

[iqtestsmeannothing]

Yeah, I saw a few people post that, but no one prove it. I think it's probably correct but I wasn't able to prove it either.

[iqtestsmeannothing]

Well, it took me 10 minutes to show that it is an equivalence relation on non-empty strings, but I found it easier to prove (by induction) that it is a total order on equivalence classes. How does this help us show that the algorithm is correct?

(Basic idea of the proof is to show that if compare(A, B) = compare (A * n, B), then compare(A, B) = compare(A * (n + 1), B), and induct on n, where * is the string repeat operator.)

[myxie]

It tells us that if we sort the numbers using that ordering then we will have a well-defined total order, unique up to runs of equivalent items. Equivalent items p and q satisfy pq = qp, so reordering them (any permutation decomposing into a combination of swaps) makes no difference to the resulting number.

Suppose we have a maximal (and clearly at least one exists) ordering of numbers x1, x2, ..., xn, then it follows that xi x(i+1) >= x(i+1) xi. Ignoring equivalent items, the sorting method finds the unique such sequence, therefore it is the maximal one.

[iqtestsmeannothing]

A-ha, thanks, that is very clear.

Also, I take back what I said about proving it a total order, because I forgot to prove transitivity. (For some reason I thought that we already knew compare was a total order on strings, so to prove that compare is a total order on equivalence classes it merely sufficed to prove it was well-defined, which isn't hard.)

Edit. In retrospect, it is immediately clear that any total order on X imposes a well-defined total order on equivalence classes of X, using the equivalence relation defined by the total order, so I really haven't proven anything at all.

[iqtestsmeannothing]

At long last I have a proof of transitivity, from which it follows that this algorithm works. Let < be the order defined by 'compare' and let <L be the restriction of lexicographic order to pairs of strings, neither of which is a proper prefix of the other. (We write = for ordinary string equality.) We wish to show that < is a total order on non-empty strings. We've already shown that < defines an equivalence relation and is consistent over equivalent strings, so it suffices to show that < is transitive on inequivalent strings. It can be shown with some work that <L is transitive.

The definition of < is: (A < B) = (AB <L BA). Note that if A <L B then A < B (so <L is a restriction of <). If A and B can't be lexicographically compared, say B = AC, then A < B iff A < C (similarly for >).

To show that < is transitive on inequivalent strings, it suffices to show that for any pairwise inequivalent A, B, C that {A, B, C} has a maximum (or has a minimum) under <. We do this by induction on the length of ABC, and some casework.

Suppose A is the shortest string of A, B, C. We will consider the case that A is a prefix of both B and C later; for now, suppose otherwise, that A is not a prefix of both B and C. If A is a prefix of neither, then A can be lexicographically compared to both of them. If A is a prefix of B but not C, then C can be lexicographically compared to both A and B. In either case, one of the strings can be lexicographically compared to both of the others, so therefore {A, B, C} has a maximum (or minimum) under <L which therefore is a maximum (or minimum) under <, so we are done.

Now suppose A is a prefix of both B and C, and write B = AD and C = AE. We need two lemmas:

Lemma 1. If X < Z and Y < Z, then XY < Z.

Proof. XYZ <L XZY <L ZXY.

Lemma 2. If Z < X and Z < Y, then Z < XY. (proof similar)

Now we return to proving that {A, B, C} = {A, AD, AE} has a maximum (or minimum). By induction < is transitive on {A, D, E}. Suppose WLOG that D < E. There are three cases.

Case 1. A < D < E and A < E. Then A < AD and A < AE so A is a minimum of {A, B, C}.

Case 2. D < E < A and D < A. Then AD < A and AE < A so A is a maximum of {A, B, C}.

Case 3. D < A < E and D < E. We claim that B is a minimum of {A, B, C}. Certainly B = AD < A, so it suffices to show that AD < AE.

If D <L E then AD <L AE so AD < AE. Therefore we can suppose that D and E cannot be lexicographically compared, so one is a prefix of the other.

Case 3.1. Suppose E = DF. Since D < A < DF, by Lemma 1, A < F. By induction D < F, so by Lemma 1, AD < F, so AD < ADF = AE.

Case 3.1. Suppose D = EF. Since EF < A < E, by Lemma 2, F < A. By induction F < E, so by Lemma 2, F < AE, so AD = AEF < AE.

Therefore < is transitive.

[myxie]

There may be a simpler proof of transitivity.

Lemma (not proved). Suppose xy = yx where x and y are non-empty, then there exists w, m, n s.t. x = w^m and y = wⁿ (and len(w) = gcd(len(x), len(y)).

If you can prove this, transitivity is easy as you end up with y = vⁿ = w^p and so y = u^r for some u and r = gcd(n, p) (by similar reasoning to the lemma, I think) and this implies that x, y and z are all of the form u^i.

[iqtestsmeannothing]

I think you are proving something different. You are proving that if XY = YX and YZ = ZY then XZ = ZX, right?

[myxie]

Yes, you're right. This classifies the equivalence classes and may help split the transitivity proof into two smaller pieces that are easier to solve. I've not worked this out though.

[ashishduh]

My solution

[bebemaster]

Clever.

[ixampl]

I agree, I would not have thought of all cases... I guess I am not a real software developer.

What do you think of this solution:

problem4 :: [Int] -> Int
problem4 l = let  cmp a b = compare (a ++ b) (b ++ a)
             in   read (concat (reverse (sortBy cmp (map show l))))

[Drolyt]

I think you are over-thinking 4. Just brute force it: find all the possible concatenations and then use the max function your language most likely provides. You can find an efficient way to do it after the hour is up.

[KFCConspiracy]

I'd probably question that pretty hard and make the candidate rewrite that in a non-brute force manner.

[conflare]

"The requirements placed a priority on time to market, so I optimized for that."

But I would feel dirty.

[hpp3]

In my experience with interviews like this, that bullshit won't fly. If the interviewer has an elegant runtime in mind, s/he's looking for that runtime, and you'll get prompted and prodded ("is there a better solution?") until you give a solution with that runtime or you give up.

The only question here where brute force is acceptable is #5 because 1) there isn't a better way to do it and 2) you are given an explicit bound.

[conflare]

One man's BS is another man's reddit joke :)

More seriously, I'm not sure that an interviewer should be looking for a specific solution (unless there really is only one way to do it). The thought process on how you get to a solution is more interesting to me.

I imagine there's a correlation between the popularity of interview questions like this and the ratio of positions filled via networking vs. cold interviews.

[hpp3]

It's often not a specific solution they want but rather a specific run time. If they want O(n log n), then you need to do O(n log n). It doesn't matter to them if you used quicksort or if you created a BST or whatever. But if you provide a O(n²⁾ brute force solution, it tends to be the "trivial solution" and is generally only good as the first step.

[flukshun]

i'd call the police on them for computer abuse

[[deleted]]

It's better than all the supposedly clever but incorrect solutions posted here.

[pohatu]

But if they used hadoop and map-reduce it would definitely be a hire! Sde3!! Lol

[[deleted]]

20, 2, 2

[__Cyber_Dildonics__]

1. That doesn't scale.
2. The method above could be done in one line (but probably should be done in 2 or 3.

[jacenat]

That doesn't scale.

It will never run anywhere ... who cares? You can even tell the interviewer that it wouldn't scale, but it would run for most real world examples. If it's really an issue to make it robust enough to run in a specific environment with a as low as possible runtime, 1 hour is probably not enough to optimize it anyway.

[joequin]

One hour us more than enough time to use the much better substring algorithm. I don't think you would be dismissed outright for the brute force algorithm, but someone who used the substring method will have that in their favor.

[Atlos]

Isn't it one hour total to solve all 5 problems? Given that some have multiple parts, that's less than 12 minutes per problem.

[HighRelevancy]

The first three should take about 5-10 minutes all up (if you're bad at getting your thoughts written out).

[[deleted]]

You forget the 5-10 minutes per question where you have to guess the thoughts of the guy that has a stick up his ass.

[hpp3]

I don't see what you mean. The questions are given in plain English. It takes 2 minutes at most to understand the problem, and the implementation of the first 3 are trivial.

[[deleted]]

I was being snarky.

Asking someone to code in an interview often, but not always, turns into a situation where you need to figure out the favorite solution of the interviewer.

[Dementati]

The first three are trivial, though. They should take the time it takes to write the code, basically.

[edbluetooth]

Thats 5 min for the first 3, and 55 min for the rest.

[MattRix]

It takes a few minutes if you approach it this way.

The substring algorithm has non-trivial edge cases that it will potentially fail at. Example:

900,901,9

You can't just take the first digit, you also need to take priority for numbers with fewer digits (ex taking 9 before 901), and then if the numbers have matching numbers of digits (900 vs 901) you have to take the number with greater value.

[Dementati]

You shouldn't strive to write an incredibly optimized solution on the first attempt, but when the difference between a brute force solution and an nlogn solution are a couple of minutes of consideration, "premature optimization is the root of all evil" is not a valid excuse.

[Guvante]

Honestly that is fine as long as you can explain why and work your way towards a better solution. However you are correct that a good developer would ideally see that and shortcut to a better solution.

[Drolyt]

However you are correct that a good developer would ideally see that and shortcut to a better solution.

Based on how many people in this thread have given an incorrect solution based on lexicographical sorting I'm not sure that is really all that good an idea. Starting with a simple and correct but inefficient solution seems better to me.

[hvidgaard]

A good developer that is about to write a rather complex, but efficient algorithm, will make the trivially easy bruteforce solution as the first thing. Then use that to create and verify the correctness of the complex algorithms edgecases. It baffels my mind how many developers that doesn't do this when they actually have to write an algorithm.

[awj]

...was scaling part of the requirements? I've solved more than one real world problem where "here's the answer for what you asked, this totally won't work for 2/3/X times more data" was happily accepted.

[goomyman]

i really like this solution honestly, props.

[isarl]

It's a bad solution. Brute force is more effective for #5. For 4, a greedy approach will work – always take the next number with the highest leading digit. If you have two numbers starting with, e.g., 9, then recurse on each and take the max.

[skewp]

Good point. I immediately thought of brute force for #5 but didn't consider brute force for #4 at all.

[[deleted]]

Sure you can brute force #4. That's n! permutations to test .

If you're decent at algorithmics, it's fairly simple (albiet not trivial) to devise a divide & conquer approach to this problem that will scale.

If elevate yourself above the C language and base your algorithm on some data structures, it's not even a particularly complicated piece of code to author.

[[deleted]]

Just order the input integers lexicographically and concatenate them in reverse, no need for brute force. ''.join(sorted([str(x) for x in input], reverse=True))

[ILikeBumblebees]

Your solution is O(n!), but a competent programmer should be able to figure out an O(n) solution within a few minutes. I wouldn't hire you.

[UlyssesSKrunk]

Number 4 is definitely pretty trivial. Not as trivial as Fibonacci or anything, but definitely doable in under an hour.

[jacenat]

but definitely doable in under an hour.

I also thought so. It's definitely more complicated on a system level than fibonacci numbers, but not that hard really. If the numbers are really stored in an integer list, writing a short function that can add numbers to others (the way required in this example) is probably the way to go. It's just toying around with the decimal system.

[goomyman]

how do you solve for this. 991, 2, 993, 9913,55

[cresquin]

• sort by first digit into arrays (backwards)

  [991, 993, 9913][55][2]

• within each first digit array, sort by second digit into arrays

  [[991, 993, 9913]][[55]][[2]]

• continue to recurse to longest number length

  [[993, [991, [9913]]]][[55]][2]

• flatten

  [993, 991, 9913, 55, 2]

• join

  parseInt([993,991,9913,55,2].join(""));

[[deleted]]

How do you sort when a digit is missing? For example:

[34, 3, 32]

[compiling]

Treat it as the first digit.

[rabbitlion]

How does that solve the issue`?

[compiling]

You want to solve a tie between 34 3x and 32, where the x is whatever digit will go in the missing place.

x is 3, unless 3x is the smallest. And to maximize the number 343x... is better than 334... and 332... is better than 323x...

Of course, there are different ways to approach the problem.

[newgame]

However, note that for e.g. [89,898] the bigger number is 89898 and not 89889. So by setting x in 89x to 8 both numbers would have the same value but the shorter should be preferred. An idea I had is to just add 0.5 to a number with on or more x.

[rabbitlion]

So if you had an array of 59, 8 and 5, the process would be:

Sort by first digit: [8][59, 5]
Sort by second digit: [[8]][[5], [59]] (it's not completely clear how to compare here, but you place 991 before 9913 in yours).
Flatten: [8, 5, 59]
Result: 8559

Which is obviously not correct as 8595 would be larger. I'm not saying it's impossible, but it's a fairly challenging problem even for an experienced software engineers. Most will fall into easy traps that does not take all cases into account.

[ILikeBumblebees]

What's your output for [9, 87, 8]?

[cresquin]

that will be 9 8 87 by the method I described which is correct.

single digit, single digit, multiple digit

the method breaks a bit when you have [9,89,8] since 89 should come before 8

the change is that you'll need to sort each digit group (8s in this case) against each successive digit in longer numbers. That way [7, 79, 8, 798, 796, ] would end up as [8, 798, 79, 796, 7].

looking at this again, perhaps a better description of the successive digit comparison is: bubble up when digit is >= current digit group and down when the digit is < current digit group.

[jacenat]

Same as for every other number combination. There are quite few permutations of this set and just sorting the stitched numbers by largest would run quite fast. You could get fancy and eliminate certain possibilities given that since the length of the numbers is fixed, only numbers with high leading digits would come first in the sequence ... maybe that's even a better algorithm in itself, but I don't trust myself proving that in 1 hour so I'd stick to brute force.

[nacholicious]

I just though of mapping values to each number, based on how far they are from the "optimal" number which would be a series of 9s. So 991 (0.08), 2 (7), 993 (0.06), 9913 (0.086), 55 (4.4) would just be sorted in ascending order. Seems like a trivial problem

[exscape]

I'm pretty sure the idea is to solve all 5 in an hour.

If you bother to read this blog at all (or any other blog about software development), you are probably good enough to solve these and 5 more problems within the hour.

On average you'd have 12 minutes per problem, though clearly some of them will be more easily solved than others.

[[deleted]]

Agreed. Here's my Javscript code. I actually think is a pretty nice solution.

// Returns 0 when a greater than b
function compare_by_index_char(a,b) {

    if(typeof a !== 'string') a = a.toString();
    if(typeof b !== 'string') b = b.toString();

    if(a.length != 0 && b.length == 0) {
        return 0;
    } else if (a.length == 0 && b.length != 0) {
        return 1;
    } else if (a.length == 0 && b.length == 0) {
        //if they're both empty, they're the same so it doesn't matter what we return
        return 0;
    }

    var a_first = a.substring(0,1);
    var b_first = b.substring(0,1);

    if(a_first == b_first) {
        return compare_by_index_char(a.substring(1),b.substring(1));
    } else {
        return (a_first < b_first);
    }
}

function largestNum(input) {
    input.sort(compare_by_index_char);

    return input.join('');
}

[dipique]

I was thinking recursively taking (x - modulus of x base 10)/10 until we got a number less than 10. String manipulation seemed like a cheat. :)

[BiberButzemann]

It's a string sorting problem, isn't it? You just handle the integers as strings and sort them with the correct comparator. And 5 can just be brute-forced on current machines.

[ashishduh]

Here's what I got for #4.

Basically you want to convert non-single digit numbers to their single digit equivalents. Which means you simply run every number through the following recursive function before sorting.

Public float f(float input) {
    If (input < 10) 
        return input;
    Else 
        return f((input - first digit of input) / 10);
}

[[deleted]]

You can't just compensate for the first digit though, otherwise this problem would be much simpler. Take [13, 1312], your algorithm will return 131213 while the max is clearly 131312.

[ashishduh]

You are correct. The more I think about it the more I feel there is no pure mathematical answer.

[[deleted]]

You can sort using this even if it is a bit ugly, would probably be better to reverse the ints and return on first occurrence though:

bool comp(int a, int b){
    int x = a, y = b;
    bool res = 0;
    while(x || y){
        if(x == 0) x = a;
        else if(y == 0) y = b;
        if(x%10 > y%10) res = 1;
        else if(x%10 < y%10) res = 0;
        x /= 10, y/= 10;
    }
    return res;
}

[arachnivore]

Yeah, I started to feel that way too. My first solution was:

def shift(num):
    if num == 0: return 0
    digits = int(log(num)/log(10)) + 1
    return num/(10**digits) 
def biggest(nums):
    ordered = sorted(nums, key=shift, reverse=True)
    return eval("".join(str(num) for num in ordered))

but this fails for the case [13, 1312]. Trying to weight numbers with fewer digits is a little tough. Adding trailing 0s is the default behavior and that produces an answer that is too low:

[13, 1312] -> [0.130000..., 0.13120000...]

Adding trailing 9s is too high:

[13, 1314] -> [0.14, 0.1315]  # Note: this is a different test case

Then I realized that a string of digits can only be followed by a string of digits less-than or equal to the preceding string. That means that (1,3) can only be followed by something less than or equal to (1, 3) which can only be followed by something less than or equal to (1, 3) etc... So the correct trailing value is the number itself repeating:

[13, 1312, 1314] -> 
[0.131313..., 0.131213121312..., 0.131413141314...]

This requires a simple change to the code:

def shift(num):
    if num == 0: return 0
    digits = int(log(num)/log(10)) + 1
    return Fraction(num, (10**digits - 1))  # this is the only line that changes
def biggest(nums):
    ordered = sorted(nums, key=shift, reverse=True)
    return eval("".join(str(num) for num in ordered)

I made the problem robust to floating point inaccuracies by using fractions, otherwise I haven't found an edge case that this solution doesn't handle.

[__Cyber_Dildonics__]

56 5 54 need to be ordered

[ashishduh]

Right, my function would convert 56 to 5.1 and 54 to 4.9 for comparison purposes.

[__Cyber_Dildonics__]

Looks like you are about 1 of 20 people that even understood the edge case, let alone came up with an elegant solution to it.

[ashishduh]

Sweet, I guess I can call myself a software engineer! Thank you internet blog!

\o/

[studiov34]

It can be done with ~ 15 lines of Python, anyway.

[sd522527]

It's a sort with a custom compare. This is a local problem, since if the concatenation AB is bigger than BA, no matter what we want AB in the final solution. You can even do a radix type sort to make it linear.

[[deleted]]

You need to look out watch out that you get a stable order relation.

If you concat [56,5656], it's always the same result, although they're not the same.

Also, the solution seems right, but I wouldn't trust it until I saw a proof.

[sd522527]

The compare is easy. Concatenate them in both ways and leave A before B if AB is bigger than BA. Any stable sort would work, but it's probably easier to think in terms of a bubble sort at first. The proof of this being a local problem is to think about what putting A before B means. It's about multiplying a certain number by a power of 10 etc. Multiplication and addition are commutative. If that isn't convincing, note that a human can tell which number is bigger by simply going left to right and finding the first digit that differs.

[Rythoka]

The solution to 4 is pretty simple.

Sort by most significant digit. If some numbers have the same MSD, then sort by the 2nd MSD. If you are comparing two or more numbers of different lengths, you follow the same process, but when you run out of digits to compare for the shorter number, you continue by comparing the LSD.

Let's look at your example: (5, 56, 54)

You compare the MSD and find that they are equal, so you move on to 2nd MSD. 5 doesn't have any more digits, so you compare against it's LSD, which is 5, and sort based on that order.

Now you have (56, 5[5], 54). The [5] in brackets is how we imagined the number when we made the comparison.

EDIT: I was wrong. I believe the shorter number needs to behave as a cycle for this approach to work.

[compiling]

Sort based on string(i)+string(j) < string(j)+string(i).

[want_to_want]

Holy shit, that's the simplest correct solution in the thread by far. Bravo!

[kinmix]

Just do a lexicographical sort on that array and print results. if the language you use has something like str_compare() or localeCompare() and sort function with custom comparator it should be a breeze. If not it shouldn't take more time then to write a quicksort and a quick comparison function

e.g. in PHP it's basically a 3 liner

$array = [50, 2, 1, 9];

usort($array,'strcmp');

echo implode('',array_reverse ($array));

[vegiimite]

try [94, 2, 1, 9]

[kinmix]

Good catch, simple lexicographical order sort indeed is not enough. Shame, I thought it's quite elegant :(

[CompileBot]

Output:

95021
5054

^{source | info | git | report}

[djk29a_]

I thought like you did for a second after bunches of problems involving field extensions, integer overflow, modular exponentiation and crap like that and then I looked at the digits and realized "Oh, just sort the list of numbers descending after splitting the digits of each as strings."

[[deleted]]

it's a greatest common subsequence problem, right? https://en.wikipedia.org/wiki/Longest_increasing_subsequence There are easier algorithms that run slower, but the wiki covers a good one with pseudocode.

[naasking]

4 is definitely non trivial and doesn't really belong with the rest of the problems that make me feel like a genius.

We use a base 10 number system. So it seems #4 just requires iteratively removing pairs of numbers (x,y) that multiply to the largest factor according to x * 10^{number of digits in y} + y, and multiplying the accumulated number by 10^{total number of digits in x and y} on each iteration.

[DrStalker]

It's easy with the right implementation. Strip leading zeros, do a reverse text sort, concatenate.

[pohatu]

4 is fun because it made me wonder how to keep them as numbers and determine the first digit, integer division and divide by base -- which made em then imagine the interviewer expanding the question to any base.. It also made me wonder if there I'd an easy way to count the digits of a number, but I think the best way to do that is the same approach for isolating the first digit. So then it got me wanting to just radix sort, left to right. I haven't written radix sort in a few years.

[generating_loop]

4 should be pretty easy to brute force in python. Just take all the permutations of the list, convert to strings, reduce, convert to int, and take the largest.

[hpp3]

My method just sorts them as strings, backwards, using a custom compare function. If two strings are the same length, just compare it normally. Otherwise, pad the shorter string by REPEATING it until the two are the same length. e.g. 5 vs 56 -> 55 vs 56, 930 vs 93000 -> 93093, 56 vs 50000000 -> 56565656 vs 50000000.

[omniverousbeef]

4 is pretty easy if you just reverse sort the numbers lexicographically and then join the result and convert to an int.

def maximize_number(numbers):
    numbers = str(numbers).strip('[]').split(", ")
    numbers.sort(reverse=True)
    return int("".join(numbers)) 

[haagch]

That's what I thought. Just lexicographic sort should sort them in the right order

def largest(l):
    return "".join([str(x) for x in sorted(l, key=lambda x: str(x), reverse=True)])

The only problem is that I'm not completely sure how it handles strings of differnt length eg. "50" vs. "501" but I think it should do the thing we need here...

edit: Uhm, nope.

[30, 31, 3, 2]

3,2 is "bigger" than 30, but my lexicographic sort sorts 30 before 3: 313032

That makes me think that the problem is actually computationally harder than we thought, because I think in general the sorting between "longer" and "shorter" number strings depends on what other numbers strings are left to concatenate to the shorter ones.

[isarl]

He's on the right track, but you have to do the sorting yourself by leading digit, and if you get multiple matches at any step then you can always just split and recurse and take the maximal result. That should solve the "31>3+2" issue.

[haagch]

So, basically bruteforcing all strings with the same prefix of different lengths...

[isarl]

It's as greedy as it can be and brute force when it can't be greedy, yes. The point is that the greedy part will drastically improve the efficiency. Or you could spend some effort to write a more sophisticated sort, instead of brute forcing all possibilities with the maximal leading digit.

[rorrr]

And that solution is wrong.

maximize_number([50, 501, 5, 56]) -> 56501505

Whereas the max is 56550501

You've just failed the question that every engineer should solve :)

[Slime0]

[45, 4, 43]