3 ms·
Let's take the example interview question: given a string, how do you determine if it is an anagram of a palindrome? The answer is that, for any given character
by rybosome 12y ago
Let's take the example interview question: given a string, how do you determine if it is an anagram of a palindrome? The answer is that, for any given character, at most 1 should appear in the string an odd number of times. Here is an implementation in Scala, with higher-order functions:
def isAnagramOfPalindrome(s: String): Boolean =
s.groupBy { c => c }
.map { case(key, value) => value.size() }
.filter { n => n % 2 != 0 }
.size <= 1
And here's a more traditional implementation in JavaScript.
function isAnagramOfPalindrome(str) {
var chars = {};
for (var i = 0; i < str.length; i++) {
var char = str.charAt(i);
chars[char] = (chars[char] || 0) + 1;
}
var numOdd = 0;
for (var key in chars) {
if (chars[key] % 2 != 0) numOdd++;
}
return numOdd <= 1;
}
I find the Scala version much more readable, but I'm assuming you'll prefer the JS version?
- jaekwon 12y agoIn Go: func isAnagramOfPalindrome(str string) bool { charCounts := map[rune]int{} for _, c := range str { charCounts[c]++ } numOdd := 0 for _, count := range charCounts { if count%2 == 1 { numOdd++ } } return numOdd <= 1; } In this case I think I do prefer the latter. I like how I can name the intermediate objects. :) Also I don't like the practice of groupBy().map(=>_.size()), which hides the performance penalty of creating arrays. I'm sure a better compiler can do better, but I'd have to know the compiler to assume that.
- carapace 12y agoI'll bite. In Python: def odd_count(letters): return lambda ch: letters.count(ch) % 2 def anagram_of_palindrome(letters): return sum(map(odd_count(letters), set(letters))) <= 1 How's that for some higher-order function action? But really, unless you are deriving programs by doing algebra you are missing the point of things like map() and reduce() (as far as I know no one is actually doing Functional Programing the way Backus described. Am I wrong? I'd love to be wrong.) Go read Backus' Turing Award paper: http://web.stanford.edu/class/cs242/readings/backus.pdf http://web.stanford.edu/class/cs242/readings/backus.pdf
- burntsushi 12y agoThe Haskell programmer in me can't resist---eta reduce your functions! :P from functools import partial def odd_count(letters, ch): return letters.count(ch) % 2 def anagram_of_palindrome(letters): return sum(map(partial(odd_count, letters), set(letters))) <= 1
- masklinn 12y agoA more modern take would use collections.Counter(letters) to extract the letter counts, that avoids traversing the string for each letter count: def anagram_of_palindrome(letters): return sum(c % 2 for c in Counter(letters).itervalues()) <= 1