I will ask all of those questions. But I don't expect perfect answers. You should at least know what big O is. I would really like it if you can tell an O(n^2) algorithm from a linear one. (That is often really important in real-world code). I would like you to consider different ways you can optimize the code.
I don't expect you to quickly crank out a novel optimal algorithm. But I like to see that you can think about how to solve problems programmatically. I would like to see you can identify differences in different algorithms and what tradeoffs there are. Considering different approaches that may be faster also shows that you didn't just memorize an algorithm from somewhere but that too took time to actual understand the problem and build a mental model in your head.
I have given people great reviews when they couldn't come up with a working algorthim because the clearly knew how to think like a programmer and considered all of the important things.
As an electrical engineer who has basically always worked as an embedded programmer, I don't know what big O is. But, I'm probably not applying for your open positions.
It definitely depends on the domain. In embedded programming you can often know that your n is small for your algorithms. If you are making a desktop app or web service it is very important to prepare for people using your service in unexpected ways and a super linear algorithm can result in terrible performance or downtime if not managed correctly.
I don't expect you to quickly crank out a novel optimal algorithm. But I like to see that you can think about how to solve problems programmatically. I would like to see you can identify differences in different algorithms and what tradeoffs there are. Considering different approaches that may be faster also shows that you didn't just memorize an algorithm from somewhere but that too took time to actual understand the problem and build a mental model in your head.
I have given people great reviews when they couldn't come up with a working algorthim because the clearly knew how to think like a programmer and considered all of the important things.