l********s
发帖数: 30 | 1 facebook 电话一面。面筋之前，先问一下大家：一般第一轮电话面试后多久会有消息？
即多久会被据或者被通知下一步？等待的滋味不好受啊~ 不管面的是不是facebook的，
都请大家说一下，我好心里有底，谢谢~
面经：
1. Remove duplicate elements from a sorted array in place.
比如给，[1,3,3,5,5,6,9,9,9]
则结果为[1,3,5,6,9]
给的函数原型为：void dedup(int arr[], int &len)
2. I have large set of integers in a file (in billions). Integer values
range from 1 to 1000. I want to partition this file into three files. Top 20
% in one file next 30% in another file. Low 50% in another file.
if there 10 elements then top 2 will | s*********s
发帖数: 318 | 2 没有理解第二题。Pivot设为20%， 50%？
第一道题是不是还要free space? | w**********8
发帖数: 97 | 3 是老印的话，就算onsite 8成都是走过场，如果他一个组都是老印同胞，为什么要找你
进去破坏气氛？！
我已经领教过很多了，恨死他们了！ | r****o
发帖数: 1950 | 4 But how to partition billions of numbers?
【在 s*********s 的大作中提到】
: 没有理解第二题。Pivot设为20%， 50%？
: 第一道题是不是还要free space?
| r****o
发帖数: 1950 | 5 For the 2nd question,
scan all the numbers, dynamically maintain the 50%th and 20%th largest
number?
Then scan all the numbers we can partition the numbers into 3 groups based
on the 50%th and 20%th largest number?
息？
20
【在 l********s 的大作中提到】
: facebook 电话一面。面筋之前，先问一下大家：一般第一轮电话面试后多久会有消息？
: 即多久会被据或者被通知下一步？等待的滋味不好受啊~ 不管面的是不是facebook的，
: 都请大家说一下，我好心里有底，谢谢~
: 面经：
: 1. Remove duplicate elements from a sorted array in place.
: 比如给，[1,3,3,5,5,6,9,9,9]
: 则结果为[1,3,5,6,9]
: 给的函数原型为：void dedup(int arr[], int &len)
: 2. I have large set of integers in a file (in billions). Integer values
: range from 1 to 1000. I want to partition this file into three files. Top 20
| g**********1
发帖数: 1113 | 6 If HR does not contact with you very soon, most time you will not be
contacted unless you go to bother him/her. | m*****g
发帖数: 226 | | l*****a
发帖数: 14598 | 8 没看懂第二题什么意思。
你是要值大小的top 20% 还是就是出现次序的前面20%
counting sort,find the occurance of 1,2,3,...999,1000
then sum occu[k]<20%* billion
sum occu[k+1]>=20% * billion
then put 1,..K and few K+1 to the first file?
息？
values
Top 20
【在 l********s 的大作中提到】
: facebook 电话一面。面筋之前，先问一下大家：一般第一轮电话面试后多久会有消息？
: 即多久会被据或者被通知下一步？等待的滋味不好受啊~ 不管面的是不是facebook的，
: 都请大家说一下，我好心里有底，谢谢~
: 面经：
: 1. Remove duplicate elements from a sorted array in place.
: 比如给，[1,3,3,5,5,6,9,9,9]
: 则结果为[1,3,5,6,9]
: 给的函数原型为：void dedup(int arr[], int &len)
: 2. I have large set of integers in a file (in billions). Integer values
: range from 1 to 1000. I want to partition this file into three files. Top 20
| l********s
发帖数: 30 | 9 就是说，在这么多整数中，如果把它们排个序，则前 20% 的元素分到第一个文件，前
20%-50% 的分到第二个，后面的 50% 分到第三个文件中。
第一题不要 free space，要求你 in place 操作，只要正确的设置 len 即可
【在 s*********s 的大作中提到】
: 没有理解第二题。Pivot设为20%， 50%？
: 第一道题是不是还要free space?
| l********s
发帖数: 30 | 10 嗯，由于 range 只是在 0-1000 之间，所有，可以在内存中为每个整数分配一个
counter，然后读一遍所有整数，计算出每个整数有多少个。知道了这些信息后，我们
就知道了 top 20%, top 20%-50% 或 top50% 后的元素是哪些了。这个过程就类似
counting sort。最后，再读一遍这个大文件，把整数正确地分派到相应的文件中。
如果不要求保持原来的整数顺序，就不需要最后一遍的读大文件了，因为我们都知道了
这三个文件中应当包含什么整数，各多少个了。
【在 r****o 的大作中提到】
: For the 2nd question,
: scan all the numbers, dynamically maintain the 50%th and 20%th largest
: number?
: Then scan all the numbers we can partition the numbers into 3 groups based
: on the 50%th and 20%th largest number?
:
: 息？
: 20
| | | w*****1
发帖数: 245 | 11 第三题咋整的？ BFS ? 怎么知道啥时候该打下个level？？ | f*********i
发帖数: 197 | 12 I want to know the answer for the third question.
Can someone give me a solution? | t******h
发帖数: 120 | 13 第三题 大概是这样
用队列 设一个dummy node
循环开始前把root dummy enqueue
当读到dummy就表示这层结束了 输出换行
如果队列里还有元素 就再enqueue dummy
否则结束循环
我倒是很怕那种处理大量数据的题 | q**f
发帖数: 21 | 14 You don't need the dummy node. It has a simple approach.
【在 t******h 的大作中提到】
: 第三题 大概是这样
: 用队列 设一个dummy node
: 循环开始前把root dummy enqueue
: 当读到dummy就表示这层结束了 输出换行
: 如果队列里还有元素 就再enqueue dummy
: 否则结束循环
: 我倒是很怕那种处理大量数据的题
| a***g
发帖数: 234 | 15 like what?
【在 q**f 的大作中提到】
: You don't need the dummy node. It has a simple approach.
| l********s
发帖数: 30 | 16 如果不用dummy结点的话，我的思路是：用两个计算数器 a 和 b，a 表示当前正在打印
的level还有多少结点没打， b 表示有多少个下一 level 的结点已经入队。初始时，
把根入队，并设置 a=1,b=0。处理当前结点时，先把其孩子（如果有的话）入队，每往
队里加一个结点，b++；然后，打印当前结点，a--。如果 a=0，打印新行，并令 a=b,b
=0。
尚未验证，大家拍砖~
【在 a***g 的大作中提到】
: like what?
| c**y
发帖数: 172 | 17 solution for question 3 (BFS)
here T is a binary tree, and s is its root node.
void BFS(T, s) {
list *level[T.height + 1];
level[0] = new list;
level[0]->insert(s);
int i = 0;
while (!level[i].empty()) {
level[i+1] = new list;
for (list::iterator p = level[i]->begin(); p != level[i]->end();
p++) {
if ( T.leftChild(*p) != NULL ) {
level[i+1]->insert(T.leftChild(*p));
}
if ( T.rightChild(*p) != NULL ) {
level[i |
|
