Another anecdote of an incompetent interviewer blindly looking for a certain answer:
I once had an interview where, for a pretty long question, one trivial step was to check that one set was a subset of another set. Neither set had any special preconditions, just two plain unordered Java HashSets. Not thinking twice about it, I wrote a simple for loop that checked if every element in the smaller set was present in the bigger set.
When I finished the question, the interviewer started questioning me about the runtime of the for loop. He started hinting that it could be more efficient, which confused me, since it seemed impossible to check every element of a set in faster than O(n) time. I also didn't see how it was useful to think so carefully about the runtime of such a trivial thing, seeing as the "story" of the problem indicated that the sets would never be particularly large and the task wasn't one that would be sensitive to a couple microseconds difference in runtime.
We spent about 20 minutes stuck on this, with me awkwardly repeating I didn't see how it was possible to be faster and him telling me to just think harder and look at the problem "mathematically", "forget about the code, just think, in math, if you have a set A and a set B, how do you efficiently find if one is a subset of the other?". Eventually we ran out of time for the interview. As we wrapped up, he revealed to me the elusive answer: "Since you're checking if it's a subset, you should use the built-in isSubset() method that Java sets have". Of course, he hadn't conveyed to me at all that he was looking for a specific built-in method, so I thought there was some secret algorithm that I would have to write to make it go faster. I didn't mention that though, and instead replied that even if it were a built-in method I didn't see how it could be faster than O(n) in its implementation. He didn't have response, and just stammered something like "well it's built in and it's actually the most efficient way" and the interview ended awkwardly. Anyways, I had my doubts, so when I got home I checked.
There is no isSubset() in Java sets.
There is a containsAll(). It's implemented as a while loop that runs in O(n) time, making it no more efficient than writing your own loop.
Three years ago I interviewed in house (after several hours of phone screens) at an SF tech company that has since gone public. The position was for a senior software engineer doing mostly backend Rails stuff.
The biggest portion of the in-house interview was some fairly simple algorithm puzzle involving solving some word game given some rules and a list of valid English words. That section of the interview ended with me explaining how hash table lookups are constant time and the interviewer insisting that they are linear time.
To be clear, there was no “gotcha” about collision resolution or anything subtle like that. My claim just came up as an obvious step in my explanation of the running time of my proposed solution and the interviewer jumped on it.
I thought I was quite cordial, but I didn’t back down, and the interviewer seemed quite aggressive. The other interviewer in the room at the time seemed very uncomfortable with the fact that I would question something so basic, but didn’t intervene or express any “opinion” on the “debate.”
I once had an interview where, for a pretty long question, one trivial step was to check that one set was a subset of another set. Neither set had any special preconditions, just two plain unordered Java HashSets. Not thinking twice about it, I wrote a simple for loop that checked if every element in the smaller set was present in the bigger set.
When I finished the question, the interviewer started questioning me about the runtime of the for loop. He started hinting that it could be more efficient, which confused me, since it seemed impossible to check every element of a set in faster than O(n) time. I also didn't see how it was useful to think so carefully about the runtime of such a trivial thing, seeing as the "story" of the problem indicated that the sets would never be particularly large and the task wasn't one that would be sensitive to a couple microseconds difference in runtime.
We spent about 20 minutes stuck on this, with me awkwardly repeating I didn't see how it was possible to be faster and him telling me to just think harder and look at the problem "mathematically", "forget about the code, just think, in math, if you have a set A and a set B, how do you efficiently find if one is a subset of the other?". Eventually we ran out of time for the interview. As we wrapped up, he revealed to me the elusive answer: "Since you're checking if it's a subset, you should use the built-in isSubset() method that Java sets have". Of course, he hadn't conveyed to me at all that he was looking for a specific built-in method, so I thought there was some secret algorithm that I would have to write to make it go faster. I didn't mention that though, and instead replied that even if it were a built-in method I didn't see how it could be faster than O(n) in its implementation. He didn't have response, and just stammered something like "well it's built in and it's actually the most efficient way" and the interview ended awkwardly. Anyways, I had my doubts, so when I got home I checked.
There is no isSubset() in Java sets.
There is a containsAll(). It's implemented as a while loop that runs in O(n) time, making it no more efficient than writing your own loop.
Naturally, the company ghosted me too.