"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 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
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
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:
"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
#include
#include
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
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
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
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 (or unsigned __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!
"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
#include
#include
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