Friday, December 6, 2019

“No ‘x’ in ‘Nixon’”

I just had a phone screen where they asked if I could write a palindrome detector. I wrote a recursive and an iterative version. I like the recursive solution because it is so simple. There are only three equations:

  • An empty string is a palindrome.
  • A string with one character is a palindrome.
  • If a string starts and ends with the same character, and the substring between them is a palindrome, then the entire string is a palindrome.
I wrote them the iterative version so I wouldn't look like an idiot.  The iterative version is generally faster with a standard compiler, but it is more complex.  Not much more complex, but still, you have to keep track of two indexes into the string and how close they've gotten to each other.

The recursive solution is just more elegant.

Apparently I cannot post comments on my own blog.  Well, I can edit the post.  "if s[pos] != s[-pos-1]" sure looks like two pointers, but to be fair, the recursive solution hides its pointers in the string structure or in the slices if it is using them.  As for "(string= x (string-reverse x))", there is something elegant in something that crude.
at

3 comments:

  1. ClémentDecember 6, 2019 at 4:38 PM

    Why do you need to keep track of two indices in the iterative solution?

    def palindrome(s):
        for pos in range((len(s) + 1) // 2):
            if s[pos] != s[-pos-1]:
                return False
        return True

    (which is just all(s[pos] == s[-pos-1] for pos in range((len(s) + 1) // 2)))

    (How do you post code in Blogger comments?)

    ReplyDelete
  2. UnknownDecember 10, 2019 at 4:09 AM

    alternative formulation:
    (string= x (string-reverse x))

    ReplyDelete
  3. TrambDecember 14, 2019 at 5:11 AM

    Elegant for blog posting does not mean you don't want the imperative version in production code :)
    It's very probably faster in optimized builds, so much faster in unoptimized builds, doesn't need allocations, and not that much harder.
    It factors in elegance for me, terseness is not the alpha and omega :)

    ReplyDelete