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.
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
(This type of stuff might fail the "overengineering" test that the grandparent comment talked about though.)
Personally, I'd use the simplest implementation as a reference, and use it to test more optimised solutions if I ever need them.
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?
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
The crux here is to notice that the order of the letters in the word we're given does not matter (because of the "any permutation" part). So it must be a matter of counting the letters. GlennS got it right: https://news.ycombinator.com/item?id=28550511
The second insight was that only the parity of occurrence mattered. Having 2 or 4 or 6 times the same letter is the same as not having the letter at all, so I only have to retain "zero" or "one" for each letter. Sets are perfect for this: "zero" means "not there", "one" means it's there, and at the end I can tolerate at most one odd letter.
Also exactly the reason I posted my message since that doesn’t apply for everyone. People that already know may be blind to that though.
The problem is they also filter out people who get nervous during tests. I'm someone who marginally failed a programming test and am now one of the most in-demand developers at my company (where I failed the test). The tech director who rejected my failed test has since told me not hiring me to his team at that time was one of the biggest mistakes of his career and I've also heard he's stopped being a believer in programming tests because of my application.
I've also been involved in hiring decisions and I've hired people who have bombed programming tests (and in ways where it was clear they just didn't grok the logic they should have). They've also been perfectly fine contributors, because our test questions required knowledge that wasn't going to be relevant (a CRUD-gluer doesn't really need to be proficient with geometry).
I still believe programming tests are useful, though. In the hiring I've done, it has been one factor to discuss during the interview. We always give developers a take-home test and then discuss the results in the interview. If they messed up, we illustrate where their solution is wrong and see if they're able to reason through the problem. If they didn't mess up, hey, that's a great sign.
If we can see them really start re-reasoning through the problem, that's a good sign that they (a) don't take programming failure personally and (b) are the sort of person who will re-evaluate what they think they know. On the other hand, if they just throw up their hands and give up without really giving the problem any extra effort, that's a bad sign. Our reasoning for this approach is that everyone writes bugs, but nobody gets to give up when fixing bugs.
As an aside, we've never tested someone who just couldn't write a for loop at all, so it's possible our hiring pool is different and so our needs/solutions are different.
And for context, the take-home test questions we use (they're always the same and they're not a secret) are:
1. Given a rectangle and a point, write a function to determine if the point is within a certain distance of the rectangle.
2. Given a string, write a function that determines if any permutation is a palindrome (this one's for the over-engineers who don't first think through the problem)
3. Write a CLI dice game where the computer cheats to maintain around a 70% win rate (there are some basic rules for scoring I'm leaving out for space - this one people rarely get totally wrong, but talking about why they picked a particular cheating mechanism can be enlightening).