First off, I'll say there was a huge language barrier between my interviewer and me. He did not speak fluent English by a long shot. The choppy Google Voice connection, mixed with him being fairly quiet, didn't help either.

He asked me questions like, "What does it mean?" when pointing to pieces of code. I answered by explaining what that line did, which was not what he was looking for.

In the beginning, he also said to ask him any clarifying questions along the way, which I did. I had to repeat myself multiple times, and he had trouble answering them in a way that made much sense to me.

They are definitely looking for CS fundamentals: algorithms, data structures, runtimes, etc. You code in a Google Doc, and they don't allow you to run or test your code, so you have to be pretty confident about writing the problem out correctly, top to bottom.

They didn't care at all about my practical, real-world software development experience and instead only focused on academic CS fundamentals, as listed above. I even specifically asked if my industry experience was relevant, and they said no. So, in a way, I don't think it would have been a good fit for me anyways.

What is the runtime of {popular search algorithm}? Explain why.