My interview question - finding all paths through a DAG.
Today I had a technical phone interview for a new grad gig. There were two problems and the second one built upon the first. The second problem boiled down to finding all the paths from source to sink nodes in a directed acyclic graph (that wasn’t the whole problem, but it was the core of it). Unfortunately we ran out of time before I could finish implementing my solution (I don’t expect to make it to the next round…).
Since I don’t like leaving things unfinished I found the same problem on leetcode and submitted a correct solution:
class Solution {
private:
// Returns the path starting at currentNode but in reverse.
vector<vector<int>> helper(int currentNode, vector<vector<int>>& graph) {
vector<vector<int>> result;
// If currentNode is a sink then the result is a single path containing just currentNode
if (graph[currentNode].size() == 0) {
vector<int> path;
path.push_back(currentNode);
result.push_back(path);
return result;
}
// If currentNode has neighbors then the result is all the paths generated by calling
// helper on its neighbors, with currentNode appended.
for (const int neighbor: graph[currentNode]) {
vector<vector<int>> paths = helper(neighbor, graph);
for (vector<int>& path: paths) {
path.push_back(currentNode);
result.push_back(path);
}
}
return result;
}
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> result = helper(0, graph);
for (vector<int>& reversedPath: result) {
reverse(reversedPath.begin(), reversedPath.end());
}
return result;
}
};
In my interview I had everything you see here EXCEPT the if statement in helper handling the case when the current node is a sink. I spent about 10 minutes during my interview trying to figure out why the size of the result vector was always 0…
According to leetcode this is a poor solution, beating only 13% of submissions on speed and 10% of submissions on memory. But it is a working solution and if I had figured out that I needed that if statement in my interview I’m confident I would have been able to finish the entire question. Oh well. Lesson learned. It’s safe to say I will never fail to implement finding all paths through a DAG during an interview ever again. LOL.