Google Interview Question
Applications DevelopersCountry: India
Interview Type: Phone Interview
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.
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.)
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);
}
}
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;
}
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);}
}
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);}
}
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);
}
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;
}
}
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)
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;
}
- arturo July 11, 2013