Instead of being probabilistically wrong, you can save memory by removing some branches of the trie and becoming deterministically wrong.

You could remove the largest branches that correspond to the fewest words. Alternatively, you could remove the branches that correspond to the least queried words if you know something a priori about the query pattern.

Instead of making it probabilistic, I would rather add more memory to the system. The idea of making it probabilistic seems to me to be entirely for leading the interview candidate to the solution you have in mind.