Facebook Interview Question
SDE1sCountry: United States
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;
}
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}};
int n = cyclesCount(adjM);
System.out.println(n);
}
public static int cyclesCount(int[][] adjm) {
int n = adjm.length;
int count = 0;
List<List<Integer>> nodesPath = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
int[] conodes = adjm[i];
List<Integer> cnodes = new ArrayList<Integer>();
cnodes.add(i);
for (int j = 0; j < conodes.length; j++) {
if (adjm[i][j] == 1){
cnodes.add(j);
adjm[i][j] = -1;
count += cycles(adjm, i, j, 0, nodesPath, cnodes);
adjm[i][j] = 1;
}
}
}
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);
nodesPath.add(temp);
return count + 1;
}
if (snode == cnode && nodesPath.contains(conodes))
return count;
int[] nodes = adjm[cnode];
int n = nodes.length;
for (int i = 0; i < n; i++) {
if (adjm[cnode][i] == 1) {
adjm[cnode][i] = -1;
if(i != snode)
conodes.add(i);
Collections.sort(conodes);
count = cycles(adjm, snode, i, count, nodesPath, conodes);
adjm[cnode][i] = 1;
if(i != snode)
conodes.remove(new Integer(i));
}
}
return count;
}
I guess its NP-Hard, www . cs . umd.edu/~jkatz/complexity/f11/lecture23.pdf
- sri December 14, 2017