由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - G家电面结束,必挂。附面经。
相关主题
L家这题咋搞,巨变态请问Oracle口头offer多久正式offer能下来?【附面经】
湾区2012-2013,个人面筋总结刚面A家,附面经,求bless,顺便问个事
终于理解当初面我的某同胞了请教一道面试题
请教amazon面试题今天的Google电话面试题目
F家电面谁会做>??????????????????????????????????????
MS onsite 面经这题有啥好方法吗?
Depth-First-Search被基础题搞挂了
G家电面面经--佛云了~~find top K most occurring words in streaming data 这题怎么做比较好
相关话题的讨论汇总
话题: node话题: 分钟话题: list话题: 必挂话题: 面经
进入JobHunting版参与讨论
1 (共1页)
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成都是想放水的国人
: 你自己赚了却不知道……

1 (共1页)
进入JobHunting版参与讨论
相关主题
find top K most occurring words in streaming data 这题怎么做比较好F家电面
Qualcomm的 On siteMS onsite 面经
2维matrix装水问题Depth-First-Search
这题被问过两次都不会,请教G家电面面经--佛云了~~
L家这题咋搞,巨变态请问Oracle口头offer多久正式offer能下来?【附面经】
湾区2012-2013,个人面筋总结刚面A家,附面经,求bless,顺便问个事
终于理解当初面我的某同胞了请教一道面试题
请教amazon面试题今天的Google电话面试题目
相关话题的讨论汇总
话题: node话题: 分钟话题: list话题: 必挂话题: 面经