Engineering #23: O(1) time, and quizzing employed engineers
+ Save the Date by Deborah Azzopardi
This series is helping me figure out the things that most software engineers aren’t asked to do at their jobs. I’m learning basic building blocks and my smarter engineer friends learned them but haven’t scrutinized each of them recently, so I’ve ended up asking friends a few things that turned into multiple-conversation discussions1, when I expected them to last like ten seconds. That expectation of mine is due to not understanding the full scene and how career paths go.
And I learn what engineers find interesting. To one good friend this wasn’t interesting at all:
It’s good to know. If it is not interesting because asking those kinds of questions doesn’t get you results better or faster, then — well, you shouldn’t learn just through others’ points-of-view, but it’s useful to understand that this or that is just a distraction or whatever.
But Kevin asked me about it in the comments:
Curious about your approach to this question with an additional condition: the user wants to perform case insensitive lookups in O(1) time.
ChatGPT and Gemini helped; with sets and dicts Python uses a hash table under the hood. That gives us O(1) lookup, though often amortized due to the need to resize and rehash the hash table.
I won’t post a solution since I only learned enough to read one. And looks like amortization has a bunch of interesting details which I will get to.
One example:
Which of the following values can't be used as a key in a dict object, and why?
'cat'
(3, 1, 4, 1, 5, 9, 2)
['a', 'b']
{'a': 1, 'b': 2}
range(5)
{1, 4, 9, 16, 25}
30.0
frozenset({1, 4, 9, 16, 25})