I won't call out the company because at least until now they were still using the question (I got accidentally cc'ed on a subsequent candidates email), but last summer I got an interview homework question from a "who is hiring" post that was to solve hangman for a given dictionary. I implemented all of the strategies outlined here, and while they seemed impressed with the execution speed of my solution, they implied it could have scored better, saying it was only "average" in that regard.
The thing is, at least for the dictionaries I had available, trying to weight for information gain only considering the guess correctness wasn't all that great a strategy. Even if you know 100% certain that the letter will be correct, its very likely to still cut the search space down by virtue of the pattern of letters, and in aggregate my strategy made no statistical difference. (+/- 1% depending on random seed).
If I were going to try and improve my scores, I guess the next thing would be look at the distribution of letter-patterns for each remaining letter, but my intuition is that it just wouldn't be a big deal.
The thing is, at least for the dictionaries I had available, trying to weight for information gain only considering the guess correctness wasn't all that great a strategy. Even if you know 100% certain that the letter will be correct, its very likely to still cut the search space down by virtue of the pattern of letters, and in aggregate my strategy made no statistical difference. (+/- 1% depending on random seed).
If I were going to try and improve my scores, I guess the next thing would be look at the distribution of letter-patterns for each remaining letter, but my intuition is that it just wouldn't be a big deal.