Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

Here is a note why simply modified DFS/BFS/Prim span-searching algorithms are not applicable. Lets consider graph with for vertex with e1 in the middle with following (vertex,vertex,color) tripples: (e1,e2,b),(e1,e3,r),(e1,e4,b). If all these modified algorithms would start with node e4 (as a root) they will fail to find a spanning tree as node e2 may not be included. However, if we choose e3 as a root, the graph per se is a valid spanning tree. So, for any algorithm, when it chooses a starting node it should consider 2 choices: it will be the root or not. Also, while any sub-tree of the standard spanning tree is a "valid" tree, this is not true for this problem (f.e. for the sample above, the sub-tree (e1,e2,e4) is not valid sub-tree as it has only two black edges). This makes impossible to use usual recursive approach: "if we found some valid sub-tree, continue with searching sub-tree for each node for the rest of the graph's vertex".
Also, if we try for every node to assign it as a root and apply some "simply modified" standard algorithm it may fail. Here is an example, where "modified" BFS search would fail to find a valid span-tree for the graph (e1,e2,b),(e1,e3,b),(e2,e3,r),(e3,e4,b) if it starts with e1 as a root. It would accepts e2 and e3 on the first step and stops with fail on the second as e4 may not be attached to the tree. However, there exists a "valid" spanning tree with the root e1: (e1-e2-e3-e4).
I am still searching for the solution...

- celicom May 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think its in fact hidden hamiltonian path problem (because if such a tree exists, it should be just a path trough all nodes)
But this problem has NP-hardness, so bruteforce solution is good enough.

- Matvei April 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about a variation of Prim algorithm:

1.start with an arbitrary edge and add to ST. Let assume that it's black.

2
2.1. add to ST all red edges that cross a cut and respect the restriction (adjacent edges to edges that were added in the previous iteration)
2.2. add to ST all black edges that cross a new cut and respect the restriction
3.repeat until there is no edges that cross a new cut and respect the restriction

- marina.gupshpun April 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't see the reason by the simple modification of Prim algorithm shouldn't work there.

If we have set of vertices which are already in the tree, we can just add any vertex from non-added set. Why? Let's say we cannot do that on some step. That means that there is no edge (valid edge), connecting these 2 sets and there is no solution which is contrary with the statement.

Another great solution is upper in the comments: let's just run Kruskal algorithm, but skip all edges with same color vertices.

- Alex April 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

should we find st or mst?

- ugurdonmez87 April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using BFS, O(m+n). simple. Its sorta adhoc.

- mansi19950 May 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My Solution solves graph Red-Black using a modified DFS, since if always a tree is guaranteed to exist, then you can pick any node as root and start from it's edge list, there will be a guaranteed path to the spanning tree. Time: O (V + E)

public void findRedBlackSpanningTree() {
	List<Edge> r = new ArrayList<>();		
	boolean[] v = new boolean[nodes.size()];
	
	// FIRST TRY BLACK from this node
	dfsBlackRed(nodes.get(0), v, Color.BLACK, r);
	if (r.size() == nodes.size() - 1) {
		printEdges(r);
	} 
	else // IF FROM BLACK NO SPANNING TREE RED-BLACK found TRY RED 
	{
	    r = new ArrayList<>();
		v = new boolean[nodes.size()];
		
		dfsBlackRed(nodes.get(0), v, Color.RED, r);
		if (r.size() == nodes.size() - 1) {
			printEdges(r);
		}			
	}		
}

public void dfsBlackRed(Node root, boolean[] visited, Color previousEdgeColor, List<Edge> r) {
	visited[root.v - 1] = true;		
	Node n = null; // neighbor
	
	for (Edge e : root.edges) {
		
		// get neighbor
		if (root.v == e.n1.v) {
			n = e.n2;
		} else {
			n = e.n1;
		}
		
		if (!visited[n.v - 1] && !e.color.equals(previousEdgeColor)) {
			r.add(e);
			
			if (r.size() == this.nodes.size() - 1) {					
				// found list;
				return;
			}
			
			dfsBlackRed(n, visited, previousEdgeColor.equals(Color.BLACK) ? Color.RED : Color.BLACK, r);					
		}						
	}
}
/*
Sample Test:
Edge e12 = new Edge(n1, n2, Color.BLACK);
Edge e13 = new Edge(n1, n3, Color.BLACK);
Edge e23 = new Edge(n2, n3, Color.RED);
Edge e34 = new Edge(n3, n4, Color.BLACK);

// output: 
1 2 Color: BLACK
2 3 Color: RED
3 4 Color: BLACK
*/

