logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
看着有什么问题
avatar
看着有什么问题# Joke - 肚皮舞运动
f*e
1 楼
第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见
过这个题目。
3. 9月底的时候google安排10月11号onsite面试。
4. 9月中旬到9月底这段时间，我主要在看算法导论视频跟着练习口语。
5. 10.1 fb onsite。 我的运气很好，没有遇到印度人，3轮面试中2个面试官是白人，
另外一个是中国人，所以听力这块没任何压力。fb的题目总体不难，他们每次面试前都
会介绍自己在哪个组，是做什么的。第一轮的时候面试官自我介绍完后就直接步入正题
，在白板上写代码，题目有：判断一堆线段是否相交，3 sum zero, 实现next_
permutation，然后一道数学题（无限大棋盘的跳马问题，时间不够，没做出来）。
第二轮的面试官自我介绍完后跟我聊了很多我研究生期间做的东西，以及简历上的一个
项目，然后让我在纸上实现字符串查找函数strstr。这个时候我没马上写代码，而是告
诉他有很多算法可以做这件事情，比如有naive的，或者比较高级的，然后他马上说
naive的就ok了。写完后，他问我刚才提到有比较高级的算法？我就给他解释了下kmp。
之后他又开始扩展这题，说如果待匹配的内容很大并且不会变，但是有很多模式串怎
么办。我给了说了2种算法，一种是把待匹配串的所有后缀都插入到一颗TRIE树种，另
一种是利用RQ hash函数（这种算法需要假设模式串的长度都不会很长）。
第三轮大部分时间都在聊项目以及以前的一些经历，最后快结束的时候让我写了2个程
序，一个是数的进制转换，一个是在一个BST中求第k大的数。。
6. fb onsite完后第二天hr找我要reference，又过了4天左右offer就来了。
7. 10.11号google onsite，在上海进行的，上午2轮，然后在那边吃午饭，下午再进行
一轮。onsite的题目不便多讲，有一题在昨天的某个帖子中已经提到了(binary tree
max path sum)，另外值得分享的一题是给定一颗完全二叉树的根结点，求这颗树的结
点数。这个题大家可以想下。
另外下午三面的时候，那个面试官很凶的样子，不知道是不是故意的，跟他讨论的时候
他的分贝会逐渐提高。。。。 搞的我很心虚，还好对做题没多大影响。
最终结果： G和F都拿到了offer，F的RSU多些，并且G没sign on，个人感觉F更适合我
，于是上周六给fb hr说准备去hr了。 不过今天G又打电话说可以给我加package，比F
会高，考虑到我已经给fb说要去了，反悔不太好，于是拒绝了。。。
avatar
m*d
2 楼
avatar
t*1
3 楼
牛，再国内拿的offer？
avatar
r*e
4 楼
腿弯的不正常

【在 m**d 的大作中提到】

avatar
f*4
5 楼
完全二叉树总结点数是用二分判断高度来做吗？
g电面只一轮？

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
f*e
6 楼
nb!

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
f*e
7 楼
恩 反正google总共就4轮面试，你要是进行了2轮电话面试，onsite的话就只有2轮。
求高度不是直接从根节点一直向左走就可以了吗?

【在 f*******4 的大作中提到】
: 完全二叉树总结点数是用二分判断高度来做吗？
: g电面只一轮？
avatar
f*e
8 楼
Google全部是在国内面的，面的国外的职位。
Facebook onsite是去美国面的。

【在 t******1 的大作中提到】
: 牛，再国内拿的offer？
avatar
f*e
9 楼
O(h)怎么算出来? 完全二叉树不是满二叉树。
avatar
h*u
10 楼
mark
avatar
f*e
11 楼
找最底层最右边叶子结点？从根节点先右转再左转，然后从根节点先左转再右转找转捩
点，i.e.左拐or右拐点。每一步耗时2*h，然后recurse on next level。
所以sum(2*i)=O(h^2)

