Indeed Interview Question
SDE-2sCountry: United States
(let i and j be the given nodes)
- reverse the graph
- perform a BFS from 'i' keeping track of the layer/level where the other nodes are discovered (let Ki denote the distance of node K from i)
- perform a similar BFS from 'j', collecting Kj for every node K in the graoh
at this point, the shortest distance (in hops) from every node to nodes 'i' and 'j' is known
min(abs(Ki - Kj)) for every node K will give the K that is the least common ancestor
- Nits August 16, 2019