logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
galaxy s4 active
avatar
galaxy s4 active# PDA - 掌中宝
w*x
1 楼
Infrastructure team, 用c++的
刚结束的一个电面
1. 写一个二叉树中序遍历的c++ class iterator
2. 给一个单向链表,随机选择一个node in one pass
3. 数组最大连续和的范围
一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
很紧.
avatar
z*c
2 楼
i got a lot brand new galaxy s4 and want to sell it, can anyone help.
thanks
avatar
p*2
3 楼
靠一个电面三道题，真是面大牛的标准呀。
avatar
l*r
4 楼
关键是how much？

【在 z******c 的大作中提到】
: i got a lot brand new galaxy s4 and want to sell it, can anyone help.
: thanks
avatar
k*x
5 楼
做题少，2和3没看明白是什么要求。。。
avatar
z*c
6 楼
Thanks for your help
Of course i want as much as i can get but im thinking around 500 since it is
water proof.
avatar
j*o
7 楼
第一个怎么做。。？
数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
d*g
8 楼
wash wash sleep ba

is

【在 z******c 的大作中提到】
: Thanks for your help
: Of course i want as much as i can get but im thinking around 500 since it is
: water proof.
avatar
w*x
9 楼

你把它的index输出来就可以了

【在 j*****o 的大作中提到】
: 第一个怎么做。。？
: 数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
avatar
d*0
10 楼
本版都是人精
avatar
a*o
11 楼
大牛写个第一题吧，iterator具体咋写？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
p*r
12 楼
If you can get more at much lower cost, say less than $400, then you can
sell at lower price to get big volume. $450 will have much more demand.
avatar
C*U
13 楼
10分钟写code?
那不是会死人啊？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
i*g
14 楼
500块这里没人受理，这里的人都抢deal的, 500半个deal都不是。 450会有很多人买。
400几小时内被抢光。另外加了个active就不等于比没active贵，你自己看看ATT的价
格。
avatar
t*l
15 楼
2. 知道总node个数吗

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
d*g
16 楼
Active我实际对比过普通S4，屏幕实在太烂了，实体按钮手感也不好。多出来的那个厚
度，还不如普通S4上个靠谱的潜水壳呢

【在 i******g 的大作中提到】
: 500块这里没人受理，这里的人都抢deal的, 500半个deal都不是。 450会有很多人买。
: 400几小时内被抢光。另外加了个active就不等于比没active贵，你自己看看ATT的价
: 格。
avatar
v*k
17 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
d*2
18 楼
500块钱还可以啦 ebay的成交价都比这个高
avatar
w*x
19 楼

不知道

【在 t*****l 的大作中提到】
: 2. 知道总node个数吗
avatar
i*g
20 楼
我个人也是觉得不如普通的，还有人专门带手机下水？又打不了电话

【在 d********g 的大作中提到】
: Active我实际对比过普通S4，屏幕实在太烂了，实体按钮手感也不好。多出来的那个厚
: 度，还不如普通S4上个靠谱的潜水壳呢
avatar
w*x
21 楼

最后一题的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?
avatar
s*d
22 楼
我室友 500刀 S4
local 卖了2个
avatar
T*i
23 楼
2. 什么意思啊
avatar
i*g
24 楼

我只是想告诉他，如果想卖500，这里就不必费劲了，这里版上的人估计一个肯买的都
没有。ebay上傻人多，乱七八糟的水货和山寨手机那么多人乐呵呵的抢。我觉得楼主想
卖500就在local cl上慢慢卖，根据我的看法估计最后都是在450－480间的价格出掉。
要知道现在的旗舰过半年就变成二等公民了。

【在 d*****2 的大作中提到】
: 500块钱还可以啦 ebay的成交价都比这个高
avatar
v*k
25 楼
kao, this is a typo....

【在 w****x 的大作中提到】
:
: 最后一题的bug是
: if (max < cur) max = cur
: 写成了
: if (max > cur) max = cur
avatar
p*r
26 楼

The review seems to say overall 普通 S4 is better. Active only advantages
are more durable, water proof. Most of users don't need to use it under
water, and will buy a case for the phone.
Regular S4 advantages are
* Better display. AMOLED consume less power, and the black is real black.
The screen is less reflective to the light.
* Slightly better camera.
* Slightly better voice quality.
* Slightly thin.
If people always will buy a case for their phones, then regular S4 is better
.

