So I was browsing Facebook, my second favorite social network (my most favorite being Notecentric, of course). Unbeknownst to most, Facebook has a bunch of random pages linked to from their footer. There’s a pretty cool developer blog, and other random junk. I was looking at the jobs section (I need something to do this Summer) and I came across a section called “Puzzles.”
There’s just a bunch of programming puzzles. Some are harder than others. As in programming wise and computationally too. The Prime Bits problem seemed pretty easy (as in, doable in about an hour) so I did it. I guess I’ll just send it to Facebook and tell them that I’m looking for a Summer internship or something.
The only thing is, it seems like the puzzle is too easy. What if they use this puzzle as some kind of red herring to capture lazy programmers in order to blacklist them? Or maybe there’s a way to be clever that I didn’t think of? I’ll probably send it anyway. It only took me like an hour. It’s probably mostly just to see what peoples’ programming styles are like (OOP, functional, etc.).
What’s the point of my post? I dunno, but Facebook seems like a pretty fun place to work for if they just randomly post programming puzzles for people to solve.
did you get this part ?
Your implementation should have a running time faster than O(n), where n is b - a.
id like to see how you solved it.
Hmmm. I could’ve sworn I didn’t see that “running time must be better than O(n)” when I looked at the problem for the first time… Weird.
I have a feeling my solution isn’t O(n). So I might take a look at it and try again.
A O(n) implementation when the possible inputs to that function are 64-bit integers would take thousands of years to finish running (on a modern GHz computer), and still on the order of years when run on the fastest TFLOP supercomputers available today.
So yes, if you thought it was “too easy” (in the sense that you gave a linear-time solution that just examines all the numbers in the range), then you probably fell for their red herring.
Right, I know what O(n) notation is… I didn’t see that less than O(n) requirement, which makes this problem a lot more interesting than it was before.
And by more interesting, I mean I might actually put some thought into it now!
also, some guy on reddit used a highly mathematical language called J to solve it, and the program (which is utterly unreadable) supposedly can solve the problem even for the range between the numbers 50! and 100! (where 50 factorial is, according to the post, 30414093201713378043612608166064768844377641568960512000000000000).
This problem took me two days, but I finally solved it. It took about 3 separate “eureka”s for me to figure it out. It’s nice to not be able to find a solution online, either
It can be done in worst case log(n) or log^2(n) depending on whether you consider array mapping to be one computation or not.
On my system it calculates the number of primes between 482904823908 and 905848920 [answer: 317303301] in about .002 seconds… a slight improvement over 1000 years.
As per the purpose of this problem, it is definitely a very difficult problem — each of their problems is designed to appeal to a certain type of engineer. This one seems to me to appeal to the “C guru” or “Comp Sci Nerd” who enjoys handling things on the bit level. Their other problems are for general problem solvers and PHP gurus, it seems.
-sam
Hey, I wrote my own implementation and posted it: http://20bits.com/2007/04/27/facebook-job-puzzles-prime-bits/
How does it compare to yours?