?

Log in

"Five programming problems every Software Engineer should be able to solve in less than 1 hour." - Adventures in Engineering
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2015-05-10 10:11
  Subject:   "Five programming problems every Software Engineer should be able to solve in less than 1 hour."
Public
  Mood:white & nerdy
  Music:http://genius.com/Monzy-so-much-drama-in-the-phd-lyrics
There's been a fair bit of discussion over at Reddit about this blog post: https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour

To clarify one point right from the start: The author said that he expects applicants to be able to solve all five problems in a single hour. Not one hour per problem; all five problems in the same hour. (He also (much more than an hour) later posted a solution for problem #4 that was incorrect, much to the hilarity of /r/programming/.)

Problems 1 and 2 are trivial, I agree that anyone who wants to get their paycheck from programming should be able to do those in their favorite language in less than an hour very easily. (I didn't time myself on those, but I'm sure I came in under 15 mins to solve the pair.)

Problems 4 and 5 are tougher. With problem #4 you can probably get away with using a brute-force solution, and the resulting program will still run quickly enough. So in that way you can probably solve problems 1-4 in an hour. (Though depending on programming language traps - see below.)

Problem 5 is much, much tougher. Personally, I don't think I would have even gotten started on problem 5 within the hour. My personal opinion is that the inclusion of problem #5 in the same hour as problems #1-4 invalidates this test.


But I actually don't want to talk about problem 5, or even problem 4. I want to talk about problem 3, the Fibonacci one. I think Reddit adequately covered problems 4 and 5. Problem 3 on the other hand wasn't talked about much, and can be either briefly interesting or really goddamn annoying depending on the language you use.

My first crack at problem 3 was a naive solution in C (gcc 4.2.7, x86) using long long ints. The last five or so Fibonacci numbers that version of the program spit out were way off. So at that point I went and typed lg(218922995834555169026) (log base 2 of the 100th Fibonacci number) into Google and got lg(218 922 995 834 555 169 026) = 67.5689854. So it would take at least 68 bits to (correctly) represent the 100th Fibonacci number.

The C standard is flexible about how many bits are allowed to be in an int, long int, long long int, etc - the ony rule is that the larger data types must have at least as much storage as the smaller ones. I wonder how many bits are in a long long with my particular compiler?

owl:~/fiveproblems> cat sizeof-longlong.c
#include <stdio.h>

int main(void)
{
        printf("sizeof(long long int) = %zu\n", sizeof(long long int));
        return 0;
}
owl:~/fiveproblems> gcc -Wall -Wextra -pedantic sizeof-longlong.c
owl:~/fiveproblems> ./a.out
sizeof(long long int) = 8
owl:~/fiveproblems> 


Well, there's your problem! long long is only 8 bytes aka 64 bits. It can't accurately represent a 68 bit integer.

(This is probably obvious, but the "%zu" format specifier for printf() is a special GCC thing to allow you to easily print out size_t types (what sizeof() returns) without casting them to something else. This isn't very portable across architectures or compilers. But since I only wanted to know how may bits in a long long on this specific compiler and architecture, that's OK.)


Now that I was certain a long long int wouldn't work, I wondered if a floating-point representation might help. It might not get the answer precisely down to the 17th decimal place, but I thought maybe the results would be correct if they were rounded to the nearest integer. Wikipedia said that long double was usually an 80 bit extended precision type on x86 GCC, so it looked like it was worth a try, in spite of the fact that the mantissa in an 80-bit extended precision is only 63 bits long. So I quickly changed the program to use long doubles instead. When I ran this version of the program the last few numbers were much closer, but still not right:

#include <stdio.h>


int main(int argc, char **argv)
{
        int i;
        long double fibs[100];

        fibs[0] = 0L;
        fibs[1] = 1L;

        for(i = 2; i < 100; i++)
        {
                fibs[i] = fibs[i-1] + fibs[i-2];
        }

        printf("First 100 Fibonacci numbers =\n");
        for(i=0; i < 100; i++)
        {
                printf("%.0Lf\n ", fibs[i]);
        }
        printf("\n");

        return 0;
}
owl:~/fiveproblems> gcc -Wall -Wextra -pedantic fibs-longdouble.c
fibs-longdouble.c: In function ‘main’:
fibs-longdouble.c:4:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
fibs-longdouble.c:4:27: warning: unused parameter ‘argv’ [-Wunused-parameter]
owl:~/fiveproblems> ./a.out
First 100 Fibonacci numbers =
0
 1
 1
 2
 3
 5
 8
 13
 21
 34
 55
 89
 144
 233
 377
 610
 987
 1597
 2584
 4181
 6765
 10946
 17711
 28657
 46368
 75025
 121393
 196418
 317811
 514229
 832040
 1346269
 2178309
 3524578
 5702887
 9227465
 14930352
 24157817
 39088169
 63245986
 102334155
 165580141
 267914296
 433494437
 701408733
 1134903170
 1836311903
 2971215073
 4807526976
 7778742049
 12586269025
 20365011074
 32951280099
 53316291173
 86267571272
 139583862445
 225851433717
 365435296162
 591286729879
 956722026041
 1548008755920
 2504730781961
 4052739537881
 6557470319842
 10610209857723
 17167680177565
 27777890035288
 44945570212853
 72723460248141
 117669030460994
 190392490709135
 308061521170129
 498454011879264
 806515533049393
 1304969544928657
 2111485077978050
 3416454622906707
 5527939700884757
 8944394323791464
 14472334024676221
 23416728348467685
 37889062373143906
 61305790721611591
 99194853094755497
 160500643816367088
 259695496911122585
 420196140727489673
 679891637638612258
 1100087778366101931
 1779979416004714189
 2880067194370816120
 4660046610375530309
 7540113804746346429
 12200160415121876738
 19740274219868223168
 31940434634990099906
 51680708854858323072
 83621143489848422976
 135301852344706746048
 218922995834555169024

owl:~/fiveproblems>


So now, I was kinda stuck. I knew that long double wasn't going to do it either. I wasn't about to write my own BigNum library, time was critical here. I had heard about some new, not very standard thing with 128 bit ints, so I went Googling, and found this:

http://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc

Two things you should take away from reading that:
  1. GCC (with -std=c99) does support a 128 bit integer, __int128 (or unsigned __int128 if you prefer).
  2. GCC does not have a printf() format specifier for printing out 128 bit integers! You will have to write your own function to print out 128 bit ints!

(As an aside, let me say: the second item is total bullshit. I can't believe the people maintaining GNU libc would put a __int128 type into the language but NOT give you a way to print it out. The entire reason computers were invented was so they could do the math for us and tell us the answer, instead of having to do it ourselves!

"Well it's open-source, why don't you contribute and fix it?" Because my time has value. This whole discussion started with a set of five problems that had to be solved within an hour. If I have to spend weeks REWRITING THE GODDAMN COMPILER AND STANDARD LIBRARY then I've already failed.

Yes, GMP is a thing. And, hallelujah, it even comes with routines to print out the numbers it manipulates! But I shouldn't have to resort to that when there's an __int128 in the standard library.

Did I just choose the wrong language, trying to use C for large integers? Quite possibly so. Those of you who write code in Java probably know that Java has a BigInteger class that does arbitrary precision integers. Is C so crusty and ancient and badly curated that it's time to abandon it for Java? Because if so, I will. I would prefer to keep C as my go-to language. But if it's gonna ultra-fail on the simplest of things, like printing out an integer...)

So, finally, here's what ended up working (print_u128() function shamelessly copied from that StackOverflow page above):

owl:~/fiveproblems> cat fibs.c
#include <stdio.h>
#include <inttypes.h>
#include <stdint.h>


typedef unsigned __int128 uint128_t;

/*      UINT64_MAX 18446744073709551615ULL */
#define P10_UINT64 10000000000000000000ULL   /* 19 zeroes */
#define E10_UINT64 19

#define STRINGIZER(x)   # x
#define TO_STRING(x)    STRINGIZER(x)

static int print_u128(uint128_t u128)
{
    int rc;
    if (u128 > UINT64_MAX)
    {
        uint128_t leading  = u128 / P10_UINT64;
        uint64_t  trailing = u128 % P10_UINT64;
        rc = print_u128(leading);
        rc += printf("%." TO_STRING(E10_UINT64) PRIu64, trailing);
    }
    else
    {
        uint64_t u64 = u128;
        rc = printf("%" PRIu64, u64);
    }
    return rc;
}


// A GCC-specific trick to silence "unused variable" warns w/"-Wall -Wextra".
#define DIABLE_WARN_UNUSED __attribute__((unused))

int main(int DIABLE_WARN_UNUSED argc, char DIABLE_WARN_UNUSED **argv)
{
        int i;
        uint128_t fibs[100];

        fibs[0] = (uint128_t)0;
        fibs[1] = (uint128_t)1;

        for(i = 2; i < 100; i++)
        {
                fibs[i] = fibs[i-1] + fibs[i-2];
        }

        printf("First 100 Fibonacci numbers =\n");
        for(i=0; i < 100; i++)
        {
                print_u128(fibs[i]);
                printf("\n");
        }

        return 0;
}
owl:~/fiveproblems>
owl:~/fiveproblems> gcc -std=c99 -Wall -Wextra -pedantic fibs.c
fibs.c:6:18: warning: ISO C does not support ‘__int128’ type [-pedantic]
owl:~/fiveproblems>
owl:~/fiveproblems> ./a.out
First 100 Fibonacci numbers =
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738
19740274219868223167
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
owl:~/fiveproblems>


And for the record: pulling all the teeth and kicking all the dead whales down the beach that I had to, in order to make this program work, ended up taking two to three hours. So clearly, I'm not worthy to be a programmer. :P
Post A Comment | 5 Comments | Share | Link






Jon: satchel
  User: j_b
  Date: 2015-05-10 19:46 (UTC)
  Subject:   (no subject)
Keyword:satchel "what"
There's some Doing Big Math Things lib that GCC requires for some of its more esoteric optimizer-fu - could that have helped the C-with-hardnums issue?
Reply | Thread | Link



Ben Cantrick
  User: mackys
  Date: 2015-05-10 20:17 (UTC)
  Subject:   (no subject)
Because I don't know what library you're referring to, I don't know the answer to that question.
Reply | Parent | Thread | Link



Jon
  User: j_b
  Date: 2015-05-11 18:43 (UTC)
  Subject:   (no subject)
https://gmplib.org/
Reply | Parent | Thread | Link



Alex Belits
  User: abelits
  Date: 2015-05-10 22:28 (UTC)
  Subject:   (no subject)
You can always use divide and modulo, and to get chunks of decimal representation of a number, and print their zero-padded text representations in a sequence. Typical such procedure simply used "chunks" one decimal digit long, but nothing prevents people from using 19-digit or 9-digit ones (so they will fit into 64-bit or 32-bit unsigned that can be printed).
Reply | Thread | Link



Ben Cantrick
  User: mackys
  Date: 2015-05-11 00:51 (UTC)
  Subject:   (no subject)
Very true. And indeed that's pretty much what print_u128() does.

I just think that if GCC is going to include a 128 bit type in their libc, they should also add a way to print it. Even if it's not printf(). Something.
Reply | Parent | Thread | Link



browse
May 2015