【在 f****e 的大作中提到】
: O(h)怎么算出来? 完全二叉树不是满二叉树。
avatar
f*e
12 楼
…… 你就直接说具体算法吧
O(h)求出高度了，怎么确定总结点数？
再说一下，完全二叉树不是满二叉树。完全二叉树最后一层的结点都在左边，但没必要
是满的。
另外你说“2倍叶子节点数”，先不管这个对不对，你怎么确定叶子结点数？

【在 f*****e 的大作中提到】
: 找最底层最右边叶子结点？从根节点先右转再左转，然后从根节点先左转再右转找转捩
: 点，i.e.左拐or右拐点。每一步耗时2*h，然后recurse on next level。
: 所以sum(2*i)=O(h^2)
avatar
m*s
13 楼
喔，好像不太对。。。O(h^2)出来恩。。。
二分 h * log(2^h)

【在 f****e 的大作中提到】
: O(h)怎么算出来? 完全二叉树不是满二叉树。
avatar
f*e
14 楼
恩 O(h^2)的话应该和我当时说的算法一样，面试官没让继续优化，应该是最优的了吧
....

【在 m******s 的大作中提到】
: 喔，好像不太对。。。O(h^2)出来恩。。。
: 二分 h * log(2^h)
avatar
m*s
15 楼
一时想不出来了恩。。。gxgx

【在 f****e 的大作中提到】
: 恩 O(h^2)的话应该和我当时说的算法一样，面试官没让继续优化，应该是最优的了吧
: ....
avatar
h*n
16 楼
NB。。。楼主是搞ACM的吧。。

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
j*g
17 楼
LZ好牛！谢谢分享！
“判断一堆线段是否相交”
请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
sweep line也可以弄成general的？
avatar
f*e
18 楼
CLRS上好像有这题。

【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
avatar
A*u
19 楼
牛

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
m*s
20 楼
line sweep O(nlogn)
不过计算几何的东西写起来要小心

【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
avatar
l*m
21 楼
先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）

【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
avatar
p*2
22 楼
不睡觉了。过来膜拜一下大牛。
avatar
p*2
23 楼
对了，LZ是master吗？感觉G对master其实不是很友好。
avatar
h*n
24 楼
你这是在一条直线上么，我以为是二维的

【在 l***m 的大作中提到】
: 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）
avatar
l*m
25 楼
是二维的啊。。

【在 h****n 的大作中提到】
: 你这是在一条直线上么，我以为是二维的
avatar
f*e
26 楼
书上用的是Red black tree。

【在 l***m 的大作中提到】
: 是二维的啊。。
avatar
C*U
27 楼
牛逼
恭喜!
顺便问 copy a link list with a random ptr
这个题是啥?
avatar
h*n
28 楼
能展开说说你的方法吗
怎么还用到了二叉树？

【在 l***m 的大作中提到】
: 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）
avatar
p*2
29 楼

书上哪一章呀？

【在 f*****e 的大作中提到】
: 书上用的是Red black tree。
avatar
p*2
30 楼

河海涛上有。是道老题。很坑爹。感觉没见过估计要跪。

【在 C***U 的大作中提到】
: 牛逼
: 恭喜!
: 顺便问 copy a link list with a random ptr
: 这个题是啥?
avatar
C*U
31 楼
再问河海涛是啥?
谢二爷啊

