## Facebook Interview Question for Software Engineers

Country: United States

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

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.

Comment hidden because of low score. Click to expand.
0

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
//Uni-directional graph in reverse-direction of DFS scan

// Bi-directional Graph
public void addEdgeBiDirectional(int a , int b){
}else{
}

}else{
}
}

if(map.containsKey(a)){
}else{
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);
}

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

// Convert bi-directional Graph to Directed Graph in reverse-direction of DFS Scan. leading to element 6
obj.DFS(6, new HashSet<Integer>(),-1);
}
}``````

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

its an undirected graph...how do you topological sort an undirected graph ?

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

1) Topological sort a graph.
2) Delete the edges where order is not satisfied by the sorted vertices.

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

Does the question assume a connected graph?

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

This is really simple:
1. Topological sort the graph with root as the specified node. Assume this node has least topological order.
2. For all edges, orient them from higher topological order node to lower topological order node.

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 = 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 ) ) {
}
}
}

public void FillFromNodes( List<Node> currList, List<Node> nextLayer ) {
foreach ( var connNode in Nodes ) {

if ( ToNodes != null && ToNodes.Contains( connNode ) ) { continue; }

if ( currList.Contains( connNode ) ) { continue; }
}
}
}

static void Main(string[] args) { }
}
}``````

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.

### 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.