Clone a graph

Competency asserted: Data Structures and Algorithms
Frequency: 1
Job title: Software Development Engineer (SDE II)
Interviewer role: Senior Software Development Engineer (SDE III)

Problem Statement

Given a graph of nodes that have links to zero or more other nodes, and an initial node in the graph, discover the graph and clone it and its links.

Example graph:

a->b
b->c,d
c->d,e
e->f,b

(given node “b”)

Solution

https://leetcode.com/problems/clone-graph/
https://www.geeksforgeeks.org/clone-an-undirected-graph/

Example feedback

For a coding problem I gave the candidate a straightforward problem of cloning a graph, given a single node as a starting point.

For a coding problem I gave the candidate a straightforward problem of cloning a graph, given a single node as a starting point. He was able to code the basic traversal with both a recursive and (on his own initiative) queue based approach. However, in neither case did he mange to handle cloning the connections between nodes. He did know to use an unordered map to map old to new items, and to use the same map to detect recursion – which are nice plusses.

Overall, I think he did ‘Okay’ – but he didn’t really raise the bar for an SDE-2.

Candidate’s code:

struct Node {
    int val;
    vector<Node*> next;
}
class clone {
public:
    void clone(Node* root) {
        queue<Node*> q;
        q.push(root);
        while (q.empty()) {
            Node * cur = q.front(); q.pop();
            m[cur] = new Node(cur->val);
            for (auto & it : cur->next) {
                q.push(it);
            }
        }
    }

private:
    unordered_map<Node*, Node*> m;
};