"Five programming problems every Software Engineer should be able to solve in less than 1 hour."
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
The C standard is flexible about how many bits are allowed to be in an
Well, there's your problem!
(This is probably obvious, but the "%zu" format specifier for printf() is a special GCC thing to allow you to easily print out
Now that I was certain a
So now, I was kinda stuck. I knew that
http://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc
Two things you should take away from reading that:
(As an aside, let me say: the second item is total bullshit. I can't believe the people maintaining GNU libc would put a
"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
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 (
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
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 int
s. 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 double
s 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:
- GCC (with
-std=c99
) does support a 128 bit integer,__int128
(orunsigned __int128
if you prefer). - 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