w****x
发帖数: 2483 | 1 Infrastructure team, 用c++的
刚结束的一个电面
1. 写一个二叉树中序遍历的c++ class iterator
2. 给一个单向链表,随机选择一个node in one pass
3. 数组最大连续和的范围
一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
很紧. |
p*****2
发帖数: 21240 | |
k***x
发帖数: 6799 | |
j*****o
发帖数: 394 | 4 第一个怎么做。。？
数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 5
你把它的index输出来就可以了
【在 j*****o 的大作中提到】
: 第一个怎么做。。？
: 数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
|
a***o
发帖数: 1182 | 6 大牛写个第一题吧，iterator具体咋写？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
C***U
发帖数: 2406 | 7 10分钟写code?
那不是会死人啊？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
t*****l
发帖数: 241 | 8 2. 知道总node个数吗
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
v*****k
发帖数: 7798 | 9 1. Is it just a non-recursive in-order traversal? I am not quite familiar
with the grammar of C++ iterators but I guess you need to implement next()
and handle some exceptions like empty tree or leaf nodes?
2. two pointers? one is rand(n) steps ahead of the other?
3. did you make a mistake on all negative numbers?
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 10
不知道
【在 t*****l 的大作中提到】
: 2. 知道总node个数吗
|
|
|
w****x
发帖数: 2483 | 11
最后一题的bug是
if (max < cur) max = cur
写成了
if (max > cur) max = cur
【在 v*****k 的大作中提到】
: 1. Is it just a non-recursive in-order traversal? I am not quite familiar
: with the grammar of C++ iterators but I guess you need to implement next()
: and handle some exceptions like empty tree or leaf nodes?
: 2. two pointers? one is rand(n) steps ahead of the other?
: 3. did you make a mistake on all negative numbers?
|
T*******i
发帖数: 4442 | |
v*****k
发帖数: 7798 | 13 kao, this is a typo....
【在 w****x 的大作中提到】
:
: 最后一题的bug是
: if (max < cur) max = cur
: 写成了
: if (max > cur) max = cur
|
w****x
发帖数: 2483 | 14
不知道链表长度, 过一遍链表然后随机挑选一个节点返回
【在 T*******i 的大作中提到】
: 2. 什么意思啊
|
w****x
发帖数: 2483 | 15
只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
【在 T*******i 的大作中提到】
: 2. 什么意思啊
|
p*****2
发帖数: 21240 | 16 第一题你10分钟写完bug free的code很牛逼呀。 |
T*******i
发帖数: 4442 | 17 哦 那样先存第一个，每一跳随机决定更新或者不更新 ？
【在 w****x 的大作中提到】
:
: 只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
|
h********6
发帖数: 285 | 18 一次电面写三题太牛了。第二题的意思是每个node选择与否都是独立事件？ |
p**o
发帖数: 1012 | 19 45minute，3道题。。。。。真可怕,你必须通过了 |
r*******m
发帖数: 457 | 20 好厉害啊 ！
第二题是reservoir sampling吗？ |
|
|
i***e
发帖数: 452 | 21 应该是！ 跟从一个数据流的那个题目一样！
【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
|
i***e
发帖数: 452 | 22 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
l***i
发帖数: 1309 | 23 FB还是很难阿。2想了半天。
solution to 2:
Let head be the pointer to the input list. Use ptr to keep track of
currently selected node, ptr points to head initially.
cnt = 1
ptr = curr = head;
while(curr has next)
{
curr = curr->next
cnt++
p = rand(1,cnt) // generate random int in [1,cnt]
if (p==1) ptr = curr
}
return ptr
Proof by induction can show ptr points to a random node.
有其他做法么？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
l*****a
发帖数: 14598 | 24 M早就给你保底了吧？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
T*******i
发帖数: 4442 | 25 这种题根本就不是给你面试时候考虑的 45分钟三道题 都得是熟悉的题目才行
指望面试的时候灵机一动 不现实
【在 l***i 的大作中提到】
: FB还是很难阿。2想了半天。
: solution to 2:
: Let head be the pointer to the input list. Use ptr to keep track of
: currently selected node, ptr points to head initially.
: cnt = 1
: ptr = curr = head;
: while(curr has next)
: {
: curr = curr->next
: cnt++
|
w****x
发帖数: 2483 | 26
没有, 我没有offer, 你就别揭我伤疤了~~~
【在 l*****a 的大作中提到】
: M早就给你保底了吧？
|
w****x
发帖数: 2483 | 27
没有parent node, 我是用stack实现的
【在 i***e 的大作中提到】
: 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
: startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
: 第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
|
i***e
发帖数: 452 | 28 非递归的inorder walk 的思想？ 一直没搞明白题目到底什么意思？
【在 w****x 的大作中提到】
:
: 没有parent node, 我是用stack实现的
|
h****e
发帖数: 928 | |
W******g
发帖数: 887 | 30 这位大牛搞过竞赛吗？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
|
|
S********e
发帖数: 72 | 31 第3题还是没看懂意思，给个例子吧。。。
第2题的正解是？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 32
第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
第三题求连续和最大的sequence, 他还问了怎么测试第三题
第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
自己设计接口
【在 S********e 的大作中提到】
: 第3题还是没看懂意思，给个例子吧。。。
: 第2题的正解是？
|
N**n
发帖数: 832 | 33 有个题目不断地给输入，拿到一个随机，一样的做法
来第一个先选着，假设已经过了k个了，你手上有一个random拿到的Ni，来第k+1的时候
，你以1/(k+1)的概率用第N(k+1)取代Ni，否则还是Ni
【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
|
b*******d
发帖数: 750 | 34
~~
yes.
【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
|
d**o
发帖数: 864 | 35 这种错我也犯过，实际的程序，debug苦死人。
后来就只写max=curr>max?curr:max;
【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
|
m****i
发帖数: 1340 | |
d*******u
发帖数: 186 | 37 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end node
}
this->Node = node;
return *this;
}
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
d*******u
发帖数: 186 | 38 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end node
}
this->Node = node;
return *this;
}
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
c****x
发帖数: 15 | 39 第一题是要求写STL标准的iterator？还是就写个算法出来就行？ |
f******h
发帖数: 45 | 40 第二题用java 这样子写行么？
public class ReserviorSampling {
public ListNode sampling(ListNode head){
ListNode s = head;
Random rand = new Random();
int count = 1;
while(head != null){
int position = (int) (rand.nextInt(count) + 1);
count++;
if(position == 1)
s = head;
}
return s;
}
}
这题怎么测试啊？ 要生成很长的linkedlist 然后随机选择，看概率是否接近1/n? |
|
|
w****x
发帖数: 2483 | 41 Infrastructure team, 用c++的
刚结束的一个电面
1. 写一个二叉树中序遍历的c++ class iterator
2. 给一个单向链表,随机选择一个node in one pass
3. 数组最大连续和的范围
一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
很紧. |
p*****2
发帖数: 21240 | |
k***x
发帖数: 6799 | |
j*****o
发帖数: 394 | 44 第一个怎么做。。？
数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 45
你把它的index输出来就可以了
【在 j*****o 的大作中提到】
: 第一个怎么做。。？
: 数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
|
a***o
发帖数: 1182 | 46 大牛写个第一题吧，iterator具体咋写？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
C***U
发帖数: 2406 | 47 10分钟写code?
那不是会死人啊？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
t*****l
发帖数: 241 | 48 2. 知道总node个数吗
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
v*****k
发帖数: 7798 | 49 1. Is it just a non-recursive in-order traversal? I am not quite familiar
with the grammar of C++ iterators but I guess you need to implement next()
and handle some exceptions like empty tree or leaf nodes?
2. two pointers? one is rand(n) steps ahead of the other?
3. did you make a mistake on all negative numbers?
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 50
不知道
【在 t*****l 的大作中提到】
: 2. 知道总node个数吗
|
|
|
w****x
发帖数: 2483 | 51
最后一题的bug是
if (max < cur) max = cur
写成了
if (max > cur) max = cur
【在 v*****k 的大作中提到】
: 1. Is it just a non-recursive in-order traversal? I am not quite familiar
: with the grammar of C++ iterators but I guess you need to implement next()
: and handle some exceptions like empty tree or leaf nodes?
: 2. two pointers? one is rand(n) steps ahead of the other?
: 3. did you make a mistake on all negative numbers?
|
T*******i
发帖数: 4442 | |
v*****k
发帖数: 7798 | 53 kao, this is a typo....
【在 w****x 的大作中提到】
:
: 最后一题的bug是
: if (max < cur) max = cur
: 写成了
: if (max > cur) max = cur
|
w****x
发帖数: 2483 | 54
不知道链表长度, 过一遍链表然后随机挑选一个节点返回
【在 T*******i 的大作中提到】
: 2. 什么意思啊
|
w****x
发帖数: 2483 | 55
只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
【在 T*******i 的大作中提到】
: 2. 什么意思啊
|
p*****2
发帖数: 21240 | 56 第一题你10分钟写完bug free的code很牛逼呀。 |
T*******i
发帖数: 4442 | 57 哦 那样先存第一个，每一跳随机决定更新或者不更新 ？
【在 w****x 的大作中提到】
:
: 只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
|
h********6
发帖数: 285 | 58 一次电面写三题太牛了。第二题的意思是每个node选择与否都是独立事件？ |
p**o
发帖数: 1012 | 59 45minute，3道题。。。。。真可怕,你必须通过了 |
r*******m
发帖数: 457 | 60 好厉害啊 ！
第二题是reservoir sampling吗？ |
|
|
i***e
发帖数: 452 | 61 应该是！ 跟从一个数据流的那个题目一样！
【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
|
i***e
发帖数: 452 | 62 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
l***i
发帖数: 1309 | 63 FB还是很难阿。2想了半天。
solution to 2:
Let head be the pointer to the input list. Use ptr to keep track of
currently selected node, ptr points to head initially.
cnt = 1
ptr = curr = head;
while(curr has next)
{
curr = curr->next
cnt++
p = rand(1,cnt) // generate random int in [1,cnt]
if (p==1) ptr = curr
}
return ptr
Proof by induction can show ptr points to a random node.
有其他做法么？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
l*****a
发帖数: 14598 | 64 M早就给你保底了吧？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
T*******i
发帖数: 4442 | 65 这种题根本就不是给你面试时候考虑的 45分钟三道题 都得是熟悉的题目才行
指望面试的时候灵机一动 不现实
【在 l***i 的大作中提到】
: FB还是很难阿。2想了半天。
: solution to 2:
: Let head be the pointer to the input list. Use ptr to keep track of
: currently selected node, ptr points to head initially.
: cnt = 1
: ptr = curr = head;
: while(curr has next)
: {
: curr = curr->next
: cnt++
|
w****x
发帖数: 2483 | 66
没有, 我没有offer, 你就别揭我伤疤了~~~
【在 l*****a 的大作中提到】
: M早就给你保底了吧？
|
w****x
发帖数: 2483 | 67
没有parent node, 我是用stack实现的
【在 i***e 的大作中提到】
: 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
: startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
: 第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
|
i***e
发帖数: 452 | 68 非递归的inorder walk 的思想？ 一直没搞明白题目到底什么意思？
【在 w****x 的大作中提到】
:
: 没有parent node, 我是用stack实现的
|
h****e
发帖数: 928 | |
W******g
发帖数: 887 | 70 这位大牛搞过竞赛吗？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
|
|
S********e
发帖数: 72 | 71 第3题还是没看懂意思，给个例子吧。。。
第2题的正解是？
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
w****x
发帖数: 2483 | 72
第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
第三题求连续和最大的sequence, 他还问了怎么测试第三题
第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
自己设计接口
【在 S********e 的大作中提到】
: 第3题还是没看懂意思，给个例子吧。。。
: 第2题的正解是？
|
N**n
发帖数: 832 | 73 有个题目不断地给输入，拿到一个随机，一样的做法
来第一个先选着，假设已经过了k个了，你手上有一个random拿到的Ni，来第k+1的时候
，你以1/(k+1)的概率用第N(k+1)取代Ni，否则还是Ni
【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
|
b*******d
发帖数: 750 | 74
~~
yes.
【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
|
d**o
发帖数: 864 | 75 这种错我也犯过，实际的程序，debug苦死人。
后来就只写max=curr>max?curr:max;
【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
|
m****i
发帖数: 1340 | |
d*******u
发帖数: 186 | 77 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end node
}
this->Node = node;
return *this;
}
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
d*******u
发帖数: 186 | 78 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end node
}
this->Node = node;
return *this;
}
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
c****x
发帖数: 15 | 79 第一题是要求写STL标准的iterator？还是就写个算法出来就行？ |
f******h
发帖数: 45 | 80 第二题用java 这样子写行么？
public class ReserviorSampling {
public ListNode sampling(ListNode head){
ListNode s = head;
Random rand = new Random();
int count = 1;
while(head != null){
int position = (int) (rand.nextInt(count) + 1);
count++;
if(position == 1)
s = head;
}
return s;
}
}
这题怎么测试啊？ 要生成很长的linkedlist 然后随机选择，看概率是否接近1/n? |
|
|
f*********m
发帖数: 726 | 81 哪位能给个第一题的答案？谢谢。
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
c*****a
发帖数: 808 | 82 3 题都要code啊。。。。。楼主牛
blesss |
j*****I
发帖数: 2626 | 83 不是我看不起FB. 不就是做做网页嘛，哪还需要什么Infrastructure?
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
l*****a
发帖数: 14598 | 84 写的不好，算抛砖引玉吧,JAVA版
Class InOrderIterator
{
private Stack s;
private Node next;
public InOrderIterator(Node root)
{
this.s = new Stack();
Node current = root;
while(current.left) {
s.push(current);
current = current.left;
}
this.next = current;
}
public boolean hasNext() {
return this.next!=null;
}
public Node next() {
Node temp = this.next;
this.next = getNext(temp);
return temp;
}
private Node getNext(Node current) {
// use stack to get next node in BST
}
}
Usage:
Node root = ...;
InOrderIterator it = new InOrderIterator(root);
while(it.hasNext()) {
System.out.println(it.next());
}
【在 f*********m 的大作中提到】
: 哪位能给个第一题的答案？谢谢。
|
c*****r
发帖数: 214 | 85 别无知无畏了
听说FB的数据都有几百个PB了，搞infrastructure的人数以百计
【在 j*****I 的大作中提到】
: 不是我看不起FB. 不就是做做网页嘛，哪还需要什么Infrastructure?
|
l*****a
发帖数: 14598 | 86 你不应该唤醒他
【在 c*****r 的大作中提到】
: 别无知无畏了
: 听说FB的数据都有几百个PB了，搞infrastructure的人数以百计
|
c********t
发帖数: 5706 | 87 第一题，如果要写一个iterator，要overwrite next(), hasNext(), and remove(),十
分钟不可能吧，可不可以把tree 转成 in-order list,返回list iterator？
第二题， reservoir sampling
第三题，计算SUM(i),范围是index(min)+1 -- index(max), max is the max after
min?
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
c********t
发帖数: 5706 | 88 没懂，右子树怎么处理的？
【在 l*****a 的大作中提到】
: 写的不好，算抛砖引玉吧,JAVA版
: Class InOrderIterator
: {
: private Stack s;
: private Node next;
: public InOrderIterator(Node root)
: {
: this.s = new Stack();
: Node current = root;
: while(current.left) {
|
l*****a
发帖数: 14598 | 89 什么右子树怎么处理
用stack+current node可以保存tree全部信息
然后实现In order getnext就可以了
【在 c********t 的大作中提到】
: 没懂，右子树怎么处理的？
|
m*****k
发帖数: 731 | 90 first 1, keep it or not, 100% keep it,
2nd one, keep it or not? 50% keep it,
....
nth one, keep it or not? P(keep it) = 1/n |
|
|
C***U
发帖数: 2406 | 91 你过了第一轮吧
【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
|
m*****k
发帖数: 731 | 92 我觉得就是inOrder travesal break into 2 parts 吧？
void init()
{
pushLeftDown(root )
}
void pushLeftDown(Node cur){
if(cur == null) return;
stack.push(cur);
while(cur.left!=null){
stack.push(cur.left);
cur = cur.left;
}
}
boolean hasNext()
{
return stack.isEmpty();
}
Node next(){
if hasNext(){
Node top = stack.pop();
pushLeftDown(top.right);
return top;
}
else{
return null;
}
}
then hasNext() just returns if
【在 c********t 的大作中提到】
: 第一题，如果要写一个iterator，要overwrite next(), hasNext(), and remove(),十
: 分钟不可能吧，可不可以把tree 转成 in-order list,返回list iterator？
: 第二题， reservoir sampling
: 第三题，计算SUM(i),范围是index(min)+1 -- index(max), max is the max after
: min?
|
l****o
发帖数: 43 | 93 膜拜一下，big bless...(貌似多余....) |
l****o
发帖数: 43 | 94 如果dereference这个iterator的话，是不是应该得到一个TreeNode*？Node这个
element是必要的吗？
【在 d*******u 的大作中提到】
: Question one:
: Tree::_InOrderIterator::operator++()
: {
: TreeNode* node = this->Node->right();
: stack itstack;
: //leftmost of right child.
: while(node != NULL)
: {
: itstack.Push(node);
: node = node->left();
|
j*****I
发帖数: 2626 | 95 不要告诉我FB自己要研发storage. 如果只是用storage的产品，做做maintenance/
support,想不出为什么instrastructure team要考coding.
【在 c*****r 的大作中提到】
: 别无知无畏了
: 听说FB的数据都有几百个PB了，搞infrastructure的人数以百计
|
