Google Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
5
of 7 vote

1. Remove the edge (pointer) from 1.
2. Find connected components.
3. The answer is the number of connected components - 1 (i.e. all the connected components except for the one that contains 1).

- Julian January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Step 2 is linear time, btw: we just run a depth-first search, which is linear because we have O(N) edges.

- Julian January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why we should remove the edge from 1.
And How your solution work for sample test case 2.
please elaborate

- Gaurav Gupta June 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey please elaborate how sample 2 work according your algo. thanks

- gauravit94 June 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For sample2: there is only one connected component, but no pointer points to node 1, so we need to change one node in this case.
In summary:
1. Find connected components
2. Categorize connected components into three:
1). component that doesn't contain node1
2). component that contain node 1, but doesn't have a node point to it
3). component that contain node 1, but do have a node point to it
3. so the total number is:
1) + 2)

- carotene February 02, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

,

- c February 02, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think this problem can be reduced to finding a spanning dfs forest with minimum number of trees.

1. First, we'll create a new graph by reversing all the edges in original input graph, this graph will simply be denoted by G. Notice that all the vertices reachable from 1 in G are "good vertices".

2. We'll build a stack of the roots of the dfs forest which is the result of running dfs on G starting from the vertex 1 and when you need to select a new root, select the minimum possible (notice that if all the vertices are reachable from 1 then instead of a forest we have a single tree). Whenever we encounter a new root throughout the dfs run we'll just push it to the stack.

3. We'll run dfs again on G but this time, instead of starting from 1, we'll use the roots stack from (2) whenever we need a new root to traverse from (roots that were already encountered throughout the dfs run will just be popped and ignored). Throughout this dfs run we'll yet again build a root stack of the roots in the dfs forest (for this dfs run).

4. The resulting root stack from step (3) should contain the minimum number of trees in the dfs forest for the graph G (considering the special structure of G - exactly 1 incoming edge to each vertex). The result is the number of roots in the stack from (3) minus 1 if 1 is a root as well.

Complexity: Two dfs runs - O(n) (the number of vertices and edges is O(n)).

Code: snipt.org/BihG4

- IvgenyNovo January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it seems correct, but i cant get why it's work.

- glebstepanov1992 January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this example doesnt work 2,3,4,2,6,5 expected 2, actual -1

- glebstepanov1992 January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

glebstepanov1992, in my code I count from 0 to n-1 instead of from 1 to n. So the input for the example above should be {1,2,3,1,5,4} which yields the output 2 as desired.


Anyway, Julian offered a much more elegant solution below whose correctness is based on the following claims:

1. Let C be a (weakly) connected component in a directed graph. Suppose the incoming degree of each vertex in C is exactly 1. Then there exists some vertex r in C from for which every other vertex v in C is reachable from (in the directed graph). In other words, r is a root of C. This can be proved using the correctness of the algorithm for finding a root in a directed graph.

2. Let C be a (weakly) connected component in a directed graph. Suppose the incoming degree of every vertex in C, except some vertex r, is exactly 1 while r's incoming degree is 0. Then r is a root of C in the directed graph. This can be proved by simply determining the orientation of each edge in the undirected path from r to every other vertex in C (using the fact that the incoming degree is exactly 1 for every other vertex).

Removing the outgoing edge from the vertex 1 means that the vertex 1 has an incoming degree of 0 in the edge reversed graph while all the other vertices have an incoming degree of exactly 1. The claims above imply that by finding the number of (weakly) connected components in the new directed graph we'll be able to determine the minimum amount of roots in a dfs spanning forest where 1 is a root as well. So the answer would be the number of connected components minus 1 (for the component of the vertex 1) as Julian noted.

- IvgenyNovo January 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

It is so simple why people are even using any algorithms

#include <stdio.h>

int main() {

    int n,i,ans=0;
    scanf("%d",&n);
    int a;
    int c[1000]={0};
    for(i=0;i<n;i++){
        scanf("%d",&a);
        c[a-1]=1;
    }
    for(i=1;i<1000;i++){
        if(c[i]==1)
            ans++;
    }
    printf("%d",ans);
    return 0;
}

- Mohit Sati September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

This won't work when the input is 555555. It will state 4 changes when it should be 1.

- Thomas April 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. build graphs: label -> Node
2. remove all nodes point to(directly or in-directly) #1
3. count remaining independent graphs

import java.util.*;