【在 d********g 的大作中提到】
: Active我实际对比过普通S4，屏幕实在太烂了，实体按钮手感也不好。多出来的那个厚
: 度，还不如普通S4上个靠谱的潜水壳呢
avatar
w*x
27 楼

不知道链表长度, 过一遍链表然后随机挑选一个节点返回

【在 T*******i 的大作中提到】
: 2. 什么意思啊
avatar
p*r
28 楼

But, that's hard to sell in volume. If the LZ want to have quick sale for
some some volume, say over 100/day. The price has to go down more.

【在 s*********d 的大作中提到】
: 我室友 500刀 S4
: local 卖了2个
avatar
w*x
29 楼

只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了

【在 T*******i 的大作中提到】
: 2. 什么意思啊
avatar
m*t
30 楼
active unlocked?
avatar
p*2
31 楼
第一题你10分钟写完bug free的code很牛逼呀。
avatar
z*c
32 楼
thanks everyone's advise, i will try to sell local then.
avatar
T*i
33 楼
哦 那样先存第一个，每一跳随机决定更新或者不更新 ？

【在 w****x 的大作中提到】
:
: 只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
avatar
A*D
34 楼
6i？
avatar
h*6
35 楼
一次电面写三题太牛了。第二题的意思是每个node选择与否都是独立事件？
avatar
v*e
36 楼
卖了吗？

【在 z******c 的大作中提到】
: i got a lot brand new galaxy s4 and want to sell it, can anyone help.
: thanks
avatar
p*o
37 楼
45minute，3道题。。。。。真可怕,你必须通过了
avatar
r*m
38 楼
好厉害啊 ！
第二题是reservoir sampling吗？
avatar
i*e
39 楼
应该是！ 跟从一个数据流的那个题目一样！

【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
avatar
i*e
40 楼
感觉第三题是有点难写， 应为平时都没注意要记录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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
l*i
41 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
l*a
42 楼
M早就给你保底了吧？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
T*i
43 楼
这种题根本就不是给你面试时候考虑的 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++
avatar
w*x
44 楼

没有, 我没有offer, 你就别揭我伤疤了~~~

【在 l*****a 的大作中提到】
: M早就给你保底了吧？
avatar
w*x
45 楼

没有parent node, 我是用stack实现的

【在 i***e 的大作中提到】
: 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
: startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
: 第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
avatar
i*e
46 楼
非递归的inorder walk 的思想？ 一直没搞明白题目到底什么意思？

【在 w****x 的大作中提到】
:
: 没有parent node, 我是用stack实现的
avatar
h*e
47 楼
电面感觉就很难了。祝好运！
avatar
W*g
48 楼
这位大牛搞过竞赛吗？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
S*e
49 楼
第3题还是没看懂意思，给个例子吧。。。
第2题的正解是？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
w*x
50 楼

第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
第三题求连续和最大的sequence, 他还问了怎么测试第三题
第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
自己设计接口

【在 S********e 的大作中提到】
: 第3题还是没看懂意思，给个例子吧。。。
: 第2题的正解是？
avatar
N*n
51 楼
有个题目不断地给输入，拿到一个随机，一样的做法
来第一个先选着，假设已经过了k个了，你手上有一个random拿到的Ni，来第k+1的时候
，你以1/(k+1)的概率用第N(k+1)取代Ni，否则还是Ni

【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
avatar
b*d
52 楼

~~
yes.

【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
avatar
d*o
53 楼
这种错我也犯过，实际的程序，debug苦死人。
后来就只写max=curr>max?curr:max;

【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
avatar
m*i
54 楼
F面筋不是我的菜，路过看看。
avatar
d*u
55 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
d*u
56 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
c*x
57 楼
第一题是要求写STL标准的iterator？还是就写个算法出来就行？
avatar
f*h
58 楼
第二题用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?
avatar
w*x
59 楼
Infrastructure team, 用c++的
刚结束的一个电面
1. 写一个二叉树中序遍历的c++ class iterator
2. 给一个单向链表,随机选择一个node in one pass
3. 数组最大连续和的范围
一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
很紧.
avatar
p*2
60 楼
靠一个电面三道题，真是面大牛的标准呀。
avatar
k*x
61 楼
做题少，2和3没看明白是什么要求。。。
avatar
j*o
62 楼
第一个怎么做。。？
数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
w*x
63 楼

