w********g
发帖数: 106 | 1 20分钟 - 问我问题基础概念题。
15分钟 - 只出了一道coding题，很简单，是我水平不行才花了那么久。
5分钟 - 针对上题问问题。不是bug，就是针对题目问问题。
5分钟 - 叫我问问题。
正好45分钟。
版上大牛们都至少问两道题，可是我只被问了一道，完全是因为我水平差，15分钟只能
写一道简单题。
必挂，不过也不沮丧。
面经：
介绍我的project和困难
thread和process区别
为什么多线程
为什么多进程
怎么确保线程并行不出错，他貌似期待预防死锁之类的回答
java generic和旧版java中什么类似 ----这题谁能给我讲讲？
TCP从协议角度看怎么工作的
TCP连接从实际角度看怎么工作的
还有大约四五道问题，想不起来了。
coding：
有个list，他的节点的是
class Node
{
T data;
Node next;//singly linked. Assume no loop.
Node extra;//Points to another node in the list
}
写个deep copy。就这么简单。
我大脑秀逗了，写了15分钟，还好自己测试了没发现bug。
其实写个七八分钟就该能写完。不过也没什么沮丧的，继续努力吧。
哦by the way，谁能告诉我这题怎么写。我想看看自己是不是花了15分钟仍然写出来了
一坨垃圾。 |
w********g
发帖数: 106 | 2 还有，recruiter的话不可全信。说是完全不问简历上的内容，也不问general
questions，只问coding，结果coding之前就花了20分钟时间。
【在 w********g 的大作中提到】
: 20分钟 - 问我问题基础概念题。
: 15分钟 - 只出了一道coding题，很简单，是我水平不行才花了那么久。
: 5分钟 - 针对上题问问题。不是bug，就是针对题目问问题。
: 5分钟 - 叫我问问题。
: 正好45分钟。
: 版上大牛们都至少问两道题，可是我只被问了一道，完全是因为我水平差，15分钟只能
: 写一道简单题。
: 必挂，不过也不沮丧。
: 面经：
: 介绍我的project和困难
|
g********E
发帖数: 178 | 3 15分钟写出来很快了啊，deep copy关键是用个map记录copied nodes防止重复copy。当
然对这个题来说还有个高级解法不要extra space,扫两遍list就行了。
-----
另外我45分钟就做了一道题，也过了，还是个老印面试官，所以你也很有希望的，
bless! |
w********g
发帖数: 106 | 4 我用HashTable做的。其实本质上就是deep copy一个图。当然因为是list也能按list线
性做，麻烦点，但还是O(n)。
他对用hashTable很不满意，于是追问为什么真运行起来会比O(n)慢很多，我不知道，
他说你一行一行看，我说因为HashTable真运行起来会冲突，hash一次就不是O(1)了，
他同意。
请问你说的那个不要extra space的高级解法怎么做？
【在 g********E 的大作中提到】
: 15分钟写出来很快了啊，deep copy关键是用个map记录copied nodes防止重复copy。当
: 然对这个题来说还有个高级解法不要extra space,扫两遍list就行了。
: -----
: 另外我45分钟就做了一道题，也过了，还是个老印面试官，所以你也很有希望的，
: bless!
|
h********e
发帖数: 1972 | 5 不出意料的话，这题的另一个解法是图的深度优先搜索。复杂度边线性。不需要额外空
间和hashtable |
g*******s
发帖数: 2963 | 6 第一遍follow next指针copy所有node
第二遍copy extra指针，这时所有node都已经存在了，也不用create新node了，所以不
用hash判断了。
【在 w********g 的大作中提到】
: 我用HashTable做的。其实本质上就是deep copy一个图。当然因为是list也能按list线
: 性做，麻烦点，但还是O(n)。
: 他对用hashTable很不满意，于是追问为什么真运行起来会比O(n)慢很多，我不知道，
: 他说你一行一行看，我说因为HashTable真运行起来会冲突，hash一次就不是O(1)了，
: 他同意。
: 请问你说的那个不要extra space的高级解法怎么做？
|
g*******e
发帖数: 91 | 7 别灰心。非大牛问一道题也过，比如我去年。不过onsite还是被拒。如果真没过，想想
你至少省下来了一天假期。再说你不是给了面经，攒的人品可能够你过了。
【在 w********g 的大作中提到】
: 20分钟 - 问我问题基础概念题。
: 15分钟 - 只出了一道coding题，很简单，是我水平不行才花了那么久。
: 5分钟 - 针对上题问问题。不是bug，就是针对题目问问题。
: 5分钟 - 叫我问问题。
: 正好45分钟。
: 版上大牛们都至少问两道题，可是我只被问了一道，完全是因为我水平差，15分钟只能
: 写一道简单题。
: 必挂，不过也不沮丧。
: 面经：
: 介绍我的project和困难
|
w********g
发帖数: 106 | 8 原图
a----b----c----d
|___________^
新图
A----B----C----D
|___________^
第二遍copy extra指针时，怎么确定 a->b 和 A->B 的对应关系呢？
【在 g*******s 的大作中提到】
: 第一遍follow next指针copy所有node
: 第二遍copy extra指针，这时所有node都已经存在了，也不用create新node了，所以不
: 用hash判断了。
|
g********E
发帖数: 178 | 9 你这样还是得用map来记录原node和目标node的对应关系。
图的DFS也是需要map记录visited nodes的
如果只是这样一个list with arbitrary pointer,第一遍在每个node后面复制一个：
a->b->c => a->a'->b->b'->c->c'
第二遍添加arbitrary pointer, 比如a'->child = a->child->next
最后把origin nodes都去掉就行了，因为是linked list,总时间还是线性的。
【在 g*******s 的大作中提到】
: 第一遍follow next指针copy所有node
: 第二遍copy extra指针，这时所有node都已经存在了，也不用create新node了，所以不
: 用hash判断了。
|
w********g
发帖数: 106 | 10 明白了，谢谢！
【在 g********E 的大作中提到】
: 你这样还是得用map来记录原node和目标node的对应关系。
: 图的DFS也是需要map记录visited nodes的
: 如果只是这样一个list with arbitrary pointer,第一遍在每个node后面复制一个：
: a->b->c => a->a'->b->b'->c->c'
: 第二遍添加arbitrary pointer, 比如a'->child = a->child->next
: 最后把origin nodes都去掉就行了，因为是linked list,总时间还是线性的。
|
g****y
发帖数: 2810 | 11 海涛程序员面试题100问原题
此题过于技巧化，没什么大意思。但是只要在国内找过工作的都知道，烙印基本都不会
但凡问你这道题8,9成都是想放水的国人
你自己赚了却不知道……
【在 w********g 的大作中提到】
: 20分钟 - 问我问题基础概念题。
: 15分钟 - 只出了一道coding题，很简单，是我水平不行才花了那么久。
: 5分钟 - 针对上题问问题。不是bug，就是针对题目问问题。
: 5分钟 - 叫我问问题。
: 正好45分钟。
: 版上大牛们都至少问两道题，可是我只被问了一道，完全是因为我水平差，15分钟只能
: 写一道简单题。
: 必挂，不过也不沮丧。
: 面经：
: 介绍我的project和困难
|
w********g
发帖数: 106 | 12 面试官是个美国MM
【在 g****y 的大作中提到】
: 海涛程序员面试题100问原题
: 此题过于技巧化，没什么大意思。但是只要在国内找过工作的都知道，烙印基本都不会
: 但凡问你这道题8,9成都是想放水的国人
: 你自己赚了却不知道……
|
