[abalone]

> Of course that doesn't mean you shouldn't know how advanced data structures work and be able to work with them..

We don't disagree. Understanding data structures is about reaching for the right tool, and very often the hammer of an array/map is the right tool. But the problem I gave isn't that exotic. It's a case where "reaching for an array" is a brute force solution that won't scale.

So how do you separate candidates who understand those limitations from those that don't? By asking about those cases. They're not that common, but that doesn't mean they never come up or you won't get a nasty bug if you don't understand these foundations.

[anaphor]

I would start by asking the question without mentioning scaling at all, and see how they respond.

If they immediately jump to using a fancy data structure like a suffix array, but they don't ask any questions about how critical performance and scaling are, then it shows they know a lot of stuff about CS, but they may be lacking in more practical experience.

If they tell you they would just use an array or a map (which would be extremely inefficient with large amounts of data), then you ask a follow-up question about scaling, and see how they respond. If they can't answer that question, then they lack practical experience and fundamental knowledge of advanced data structures.

Do you agree with that approach?

[abalone]

I totally agree with asking the basic question and then adding scale and complexity.

I don't know if I agree that using a trie at the outset reflects poorly on a candidate. They might see where you are going with the question, even though "you didn't mention scale." Good candidates are going to think about scale at least a little bit. That's not necessarily "lacking practical experience." It's not like basic tries or linked lists are super complex "fancy" data structures.

I think the key is for both parties to communicate thought process. If you're concerned about overengineering then prompt them to explain why they didn't choose an array.