你把它的index输出来就可以了

【在 j*****o 的大作中提到】
: 第一个怎么做。。？
: 数组最大连续和，最大不是一个值吗？范围是说这个最大值是由哪些组成的？
avatar
a*o
64 楼
大牛写个第一题吧，iterator具体咋写？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
C*U
65 楼
10分钟写code?
那不是会死人啊？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
t*l
66 楼
2. 知道总node个数吗

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
v*k
67 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
w*x
68 楼

不知道

【在 t*****l 的大作中提到】
: 2. 知道总node个数吗
avatar
w*x
69 楼

最后一题的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?
avatar
T*i
70 楼
2. 什么意思啊
avatar
v*k
71 楼
kao, this is a typo....

【在 w****x 的大作中提到】
:
: 最后一题的bug是
: if (max < cur) max = cur
: 写成了
: if (max > cur) max = cur
avatar
w*x
72 楼

不知道链表长度, 过一遍链表然后随机挑选一个节点返回

【在 T*******i 的大作中提到】
: 2. 什么意思啊
avatar
w*x
73 楼

只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了

【在 T*******i 的大作中提到】
: 2. 什么意思啊
avatar
p*2
74 楼
第一题你10分钟写完bug free的code很牛逼呀。
avatar
T*i
75 楼
哦 那样先存第一个，每一跳随机决定更新或者不更新 ？

【在 w****x 的大作中提到】
:
: 只能过一遍, 不能预先计算长度, 你那样要过一遍算长度然后再过一遍pick节点了
avatar
h*6
76 楼
一次电面写三题太牛了。第二题的意思是每个node选择与否都是独立事件？
avatar
p*o
77 楼
45minute，3道题。。。。。真可怕,你必须通过了
avatar
r*m
78 楼
好厉害啊 ！
第二题是reservoir sampling吗？
avatar
i*e
79 楼
应该是！ 跟从一个数据流的那个题目一样！

【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
avatar
i*e
80 楼
感觉第三题是有点难写， 应为平时都没注意要记录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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
l*i
81 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
l*a
82 楼
M早就给你保底了吧？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
T*i
83 楼
这种题根本就不是给你面试时候考虑的 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++
avatar
w*x
84 楼

没有, 我没有offer, 你就别揭我伤疤了~~~

【在 l*****a 的大作中提到】
: M早就给你保底了吧？
avatar
w*x
85 楼

没有parent node, 我是用stack实现的

【在 i***e 的大作中提到】
: 感觉第三题是有点难写， 应为平时都没注意要记录index。 不过可以用两个
: startIndex, endIndex 来存当前最优的。 然后相应的update这两index.
: 第一有parent pointer 吗？ 这个class只有一个.next的函数还是怎么样的？
avatar
i*e
86 楼
非递归的inorder walk 的思想？ 一直没搞明白题目到底什么意思？

【在 w****x 的大作中提到】
:
: 没有parent node, 我是用stack实现的
avatar
h*e
87 楼
电面感觉就很难了。祝好运！
avatar
W*g
88 楼
这位大牛搞过竞赛吗？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
S*e
89 楼
第3题还是没看懂意思，给个例子吧。。。
第2题的正解是？

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
w*x
90 楼

第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
第三题求连续和最大的sequence, 他还问了怎么测试第三题
第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
自己设计接口

【在 S********e 的大作中提到】
: 第3题还是没看懂意思，给个例子吧。。。
: 第2题的正解是？
avatar
N*n
91 楼
有个题目不断地给输入，拿到一个随机，一样的做法
来第一个先选着，假设已经过了k个了，你手上有一个random拿到的Ni，来第k+1的时候
，你以1/(k+1)的概率用第N(k+1)取代Ni，否则还是Ni

【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
avatar
b*d
92 楼

~~
yes.

