CareerCup

I have already mentioned a space based solution which some1 has downgraded without giving reason
the other solution without keeping space is:

for(each node in array)
if(node->left!=NULL &&  node->right!=NULL)
count++
else if(node->left==NULL && node->right==NULL)
count--;
else
do nothing;

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);
		}
	}
}

i guess the array of nodes is unordered or else its just a simple question

on a simple thought:
can create a bool a[n] = {false}
and then set it for every occurance in the array then rescan the bool array and we will have the count

By cluster do they mean greater than 1 successive node?

if yes, high level:
- clusterCount = 0
- Sort the Array (if not sorted - nLogN)
- foreach node in the NodeList, do a BinarySeach on the Array nLogN
- increment the clusterCount only if two or greater nodes are found

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.