Google Phone Interviews for Summer Internship

楼主能详细说下第三题的做法吗，用了什么数据结构呀，以及找到之后怎么继续往后查找呢

xiaozhuxiaozhu 发表于 2016-1-15 11:21
有向图查cycle,或者用dfs遍历任何点，然后看路径中，有没有点和起始点重合。
lz比较牛，能写3道题。不过 ...

还是不太懂 input是数组的数组 怎么通过这个构建一个有向图呢？dfs遍历任何点的话感觉时间复杂度会是O(n^n)啊...

atwoodwang0918 发表于 2016-1-15 11:32
还是不太懂 input是数组的数组 怎么通过这个构建一个有向图呢？dfs遍历任何点的话感觉时间复杂度会是O(n^ ...

leetcode里面有一道题是course schedule吧。
图，可以有几种方式表达。
[1,2] [2,3] 这种叫edge lists.

https://leetcode.com/problems/course-schedule/
一道很好的练习。

xiaozhuxiaozhu 发表于 2016-1-15 11:36
leetcode里面有一道题是course schedule吧。
图，可以有几种方式表达。
[1,2] [2,3] 这种叫edge lists. ...

太感谢了！！

xiaozhuxiaozhu 发表于 2016-1-15 10:23
lz能具体讲一下，2 3题的解法么

1. 最短loop那道题我是生成了所有可能情况的排列，比如有三个点a1,a2,a3，就会有6种排列，对于其中一种排列a1,a2,a3，环是a1,a2,a3,a1，距离是dist(a1,a2) + dist(a2,a3) + dist(a3,a1)
2. 求交集的是每次取所有array当前头部的最大值，判断是否这个最大的头部在所有array中出现，如果出现，就加到交集里。

jianglilong0225 发表于 2016-1-16 09:46
1. 最短loop那道题我是生成了所有可能情况的排列，比如有三个点a1,a2,a3，就会有6种排列，对于其中一种排 ...

最短Loop那个估计是个NP问题，应该有更好的解法。但是当时没想到。

atwoodwang0918 发表于 2016-1-15 10:24
楼主能不能详细说下第一题的思路呀 包括老鼠这个类里面有哪些变量？？谢谢了！！祝Offer！！

补充内容 (20 ...

struct Node {
    Node* mom, *dad,
    vector<Node*> children;
    vecctor<Node*> siblings;
};
然后BFS求出他的所有ancestors, 然后求另一个的ancestors的时候查询是否有相同的ancestors。这轮美国哥几乎不说话，所以也不知道这种解法到底好不好。。。

jianglilong0225 发表于 2016-1-16 09:46
1. 最短loop那道题我是生成了所有可能情况的排列，比如有三个点a1,a2,a3，就会有6种排列，对于其中一种排 ...

1. 那找到头部的最大值之后，怎么更快地判断这个值是不是在所有数组里出现了呢？
2. 如果这个值在所有数组里面出现了，加入到结果中，下一步是把所有数组的指针挪到这个值的位置么？

不太懂LZ加面第3题，什么叫“每次取所有array当前头部的最大值”？比如下面几组数
1,2,3,4,5
3,4,5,6,7
3,5,7,9,10
什么是所有array当前头部的最大值？

加面第三题，用一个map把所有array中的数字的出现次数统计出来（同一个array的同一个数字只统计一次），然后取map中所有value==(array的个数)的key就是交集了？

不知道对array交集的定义是否理解正确。