谷歌实习店面

Job Hunting Interview
, , , ,
1

两次45分钟的面试, the interviewers pretty much jumped right into it.

一面

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

2

NP-Hard bin packing problem

this one Bin Packing Problem (Minimize number of used Bins) - GeeksforGeeks ?

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

directed/undirected graph?

3

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;
        seeing.add(i);
        for (let nv of graph[i]) {
            if (!dfs(nv)) return false;
        }
        seeing.delete(i);
        seen.add(i);
        return true; 
    }
};

For this one: Find all the nodes that can enter a cycle in a graph. Is the graph directed or undirected? Can the graph have multiple cycles? Can it have multiple connected components? Here’s what I’m thinking:

  1. In a connected component, start DFS from any point and the moment you visit some already visited point, mark that point as start for step 2.
  2. Start from previously marked point and perform DFS. Maintain a set of Nodes that are visited in the DFS path (this is apart from the visited set across all paths). The path where we end up visiting the start again, will have the set of nodes in the cycle.