Indeed, my best guess is that the interviewer had a mental check list and simply wanted me to say "prefix tree" or "trie" or similar. I suspect the debate over

Indeed, my best guess is that the interviewer had a mental check list and simply wanted me to say "prefix tree" or "trie" or similar. I suspect the debate over running time was just the interviewer's attempt to get me to say the magic word he wanted to hear. I also suspect the interviewer did not know much about hash tables or tries, or was so nervous and misguided about interviewing that the information was not readily recallable.