The problem was to find all ancestors for each node in a DAG. So the solution should be a map of node to array, where the array is that node's ancestral nodes (can traverse down from them to reach node).

Example 1:

Input:

Output:
A: {}
D: {A}
G: {A}
F: {A, G}
R: {A, G}

Example 2:

Input:

Output:
A: {}
B: {A}
C: {A, B}
D: {A, B, C}
E: {A, B, C, D}
F: {A, B, C, D, E}

My solution was just dfs starting at each vertex (I stated I'd repackage to have the graph be incoming nodes), and just placing the current node in the array which is the value of that source vertex's key in the map. So pretty brute force. I stated that regardless of how we traverse, we are limited by what the ouput requires, and thus brute force is probably as good as we can do.

The interviewer asked for potential optimization, so I obliged by talking about post-order collect nodes during recursion and then place current node in each of those nodes' array...but that still involves having to traverse subtrees more than once. Mentioned topological sort but it's really not that useful here and interviewer didn't seem open to it. Hoping interviewer was just asking as one of those stumpers with no solution...