## Facebook Interview Question for SDE-2s

• 0

Country: India
Interview Type: Written Test

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

You can do smth similar to DFS( or BFS) travel that you only visit the node that you have not visited to prevent loop. You also have to keep track the path from the source so that we can print it out when you reach the destination.

Something to note
- The length of the path is less or equal to N which is the number of vertices
- When you reach the destination then print the path and stop the current search branch since the destination can not be visited second time
- We need to un-visit a node at the end of the recursive function to allow investigation from other branch that might come back to the same node (this is the main different from original DFS or BFS)

``````class Graph {
public:
Graph(int n) : g(n), visit(n, false), path(n, -1) {}
void add(int from, int to) {
g[from].push_back(to); g[to].push_back(from); }
void print_path(int l) const {
for (int i=0; i< l; ++i) cout << path[i] << ' ';
cout << endl;
}
void traverse(int source, int dest) {
fill(visit.begin(), visit.end(), false);
DFS(source, dest, 0);
}
private:
void DFS(int u, int dest, int level) {
path[level] = u;
if (u == dest) {
print_path(level+1);
return;
}
visit[u] = true;
for (auto v : g[u] )
if (!visit[v])
DFS(v, dest, level + 1);
visit[u] = false;
}
vector<vector<int> > g;
vector<bool> visit;
vector<int> path;
}``````

Beside I don't care if you up vote or down-vote my answer, but if you down-vote, that means I did something stupid and I want to know what is your perspective.

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

+1 because you put DFS ( or BFS) instead of the other way around

I assume you compiled and tested (based on what you said in another thread) it so no need to read

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

You should remove the line

``visit[u] = false;``

out of the for loop else it can visit u again for paths originating from v.

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

{{
class Graph {
public:
Graph(int n) : g(n), visit(n, false), path(n, -1) {}
void add(int from, int to) {
g[from].push_back(to); g[to].push_back(from); }
void print_path(int l) const {
for (int i=0; i< l; ++i) cout << path[i] << ' ';
cout << endl;
}
void traverse(int source, int dest) {
fill(visit.begin(), visit.end(), false);
DFS(source, dest, 0);
}
private:
void DFS(int u, int dest, int level) {
path[level] = u;
if (u == dest) {
print_path(level+1);
return;
}
visit[u] = true;
for (auto v : g[u] )
if (!visit[v])
DFS(v, dest, level + 1);
visit[u] = false;
}
vector<vector<int> > g;
vector<bool> visit;
vector<int> path;
}
}}

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

``````class Graph {
public:
Graph(int n) : g(n), visit(n, false), path(n, -1) {}
void add(int from, int to) {
g[from].push_back(to); g[to].push_back(from); }
void print_path(int l) const {
for (int i=0; i< l; ++i) cout << path[i] << ' ';
cout << endl;
}
void traverse(int source, int dest) {
fill(visit.begin(), visit.end(), false);
DFS(source, dest, 0);
}
private:
void DFS(int u, int dest, int level) {
path[level] = u;
if (u == dest) {
print_path(level+1);
return;
}
visit[u] = true;
for (auto v : g[u] )
if (!visit[v])
DFS(v, dest, level + 1);
visit[u] = false;
}
vector<vector<int> > g;
vector<bool> visit;
vector<int> path;
}``````

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

I wonder who are haha and Test, these sound like some test "names".

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

``````static void PrintAllPaths(List<int>[] graph, int n, int source, int dest)
{
DFS(source, dest, graph, new List<int>(), new bool[n]);
}

static void DFS(int v, int dest, List<int>[] g, List<int> path, bool[] used)
{
used[v] = true;

if (v == dest)
{
Print(path);
}
else
{
foreach(int u in g[v])
{
if (!used[u]) DFS(u, dest, g, path, used);
}
}

path.RemoveAt(path.Count - 1);
used[v] = false;
}``````

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

print path in a recursive way

``````GRAPH={'A':['B','C','D'], 'B':['A','C','D'], 'C':['A','B','D'], 'D':['A','B','C']}

def find_noloop_path(s, t, path):
if s in path:###already visited in path
return

if s == t:###find the target
print path + [t]
return

path.append(s)
for n in GRAPH[s]:
find_noloop_path(n, t, path[:])

find_noloop_path('A', 'C', [])``````

result:
['A', 'B', 'C']
['A', 'B', 'D', 'C']
['A', 'C']
['A', 'D', 'B', 'C']
['A', 'D', 'C']

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

``````ArrayList<ArrayList<Node>> allPath(Node s, Node t){
Queue<ArrayList<Node>> q = new Queue<ArrayList<Node>>();
ArrayList<Node> list = new ArrayList<Node> ();
q.enque(list);
ArrayList<ArrayList<Node>> result = new ArrayList<ArrayList<Node>>();
while(!q.empty()){
ArrayList<Node> cur = q.deque();
Node temp = cur.get(cur.size()-1);
for(Node n : temp.neighbors){
if(!cur.contains(n)){
ArrayList<Node> tar = new ArrayList<Node>(cur.subList(0, cur.size()));
if(n == t){
}
else
q.enque(tar);
}
}
}
return result;
}``````

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

Here my C++ solution:

``````#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
public:
Graph(int n) : g(n) {}

void add(int from, int to) {
g[from].push_back(to); g[to].push_back(from); }

public:
void print_path() {
for(int i = 0; i < path.size(); i++) {
cout << path[i] << ' ';
}
cout << endl;
}
void traverse(int source, int dest) {
DFS(source, dest);
}
private:
void DFS(int u, int dest) {
path.push_back(u);

if (u == dest) {
print_path();
}
else {
for (auto v : g[u]) {
bool stop = false;

for(auto s : path) {
if(s == v) {
stop = true;
}
}

if(!stop) {
DFS(v, dest);
}
}
}
path.pop_back();
}

vector<vector<int> > g;
vector<int> path;
};

int main() {

Graph g(8);

// no node with 3

g.traverse(0, 6);

return 0;
}``````

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.