【在 p*****2 的大作中提到】
:
: 河海涛上有。是道老题。很坑爹。感觉没见过估计要跪。
avatar
l*m
32 楼
Step 1: Sort the endpoints of the segments by their x-coordinates。 Recall
sorting can be done in O(nlogn）
Step 2: for i = 1…2n If point Pi is a left endpoint of segment Sa, insert
Sa into a BST using the ycoordinate
of Pi as the key
During inserts: update the key of each node visited. New key is y-value of
point where corresponding segment intersects with red line.
􀂾After insert of segment sa, find its neighbors, S(predecessor) and
S(successor), and test if Sa intersects with either one
If point pi is a right endpoint of segment Sa, remove Sa. Check if the
neighbors of sa intersect after it
is removed
During inserts: update the key of each node visited. New key is y-value of
point where corresponding segment intersects with red line.
After insert of segment sa, find its neighbors, S(predecessor) and S(
successor), and test if sa intersects with either one

【在 h****n 的大作中提到】
: 能展开说说你的方法吗
: 怎么还用到了二叉树？
avatar
p*2
33 楼

我还以为大家都知道呢。我其实也没怎么看过，就看过这一题。

【在 C***U 的大作中提到】
: 再问河海涛是啥?
: 谢二爷啊
avatar
h*n
34 楼
多谢，学习了
楼主一个45分钟面试能写出三个难题出来，也难怪拿牛offer

and

【在 l***m 的大作中提到】
: Step 1: Sort the endpoints of the segments by their x-coordinates。 Recall
: sorting can be done in O(nlogn）
: Step 2: for i = 1…2n If point Pi is a left endpoint of segment Sa, insert
: Sa into a BST using the ycoordinate
: of Pi as the key
: During inserts: update the key of each node visited. New key is y-value of
: point where corresponding segment intersects with red line.
: 􀂾After insert of segment sa, find its neighbors, S(predecessor) and
: S(successor), and test if Sa intersects with either one
: If point pi is a right endpoint of segment Sa, remove Sa. Check if the
avatar
C*U
35 楼
那给我讲一下具体题目啊
谢了哦

【在 p*****2 的大作中提到】
:
: 我还以为大家都知道呢。我其实也没怎么看过，就看过这一题。
avatar
p*2
36 楼

就是一个linkedlist, 每个node有一个random ptr 指向一个随机的node，然后要clone
这个linkedlist。

【在 C***U 的大作中提到】
: 那给我讲一下具体题目啊
: 谢了哦
avatar
f*e
37 楼
33.2 第三版 p1021

【在 p*****2 的大作中提到】
:
: 就是一个linkedlist, 每个node有一个random ptr 指向一个随机的node，然后要clone
: 这个linkedlist。
avatar
D*d
38 楼
可以先按 x axis 排序(假设升序)，然后查 y 是否有降序的。
总共是 O(nlgn) + O(n) = O(nlgn)

【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
avatar
e*s
39 楼
膜拜大牛～mark 着慢慢看
avatar
e*s
40 楼
copy a link list with a random ptr
这题有两中方法。
一种用hashmap，Loop两次，一次写next，一次写random
一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
avatar
h*r
41 楼
on site 有两轮？不是都一轮么？

【在 f****e 的大作中提到】
: 恩 反正google总共就4轮面试，你要是进行了2轮电话面试，onsite的话就只有2轮。
: 求高度不是直接从根节点一直向左走就可以了吗?
avatar
p*2
42 楼

多谢。晚上去看看。

【在 f*****e 的大作中提到】
: 33.2 第三版 p1021
avatar
g*u
43 楼
多谢分享
Super Congrats!
avatar
c*r
44 楼
cong!
现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了

第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见
过这个题目。
3. 9月底的时候google安排10月11号onsite面试。
4. 9月中旬到9月底这段时间，我主要在看算法导论视频跟着练习口语。
5. 10.1 fb onsite。 我的运气很好，没有遇到印度人，3轮面试中2个面试官是白人，
另外一个是中国人，所以听力这块没任何压力。fb的题目总体不难，他们每次面试前都
会介绍自己在哪个组，是做什么的。第一轮的时候面试官自我介绍完后就直接步入正题
，在白板上写代码，题目有：判断一堆线段是否相交，3 sum zero, 实现next_
permutation，然后一道数学题（无限大棋盘的跳马问题，时间不够，没做出来）。
第二轮的面试官自我介绍完后跟我聊了很多我研究生期间做的东西，以及简历上的一个
项目，然后让我在纸上实现字符串查找函数strstr。这个时候我没马上写代码，而是告
诉他有很多算法可以做这件事情，比如有naive的，或者比较高级的，然后他马上说
naive的就ok了。写完后，他问我刚才提到有比较高级的算法？我就给他解释了下kmp。
之后他又开始扩展这题，说如果待匹配的内容很大并且不会变，但是有很多模式串怎
么办。我给了说了2种算法，一种是把待匹配串的所有后缀都插入到一颗TRIE树种，另
一种是利用RK hash函数（这种算法需要假设模式串的长度都不会很长）。
第三轮大部分时间都在聊项目以及以前的一些经历，最后快结束的时候让我写了2个程
序，一个是数的进制转换，一个是在一个BST中求第k大的数。。
6. fb onsite完后第二天hr找我要reference，又过了4天左右offer就来了。
7. 10.11号google onsite，在上海进行的，上午2轮，然后在那边吃午饭，下午再进行
一轮。onsite的题目不便多讲，有一题在昨天的某个帖子中已经提到了(binary tree
max path sum)，另外值得分享的一题是给定一颗完全二叉树的根结点，求这颗树的结
点数。这个题大家可以想下。
另外下午三面的时候，那个面试官很凶的样子，不知道是不是故意的，跟他讨论的时候
他的分贝会逐渐提高。。。。 搞的我很心虚，还好对做题没多大影响。
最终结果： G和F都拿到了offer，F的RSU多些，并且G没sign on，个人感觉F更适合我
，于是上周六给fb hr说准备去hr了。 不过今天G又打电话说可以给我加package，比F
会高，考虑到我已经给fb说要去了，反悔不太好，于是拒绝了。。。

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
f*e
45 楼
那还不如本科过来。

【在 c*****r 的大作中提到】
: cong!
: 现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了
:
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
avatar
p*2
46 楼

都是大牛，一般人也比不了吧

【在 c*****r 的大作中提到】
: cong!
: 现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了
:
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
avatar
j*2
47 楼
拓扑排序和穿线二叉树那两题分别是什么啊？大牛能详细说说吗？

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
l*m
48 楼
我觉得拓扑排序应该是定义一些关系，然后让你输出最终的order吧，比如现在定义的
字母顺序是a,b,c,d,e,f,g,他如果重新定义一些顺序比如c->a，等等，让你重新输出
order的序列，就是用拓扑排序。
穿线二叉树我猜是把树的每一层连起来成一个linked list吧。

【在 j******2 的大作中提到】
: 拓扑排序和穿线二叉树那两题分别是什么啊？大牛能详细说说吗？
avatar
e*e
49 楼
Can you elaborate on the hashmap approach, particularly how to locate the
node to which the random pointer points in the copied list by using hashmap.
Thanks.

【在 e***s 的大作中提到】
: copy a link list with a random ptr
: 这题有两中方法。
: 一种用hashmap，Loop两次，一次写next，一次写random
: 一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
avatar
f*e
50 楼
第二种方法好简单，妙！

【在 e***s 的大作中提到】
: copy a link list with a random ptr
: 这题有两中方法。
: 一种用hashmap，Loop两次，一次写next，一次写random
: 一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
avatar
e*s
51 楼
hashmap
那么
newhead.random = hashmap[oldhead.random];

hashmap.

【在 e****e 的大作中提到】
: Can you elaborate on the hashmap approach, particularly how to locate the
: node to which the random pointer points in the copied list by using hashmap.
: Thanks.
avatar
l*c
52 楼
厉害
avatar
e*e
53 楼
Thanks for your reply.
I'm still puzzled. I guess hashmap store the old node as its key and the old
node which its random pointer points to as its value? For new node, how it
can find the new random node by looking up hashmap? Thanks.

【在 e***s 的大作中提到】
: hashmap
: 那么
: newhead.random = hashmap[oldhead.random];
:
: hashmap.
avatar
e*s
54 楼
不是key = node, Value = node.random
是，key = oldnode， Value = newnode. Which newnode has the same value as
oldnode.
if (head == null)
return null;
StrangLLNode h = head;
StrangLLNode ret = new StrangLLNode(h.Value);
StrangLLNode p = ret;
Dictionary map = new Dictionary<
StrangLLNode, StrangLLNode>();
map.Add(head, ret);
h = h.Next;
//Copy the List, assign their next pointer and put the nodes in
map
while (h != null)
{
map.Add(h, p.Next = new StrangLLNode(h.Value));
h = h.Next;
p = p.Next;
}
//loop the old list again and assign the random pointer
h = head;
p = ret;
while (h != null)
{
p.Random = map[h.Random];
h = h.Next;
p = p.Next;
}
return ret;

old
it

【在 e****e 的大作中提到】
: Thanks for your reply.
: I'm still puzzled. I guess hashmap store the old node as its key and the old
: node which its random pointer points to as its value? For new node, how it
: can find the new random node by looking up hashmap? Thanks.
avatar
e*s
55 楼
能不能解释一下怎样 O(h^2)求 complete BT nodes啊？
avatar
e*e
56 楼
Now I see your hashmap approach. Thank you so much for the details and code.
That's a novel approach for this classic question. Thanks for the sharing.
Appreciate it.

【在 e***s 的大作中提到】
: 不是key = node, Value = node.random
: 是，key = oldnode， Value = newnode. Which newnode has the same value as
: oldnode.
: if (head == null)
: return null;
: StrangLLNode h = head;
: StrangLLNode ret = new StrangLLNode(h.Value);
: StrangLLNode p = ret;
: Dictionary map = new Dictionary<
: StrangLLNode, StrangLLNode>();
avatar
p*e
57 楼
多串模式匹配做好的方法可能是suffix array+LCP
预处理O(m)，然后每个query的复杂度是O(n+lgm)

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
f*e
58 楼
let depth = d;
q=root;
for(i=0; i < d; i++){
p=q->left; p=p->right->right...; depth of p is d1.
q = (d1==d)?(q->right):(q->left);
}
O(1+2...+d)=O(d^2)

【在 e***s 的大作中提到】
: 能不能解释一下怎样 O(h^2)求 complete BT nodes啊？
avatar
C*e
59 楼
赞信息分享～～

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
m*s
60 楼
要我估计会说AC自动机，然后要写code的话直接跪掉。。。

【在 p*****e 的大作中提到】
: 多串模式匹配做好的方法可能是suffix array+LCP
: 预处理O(m)，然后每个query的复杂度是O(n+lgm)
avatar
p*e
61 楼
suffix array + LCP写code的话也要跪……
因为LCP如果要O(n)的话还要写RMQ...

【在 m******s 的大作中提到】
: 要我估计会说AC自动机，然后要写code的话直接跪掉。。。
avatar
S*1
62 楼
Great!
Thanks!

【在 e***s 的大作中提到】
: 不是key = node, Value = node.random
: 是，key = oldnode， Value = newnode. Which newnode has the same value as
: oldnode.
: if (head == null)
: return null;
: StrangLLNode h = head;
: StrangLLNode ret = new StrangLLNode(h.Value);
: StrangLLNode p = ret;
: Dictionary map = new Dictionary<
: StrangLLNode, StrangLLNode>();
avatar
S*1
63 楼
Mo Bai Niu Ren......
Not the same level...

【在 f****e 的大作中提到】
: 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
: 1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
: 是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
: 随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
: 完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
: 个过程不到30分钟。
: fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
: 个问题该怎么回答，另外还要我要好好练习英语口语。
: 2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
: 。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
avatar
l*a
64 楼
二爷看明白了讲讲。
p1027的第二行有句话看不懂。
"If p is on sweep line z, then q = p."
p是a和b的交点，再加一个endpoint q，岂不是三条线段相交了，和假设不符啊。

【在 p*****2 的大作中提到】
:
: 都是大牛，一般人也比不了吧
avatar
p*2
65 楼

刚才看了看。其实我特别烦几何。本来我数学题也不行，练了练还凑活了。结果开始流
行几何了，搞的我就放弃了。
这东西感觉有点偏呀，不觉得我面试能碰上。

【在 l*****a 的大作中提到】
: 二爷看明白了讲讲。
: p1027的第二行有句话看不懂。
: "If p is on sweep line z, then q = p."
: p是a和b的交点，再加一个endpoint q，岂不是三条线段相交了，和假设不符啊。
avatar
l*b
66 楼
NB, mark
avatar
w*x
67 楼

and
这个.... 我被震惊了， 这个算法太牛了！！
FB出这个题指望给出这个算法吗？

【在 l***m 的大作中提到】
: Step 1: Sort the endpoints of the segments by their x-coordinates。 Recall
: sorting can be done in O(nlogn）
: Step 2: for i = 1…2n If point Pi is a left endpoint of segment Sa, insert
: Sa into a BST using the ycoordinate
: of Pi as the key
: During inserts: update the key of each node visited. New key is y-value of
: point where corresponding segment intersects with red line.
: 􀂾After insert of segment sa, find its neighbors, S(predecessor) and
: S(successor), and test if Sa intersects with either one
: If point pi is a right endpoint of segment Sa, remove Sa. Check if the
avatar
p*2
68 楼

你说说你的算法吧。

【在 w****x 的大作中提到】
:
: and
: 这个.... 我被震惊了， 这个算法太牛了！！
: FB出这个题指望给出这个算法吗？
avatar
w*x
69 楼

晕， 我连怎么判断线段相交都写不出来

【在 p*****2 的大作中提到】
:
: 你说说你的算法吧。
avatar
l*m
70 楼
这个好像学校上课讲过。。。

【在 w****x 的大作中提到】
:
: 晕， 我连怎么判断线段相交都写不出来
avatar
p*2
71 楼

那天问你你不是说很简单吗？

【在 w****x 的大作中提到】
:
: 晕， 我连怎么判断线段相交都写不出来
avatar
w*x
72 楼

靠，我以为是一维的

【在 p*****2 的大作中提到】
:
: 那天问你你不是说很简单吗？
avatar
w*x
73 楼

刚对照算法导论花了3个半小时才看明白，头都快晕了

【在 l***m 的大作中提到】
: 这个好像学校上课讲过。。。
avatar
h*n
74 楼
大牛啊~~~~~
膜拜之

【在 l***m 的大作中提到】
: 这个好像学校上课讲过。。。
avatar
p*2
75 楼

靠。白让我膜拜了。

【在 w****x 的大作中提到】
:
: 刚对照算法导论花了3个半小时才看明白，头都快晕了
avatar
w*x
76 楼

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，你太搞了

【在 p*****2 的大作中提到】
:
: 靠。白让我膜拜了。
avatar
j*e
77 楼
FB要你从国内飞到美国来面试？出机票钱么？你真牛阿
avatar
q*m
78 楼
第二种方法能详细点吗？后面插的node 是random 的node 吗

【在 e***s 的大作中提到】
: copy a link list with a random ptr
: 这题有两中方法。
: 一种用hashmap，Loop两次，一次写next，一次写random
: 一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
avatar
l*o
79 楼
mark
相关阅读
隔壁老王家里热水器坏了，来咱家冲个澡今天某段子提了下Brian May，才知道叔PhD白念了。Skype为什么这么愚蠢陈百祥是周星驰电影里的配角钟最出彩的一个 (转载)骄傲的外F：中国丈母娘吐槽老外女婿：赔了闺女搭上妈(图)股市震荡而已，大家没事的~乔丹诉乔丹体育美国暗能量相机首次拍摄到宇宙暗物质关于chase 5% cashback 提醒各位：Chase开始玩阴的了 (转载)计步器的原理是什么？做羞羞的事时，女友一把推开我人口基数多少才能避免近亲结婚？拼图姐在那里？橙子？道士下山真JB烂 (转载)请教一下多普勒效应微信群继续可怕地沉默着Obama Says ‘I Could Win’ 3rd Term as President某男吹嘘与领导关系铁:“我俩从光屁股玩到现在，你说铁不铁”，美女不屑:“我和领导现在还光屁股玩呢，你说谁铁？”日本AV面试官工作实录 zz (转载)虐待动物
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。