Hacker News Reader

Comment by GlennS | Hacker News Reader

Is the answer to (2) just something like this?

If len(word) is even, check that all the characters in it appear an even number of times.

If len(word) is odd, check that all the characters in it appear an even number of times except 1.

I don't think you need to test for the length of the word. You just need to have at most 1 character that appears an odd number of times. My first instinct would be to scan the word character by character and use a set to check the number of occurrences:

  has_palindrome(word)
      s = empty_set
      for c in word
          if s.contains(c)
          then s.remove(c)
          else s.insert(c)
      return s.size() <= 1

If I'm not allowed to depend on an existing set implementation, I would likely fall back to a quadratic solution that counts each character. If there are special performance concerns I may sort the word before hand, or implement a special kind of set.

abcba is a palindrome

Yes it is, and it wouldn't fail my algorithm:

  a -> not in set -> add a    (a)
  b -> not in set -> add b    (ab)
  c -> not in set -> add c    (abc)
  b -> in set     -> remove b (ac)
  a -> in set     -> remove a (c)
  Set has 1 <= 1 element  ->  return OK

(Of course, "aabcb" would return yes as well, but that's the whole point: we're not asking whether a string is a palindrome, but whether any one of its permutations is.)

If the string is known to be in some specific alphabet (ie only lowercase a-z), you could use a 32-bit integer as an array of bools and toggle the individual bits between false and true. The final s.size() could be done with popcount(). Not even any sets needed.

(This type of stuff might fail the "overengineering" test that the grandparent comment talked about though.)

Whether that's over-engineering or not really depends on the data. For this particular interview question we might assume we have very little data to process, but real applications might want to scale that to a point where you actually care about performance (MMO permutation palindrome checker or whatnot).

Personally, I'd use the simplest implementation as a reference, and use it to test more optimised solutions if I ever need them.

You have non-quadratic alternatives. Sort the string and then start iterating through the characters. Keep a boolean for if you've ever seen a character an odd number of times. The first time you get an odd count for a given character, set the bool to true. The second time, you see the bool is already true so you know the word isn't a palindrome and can immediately return false. If you get to the end of the string without hitting that condition, return true.

Yes, that's what I had in mind when I wrote "I may sort the word before hand".

Emphasis on "may", though: for small enough words, sorting may very well slow us down, so it really depends on the data: are we processing long words, or lots of small words?

Oh yes, that's definitely better.

Reply on news.ycombinator.com