Google Interview Question for Applications Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
9
of 9 vote

#include <unordered_map>

using namespace std;

Node * CopyGraph(Node * node, unordered_map<Node*, Node*> &copied)
{
	if(node==NULL)
		return NULL;

	//First check if this node has already been copied
	unordered_map<Node*, Node*>::iterator it = copied.find(node);
	if(it!=copied.end())
		return it->second;

	//If not, then create a copy of the node
	Node * new_node = new Node;
	new_node->data = node->data;

	//Add the copied node to the Hash table
	copied[node] = new_node;

	//Copy the node's neighbors using recursive calls
	for(int i=0; i<node->neighbors.size(); i++)
		new_node->neighbors.push_back(CopyGraph(node->neighbors[i], copied));

	return new_node;
}

- arturo July 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

It is not easy coding question...there can be a lot of constrains as you may need to take care such as cycle in the graphs, or it is directed or not and other small details. If you still think it is easy then try coding and you may find many issues with first draft of your code. As said, we can use dfs or bfs and we need to take care of cycle in the graph. We may like to use hash table to track cycle in the graph.

- shsf July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does google really ask so easy question?

- Debasis Jana July 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Sure. It's a common misconception that Google questions must be incredibly algorithmically difficult. Most Google questions are not actually all that hard.

However, the standards might be higher on an easy question. That is, let's say doing "well" in an interview means being in the top 25% of candidates. On a very hard question, that might mean just barely solving with a non-optimal algorithm by the end of the question. On a medium difficulty question, that might mean getting the algorithm within 15 minutes of so and then coding it, with a few minor errors.

(Also, this question isn't "easy." It's about medium difficulty.)

- Gayle L McDowell July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.careercup.google;

import java.util.ArrayList;

public class CloneGraph {

	static class Node {
		int data;
		ArrayList<Node> neighbors;
	}

