Google Interview Question Software Developers
Country: United States
Interview Type: In-Person
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
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.
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
*/
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;
}
}
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;
}
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))
//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;
}
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);
}
}
}
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".
- celicom May 09, 2016Also, 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...