f****e
发帖数: 34 | 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说要去了，反悔不太好，于是拒绝了。。。 |
t******1
发帖数: 2239 | |
f*******4
发帖数: 64 | 3 完全二叉树总结点数是用二分判断高度来做吗？
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里面写代码。一个题目是关于
|
f*****e
发帖数: 2992 | 4 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里面写代码。一个题目是关于
|
f****e
发帖数: 34 | 5 恩 反正google总共就4轮面试，你要是进行了2轮电话面试，onsite的话就只有2轮。
求高度不是直接从根节点一直向左走就可以了吗?
【在 f*******4 的大作中提到】
: 完全二叉树总结点数是用二分判断高度来做吗？
: g电面只一轮？
|
f****e
发帖数: 34 | 6 Google全部是在国内面的，面的国外的职位。
Facebook onsite是去美国面的。
【在 t******1 的大作中提到】
: 牛，再国内拿的offer？
|
f****e
发帖数: 34 | |
h*u
发帖数: 122 | |
f*****e
发帖数: 2992 | 9 找最底层最右边叶子结点？从根节点先右转再左转，然后从根节点先左转再右转找转捩
点，i.e.左拐or右拐点。每一步耗时2*h，然后recurse on next level。
所以sum(2*i)=O(h^2)
【在 f****e 的大作中提到】
: O(h)怎么算出来? 完全二叉树不是满二叉树。
|
f****e
发帖数: 34 | 10 …… 你就直接说具体算法吧
O(h)求出高度了，怎么确定总结点数？
再说一下，完全二叉树不是满二叉树。完全二叉树最后一层的结点都在左边，但没必要
是满的。
另外你说“2倍叶子节点数”，先不管这个对不对，你怎么确定叶子结点数？
【在 f*****e 的大作中提到】
: 找最底层最右边叶子结点？从根节点先右转再左转，然后从根节点先左转再右转找转捩
: 点，i.e.左拐or右拐点。每一步耗时2*h，然后recurse on next level。
: 所以sum(2*i)=O(h^2)
|
|
|
m******s
发帖数: 165 | 11 喔，好像不太对。。。O(h^2)出来恩。。。
二分 h * log(2^h)
【在 f****e 的大作中提到】
: O(h)怎么算出来? 完全二叉树不是满二叉树。
|
f****e
发帖数: 34 | 12 恩 O(h^2)的话应该和我当时说的算法一样，面试官没让继续优化，应该是最优的了吧
....
【在 m******s 的大作中提到】
: 喔，好像不太对。。。O(h^2)出来恩。。。
: 二分 h * log(2^h)
|
m******s
发帖数: 165 | 13 一时想不出来了恩。。。gxgx
【在 f****e 的大作中提到】
: 恩 O(h^2)的话应该和我当时说的算法一样，面试官没让继续优化，应该是最优的了吧
: ....
|
h****n
发帖数: 1093 | 14 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里面写代码。一个题目是关于
|
j********g
发帖数: 244 | 15 LZ好牛！谢谢分享！
“判断一堆线段是否相交”
请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
sweep line也可以弄成general的？ |
f*****e
发帖数: 2992 | 16 CLRS上好像有这题。
【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
|
A**u
发帖数: 2458 | 17 牛
【在 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里面写代码。一个题目是关于
|
m******s
发帖数: 165 | 18 line sweep O(nlogn)
不过计算几何的东西写起来要小心
【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
|
l***m
发帖数: 339 | 19 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）
【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
|
p*****2
发帖数: 21240 | |
|
|
p*****2
发帖数: 21240 | 21 对了，LZ是master吗？感觉G对master其实不是很友好。 |
h****n
发帖数: 1093 | 22 你这是在一条直线上么，我以为是二维的
【在 l***m 的大作中提到】
: 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）
|
l***m
发帖数: 339 | 23 是二维的啊。。
【在 h****n 的大作中提到】
: 你这是在一条直线上么，我以为是二维的
|
f*****e
发帖数: 2992 | 24 书上用的是Red black tree。
【在 l***m 的大作中提到】
: 是二维的啊。。
|
C***U
发帖数: 2406 | 25 牛逼
恭喜!
顺便问 copy a link list with a random ptr
这个题是啥? |
h****n
发帖数: 1093 | 26 能展开说说你的方法吗
怎么还用到了二叉树？
【在 l***m 的大作中提到】
: 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn）
|
p*****2
发帖数: 21240 | 27
书上哪一章呀？
【在 f*****e 的大作中提到】
: 书上用的是Red black tree。
|
p*****2
发帖数: 21240 | 28
河海涛上有。是道老题。很坑爹。感觉没见过估计要跪。
【在 C***U 的大作中提到】
: 牛逼
: 恭喜!
: 顺便问 copy a link list with a random ptr
: 这个题是啥?
|
C***U
发帖数: 2406 | 29 再问河海涛是啥?
谢二爷啊
【在 p*****2 的大作中提到】
:
: 河海涛上有。是道老题。很坑爹。感觉没见过估计要跪。
|
l***m
发帖数: 339 | 30 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 的大作中提到】
: 能展开说说你的方法吗
: 怎么还用到了二叉树？
|
|
|
p*****2
发帖数: 21240 | 31
我还以为大家都知道呢。我其实也没怎么看过，就看过这一题。
【在 C***U 的大作中提到】
: 再问河海涛是啥?
: 谢二爷啊
|
h****n
发帖数: 1093 | 32 多谢，学习了
楼主一个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
|
C***U
发帖数: 2406 | 33 那给我讲一下具体题目啊
谢了哦
【在 p*****2 的大作中提到】
:
: 我还以为大家都知道呢。我其实也没怎么看过，就看过这一题。
|
p*****2
发帖数: 21240 | 34
就是一个linkedlist, 每个node有一个random ptr 指向一个随机的node，然后要clone
这个linkedlist。
【在 C***U 的大作中提到】
: 那给我讲一下具体题目啊
: 谢了哦
|
f*****e
发帖数: 2992 | 35 33.2 第三版 p1021
【在 p*****2 的大作中提到】
:
: 就是一个linkedlist, 每个node有一个random ptr 指向一个随机的node，然后要clone
: 这个linkedlist。
|
D**********d
发帖数: 849 | 36 可以先按 x axis 排序(假设升序)，然后查 y 是否有降序的。
总共是 O(nlgn) + O(n) = O(nlgn)
【在 j********g 的大作中提到】
: LZ好牛！谢谢分享！
: “判断一堆线段是否相交”
: 请问这个应该怎么写比较好啊。需要什么样的complexity?是什么样的线段？任意角度
: 的吧？不是那种简单的只有横竖然后可以Sweep Line Algorithm 的。。。不过好像
: sweep line也可以弄成general的？
|
e***s
发帖数: 799 | |
e***s
发帖数: 799 | 38 copy a link list with a random ptr
这题有两中方法。
一种用hashmap，Loop两次，一次写next，一次写random
一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。 |
h***r
发帖数: 22 | 39 on site 有两轮？不是都一轮么？
【在 f****e 的大作中提到】
: 恩 反正google总共就4轮面试，你要是进行了2轮电话面试，onsite的话就只有2轮。
: 求高度不是直接从根节点一直向左走就可以了吗?
|
p*****2
发帖数: 21240 | 40
多谢。晚上去看看。
【在 f*****e 的大作中提到】
: 33.2 第三版 p1021
|
|
|
g**u
发帖数: 583 | |
c*****r
发帖数: 214 | 42 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里面写代码。一个题目是关于
|
f*****e
发帖数: 2992 | 43 那还不如本科过来。
【在 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?这
|
p*****2
发帖数: 21240 | 44
都是大牛，一般人也比不了吧
【在 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?这
|
j******2
发帖数: 362 | 45 拓扑排序和穿线二叉树那两题分别是什么啊？大牛能详细说说吗？
【在 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里面写代码。一个题目是关于
|
l***m
发帖数: 339 | 46 我觉得拓扑排序应该是定义一些关系，然后让你输出最终的order吧，比如现在定义的
字母顺序是a,b,c,d,e,f,g,他如果重新定义一些顺序比如c->a，等等，让你重新输出
order的序列，就是用拓扑排序。
穿线二叉树我猜是把树的每一层连起来成一个linked list吧。
【在 j******2 的大作中提到】
: 拓扑排序和穿线二叉树那两题分别是什么啊？大牛能详细说说吗？
|
e****e
发帖数: 418 | 47 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分开。
|
f*****e
发帖数: 2992 | 48 第二种方法好简单，妙！
【在 e***s 的大作中提到】
: copy a link list with a random ptr
: 这题有两中方法。
: 一种用hashmap，Loop两次，一次写next，一次写random
: 一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
|
e***s
发帖数: 799 | 49 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.
|
l****c
发帖数: 782 | |
|
|
e****e
发帖数: 418 | 51 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.
|
e***s
发帖数: 799 | 52 不是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.
|
e***s
发帖数: 799 | 53 能不能解释一下怎样 O(h^2)求 complete BT nodes啊？ |
e****e
发帖数: 418 | 54 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>();
|
p*****e
发帖数: 1611 | 55 多串模式匹配做好的方法可能是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里面写代码。一个题目是关于
|
f*****e
发帖数: 2992 | 56 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啊？
|
C*********e
发帖数: 587 | 57 赞信息分享～～
【在 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里面写代码。一个题目是关于
|
m******s
发帖数: 165 | 58 要我估计会说AC自动机，然后要写code的话直接跪掉。。。
【在 p*****e 的大作中提到】
: 多串模式匹配做好的方法可能是suffix array+LCP
: 预处理O(m)，然后每个query的复杂度是O(n+lgm)
|
p*****e
发帖数: 1611 | 59 suffix array + LCP写code的话也要跪……
因为LCP如果要O(n)的话还要写RMQ...
【在 m******s 的大作中提到】
: 要我估计会说AC自动机，然后要写code的话直接跪掉。。。
|
S******1
发帖数: 269 | 60 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>();
|
|
|
S******1
发帖数: 269 | 61 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里面写代码。一个题目是关于
|
l*****a
发帖数: 559 | 62 二爷看明白了讲讲。
p1027的第二行有句话看不懂。
"If p is on sweep line z, then q = p."
p是a和b的交点，再加一个endpoint q，岂不是三条线段相交了，和假设不符啊。
【在 p*****2 的大作中提到】
:
: 都是大牛，一般人也比不了吧
|
p*****2
发帖数: 21240 | 63
刚才看了看。其实我特别烦几何。本来我数学题也不行，练了练还凑活了。结果开始流
行几何了，搞的我就放弃了。
这东西感觉有点偏呀，不觉得我面试能碰上。
【在 l*****a 的大作中提到】
: 二爷看明白了讲讲。
: p1027的第二行有句话看不懂。
: "If p is on sweep line z, then q = p."
: p是a和b的交点，再加一个endpoint q，岂不是三条线段相交了，和假设不符啊。
|
l**b
发帖数: 457 | |
w****x
发帖数: 2483 | 65
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
|
p*****2
发帖数: 21240 | 66
你说说你的算法吧。
【在 w****x 的大作中提到】
:
: and
: 这个.... 我被震惊了， 这个算法太牛了！！
: FB出这个题指望给出这个算法吗？
|
w****x
发帖数: 2483 | 67
晕， 我连怎么判断线段相交都写不出来
【在 p*****2 的大作中提到】
:
: 你说说你的算法吧。
|
l***m
发帖数: 339 | 68 这个好像学校上课讲过。。。
【在 w****x 的大作中提到】
:
: 晕， 我连怎么判断线段相交都写不出来
|
p*****2
发帖数: 21240 | 69
那天问你你不是说很简单吗？
【在 w****x 的大作中提到】
:
: 晕， 我连怎么判断线段相交都写不出来
|
w****x
发帖数: 2483 | 70
靠，我以为是一维的
【在 p*****2 的大作中提到】
:
: 那天问你你不是说很简单吗？
|
|
|
w****x
发帖数: 2483 | 71
刚对照算法导论花了3个半小时才看明白，头都快晕了
【在 l***m 的大作中提到】
: 这个好像学校上课讲过。。。
|
h****n
发帖数: 1093 | 72 大牛啊~~~~~
膜拜之
【在 l***m 的大作中提到】
: 这个好像学校上课讲过。。。
|
p*****2
发帖数: 21240 | 73
靠。白让我膜拜了。
【在 w****x 的大作中提到】
:
: 刚对照算法导论花了3个半小时才看明白，头都快晕了
|
w****x
发帖数: 2483 | 74
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，你太搞了
【在 p*****2 的大作中提到】
:
: 靠。白让我膜拜了。
|
j*******e
发帖数: 1058 | 75 FB要你从国内飞到美国来面试？出机票钱么？你真牛阿 |
q****m
发帖数: 177 | 76 第二种方法能详细点吗？后面插的node 是random 的node 吗
【在 e***s 的大作中提到】
: copy a link list with a random ptr
: 这题有两中方法。
: 一种用hashmap，Loop两次，一次写next，一次写random
: 一种在各个node后面插入一个node，loop两次，一次写random，一次把list分开。
|
l****o
发帖数: 315 | |