- guilhebl May 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinimumSpanningTreeWithRedBlackEdges<T> {


    public class EdgeComparator implements Comparator<Edge<T>>{

        @Override
        public int compare(Edge<T> edge1, Edge<T> edge2) {

            if(edge1.getWeight()>edge2.getWeight()){
                return 1;
            }else{
                return -1;
            }
        }
    }

    public List<Edge<T>> getMinimumSpanningTreeWithRedBlackEdges(Graph<T> graph){

        if(graph == null){
            return null;
        }

        List<Edge<T>> resultset = new ArrayList<Edge<T>>();

        List<Edge<T>> allEdges = graph.getAllEdges();

        List<Edge<T>> allRedEdges = new ArrayList<Edge<T>>();
        List<Edge<T>> allBlackEdges = new ArrayList<Edge<T>>();

        for(Edge<T> edge : allEdges){
            if(edge.getColor() == "red"){
                allRedEdges.add(edge);
            }else if(edge.getColor() == "black"){
                allBlackEdges.add(edge);
            }
        }

        EdgeComparator edgeComparator = new EdgeComparator();
        Collections.sort(allRedEdges,edgeComparator);
        Collections.sort(allBlackEdges,edgeComparator);
        DisjointSet disjointSet = new DisjointSet();
        disjointSet.makeSet(allRedEdges.get(0).getVertex1().getId());
        ListIterator<Edge<T>> redEdgeIterator = allRedEdges.listIterator();
        ListIterator<Edge<T>> blackEdgeIterator = allBlackEdges.listIterator();

        for(int i = 0;i<allRedEdges.size()+allBlackEdges.size();i++){
            Edge<T> currentEdge;

            if(i%2 == 0 && redEdgeIterator.hasNext()){
                currentEdge = redEdgeIterator.next();
            }else{
                currentEdge = blackEdgeIterator.next();
            }

            long root1 = disjointSet.findset(currentEdge.getVertex1().getId());
            long root2 = disjointSet.findset(currentEdge.getVertex2().getId());

            if(root1 == root2){
                continue;
            }else{
                resultset.add(currentEdge);
                disjointSet.union(currentEdge.getVertex1().getId(),currentEdge.getVertex2().getId());

            }
        }
        return resultset;
    }

}

- nilesh.d.agrawal May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my thinking process.
The open question here is, can any leaf node be a root node ? And the explanation below assumes that leaf node can be a root node.

Let's consider any non-leaf node. This node needs to have at-least one red edge and one black edge, so that path through this node will have alternate red and black edge. Also, it can not have more than one edge of the same color, as any path from that node which involves the edges of the same color will violate the condition.
So, with this what we are looking for is a path through the graph, which touches all the nodes of the graph. And it means that it has only 2 leaf nodes. And only these are the nodes which "may" have the edges of only one color in the original graph.

So following is the algorithm
1. Scan all the nodes, and check if it has edges of only one color.
2. If you get such a node, follow DFS, with alternating color edges, and since the answer is guaranteed to exist, it should result in the path.
3. If we do not find the node with edges of just one color, then choose a random node
4. Try to follow DFS with all the edges in the node.
5. If we do not get the required path, move on to next node. to step 4.

// SpanningTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

#define NO_EDGE 0
#define RED 1
#define BLACK 2

#define V 5

int FindProbableLeafNode(int graph[V][V]) {
    for(int i = 0; i < V; ++i ) {
        int color = NO_EDGE;
        int j;
        for (j = 0; j<V; ++j) {
            if(graph[i][j] == NO_EDGE) {
                continue;
            }
            if(color == NO_EDGE) {
                color = graph[i][j];
            } else if(color != graph[i][j]){
                break;               
            }
        }
        if(j == V) {
            return i;
        }
    }
    return -1;
}

