ronin

"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 <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
  • Current Music
    http://genius.com/Monzy-so-much-drama-in-the-phd-lyrics
ronin

A scale so sensitive it can track your heartbeat.

I didn't think my respect for Jim Williams could get any higher. This, however... this is the nuclear option. I am literally in awe. I have seen the face of my god, and it is Jim.



"The extremely high resolution of this scale requires filtering to produce useful results. Very slight body movement acting on the platform can cause significant noise in A3’s output. This is dramatically apparent in Figure 12’s tracings. The total force on the platform is equal to gravity pulling on the body (the “weight”) plus any additional accelerations within or acting upon the body. Figure 12 (Trace B) clearly shows that each time the heart pumps, the acceleration due to the blood (mass) moving in the arteries shows up as “weight”. To prove this, the subject gets off the scale and runs in place for 15 seconds. When the subject returns to the platform the heart should work harder. Trace A confirms this nicely. The exercise causes the heart to work harder, forcing a greater acceleration-per-stroke."

http://www.linear.com/docs/4134
ronin

Ye olde game-show button circuit.



You know that typical game-show or quiz-bowl buzzer system, where each contestant gets a button and the first to press it is allowed to answer the question the host asked?

Someone asked for a circuit to implement such a system. I have dim memories of seeing designs for such systems in the distant past, but nothing I could remember clearly. So I decided to design my own.

( Collapse )
ronin

Fast (over-)estimation of sqrt(N) for memory constrained computers.

Say you're trying to use a computer to factor a number, N. N is large and you want to stop as soon as possible in the case that it's a prime.

If you don't have a lot of memory to work with, then the obvious thing is some kind of optimized trial division. (Which is not the same as - and not to be confused with - the Sieve of Eratosthenes. SoE has a lower time complexity, but requires far more space.)

The first key point about such trial division algorithms is that you should never divide by an even number other than 2. The reasoning for this is, I hope, obvious. In short, after trying to divide N by 2, thereafter only try dividing by odd numbers. (Of course in theory we would like to try only dividing by primes. But if we're in a space constrained situation, we probably don't have a list of all primes between 0 and N sitting around.)

The second key point about trial division algorithms is that they need to stop trying possible factors when they reach sqrt(N). If you've tried every (odd) number up to sqrt(N), and N isn't evenly divisible by any of them, then give up: N is prime.

You can compute sqrt(N) outright, but honestly I wouldn't even do that. Some compilers/languages have an isqrt(N) built-in that gives you the nearest integer larger than, or equal to, sqrt(N). This is exactly what you want. In addition, most isqrt()s are constant run time. (It's usually a small constant, even.)

If for some bizarre reason you don't have isqrt(n), you can synthesize it by using Newton-Rapheson (see Wikipedia page on isqrt). However, even doing that may not be worth the trouble. Why? Because to do Newton-Rapheson, you need to start the N-R process with a value near the root you're trying to find. So one way or another, you're going to need a reasonable estimate of isqrt(N).

So, what are other ways to get a decent estimate of sqrt(N)? Again subject to the constraint that the estimate must not in any circumstances be less than sqrt(N). Hacker's Delight (which you should read) suggests just using the next power of two greater than sqrt(n), and gives four lines of branch-less C code to compute it. However, I think we can do better...

Observation: If N contains D digits, then sqrt(N) contains D/2 digits. This gives us order of magnitude.

Then, we can do a table lookup on the first two digits of N:

00-03: 2
04-08: 3
9-15: 4
16-24: 5
25-35: 6
36-48: 7
49-63: 8
64-80: 9
81-99: 10

(If you actually implement this algorithm, I suggest you express the above table as a nine item array. 2-10 are your array indices and 3, 8, 15, 24, etc are the values in the corresponding array slot. Walk the array and compare the value in each slot with your first two digits of N. Stop when first two digits of N are greater, and then go back one index. The index value itself is your table lookup number. Why do it this way? Because we're on a space-constrained system. So a worst-case twenty instruction lookup is less bad than a hundred item array.)

Now we take the table lookup number, slap on D/2 zeros, and voila - we have our estimate. And due to the way the table is structured, it's guaranteed to be an overestimate. Exactly what we want.

Example: Estimate the square root of N = 4,294,967,197 which is a prime number near 2^32. sqrt(N) = 65535.999244689937, so our estimate must not be below 65536.

There are 10 digits in N, so there will be 5 digits in the estimate. The first two digits of N are 42, so our lookup is 7. Thus our estimate is 7 * 10e5 = 70000.

How good an estimate is that? 70000 / 65536 = 1.068115..., so our estimate is within 7%. And, as required, not less than the real square root.

If you're still sweating the difference between the estimate and the correct number, then go ahead and do a couple iterations of Newton-Rapheson with the estimate. N-R converges quadratically, so even three iterations should get you almost an order of magnitude improvement.

There are many ways to optimize the above for binary representation, but I leave that as an exercise to the reader.


(Eh? You want to know an efficient way to determine the number of digits in N? Fine, ya lazy bum, I'll google it for you: http://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer

What? You can't figure out an efficient way to determine the first two digits of a binary number on a CPU without hardware divide? 2^4 = 16, mang! Find the most significant 1 bit, and the next 3 after that. Those four bits determine the first two base-ten digits of the number. Finding most significant 1 bit? Binary search by masking half the bits (the least significant half) and comparing with zero.

Jeez, you ask a lot of questions!)
ronin

Multi-meter? Moar liek MELTY-METER, amirite??

Oh the lulz...

One our our techs at work was tasked with repairing and testing a very large (1,000 W) power supply unit. Meet the Sorensen DCS 20-50:


The front panel

( Collapse )

Post-script: A fresh set of leads was plugged into the meter. The prongs that held the HRC fuse inside had melted off the PCB, but aside from the 20A current measurement mode, the meter appears to be working just fine! I tip my hat to you, Wavetek - that is one tough meter!