Given two nodes in a directed graph represented by singly linked nodes, provide an algorithm for finding the nearest common ancestor. In fact, provide as many different algorithms as you can, giving different trade-offs between time and space requirements (in big-O notation).

Question

Given two nodes in a directed graph represented by singly linked nodes, provide an algorithm for finding the nearest common ancestor.  In fact, provide as many different algorithms as you can, giving different trade-offs between time and space requirements (in big-O notation).

Anonymous · Accepted Answer

Hint: Consider the *entire* range of possible trade-offs, up to spending huge amounts of time for tiny gains in space (or vice versa).

Microsoft

Microsoft interview question

Interview Answer

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches