g*******d
发帖数: 495 | 1 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
视我的水平，写这种类似竞赛题目都是高中的事情了
其他三个面试官的问题，大家可以参考下难度：
1. linked list 实现queue还是什么的，外加删除操作
2. 电话本里输入名字前几个字母让显示相应的名字
3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
个一个指针的）
这位国人问的问题是：
有一个linked list，除了next指针以外还有一个随机指针。让我复制一下这个list。
我用C写的，首先想到的是O(n^2)复杂度的，然后我没写的时候她就说可以有O(n)的…
…然后我憋了许久没想法，最后还有15分钟的时候她提示说可以用HashTable写一个次
优的（多占内存嘛）。
我当时相当的不行啊，用C的人有哪个是常用HashTable的……而且她说“网上还有同样
O（n）而且内存更少的解法”。我当时那个恨啊，心想咋这么为难同胞呢……
今天不小心翻到何海涛的那本书，看到这道题目，一模一样的啊，瞬间明白这位同胞的
良苦用心了……可惜当时木有看到过这个题目啊 |
m******k
发帖数: 593 | 2 软广告 :-)
zan一个!
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
f********4
发帖数: 988 | 3 快快握手，我当时也是去M面的，也是第二轮一个国人问的我这个题。。
我和楼主一样啊，当时也是这道题用map做的，果然不满意。
后来我回来问的人时候大家跟我说这是国内很有名的一道题。额。。可是我在国内的时
候不是学CS的。。怨念。 |
r**h
发帖数: 1288 | 4 哈哈，赞分享经验
2. 电话本里输入名字前几个字母让显示相应的名字
这个是不是要用trie+DFS呢，还是有更好的办法？
3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
好奇问一下一个指针的情况要怎么处理？是不是需要多一个field来存当前的size？
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
p*****2
发帖数: 21240 | 5
说实话，出这题的人都有病。
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
w********p
发帖数: 948 | 6 电话本里输入名字前几个字母让显示相应的名字。
这题phone call 里写代码，有多少人有信心过？ 好奇下。 |
h**6
发帖数: 4160 | 7 我被问过，写前缀树失败了。
【在 w********p 的大作中提到】
: 电话本里输入名字前几个字母让显示相应的名字。
: 这题phone call 里写代码，有多少人有信心过？ 好奇下。
|
a***r
发帖数: 93 | 8
非常同意，我还多次注意到中国女尤其喜欢问这道题。
【在 p*****2 的大作中提到】
:
: 说实话，出这题的人都有病。
|
i**c
发帖数: 753 | 9 真幸福，可以说中文。我去面的时候也遇到一个中国人，他英语不是很好，好像在琢磨
是跟我说英语还是汉语。于是我也很紧张。
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
g*******d
发帖数: 495 | 10 开始时候面试官用英文问我，是prefer中文还是英文，我说both OK.然后她就开始中文。
一开始用中文描述简历上一些近期的经历，还有点不习惯…… |
|
|
f*******t
发帖数: 7549 | 11 哈，我面FB时碰到一国人，让我sort linked list。一开始他说有个linked list，我
还以为是这个复制带random pointer的题呢，结果他说他不喜欢考，因为最优解是个
trick，而他喜欢solid solution。 |
d****o
发帖数: 1055 | 12 哈哈，我面amazon的时候，我的直属领导面我就是这道复制题。结果我在最后只剩15
min的情况下秒杀了这题。
他很吃惊。。。说：我没有想到你能够做出来。。。
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
h****n
发帖数: 1093 | 13 这题确实考的没啥意义，属于见过能秒杀，没见过只能秒跪的类型
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
l**b
发帖数: 457 | 14 这题目真心没什么意思。
1）和实际生活太远了。
2）这个最有的解法没见过的，面试当时想，应该没有多少正常人能想出来。不排除他
们就要非正常的。 |
s**s
发帖数: 70 | 15 我也感觉是
高端粉。。
【在 m******k 的大作中提到】
: 软广告 :-)
: zan一个!
|
c******n
发帖数: 7263 | 16 人出这道题有放水的意思在里面吧
【在 l**b 的大作中提到】
: 这题目真心没什么意思。
: 1）和实际生活太远了。
: 2）这个最有的解法没见过的，面试当时想，应该没有多少正常人能想出来。不排除他
: 们就要非正常的。
|
h*d
发帖数: 19309 | 17 国内读CS但是没听说过何海涛的飘过
【在 f********4 的大作中提到】
: 快快握手，我当时也是去M面的，也是第二轮一个国人问的我这个题。。
: 我和楼主一样啊，当时也是这道题用map做的，果然不满意。
: 后来我回来问的人时候大家跟我说这是国内很有名的一道题。额。。可是我在国内的时
: 候不是学CS的。。怨念。
|
l**b
发帖数: 457 | 18 防水的话，随便出一个什么2个BT是不是一样这种不更加好吗？
【在 c******n 的大作中提到】
: 人出这道题有放水的意思在里面吧
|
b******y
发帖数: 9224 | 19
haha, 没错。折磨人玩儿。
话说那个链表另外再加一个指针的问题，正解好像是需要遍历链表两次即可
【在 p*****2 的大作中提到】
:
: 说实话，出这题的人都有病。
|
b******y
发帖数: 9224 | 20 第一遍用个map记录关系，第二遍可以还原。。。 |
|
|
b******y
发帖数: 9224 | 21 不过挺无聊的。难道公司除了雇佣会题海战术出来的程序猿外，就不考虑culture, 是
否肯干，等等等等。其实，那些东西也同样重要的。 |
z*****u
发帖数: 3010 | 22 我还是没有理解题目
感觉不是从头到尾过一遍就行了？ |
i***h
发帖数: 12655 | 23 复制链表是经典题啊
我至少被考过两次了
可惜第一次在狗家不知道正解
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
n****r
发帖数: 471 | 24 没看懂题目，能不能给仔细解释一下呢？
什么是随机指针呢？
【在 i***h 的大作中提到】
: 复制链表是经典题啊
: 我至少被考过两次了
: 可惜第一次在狗家不知道正解
|
q*****r
发帖数: 35 | |
i***h
发帖数: 12655 | |
s*******1
发帖数: 3820 | 27 国人一般都为难国人的，网上有共识的吧。
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
j********2
发帖数: 4438 | 28
客观的说一句，肯不肯干，culture合不合不是一两次interview就能搞清楚的，不如做
题来的简单直接。
【在 b******y 的大作中提到】
: 不过挺无聊的。难道公司除了雇佣会题海战术出来的程序猿外，就不考虑culture, 是
: 否肯干，等等等等。其实，那些东西也同样重要的。
|
d*****e
发帖数: 7368 | 29 当年我们组用C， 能用hashtabl得地方就不会用别的。
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
b*******l
发帖数: 590 | |
|
|
h*****4
发帖数: 4219 | |
M*********n
发帖数: 506 | 32
复制这题，需不需要保留原linked list?
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
M*********n
发帖数: 506 | 33
当年我老最后一面，也是这题，属于以前见过没时间做的，结果当场想出来了，直接在
linkedlist上面来回指，不用hashtable，不过结果破坏了原linked list。现在想想，
可以在多用一个数组，就可以把原来的还原。复杂度就是o(n),空间复杂度也是o(n)，
只是多用了一个n大小的数组
【在 g*******d 的大作中提到】
: 去年去M家面实习，第二个面我的是个女性国人，用中文面的，外加lunch interview。
: 一般说是这轮即使有技术问题也会相对简单，但是她问的问题是我觉得里面最难的。
: 当时属于没有看过任何关于面试的书的状况，翻了翻算法教材就上去了……大家不要鄙
: 视我的水平，写这种类似竞赛题目都是高中的事情了
: 其他三个面试官的问题，大家可以参考下难度：
: 1. linked list 实现queue还是什么的，外加删除操作
: 2. 电话本里输入名字前几个字母让显示相应的名字
: 3. ring buffer的实现（我马上写出来了，用两个指针，三姐还非要说只要一个指针之
: 类；之前用xen的时候，xen的ring buffer好像是两个指针，我就习惯了；后来就写了
: 个一个指针的）
|
b*******d
发帖数: 75 | 34 肯定是把人拉过来实际工作一段时间最能看得出一个人的工作能力，但大公司申请的人
那么多，都这么来一下招人的成本太高了。就像高考，虽然分数不是唯一的，但要读大
学的人那么多，让大学在每个人身上花那么多时间去考察一个学生的综合素质大学都没
时间办了，因此唯有使用简单粗暴一刀切的考试，起码大部分有能力的人是会从中脱颖
而出的。能筛选出这些人公司就已经很嗨皮了，就算因此会进来一些浑水摸鱼的，也只
能算作是机会成本了
【在 b******y 的大作中提到】
: 不过挺无聊的。难道公司除了雇佣会题海战术出来的程序猿外，就不考虑culture, 是
: 否肯干，等等等等。其实，那些东西也同样重要的。
|