class GoodNodes{
  public static void main(String[] args){
    //int[] array = {1,2,3,4,5};
    int[] array = {5,5,5,5,5};

    GoodNodes s = new GoodNodes();
    int rst = s.needChange(array);

    Helper.p(rst);
  }

  int needChange(int[] array){
    //1. build graphs: label -> Node
    Map<Integer, Node> map = buildMap(array);

    //remove all nodes point to(directly or in-directly) #1
    Set<Node> remaining = removeGoodNodes(map);

    //count remaining independent graphs
    int rst = countNumOfGraphs(remaining);

    return rst;
  }

  Map<Integer, Node> buildMap(int[] array){
    Map<Integer, Node> map = new HashMap<Integer, Node>();

    for(int i = 0; i < array.length; i++){
      int cur = i + 1;
      int to = array[i];

      if(cur == to){
        Node node = map.containsKey(cur)? map.get(cur):new Node(cur);
        map.put(cur, node);
      }else{
        Node curNode = map.containsKey(cur)? map.get(cur):new Node(cur);
        Node toNode = map.containsKey(to)? map.get(to): new Node(to);

        curNode.out = toNode;
        toNode.ins.add(curNode);

        map.put(cur, curNode);
        map.put(to, toNode);
      }
    }

    return map;
  }

  Set<Node> removeGoodNodes(Map<Integer, Node> map){
    Node origin = map.get(1);

    Set<Integer> visited = new HashSet<Integer>();
    LinkedList<Integer> q = new LinkedList<Integer>();
    visited.add(1);
    q.add(1);

    while(!q.isEmpty()){
      int cur = q.remove();

      Node node = map.get(cur);
      for(Node n: node.ins){
        int label = n.label;

        if(!visited.contains(label)){
          visited.add(label);
          q.add(label);
        }
      }
    }

    Set<Node> rst = new HashSet<Node>();
    for(int i = 1; i <= map.size(); i++){
      if(!visited.contains(i)){
        rst.add(map.get(i));
      }
    }

    return rst;
  }

  //count piece of parts
  int countNumOfGraphs(Set<Node> nodes){
    int rst = 0;
    //bfs
    Set<Node> visited = new HashSet<Node>();

    for(Node node: nodes){
      if(!visited.contains(node)){
        rst++;

        LinkedList<Node> q = new LinkedList<Node>();
        visited.add(node);
        q.add(node);

        while(!q.isEmpty()){
          Node cur = q.remove();

          Node out = cur.out;
          if(out != null && nodes.contains(out) && !visited.contains(out)){
            visited.add(out);
            q.add(out);
          }

          for(Node in : cur.ins){
            if(nodes.contains(in) && !visited.contains(in)){
              visited.add(in);
              q.add(in);
            }
          }
        }
      }
    }

    return rst;
  }

  class Node{
    int label;

    Node out;
    List<Node> ins;

    public Node(int label){
      this.label = label;
      this.ins = new ArrayList<Node>();
    }
  }
}

//TEST
//1,2,3,4,5 => 4
//5,5,5,5,5 => 1

- DiveIntoTomorrow August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class GoodBadNodes {
    public static void main(String... args) {
        System.out.println(goodNodes(new int[]{5, 3, 1, 5, 2}));
    }

    static int goodNodes(int[] points_to) {
        //there is one "good" community and some "bad" comunities
        //the answer to the problen is the number of isolated bad communities.
        //or at least i suppose so...

        Map<Integer, Set<Integer>> communities = new HashMap<>();
        communities.put(1, new HashSet<>());

        for (int i = 1; i < points_to.length; i++) {
            Set<Integer> community = communities.get(points_to[i]);
            if (community == null) {
                community = new HashSet<>();
                communities.put(points_to[i], community);
            }

            community.add(i);
        }

        //make communities larger until they don't change
        boolean changed;
        do {
            changed = false;
            for (Iterator<Integer> i = communities.keySet().iterator(); i.hasNext(); ) {
                int index = i.next();
                if (index == 1) {
                    continue;
                }
                Set<Integer> community = communities.get(index);
                //if points to itself - continue
                if (points_to[index - 1] == index) {
                    continue;
                }

                Set<Integer> newCommunity = communities.get(points_to[index - 1]);
                if (newCommunity != null) {
                    //make old community members to point to the new community
                    for (Integer member : community) {
                        points_to[member] = points_to[index - 1];
                    }

                    newCommunity.addAll(community);
                    i.remove();
                    changed = true;
                }

            }
        } while (changed);

        return communities.size() - 1;
    }
}

}

