Google Interview Question
Country: United States
Interview Type: Written Test
Go through the linked list and build a hash table mapping each node to the node that follows it. Then go through the array and for each position, look at the next position and see whether the node there matches what the hash table says the next node should be. Increment a counter each time there's not a match (counter starts with 1 since we always say there's at least 1 cluster).
private static void findClusters(Node[] nodes) {
int numberOfClusters = 1;
LinkedHashSet<Node> runningCluster = new LinkedHashSet<Node>();
for (int i = 0; i < nodes.length - 1; i++) {
if (nodeMap.get(nodes[i].getVal()).getNext() == nodes[i + 1]
|| nodeMap.get(nodes[i].getVal()).getPrev() == nodes[i + 1]) {
runningCluster.add(nodes[i]);
runningCluster.add(nodes[i+1]);
} else {
printList(runningCluster);
runningCluster.clear();
numberOfClusters++;
runningCluster.add(nodes[i+1]);
}
}
printList(runningCluster);
System.out.println("Total number of clusters are " + numberOfClusters);
}
private static Node createDoublyLinkedList(int[] array) {
Node head = null, temp = null;
for (int num : array) {
if (head == null) {
head = new Node(num, null, null);
temp = head;
nodeMap.put(num, head);
} else {
Node newNode = new Node(num, null, temp);
temp.setNext(newNode);
temp = newNode;
nodeMap.put(num, newNode);
}
}
return head;
}
// pretty printing
private static void printList(LinkedHashSet<Node> runningCluster) {
System.out.print("(");
for(Node node : runningCluster) {
System.out.print( node.getVal() + " ");
}
System.out.print(")");
System.out.println();
}
Test cases I tried are
1) Linked list 1=>2=>3=>4=>5=>6=>7
Nodes[] = 1, 2, 4, 5 ,6 ;
output
(1 2 )
(4 5 6 )
Total number of clusters are 2
2) Linked list 1=>2=>3=>4=>5=>6=>7
Nodes[] = 1, 4, 5 ;
output
(1 )
(4 5 )
Total number of clusters are 2
Consider this as a tree with only root having two children. Given a node, if I do inorder traversal, I would get the cluster in order. How would I know when to stop forming cluster? I keep going left right and stop looking in a direction if the node is not listed in array or is pointing to null.
package com.google.practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
class Server implements Comparable<Server>{
public Server left;
public Server right;
public String name;
public Server(String name){
this.name = name;
}
@Override
public int compareTo(Server s) {
// TODO Auto-generated method stub
if(this.name.equals(s.name))
return 0;
else
return ((int) Math.random())%2==0?-1:1;
}
public String toString(){
return this.name;
}
}
public class Cluster {
public static void main(String[] arg){
Server n1 = new Server("n1");
Server n2 = new Server("n2");
Server n3 = new Server("n3");
Server n4 = new Server("n4");
Server n5 = new Server("n5");
Server n6 = new Server("n6");
n1.left = null; n1.right = n2;
n2.left = n1; n2.right = n3;
n3.left = n2; n3.right = n4;
n4.left = n3; n4.right = n5;
n5.left = n4; n5.right = n6;
n6.left = n5; n6.right = null;
Server[] network = {n1,n4,n5};
Set<Server> netSet = new TreeSet<Server>();
for(int i=0;i<network.length;i++){
netSet.add(network[i]);
}
List<List<Server>> clusters = new ArrayList<List<Server>>();
findClusters(netSet,clusters);
System.out.println(clusters.toString());
}
public static void findClusters(Set<Server> netSet,List<List<Server>> clusters){
Iterator<Server> it = netSet.iterator();
while(it.hasNext()){
Server s = it.next();
List<Server> cluster = new ArrayList<Server>();
netSet.remove(s);
findConnected(s,netSet,cluster);
clusters.add(cluster);
it = netSet.iterator();
}
}
public static void findConnected(Server s, Set<Server> netSet, List<Server> cluster){
if(s.left!=null && netSet.contains(s.left)){
netSet.remove(s.left);
findConnected(s.left,netSet,cluster);
}
cluster.add(s);
if(s.right!=null && netSet.contains(s.right)){
netSet.remove(s.right);
findConnected(s.right,netSet,cluster);
}
}
}
There are 2 possible questions:
1) If you cannot shuffle the array. Then we just use 2 pointers.
2) If we can shuffle the array. (This algorithm apparently solves first case as well). We put all values from array to hash map. Then go through the linked list and check if we have node in the hash map.
I have already mentioned a space based solution which some1 has downgraded without giving reason
the other solution without keeping space is:
- kkr.ashish February 01, 2014