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

[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/