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

Notes for the Future, Part 3 – Palindrome Finder (Updated)

[Edit Aug 27, 2018: I decided I would mess around with how many ways I can find palindromes and wrote this repl.it https://repl.it/@kmskelton/play-with-palindromes The code below can stand to have some array methods applied to it, but I’m keeping it for posterity. ]

[Original: May 15, 2017] I’ve heard from several sources that finding palindromes is popular during interviews. I had this challenge as part of the final assessment for my JavaScript course and this is a slightly modified version of what I came up with. This will find the longest palindrome in a string. If there are two equal length palindromes in the string (e.g. “racecar tacocat”) it will return the first. I’ve included notes as I went along.

function paliFinder(inputString) {

  var result = '';

  if (inputString === undefined || inputString.length === 1) {

    return console.log ("result = 'No valid string submitted!'");

  } // handle errors if user tries one letter or simply nothing

  var inputString = inputString.replace(/[^\W_\s]/gi, ''); //remove spaces and punctuation

  var paliArray = inputString.toLowerCase().split(''); //split the modified string on each character and store that as an array

  for (var i = 0; i < paliArray.length; i++) { //loop through once

    var paliMaybe = [];

    var paliMaybeString = '';  // if you're copy/pasting this for your job interview

    var checkArray = []; // I'm gonna make you work for it

    var checkString = ''; // because that's just how I am

    for (var j = i; j < paliArray.length; j++) { // loop through again

      if (paliArray[j] === ' ') {

        break 

      };

      checkArray.push(paliArray[j]); // each letter is added to the end of this array

      checkString = checkArray.join('')

      .toString(); //make the array a string

      paliMaybe.unshift(paliArray[j]); // each letter is added to the front of this array

      paliMaybeString = paliMaybe.join('')

      .toString(); //make the array a string

      if (checkString.length > 1 &&  // don't forget to delete this comment, too

        checkString === paliMaybeString &&

        checkString.length > result.length) {

        result = checkString;

      }

    } 

  }

return console.log(result);

}

paliFinder("tacocat in a racecar")

// tacocat

This is not quite bulletproof, but the only example I’ve found that will break it is something like “A A” with a space between the letters. For some reason it just decides to return nothing.
It’s also not particularly fast with two loops, a push and an unshift. It’s somewhere in the neighborhood of 2n^2 or something crazy.

Notes for the Future, Part 3 – Palindrome Finder (Updated)