	static void clone(Node sGraph, Node dGraph) {
		if (sGraph != null) {
			dGraph.data = sGraph.data;
		}

		if (sGraph.neighbors != null) {
			if (dGraph.neighbors == null) {
				dGraph.neighbors = new ArrayList<Node>();
			}

			for (Node n : sGraph.neighbors) {
				Node cloneN = new Node();
				dGraph.neighbors.add(cloneN);

				clone(n, cloneN);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node node1 = new Node();
		node1.data = 1;
		node1.neighbors = new ArrayList<Node>();

		Node node2 = new Node();
		node2.data = 2;
		node1.neighbors.add(node2);

		Node node3 = new Node();
		node3.data = 3;
		node1.neighbors.add(node3);

		Node clonedGraph = new Node();
		clone(node1, clonedGraph);

	}

}

- Anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This takes care of cycles and is independent of whether the graph is directed or not.

public class CloneGraph {
	private static class Node {
		int data;
		List<Node> neighbors = new ArrayList<Node>();
	}
	
	public Node clone(Node i) {
		return clone(i, new HashMap<Integer, CloneGraph.Node>());
	}
	
	public Node clone(Node i, Map<Integer, Node> nodes) {
		Node r = new Node();
		r.data = i.data;
		nodes.put(r.data, r);
		for(Node n : i.neighbors) {
			Node j = nodes.get(n.data);
			if(j == null) {
				j = clone(n, nodes);
			}
			r.neighbors.add(j);
		}
		return r;
	}

- galli July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;


public class Clone {
private HashMap<Node, Node> marker;

public Clone() {marker = new HashMap<Node, Node>(); }

void clone(Node s, Node d) {

if (s != null) {
d.data = s.data;
marker.put(s, d);
}


for (Node w : s.neighbors) {

if (!marker.containsKey(w)) {
Node c = new Node();
clone(w, c);
d.add(c);
}
else {
d.add(marker.get(w));
}

}
}

public static void main (String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);

n1.add(n2);
n2.add(n3);
n3.add(n1);

Clone c = new Clone();
Node c1 = new Node();
c.clone(n1, c1);

DFS p1 = new DFS(c1);
}
}

class DFS {
private HashSet<Node> marker;
private int count;

public DFS(Node s) {marker = new HashSet<Node>();dfs(s);}
private void dfs(Node s) {

if (s != null) {
marker.add(s);
}

for (Node w : s.neighbors) {
if (!marker.contains(w))
dfs(w);

System.out.println("("+ s.data() + ")" + "->" + "(" + w.data() + ")");
}
}
}

class Node {
int data;
ArrayList<Node> neighbors;
public Node(){neighbors = new ArrayList<Node>();}
public Node(int data) {
this.data = data;
neighbors = new ArrayList<Node>();}
public void data(int i) {this.data = data;}
public ArrayList<Node> neighbors() {return this.neighbors;}
public int data() {return this.data;}
public void add(Node i) {this.neighbors.add(i);}
}

- imaronsu July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;


public class Clone {
	private HashMap<Node, Node> marker;
	
	public Clone() {marker = new HashMap<Node, Node>(); }
	
	void clone(Node s, Node d) {
		
		if (s != null) {
			d.data = s.data;
			marker.put(s, d);
		}
		
		
		for (Node w : s.neighbors) {

			if (!marker.containsKey(w)) {
				Node c = new Node();
				clone(w, c);
				d.add(c);
			}
			else {
				d.add(marker.get(w));
			}

		}
	}
	
	public static void main (String[] args) {
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		
		n1.add(n2);
		n2.add(n3);
		n3.add(n1);
		
		Clone c = new Clone();	
		Node c1 = new Node();
		c.clone(n1, c1);
		
		DFS p1 = new DFS(c1);
	}
}

class DFS {
	private HashSet<Node> marker;
	private int count;
	
	public DFS(Node s) {marker = new HashSet<Node>();dfs(s);}
	private void dfs(Node s) {
		
		if (s != null) {
			marker.add(s);
		}
		
		for (Node w : s.neighbors) {
			if (!marker.contains(w))
				dfs(w);
			
			System.out.println("("+ s.data() + ")" + "->" + "(" + w.data() + ")");
		}
	}
}

class Node {
	int data;
	ArrayList<Node> neighbors;
	public Node(){neighbors = new ArrayList<Node>();}
	public Node(int data) {
		this.data = data;
		neighbors = new ArrayList<Node>();}
	public void data(int i) {this.data = data;}
	public ArrayList<Node> neighbors() {return this.neighbors;}
	public int data() {return this.data;}
	public void add(Node i) {this.neighbors.add(i);}
}

- imaronsu July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a map to store the mapping between the old node and the new node

#include <assert.h>

#include <vector>
#include <map>
#include <iostream>

class Node {
public:
    int data;
    std::vector<Node*> neighbors;
    Node(int d) : data(d) {
        neighbors.clear();
    }
    void Insert(Node* t) {
        neighbors.push_back(t);
    }
};

void CopyGraphImpl(Node* r, Node*& r1, std::map<Node*, Node*>& m) {
    int i;
    std::map<Node*, Node*>::iterator mitr;
    for (i = 0; i < r->neighbors.size(); ++i) {
        if ((mitr = m.find(r->neighbors[i])) != m.end()) {
            r1->Insert(mitr->second);
            continue;
        }
        Node* t = new Node(r->neighbors[i]->data);
        assert(t);                                                                                                                                                                     
        r1->Insert(t);
        m.insert(std::make_pair(r->neighbors[i], t));
        CopyGraphImpl(r->neighbors[i], t, m); 
    }   
}

void CopyGraph(Node* r, Node*& r1) {
    if (!r) return;
    if (!r1) {
        r1 = new Node(r->data);
        assert(r1);
    }   
    std::map<Node*, Node*> m;
    m.insert(std::make_pair(r, r1));
    CopyGraphImpl(r, r1, m); 
}

- mwxjmmyjfm September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recurse through each neighbor, creating a copy as you go. To make sure you don't create a copy of the same node more than once, keep track of a mapping of original nodes to their cloned nodes. If a mapping doesn't exist, then clone the node, otherwise use the previously cloned node.

The for-loop in the Graph::clone method is really there in case the graph is in disconnected sections (Node A has no path to Node B).

public class Graph {
	public HashSet<Node> nodes;

	public Graph clone(Graph g) {
		Graph newGraph = new Graph();
		newGraph.nodes = new HashSet<>();
		IdentityHashMap<Node,Node> idh = new IdentityHashMap<>(); // mapping of current nodes to cloned nodes
		for( Node node : nodes) {
			newGraph.nodes.add(node.deepCopy(idh))
		}
	}
}

public class Node {
	public int data;
	public HashSet<Node> neighbors;


	public Node deepCopy(IdentityHashMap idh) {
		
		if( idh.get(this) != null) {
			return idh.get(this);
		}

		// Create new node and map it to reference node
		Node newNode = new Node();
		idh.put(this,newNode);

 		// copy info
		newNode.data = data;

		// copy connections
		for( Node node : neighbors ) {
			node.deepCopy(idh);
		}

		return newNode;
	}	
}

- derrek.hyland March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def cloneGraph(self, node):
        clone_node = UndirectedGraphNode(node.label)
        cloned_map = {node: clone_node}
        self.__cloneGraph(node, clone_node, cloned_map,set())
        return clone_node

    def __cloneGraph(self, node, clone_node, cloned_map,visited):
        #import pdb;pdb.set_trace()
        if node in visited:
            return
        visited.add(node)
        for neighbor in node.neighbors:
            if neighbor in cloned_map:
                clone_neighbor = cloned_map[neighbor]
            else:
                clone_neighbor = UndirectedGraphNode(neighbor.label)
                cloned_map[neighbor] = clone_neighbor

            clone_node.neighbors.append(clone_neighbor)
            self.__cloneGraph(neighbor, clone_neighbor, cloned_map,visited)

- sumitgaur.iiita January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

typedef unordered_map<Node *, Node *> Map;
 
Node *clone(Node *graph) {
    if (!graph) return NULL;
 
    Map map;
    queue<Node *> q;
    q.push(graph);
 
    Node *graphCopy = new Node();
    map[graph] = graphCopy;
 
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        int n = node->neighbors.size();
        for (int i = 0; i < n; i++) {
            Node *neighbor = node->neighbors[i];
            // no copy exists
            if (map.find(neighbor) == map.end()) {
                Node *p = new Node();
                map[node]->neighbors.push_back(p);
                map[neighbor] = p;
                q.push(neighbor);
            } else {     // a copy already exists
                map[node]->neighbors.push_back(map[neighbor]);
            }
        }
    }
 
    return graphCopy;
}

- Nitin Gupta July 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not a recursive solution to the problem!

- arturo July 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote
package com.careercup.google; import java.util.ArrayList; public class CloneGraph {{{ static class Node {{{ int data; ArrayList<Node> neighbors; }}} static void clone(Node sGraph, Node dGraph) {{{ if (sGraph != null) {{{ dGraph.data = sGraph.data; }}} if (sGraph.neighbors != null) {{{ if (dGraph.neighbors == null) {{{ dGraph.neighbors = new ArrayList<Node>(); }}} for (Node n : sGraph.neighbors) {{{ Node cloneN = new Node(); dGraph.neighbors.add(cloneN); clone(n, cloneN); }}} }}} }}} /** * @param args */ public static void main(String[] args) {{{ Node node1 = new Node(); node1.data = 1; node1.neighbors = new ArrayList<Node>(); Node node2 = new Node(); node2.data = 2; node1.neighbors.add(node2); Node node3 = new Node(); node3.data = 3; node1.neighbors.add(node3); Node clonedGraph = new Node(); clone(node1, clonedGraph); }}} }}} - Anonymous July 17, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More