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成都是想放水的国人 : 你自己赚了却不知道……
|