## Facebook Interview Question for SDE1s

Country: United States

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

I guess its NP-Hard, www . cs . umd.edu/~jkatz/complexity/f11/lecture23.pdf

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

O(n^3) time, O(n^2) space

``````int num_cycles(int** m, int n) {
int count = 0;
for (int i = 0; i < n; ++i) {
std::queue<std::pair<int, std::unordered_set<int>>> frontier;
frontier.push({ i, {} });
int steps = 0;
while (!frontier.empty() && steps < n - i) {
int src = frontier.front().first;
std::unordered_set<int> visited = frontier.front().second;
frontier.pop();
if (m[src][i] == 1) {
++count;
}
for (int j = i + 1; j < n; ++j) {
if (visited.find(j) == visited.end() && m[src][j] == 1) {
auto new_visited(visited);
new_visited.insert(j);
frontier.push({ j, new_visited });
}
}
++steps;
}
}
return count;
}``````

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

``````public static void main(String args[]) {
/**
*       0
*      / \     4
*     /   \   / \
*    3     \ /   \
*    \       1----5
*     \     /
*      \   /
*        2
*       /_\
*
*   7 cycles
*/

int[][] adjM = { { 0, 1, 0, 0, 0, 0}, { 0, 0, 1, 0, 1, 0}, { 0, 0, 1, 1, 0, 0}, { 1, 0, 0, 0 , 0, 0}, { 0, 0, 0, 0 , 0, 1}, { 0, 1, 0, 0 , 0, 0}};
System.out.println(n);
}

public static int cyclesCount(int[][] adjm) {
int count = 0;
List<List<Integer>> nodesPath = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
List<Integer> cnodes = new ArrayList<Integer>();
for (int j = 0; j < conodes.length; j++) {
count += cycles(adjm, i, j, 0, nodesPath, cnodes);
}
}
}
return count;
}

public static int cycles(int[][] adjm, int snode, int cnode, int count, List<List<Integer>> nodesPath,
List<Integer> conodes) {
if (snode == cnode && !nodesPath.contains(conodes)) {
List<Integer> temp = new ArrayList<>(conodes);
return count + 1;
}
if (snode == cnode && nodesPath.contains(conodes))
return count;

int n = nodes.length;
for (int i = 0; i < n; i++) {
if(i != snode)
Collections.sort(conodes);
count = cycles(adjm, snode, i, count, nodesPath, conodes);
if(i != snode)
conodes.remove(new Integer(i));
}
}
return count;
}``````

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.