For the chess game question, I'd be looking for the candidate to talk through some considerations, even if there's no definitive conclusion. Things like:
- how many different kinds of piece are there, and therefore, how many bits are required to encode them all?
- given that the number of each piece at the start of the game is fixed, is it more efficient to consider an indexed solution? (ie. record the position of each piece in terms of its numbered square, rather than encode each square individually).
- in the latter case, how do you cope with pawn promotion? Is it necessary to add extra bits for this, or is it OK not to be able to cope with (say) multiple queens, if the memory saving thus achieved is worth it?
- what's more important, the total memory usage of 1 game, or the average memory usage over a large number of games?
- is the code space included in the total? How about an arbitrarily large look-up table? Or at least, a custom LZW entropy coding table?
- given that all identical pieces are interchangeable, is there a saving to be had in the indexed case by sorting the pawns by some criterion before compressing the table?