Xurmo Interview Question
InternsCountry: India
Interview Type: Written Test
i would suggest use of a recursive approach with memoization, i.e. start with A, to get answer for search left hand side of all dependencies and right hand side of A , if any element on the rhs of A is in some left hand side then solve it recursively and so on.........
eg for A solve B, for B solve C but for C simply return with G as the answer since G is not on the lhs of any row
Build a graph with A,B and so on as nodes and the dependencies as edges. Then for each node, do a search (DFS or BFS) and the set of nodes you've visited are the dependencies for that class. O(N) for every class, so O(N^2) total.
- Anonymous March 23, 2013