Facebook Interview Question Software Engineers
Country: United States
Implementation of above algo.
1. Build un-directed graph
2. Scan in DFS Direction and while scanning , create a new graph( adjacency Map) with vertex and edges in reverse direction of scan
import java.util.*;
public class UnDirectedToDirectedGraph {
//Input Bi-directional graph
HashMap<Integer,LinkedList<Integer>> adjInputUnDirectedMap = new HashMap<Integer,LinkedList<Integer>>();
//Uni-directional graph in reverse-direction of DFS scan
HashMap<Integer,LinkedList<Integer>> adjOutputDirectedMap = new HashMap<Integer,LinkedList<Integer>>();
// Bi-directional Graph
public void addEdgeBiDirectional(int a , int b){
// add a -> b
if(adjInputUnDirectedMap.containsKey(a)){
adjInputUnDirectedMap.get(a).add(b);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(b);
adjInputUnDirectedMap.put(a, newList);
}
// add b -> a
if(adjInputUnDirectedMap.containsKey(b)){
adjInputUnDirectedMap.get(b).add(a);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(a);
adjInputUnDirectedMap.put(b, newList);
}
}
//Unidirectional add
public void addEdgeUniDirectional(int a , int b, HashMap<Integer,LinkedList<Integer>> map){
// add a -> b
if(map.containsKey(a)){
map.get(a).add(b);
}else{
LinkedList<Integer> newList = new LinkedList<Integer>();
newList.add(b);
map.put(a, newList);
}
}
//DFS scan
public void DFS(int startPoint , HashSet<Integer> visited, int from ){
// vertex "from" to "startPoint" is the scan direction
// for the first node, from=-1 (i.e we are starting from nowhere)
if(visited.contains(startPoint)){
return;
}
visited.add(startPoint); // mark it as visited
if(from != -1){
System.out.println("Scan direction :" + from +" -> "+ startPoint);
System.out.println(" Reverse Scan direction(added to output) :" + startPoint +" -> "+ from);
addEdgeUniDirectional( startPoint,from, adjOutputDirectedMap); // add in reverse direction of scan. Important
}
LinkedList<Integer> neighbours = adjInputUnDirectedMap.get(startPoint);
for(int neighbour : neighbours){
DFS(neighbour,visited, startPoint);
}
}
public static void main(String[] args) {
UnDirectedToDirectedGraph obj = new UnDirectedToDirectedGraph();
/*
*
* * 3 <--> 4 <--> 5
* | \
* | \
* 1 2
* \
* \
* 6
*/
// Build bi-directional Map
obj.addEdgeBiDirectional(1,3);
obj.addEdgeBiDirectional(3,1);
obj.addEdgeBiDirectional(3,2);
obj.addEdgeBiDirectional(2,3);
obj.addEdgeBiDirectional(2,6);
obj.addEdgeBiDirectional(6,2);
obj.addEdgeBiDirectional(3,4);
obj.addEdgeBiDirectional(4,3);
obj.addEdgeBiDirectional(4,5);
obj.addEdgeBiDirectional(5,4);
System.out.println("Undirected Graph " + obj.adjInputUnDirectedMap.toString()+"\n");
// Convert bi-directional Graph to Directed Graph in reverse-direction of DFS Scan. leading to element 6
obj.DFS(6, new HashSet<Integer>(),-1);
System.out.println("\nDirected Graph (leading to element 6 : " + obj.adjOutputDirectedMap.toString());
}
}
If there is a cycle in graph, the BFS may not cover all edges. For example, if you have A,B, C nodes connected in a cycle. A--B, B--C, A--C
If you run BFS from B for instance, edge AC is missing. The reason is that BFS and DFS only cover all the nodes and their output is a tree not a graph
BFS obviously.
c# implementation.
using System.Collections.Generic;
using System.Linq;
namespace UndirectedGraphToDAG {
class Program {
static private void ConvertUndirectedGraphToDAG( Node node ) {
var currList = new List<Node> { node };
var prevList = new List<Node>();
while ( currList.Any() ) {
var nextLayer = new List<Node>();
foreach ( var item in currList ) {
item.FromNodes = new List<Node>();
item.ToNodes = prevList.Count == 0 ? null : new List<Node>() ;
item.FillToNodes( prevList );
item.FillFromNodes( currList, nextLayer );
prevList.Add( item );
}
prevList = currList;
currList = nextLayer;
}
}
public class Node {
public List<Node> Nodes = new List<Node>();
public List<Node> ToNodes = null;
public List<Node> FromNodes = null;
public void FillToNodes(List<Node> prevList) {
foreach ( var prev in prevList ) {
if ( Nodes.Contains( prev ) ) {
ToNodes.Add( prev );
}
}
}
public void FillFromNodes( List<Node> currList, List<Node> nextLayer ) {
foreach ( var connNode in Nodes ) {
if ( ToNodes != null && ToNodes.Contains( connNode ) ) { continue; }
FromNodes.Add( connNode );
if ( currList.Contains( connNode ) ) { continue; }
nextLayer.Add( connNode );
}
}
}
static void Main(string[] args) { }
}
}
Perform BFS \ DFS on the undirected graph from the given node, altering edges in the direction of the scan. After you're done, reverse all the edges.
- JBO December 25, 2015