Dutch National Flag Problem and Code Golf

Last night at the Interview Preparation Night meetup that I host, I was asked to implement the Dutch National Flag problem on the whiteboard. The way it was presented to me was: given an array and a pointer element whose value acts as a pivot, return an array that has all the values less than the pointer to the left of the pointer, the pointer, and all values greater than the pointer to the right of the pointer.

I came up with a solution that works, and is fast, but it led to a discussion of expectations when the asker changed the game “oh, it’s supposed to be done in quicksort.”

Here’s all of the relevant code in one spot: https://repl.it/@kmskelton/Dutch-National-Flag-variations If you’d rather not take the time to check it out, I’m adding my comments and thoughts below.

The best implementation depends on the bottleneck in the system.
If I have to do this on a RaspberryPi I’d probably try my implementation and see if there’s still storage space; if not, let’s implement best_dnf. Same if I’m doing this on a cloud computing platform because there’s probably a storage limitation. If I’m in a browser I’d use my implementation because I’ll use all of your system’s resources all day.


These “code golf” answers drive me nuts. Essentially you can’t get to EPIP’s answer unless you a) know it or b) have most of the standard library memorized. I hadn’t seen a,b=b,a before, so I had to look it up:

https://stackoverflow.com/questions/21047524/how-does-swapping-of-members-in-the-python-tuples-a-b-b-a-work-internally

Python separates the right-hand side expression from the left-hand side assignment. First the right-hand side is evaluated, and the result is stored on the stack, and then the left-hand side names are assigned using opcodes that take values from the stack again.

Advertisements
Dutch National Flag Problem and Code Golf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s