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).

Anonimo · 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

Domanda di colloquio di Microsoft

Risposta di colloquio

Aziende seguite

Ricerche di lavoro