DevDrill #3

Today’s DevDrill was a four-question contest made up of two easy and two medium questions. I finished an easy and medium question in 45 minutes although I didn’t solve the medium in O(logn).

What Did I Learn?

Sieve of Eratosthenes

An “ancient algorithm” according to Wikipedia. I may have heard of this algorithm once in my life. I sure didn’t remember it for the first easy programming problem. Although, I like to think that I was heading toward this sieve when I spoke about removing all even numbers from consideration.

The Sieve of Eratosthenes reminds me of a struggle I face with programming puzzles: intuition vs. memorization. Am I supposed to be able to intuit the Sieve of Eratosthenes on the fly, or am I supposed to memorize it? I can’t help but feel like I’m lost if I have to memorize this. There’s just too much to remember. I may have been told the Sieve of Eratosthenes once. I’ve solved the Towers of Hanoi a few times too. Too much time passes in between their uses though. I have to hope to develop an intuition for these puzzles.

Stick with Binary Search

I abandoned binary search too early in my solution to the third problem. I could have stuck with it all the way to find the correct insertion index. Instead my solution ends up being O(logn + n/2). While I think think this is still technically O(logn), I didn’t need to do that last while loop that tacks on the n/2.