bool checkNode(int newNode, int tree[V][V], int newColor, int currentColor) {
    if(newColor == currentColor) {
        return false;//New color and old color are same. return false
    }
    for(int i = 0; i< V; ++i) {
        if(tree[newNode][i] != NO_EDGE) {
            return false;//Node is already present in the tree;
        }
    }
    return true;
}

bool spanningTreeComplete(int tree[V][V]) {
    int i;
    for(i =0; i<V; ++i) {
        bool vertexPresent = false;
        for( int j = 0; j<V; ++j) {
            if(tree[i][j] != NO_EDGE) {
                vertexPresent = true;
                break;
            }
        }
        if(!vertexPresent) {
            break;
        }
    }
    if(i<V) {
        return false;
    }
    return true;
}

bool getSpanningTree(int graph[V][V], int tree[V][V], int startNode, int currentColor) {
    for(int i = 0; i < V; ++i) {
        if(graph[startNode][i] != NO_EDGE) {
            if(checkNode(i, tree, graph[startNode][i], currentColor)){
                tree[startNode][i] = graph[startNode][i];
                tree[i][startNode] = graph[i][startNode];
                if(spanningTreeComplete(tree)){
                    return true;
                }
                if(getSpanningTree(graph, tree, i, tree[startNode][i])) {
                    return true;
                }
                tree[startNode][i] = NO_EDGE;
                tree[i][startNode] = NO_EDGE;
            }
        }
    }
    return false;
}

void initTree(int tree[V][V]) {
    for(int v1 =0; v1 < V; ++v1) {
        for(int v2 =0; v2 < V; ++v2) {
            tree[v1][v2] = 0;
        }
    }
}

void printSpanningTree(int tree[V][V]) {
    for(int i = 0; i<V;++i) {
        for(int j=0;j<V;++j) {
            printf("%d ", tree[i][j]);
        }
        printf("\n");
    }
}

bool SpanningTree(int graph[V][V]) {
    int val = FindProbableLeafNode(graph);
    if(val == -1) {
        int i;
        //iterate through nodes to find the spanning tree
        for(i = 0; i < V; ++i) {
            int tree[V][V];
            initTree(tree);
            if(getSpanningTree(graph, tree, val, NO_EDGE)) {
                printSpanningTree(tree);
                break;
            }
        }
        if(i == V) {
            printf("No spanning tree possible");
        }
    } else {
        int tree[V][V];
        initTree(tree);
        if(getSpanningTree(graph, tree, val, NO_EDGE)) {
            printSpanningTree(tree);
        } else {
            printf("No spanning tree possible");
        }
    }
    return true;
}

int _tmain(int argc, _TCHAR* argv[]) {
    int graph[V][V] = {
        {0,2,1,1,1},
        {2,0,1,1,1},
        {1,1,0,1,2},
        {1,1,1,0,1},
        {1,1,2,1,0}
    };
    SpanningTree(graph);
    getchar();
	return 0;
}

- Sunil July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have you tested your solution with
-: red
=:
x1-x2=x3-x4=x5-x6=a7-x8=x9
x6-x10
x2=x6
x6-x8
x7-x9


The valid: (x1-x2=x6-x8=x9-x7)
x6-x10
x6-x5=x4-x3

Any kinds of BSF,,.. would find
x1-x2=x3-x4=x5-x6=x7-x8=x9
then we cannot connect x6-x10.

Any ideas?

- lsquang July 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a Bipartite Matching Problem. Just find a matching on the graph and connect the pieces to form the tree.

- Partha May 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use Dijkstra's algorithm with a flag to maintain color of the node in the spanning tree.

- Shreyas April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use Dijkstra's algorithm with a flag to do color check to get the spanning tree.

- Shreyas April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Choose any node as root. Mark it as red. Do a dfs, only visiting edges if their color is opposite to the parent. Mark the destination node with the color of the edge. If all nodes are visited, then this is your tree. Else, mark your root node as black and repeat. Do this for all nodes.