- Ashot Golovenko August 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find all good nodes from the begging.( BFS or DFS)
2. Then Find all strong connected components. From those node, who arent good.
Answer uis a number of SCC.

- glebstepanov1992 January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

2 <- 3 <- 4 <- 5 has four SCCs

- Julian January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep a map M of lists such that map.get(i) = lists of nodes that points to (i) minus the i-th node;
also keep a set S of good nodes, initialize with the tail node;
then starting from the list of nodes that point to the tail node, proceed the lists and mark every node a good node (put it in the set S); repeat this step with nodes in the list;
finish when every node in the list is already a good node or the list is empty;

- meow February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int nChangesToMakeAllNodesGood(List<Integer> nodes_list)
    {
        if(nodes_list.isEmpty())
            return 0;

        // list of marked items
        List<Integer> visited_list = new ArrayList<Integer>(nodes_list.size());
        for(int i = 0; i < visited_list.size(); ++i)
            visited_list.set(i, -1);
        
        int ncomponents = 1, npass = 0;
        visited_list.set(0, 0);
        for(int i = 0; i < nodes_list.size(); ++i)
        {
            if( isNewComponent(nodes_list, visited_list, i, npass++) )
                ++ncomponents;
        }
        
        return ncomponents-1;        
    }
    public static Boolean isNewComponent(List<Integer> nodes_list, List<Integer> visited_list, int i, int cur_pass)
    {
        // delete link from first node: if first node, then it's an old component and return
        if(i == 0)
            return false;

        // found node visited on previous passes: old component
        if(visited_list.get(i) > 0 && visited_list.get(i) != cur_pass )
            return false;
        // found node visited in this pass: new component
        if(visited_list.get(i) == cur_pass)
            return true;
        // current node hasn't been visited: mark as cur_pass
        visited_list.set(i, cur_pass);
        
        return isNewComponent(nodes_list, visited_list, nodes_list.get(i), cur_pass);  
    }

- teodor.mz May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think this one works. I haven't studied much Graph theory but this was what came to my mind.

def find_root(arr, i):
	if(arr[i] == i):
		return i
	return find_root(arr, arr[i])

def count_max_nodes(arr):
	for i in range(len(arr)):
		arr[i] = arr[i] - 1
	temp = {}
	for i in range(1,len(arr)):
		root = find_root(arr,i)
		if root != 0:
			temp[root] = 1
	
	print(len(temp))

count_max_nodes([1,2,3,4,5])
count_max_nodes([5,5,5,5,5])
count_max_nodes([1,5,1,2,5])

- Hardik Parikh September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It doesn't work after testing.

- LiWang1025 April 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) assign each node with its idx, parent, rank(initially will be '0')
example. for input 1, 2, 3, 3, 5 , it will be {[1, 1, 0], [2, 2, 0], [3, 3, 0], [4, 3, 0], [5, 5, 0]}
2) go through the list and assign rank by finding parent of each node
for the above input, it will be {[1, 1, 1], [2, 2, 1], [3, 3, 2], [4, 3, 0], [5, 5, 0]}
3) Now go through the list and count non zero rank nodes except first node(its already tail node).
for the above input, it will be 2, 3, 5 with non zero ranks, so the count is 3.. you need to change nodes to make all nodes to be good node.

- Ramesh April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why aren't we just counting the nodes that are pointing to themselves? Just exclude the first node

- essgee September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Count nodes except 1 that point to themselves

- essgee September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this a normal BFS with maintaining the visted nodes.
Count the number of nodes we get while traversing and subtract that from the total count?

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

Based on @Julian's idea, the solution can be based on union-find method. union all connected nodes. count total groups number M. if there's a group which the good node is the root, than return M-1, else return M.
An optimised union-find algorithms takes almost o(n) to union all nodes. So the time and space complexity of this algorithms is o(n)

class Solution{
    int[] list=null;
    int count=0;
    public int getMinNodesToChange(int[] nodes){
        int N=nodes.length;
        count=N;
        list=new int[N+1];
        for (int i=1; i<=N; i++) list[i]=i;
        int flag=0;
        for (int i=1; i<=N; i++){
            if (nodes[i-1]==1) flag=1;
            union (i, nodes[i-1]);
        }
        return count - flag;
    }  
    public void union(int i, int j){
        int rootI=findRoot(i);
        int rootJ=findRoot(j);
        if (rootI==rootJ) return;
        list[rootJ]=rootI;
        count--;
    }
    public int findRoot(int i){
        while (list[i]!=i){
            int tmp=list[i];
            list[i]=list[tmp];
            i=tmp;            
        }
        return i;
    }
}

