Facebook Programming Puzzles – Prime Bits Revisited
So I got a comment on my original post about the Facebook Programming Puzzle called “Prime Bits” that asked:
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.
I felt really stupid for not catching that part until I checked the Google cache of the page. Apparently Facebook added that requirement some time after April 2nd and, presumably, getting a lot of inefficient entries (mine included).
It’s also funny to note that if you look at the actual html, there’s a fun message hidden in comments that reads “with ‘efficient’ meaning whatever you think it ought to mean.” Touché, facebook, touché.
Off the top of my head, I can think of a way using dynamic programming to make the problem a lot more efficient. I’m not sure whether or not it’s just an amortization hack, or an actual better than O(n) implementation, technically.
Okay, so I went ahead and coded up the dynamic programming version. The running time actually does increase at a less than O(n) rate, so I think it counts. Maybe I’ll plot out the running time growth for good measure. I believe it’s in the neighborhood of log(n). I guess I’ll send this new version along with my resume again, and see if they’ll respond this time 🙂
Also, Rest in Peace, Facebook Guy. You’ll be sorely missed.