What they're testing
Whether you choose structures from the OPERATIONS you need, or default to a map for everything.
The short answer~30 seconds
A hash table gives O(1) lookup and NO ordering — that's precisely what it traded away. If you need both, use a balanced search tree (TreeMap in Java, std::map in C++): O(log n) lookup, with ordered iteration and range queries. If you only need INSERTION order rather than sorted order, LinkedHashMap gives O(1) plus insertion ordering, and it's also the basis for an LRU cache.
The long answer
This question usually opens a follow-up: when do you need a range rather than one key. A hash table can't answer "give me every key in [a, b]" or "the smallest key above x" — the hash deliberately destroys ordering to distribute evenly. A tree answers both in O(log n + k). It's the same reason database B-tree indexes aren't hash indexes in most cases.
For an LRU cache, the classic implementation is worth knowing: a hash table for O(1) lookup combined with a doubly-linked list to move the just-used entry to the front, also O(1). No single structure does both, so you compose two and each entry lives in both. In Java, LinkedHashMap with accessOrder = true and an overridden removeEldestEntry gives you all of it for free.
There's another family where the answer is a heap rather than a map: when you only ever need the SMALLEST or LARGEST element — priority queues, top-k, merging sorted streams. A heap gives extremum access in O(log n) without maintaining full order, so it's cheaper than a tree when you never iterate.
What they'll ask next
?What about prefix search?
A trie, or in a database a B-tree index, which works because it preserves lexicographic order — LIKE 'abc%' can use it, LIKE '%abc' can't. A trie wins for in-memory autocomplete over millions of strings sharing prefixes.
These lose points
- Using a map for everything and re-sorting whenever order is needed. That's O(n log n) per read to save O(log n) per write.