- snail914 December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if there is no cycle then we just need to find the node pointing itself
Code in Python

n=6
l=[5,5,5,5,5]
change = []
for i in range(1,len(l)):
	j=i+1
	if(l[i]==j):
		change.append(l[i])
length = len(change)
print(length)

- surbhi.arora3010 March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

that was just max 15-20 line code .. dont know y u guys writing large program

#include<iostream>
using namespace std;

int fun(int arr[],int k,int []);

int main()
{
int n;
cin>>n;
int arr[n+1]={0},ar[n+1]={0};
for(int i=1;i<=n;i++)
cin>>arr[i];
arr[1]=-1;

int sum=0;
for(int i=2;i<=n;i++)
if(fun(arr,i,ar)==-1)
sum+=1;
cout<<sum;



return 0;
}

int fun(int arr[],int k,int ar[])
{
if(arr[k]==-1 || arr[k]==-2) return -2;

if(ar[k]>0) return -1;
ar[k]+=1;

arr[k]=fun(arr,arr[k],ar);

return arr[k];
}

- jit December 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define pb push_back
vector<int> v[1000];
int r[1000]={0};
int vis[1000]={0};
int dfs(int x)
{

   // cout<<"x "<<x<<endl;
    vis[x]=1;

        if(!vis[v[x][0]])
        {
            //cout<<"here\n";
            int z=dfs(v[x][0]);
            if(z==-1)
                return x;
            else
            {
                r[x]=z;
                return z;
            }
        }
        else
        {
            //r[x]=r[i];
            //cout<<"returning "<<x<<" = "<<r[v[x][0]]<<endl;
            r[x]=r[v[x][0]];
            return r[v[x][0]];
        }
    return -1;
}

int main()
{

    int n;
    cin>>n;
    int i;
    //v.resize(n+1);

    for(i=1;i<=n;i++)
        r[i]=i;
    for(i=1;i<=n;i++)
    {
        int x;
        cin>>x;

        v[i].pb(x);
    }
    for(i=1;i<=n;i++)
    {

        if(!vis[i])
        {
           // cout<<"For i "<<i<<endl;
            dfs(i);
        }
    }
    /*
    for(i=1;i<=n;i++)
        cout<<r[i]<<" ";
    cout<<endl;*/
    int ch=1;
    map<int,int> m;
    for(i=2;i<=n;i++)
    {
        if(r[i]!=ch)
        {
            m[r[i]]++;
        }
    }
    cout<<m.size()<<endl;
}

- rishav007 July 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int good_graph(vector<int> nodes)
{
	int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
    		
    		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;

}

- Anonymous October 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int good_graph(vector<int> nodes)
{
	int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
    		
    		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;
	
}

- logan October 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int good_graph(vector<int> nodes)
{int len=nodes.size();
	
		int *visited = new int[len];
		int *good = new int[len];
		memset(visited,0,sizeof visited);
		good[0]=1;
		visited[1];
	 		
	int ans=0;
	
    for(int i = 0; i < len; i++) 
    {
    	int p=nodes[i];
    	int t=i;
    	while(1)
    	{
   		if(p==0)
    			break;
    		if(good[p]==0 && visited[p]==1)
    		{
    			ans++;
    			good[p]=1;
    			break;
			}
    	
    	    //good[p]=1;
    		visited[p]=1;
    		p=nodes[p];
    		nodes[t]=0;
 			t=p;
		}
    	
	}
        
    return ans;
}
int main()
{
	
	int n;
	cout<<"enter no. of nodes: ";
	cin>>n;
	//adj = new list<int>[n]; 
	
	vector<int> nodes(n,0);
	cout<<"enter for each node the direction of edge\n";
	for(int i=0;i<n;i++)
	{
		cin>>nodes[i];
		nodes[i]-=1;
	}
	int ans=good_graph(nodes);
	cout<<"\nminimum change of pointers\n";
	cout<<ans<<endl;
	return 0;

}

- logan October 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use Union find data structure and it making everything simple right ??

- Adarsh Sunilkumar January 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

