Question

• Compress the given graph

Given

Starter code

class Node
{
    string key_;
    vector<Node*> out_edges;
};
class Solution
{
public:
    vector<Node*> compress_graph(vector<Node*> start_nodes)
    {
        // todo: implement
        return {};
    }
};

Input

//   f -           -> END
//      |         | 
//      v         |
//      u -> l -> l -> e -> s -> t -> END
//      ^              |
//      |              |
//  d -                - > r -> END

Expected Output:

//   f -   -> END
//      | | 
//      v |
//      ull -> e -> st -> END
//      ^      |
//      |      |
//   d -        -  r -> END

Thoughts

During interview

• how to merge two nodes, find the right condition.
• traverse the graph, stop at END node(Interviewer - can be null node or something else -- upto you)
• it looks like a trie but it is a graph.
• merging "l" and "l" is easy i.e in edges = out edges but this condition does not hold for "u"

Post interview

• use graph traversal- DFS or BFS

My Performance

• It was a disaster. I have solved 250 problems on LC including graph traversal (# of islands, walls and gates )but I for some reason
  invented my own way of graph traversal. Basically, since the graph did not look like a typical graph I was thrown. However, what I should have done is stayed on track and implemented DFS or BFS.

• Importantly, I want to learn from my mistakes hence this post.

• Bascially, I want to know if there is a proper known way e.g algorithm or approach to solve the problem

Follow up

• in case anyone has ideas on how to solve this problem or approach this problem, please share.
• It would be useful for future reference. Thanks!