Code in Python (self is a Graph Object):

def RedBlackGraph(self):
	colors = [None]*self.nvertices
	for i in range(self.nvertices):
		for j in range(1):
			colors[i]=bool(j) #red is True, black is False
			print "%s is %s" % (i,bool(j))
			visited = [False]*self.nvertices
			stack = [i]
			order=[]
			parents = [None]*self.nvertices
			while stack:
				node = stack.pop()
				if not visited[node]:
					visited[node] = True
					order.append(node)
					p = self.edges[node]
					while p:
						if p.color!=colors[node] and not visited[p.y]:
							colors[p.y] = not colors[node]
							stack.append(p.y)
							parents[p.y] = node
						p=p.next
			if visited == [True]*self.nvertices:
				ret = []
				for o in order:
					ret.append("%s - %s" % (parents[o],o))
				return ret
	return "No such tree found"

We are doing one dfs per vertex, so running time is O(V(V+E))

- Great Salmon April 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//Similar to DFS with some caching. Not exactly sure what the time complexity here is.I think it's something like O(V^2+E). Space complexity is O(V+E).
public class Edge
{
	int start;
	int end;
	char col;
	public Edge(int s, int e, char c)
	{
		start=s;
		end=e;
		col=c;
	}
	
	public int hashCode()
	{
		return Objects.hash(Integer.valueOf(start),Integer.valueOf(end),Character.valueOf(col));
	}
	
	public boolean equals(Object o)
	{
		if(o==null|| o !instanceof(Edge)))
		{
			return false;
		}
		Edge e=(Edge)o;
		return e.hashCode()==hashCode();
	}
}

public ArrayList<Edge> findTree(ArrayList<Edge>[] adj)
{
	if(adj==null||adj.length==0)
	{
		return Collections.<Edge>emptyList();
	}
	
	HashMap<Edge,ArrayList<Edge>> cache=new HashMap<Edge,ArrayList<Edge>>();
	for(int i=0;i<adj.length;i++)
	{
		HashMap<Integer,Edge> visited=new HashMap<Integer,Edge>();
		boolean r=find(new Edge(i,i,'-'),visited,adj,cache);
		if(r)
		{
			return makeList(visited);
		}
		
	}
	return Collections.<Edge>emptyList();
}

private boolean find(Edge curr,HashMap<Integer,Edge> v, ArrayList<Edge>[] adj,HashMap<Edge,ArrayList<Edge>> cache)
{
	v.put(curr.end,curr);//Mark the current vertex as visited and store the associated edge.
	if(v.size()==adj.length)
	{
		return true;
	}
	boolean result=false;
	//If a dfs through this edge was already done before, use its results
	if(cache.containsKey(curr))
	{
		ArrayList<Edge> ls=cache.get(curr);
		for(Edge x:ls)
		{
			if(!v.containsKey(x.end))
			{
				result=find(x,v,adj,cache);
				if(result)
				{
					break;
				}
			}
		}
	}
	//If a dfs through this edge wasn't done before, recurse
	else
	{
		cache.put(curr,new ArrayList<Edge>());
		int vertex=curr.end;
		for(Edge x: adj[vertex])
		{
			if(x.col!=curr.col && !v.containsKey(x.end))
			{
				cache.get(curr).add(x);
				result=find(x,v,adj,cache);
				if(result)
				{
					break;
				}
			}
		}
		
	}
	return result;
}

- divm01986 April 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Thinking about the resulting spanning tree, every edge in that tree will connect nodes of different color. So you can just remove the edges that connect nodes of the same color from the original graph first and then find a spanning tree (e.g. using DFS).

This algorithm is a DFS that ignores the edges that connect nodes of the same color:

private static void dfs(Node current, List<Edge> result) {
		current.mark();
		
		for (Edge e : current.getNei()){
			Node other = e.getOther();
			if (!e.getOther().isMarked() &&
				 other.getColor() != current.getColor()) {
				result.add(e);
				dfs(other, result);
			}
		}
	}

- javista April 16, 2016 | 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