# 谷歌实习店面

• Sort a list of items (warm up)
• Find all the nodes that can enter a cycle in a graph

• NP-Hard bin packing problem

The second interviewer seemed like he did not want to be there and misread the question several times. Regardless, I still think I would have failed due to limited coding experience.

NP-Hard bin packing problem

Find all the nodes that can enter a cycle in a graph

directed/undirected graph?

for finding all nodes in a graph, if you are given the number of nodes, is directed, and given an array of edges it’s like the course schedule problem…

``````var cycledNodes = function(n, edges) {
const seen = new Set();
const seeing = new Set();
const cycled = [];
const graph = Array(n).fill().map(() => []);

for (let [c, p] of edges) {
graph[c].push(p)
}

for (let i = 0; i < n; i++) {
if (!dfs(i)) cycled.push(i);
}
return cycled;

function dfs(i) {
if (seeing.has(i)) return false;
if (seen.has(i)) return true;
for (let nv of graph[i]) {
if (!dfs(nv)) return false;
}
seeing.delete(i);