(1) Scan the list, for each node U if U points to V and V is not U, mark node U (there's an out going edge from U)

(2) Scan the list and count the number of node V that is not marked in (1) and that is not the tail.

- Anonymous January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work because we don't need to modify every edge that initially has no path to node 1. It's possible to imagine a situation, for instance, where all nodes except node 1 form one giant cycle. If you now modify just any one node in the cycle to point to node 1, you will have a path for every node. The answer in that case would be 1 rather than N - 1.

- eugene.yarovoi January 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Create a graph. First run strong connected component algorithm, in the SCCG count nodes without outgoing edges.

- Anonymous January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not necessary to be strongly connected, just connected.

- Julian January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

i think that we need strong connected components, because if we want to make set of nodes good, they must be interconnected. We have to choose such node , that will be connected to all other in set.

- glebstepanov1992 January 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider the case where the graph looks like one big tree rooted at node 1, with an edge from each child to its parent. The answer is 0 because node 1 can be reached from all other nodes and there is therefore no need to change any of the edges. However, the entire tree is clearly not just one strongly connected component. You can see from this example that detecting SCCs doesn't give you the answer.

- eugene.yarovoi January 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Most answers here over-complicate the problem to graph algorithms. An O(n) time solution with O(n) space complexity is given below. The solution associates timestamps with (threads of) nodes and uses these timestamps to determine whether the encountered node is undiscovered, good or bad. No actual nodes are created all the data is maintained in two arrays of size n.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;

public class GoodNodes {
	 public static void main(String [] argv) throws Exception {
		 int [] nodes = readNodes(new BufferedReader(new InputStreamReader(System.in)));
		 int changeCnt = getNumRedirects(nodes);
		 System.out.println("Result is " + changeCnt);



	 }

	 public static int getNumRedirects(int [] nodes){
		 int n = nodes.length;
		 if(n < 1) return 0;
		 int [] timestamps = new int[n];
		 int ts = 1;
		 HashSet<Integer> goodTimes = new HashSet<>();
		 timestamps[0] = ts;
		 int ret = 0 ;
		 for(int i = 1; i < n ; i++){
			 if(timestamps[i] <= 0) {
				 ts++;
				 int c = i;
				 while(timestamps[c] <=0){
					 timestamps[c] = ts;
					 c = nodes[c];
				 }
				 if(timestamps[c] < ts){
					 if(goodTimes.contains(timestamps[c]) ){
						 goodTimes.add(ts);
					 }
				 } else { // equals
					 ret++;
				 }
			 }		

		 }
		 return ret;
	 }


	 private static int [] readNodes(BufferedReader ps) throws Exception {
		 int n = readInt(ps);
		 int [] ret = new int[n];
		 for(int i = 0; i < n ; i++){
			 ret[i] = readInt(ps)-1;
		 }
		 return ret;
	 }

	 private static int readInt(BufferedReader ps) throws Exception {
		 return Integer.parseInt(ps.readLine().trim());
	 }


 }

- konst May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
Actually, you do not need to maintain the goodTimes HashSet so the code after while can be: {{{ if(timestamps[c] == ts){ ret++; } }} - konst May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

1. We just need to detect cycles and trees, later we need just count them as in cycle we can change any node to point to first node and in tree we need to change only root node to pointing to first node, the alg quite similar to union find

public static void main(String[] args) {
        int[] nodes = {0,2,3,4,0};
        //int[] nodes = {5, 2, 3, 4, 1, 0, 0};
        int[] clusters = new int[nodes.length];
        for (int i = 0; i < clusters.length; i++) {
            clusters[i] = -1;
        }

        for (int i = 0; i < clusters.length; i++) {
            if (clusters[i] == -1) {
                int s = mark(i, i, clusters, nodes);

                if (s != i) {
                    for (int j = 0; j < clusters.length; j++) {
                        if (clusters[j] == i) {
                            clusters[j] = s;
                        }
                    }
                }
            }
        }

        //System.out.println(Arrays.toString(clusters));

        int[] count = new int[nodes.length];
        int sum = 0;
        for (int cluster : clusters) {
            if (count[cluster] == 0) {
                count[cluster] = 1;
                sum++;
            }
        }

        //System.out.println(Arrays.toString(count));

        if( clusters[0] == 0 ){
            sum--;
        }

        System.out.println(sum);
    }

    public static int mark(int cluster, int i, int[] clusters, int[] nodes) {
        if (clusters[i] == -1) {
            clusters[i] = cluster;
            if (nodes[i] != i) {
                return mark(cluster, nodes[i], clusters, nodes);
            } else {
                return i;
            }
        } else {
            return clusters[i];
        }

}

- Anonymous January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

try 1 2 3 4 3 and you'll find it does not work.

I guess we need to remove node 0 first.

- LiWang1025 April 16, 2015 | Flag
Comment hidden because of low score. Click to expand.


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