[TheOtherHobbes]

It's not an order of magnitude faster. The details depend on the hash table implementation and the language and the processor specifics and the statistical distribution of string sizes and whether you can make assumptions about the number of symbols being used and whether a tight double loop for a small symbol set and string size would fit in the cache and whether it would stay there long enough to make a useful difference.

Naive Big O is just as likely to be wrong as naive anything else.

I hope this isn't a genuine phone screen question, because if someone punted this at me as a pass/fail I'd fail them for being confused about how real computers and real languages work behind those nice clean-looking "if thing is in other_thing..." statements.

[asdginioubnou]

The second solution is safer than the first. While it will sometimes be slower, it will never be catastrophically bad. It may have a small, predictable overhead, but it will never unexpectedly bring down the whole program when you get a few unusually long strings.

When searching through a sorted list, your first instinct should be to use binary search. Your first instinct should not be "well maybe the list is always small, so linear search would be faster." Write the safe, predictable thing and save the optimizations for later.