【在 r*******m 的大作中提到】
: 好厉害啊 ！
: 第二题是reservoir sampling吗？
avatar
d*o
93 楼
这种错我也犯过，实际的程序，debug苦死人。
后来就只写max=curr>max?curr:max;

【在 w****x 的大作中提到】
:
: 第二题是Google sampling的变种,把data stream改成了不知道长度的单链表
: 第三题求连续和最大的sequence, 他还问了怎么测试第三题
: 第一题就是写一个二叉树的iterator, 会iterative遍历二叉树的旧会做这题, 他要求
: 自己设计接口
avatar
m*i
94 楼
F面筋不是我的菜，路过看看。
avatar
d*u
95 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
d*u
96 楼
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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
c*x
97 楼
第一题是要求写STL标准的iterator？还是就写个算法出来就行？
avatar
f*h
98 楼
第二题用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?
avatar
f*m
99 楼
哪位能给个第一题的答案？谢谢。

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
c*a
100 楼
3 题都要code啊。。。。。楼主牛
blesss
avatar
j*I
101 楼
不是我看不起FB. 不就是做做网页嘛，哪还需要什么Infrastructure?

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
l*a
102 楼
写的不好，算抛砖引玉吧,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 的大作中提到】
: 哪位能给个第一题的答案？谢谢。
avatar
c*r
103 楼
别无知无畏了
听说FB的数据都有几百个PB了，搞infrastructure的人数以百计

【在 j*****I 的大作中提到】
: 不是我看不起FB. 不就是做做网页嘛，哪还需要什么Infrastructure?
avatar
l*a
104 楼
你不应该唤醒他

【在 c*****r 的大作中提到】
: 别无知无畏了
: 听说FB的数据都有几百个PB了，搞infrastructure的人数以百计
avatar
c*t
105 楼
第一题，如果要写一个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,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
c*t
106 楼
没懂，右子树怎么处理的？

【在 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) {
avatar
l*a
107 楼
什么右子树怎么处理
用stack+current node可以保存tree全部信息
然后实现In order getnext就可以了

【在 c********t 的大作中提到】
: 没懂，右子树怎么处理的？
avatar
m*k
108 楼
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
avatar
C*U
109 楼
你过了第一轮吧

【在 w****x 的大作中提到】
: Infrastructure team, 用c++的
: 刚结束的一个电面
: 1. 写一个二叉树中序遍历的c++ class iterator
: 2. 给一个单向链表,随机选择一个node in one pass
: 3. 数组最大连续和的范围
: 一题只有给大概10分钟的时间, 问了3道题, 前两题评价great, 最后一题找出了我一个
: 非常愚蠢的bug,靠. 感觉就是一遍写完后可以修改, 不一定要一次写对, 但是时间真的
: 很紧.
avatar
m*k
110 楼
我觉得就是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?
avatar
l*o
111 楼
膜拜一下，big bless...(貌似多余....)
avatar
l*o
112 楼
如果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();
avatar
j*I
113 楼
不要告诉我FB自己要研发storage. 如果只是用storage的产品，做做maintenance/
support,想不出为什么instrastructure team要考coding.

【在 c*****r 的大作中提到】
: 别无知无畏了
: 听说FB的数据都有几百个PB了，搞infrastructure的人数以百计
相关阅读
微软其实也没啥好讨论的请问:哪种英中翻译软件较准确?Z7能用Tmo的4G网络吗？广电总局王效杰：将组织阿里等公司参加TVOS研发哎！刚买了X1,又来了X2???Micro SD卡跳水阿nubia z7 居然比z7 max更贵更强，怎么命名的？海美迪Q系列解码MKV，ISO文件没有声音求推荐个Nexus5的套子狗狗三哥又在瞎折腾据说诺基亚剩下的部门打算换个品牌做android在ATT用mate2的，能用attwifi吗？moto g 刷p+ spc出错samsang NOTE II 丢了还能找回来吗？问下网盘上T地哥们姐们都是干嘛地？Oneplus One 可以用Tmobile的所有band吗?请推荐一个detachable 的 laptop回天朝用，mate 2美版好还是天朝版好？1+1 可以上tmobile的lte吗?1+1的外放声音小，是我设置不对吗？ 和一点review
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。