LCA problem at interview

Sometimes I come across interview questions like this: "Find the common parent of any 2 nodes in a tree". I noticed that they ask LCA questions also at Google, Amazon, etc.

As wikipedia says LCA can be found by intersection of the paths from the given nodes to the root and it takes O(H), where H is the height of the tree. Bes开发者_如何学Goides, there are more advanced algorithms that process trees in O(N) and answer LCA queries in O(1).

I wonder what exactly interviewers want to learn about candidates asking this LCA question. The first algorithm of paths intersection seems trivial. Do they expect the candidates to remember pre-processing algorithms ? Do they expect the candidates to invent these algorithms and data structures on the fly ?

They want to see what you're made of. They want to see how you think, how you tackle on problem, and handle stress from deadline. I suppose that if you solve the problem because you already know the solution then they will just pose you another problem. It's not the solution they want, it's your brainz.

With many algorithms questions in an interview, I don't care (or want) you to remember the answer. I want you to be able to derive the answer from the main principles you know.

Realistically: I could give two cares less if you already know the answer to "how to do X", if you are able to quickly construct an answer on the fly. Ultimately: in the real world, I can't necessarily assume you have experience tackling problems of domain X, but if you run across a problem in said domain, I will certainly hope you'll have the analytical ability to figure out a reasonable answer, based on the general knowledge you hold.

A tree is a common data structure it's safe to assume most will know - if you know the answer offhand, you should be able to explain it. If you don't know the answer, but understand the data structure, you should be able to fairy easily derive the answer.