The problem is that many interviewers don't know how to suss out a good engineer. So they just ask questions that Google and Amazon ask. And that's why you spend half of your interview pre-optimizing contrived algorithms down to O(n) when the probability of the startup ever running code at scale is very small.