贡献几道A家intern的题 - 未名空间MITBBS历史存档

s*32012-03-04 08:03

1 楼

两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
offer，详细下周谈。自己几乎没做过题，也没系统准备过coding面试，做题数小于30
。能拿到offer全靠本科积累的基础知识，还有一个最重要的原因就是面试问的题都不
难。
另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
。

y*n2012-03-04 08:03

2 楼

Cong~~~之前问过他家recruiter，貌似是说如果intern最后打分高的话是可以直接留下
的。不过那时候是在career fair，说得也不是很清楚
第1题不是很懂啊。只有一个byte不同.然后找不同byte的位置？

s*32012-03-04 08:03

3 楼

对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。

【在 y*****n 的大作中提到】

: Cong~~~之前问过他家recruiter，貌似是说如果intern最后打分高的话是可以直接留下
: 的。不过那时候是在career fair，说得也不是很清楚
: 第1题不是很懂啊。只有一个byte不同.然后找不同byte的位置？

y*n2012-03-04 08:03

4 楼

谢谢哦。是要找出那个不同的byte还是什么？不好意思我对题目不是很理解 = =是说
一个文件中有一个byte在另一个文件中没有出现过嘛？

ascii

【在 s*****3 的大作中提到】

: 对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
: 带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
: 继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
: 取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
: 字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。

c*m2012-03-04 08:03

5 楼

cong～
Amazon实习如果好好干，留下来的机会还是挺高的。
转fulltime不用单独面试，就看intern时候的表现

d*n2012-03-04 08:03

6 楼

请问楼主面完之后等回复大概用了多久~ 我周五刚面完~

g*i2012-03-04 08:03

7 楼

intern就早起晚归好好做,A家拿到offer的希望应该挺大,他们在扩张期需要人手.

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。自己几乎没做过题，也没系统准备过coding面试，做题数小于30
: 。能拿到offer全靠本科积累的基础知识，还有一个最重要的原因就是面试问的题都不
: 难。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

c*e2012-03-04 08:03

8 楼

第一题用xor，因为相同的byte，假设x
x xor x xor x xor ... xor y xor x xor x ...
出来的结果就是要么x，要么0
当你一个个xor，找到第一个不为x不为0的时候，你可以停了。
具体怎么写code可以考虑考虑。

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。自己几乎没做过题，也没系统准备过coding面试，做题数小于30
: 。能拿到offer全靠本科积累的基础知识，还有一个最重要的原因就是面试问的题都不
: 难。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

g*92012-03-04 08:03

9 楼

个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M，直到小于
100 KB 才开始一个一个的XOR

c*e2012-03-04 08:03

10 楼

不需要通讯，因为拿到前3个byte就可以确定x。

SERVER

【在 g*******9 的大作中提到】

: 个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
: 带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M，直到小于
: 100 KB 才开始一个一个的XOR

y*n2012-03-04 08:03

11 楼

啊我懂了。。是说2个文件对应位置上的byte相同。只有一个位置上byte不同。然后找
出来。还是需要2个server通信的。应该用binary search,先在各自那边xor1个然后比
较是否相同。然后各自server上XOR 2个再比较..然后是xor4个然后xor2^n个。直到找
到2个结果不一样。就说明byte在2^(n-1)到2^n的区间內。再从那个区间开始search。

【在 c*****e 的大作中提到】

: 不需要通讯，因为拿到前3个byte就可以确定x。
:
: SERVER

c*e2012-03-04 08:03

12 楼

哦，居然在两个server上，那么crc + binary search好了。
hash和crc的function不一样。

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。自己几乎没做过题，也没系统准备过coding面试，做题数小于30
: 。能拿到offer全靠本科积累的基础知识，还有一个最重要的原因就是面试问的题都不
: 难。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

y*n2012-03-04 08:03

13 楼

弱问，crc是神马？

【在 c*****e 的大作中提到】

: 哦，居然在两个server上，那么crc + binary search好了。
: hash和crc的function不一样。
:
: 30

s*32012-03-04 08:03

14 楼

我是周五面完，接下来的周四收到email的。

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

: 请问楼主面完之后等回复大概用了多久~ 我周五刚面完~

d*n2012-03-04 08:03

15 楼

嗯~多谢

【在 s*****3 的大作中提到】

: 我是周五面完，接下来的周四收到email的。

q*82012-03-04 08:03

16 楼

能具体说一下吗？

【在 c*****e 的大作中提到】

: 哦，居然在两个server上，那么crc + binary search好了。
: hash和crc的function不一样。
:
: 30

f*82012-03-04 08:03

17 楼

CRC是一种传输协议，CS或者CE在计算机网络课上学过的。好像是一种可以自己修复的
传输协议。

s*32012-03-04 08:03

18 楼

两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
offer，详细下周谈。
另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
。

y*n2012-03-04 08:03

19 楼

Cong~~~之前问过他家recruiter，貌似是说如果intern最后打分高的话是可以直接留下
的。不过那时候是在career fair，说得也不是很清楚
第1题不是很懂啊。只有一个byte不同.然后找不同byte的位置？

s*32012-03-04 08:03

20 楼

对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。

【在 y*****n 的大作中提到】

: Cong~~~之前问过他家recruiter，貌似是说如果intern最后打分高的话是可以直接留下
: 的。不过那时候是在career fair，说得也不是很清楚
: 第1题不是很懂啊。只有一个byte不同.然后找不同byte的位置？

y*n2012-03-04 08:03

21 楼

谢谢哦。是要找出那个不同的byte还是什么？不好意思我对题目不是很理解 = =是说
一个文件中有一个byte在另一个文件中没有出现过嘛？

ascii

【在 s*****3 的大作中提到】

: 对了，第一题还有个条件，就是这两个文件在两台不同的server上，并且彼此之间通信
: 带宽很小。我当时没有给特别肯定的回答，就说可以考虑用hash和bloom filter。然后
: 继续谈怎么样去用hash做，以及怎么设计hash函数(大体idea是把文件一段一段的ascii
: 取模)。对于第二个问题，set用bst实现，coding题我第一次写错了(当时只考虑了左右
: 字节点，而不是左右子树)，后来在他提醒下很快重新写了个实现。

c*m2012-03-04 08:03

22 楼

cong～
Amazon实习如果好好干，留下来的机会还是挺高的。
转fulltime不用单独面试，就看intern时候的表现

d*n2012-03-04 08:03

23 楼

请问楼主面完之后等回复大概用了多久~ 我周五刚面完~

g*i2012-03-04 08:03

24 楼

intern就早起晚归好好做,A家拿到offer的希望应该挺大,他们在扩张期需要人手.

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

c*e2012-03-04 08:03

25 楼

第一题用xor，因为相同的byte，假设x
x xor x xor x xor ... xor y xor x xor x ...
出来的结果就是要么x，要么0
当你一个个xor，找到第一个不为x不为0的时候，你可以停了。
具体怎么写code可以考虑考虑。

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

g*92012-03-04 08:03

26 楼

个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M，直到小于
100 KB 才开始一个一个的XOR

c*e2012-03-04 08:03

27 楼

不需要通讯，因为拿到前3个byte就可以确定x。

SERVER

【在 g*******9 的大作中提到】

: 个人觉得第一题不能一个一个的XOR,因为这么比0会需要2个SERVER通讯，此题中SERVER
: 带宽小。所以我觉得可以先XOR 100M，比较，然后缩减范围，再XOR 50M，直到小于
: 100 KB 才开始一个一个的XOR

y*n2012-03-04 08:03

28 楼

啊我懂了。。是说2个文件对应位置上的byte相同。只有一个位置上byte不同。然后找
出来。还是需要2个server通信的。应该用binary search,先在各自那边xor1个然后比
较是否相同。然后各自server上XOR 2个再比较..然后是xor4个然后xor2^n个。直到找
到2个结果不一样。就说明byte在2^(n-1)到2^n的区间內。再从那个区间开始search。

【在 c*****e 的大作中提到】

: 不需要通讯，因为拿到前3个byte就可以确定x。
:
: SERVER

c*e2012-03-04 08:03

29 楼

哦，居然在两个server上，那么crc + binary search好了。
hash和crc的function不一样。

30

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

y*n2012-03-04 08:03

30 楼

弱问，crc是神马？

【在 c*****e 的大作中提到】

: 哦，居然在两个server上，那么crc + binary search好了。
: hash和crc的function不一样。
:
: 30

s*32012-03-04 08:03

31 楼

我是周五面完，接下来的周四收到email的。

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

: 请问楼主面完之后等回复大概用了多久~ 我周五刚面完~

d*n2012-03-04 08:03

32 楼

嗯~多谢

【在 s*****3 的大作中提到】

: 我是周五面完，接下来的周四收到email的。

q*82012-03-04 08:03

33 楼

能具体说一下吗？

【在 c*****e 的大作中提到】

: 哦，居然在两个server上，那么crc + binary search好了。
: hash和crc的function不一样。
:
: 30

f*82012-03-04 08:03

34 楼

CRC是一种传输协议，CS或者CE在计算机网络课上学过的。好像是一种可以自己修复的
传输协议。

g*e2012-03-04 08:03

35 楼

这里xor足够了。
btw，大家面试时讨论hash function，我想SHA1这种digital sign算法是不是通吃呢，
除了perf比较贵？

【在 f********8 的大作中提到】

: CRC是一种传输协议，CS或者CE在计算机网络课上学过的。好像是一种可以自己修复的
: 传输协议。

b*e2012-03-04 08:03

36 楼

CRC is probably an overkill. I'll just segment the file based on memory size
and compute the sum of all the bytes in the segment. Just comparing the
sums would be enough.

【在 c*****e 的大作中提到】

: 哦，居然在两个server上，那么crc + binary search好了。
: hash和crc的function不一样。
:
: 30

C*U2012-03-04 08:03

37 楼

cong!

【在 s*****3 的大作中提到】

: 两轮；第一轮问了个设计题，两个1terabyte的文件，只有一个byte不一样，怎么样可
: 以最有效的找到不同byte的位置；第二轮主要问了个coding题，如何判断一个tree是不
: 是binary search tree；另外还问了个C++中set是用什么实现的。之后HR邮件说有
: offer，详细下周谈。
: 另外请教个问题，他家intern转fulltime难么？还是会到时再来一次常规面？非常感谢
: 。

d*i2012-03-04 08:03

38 楼

如果有带宽小的问题，那么就要结合binary search的思想。
In server 1.
XOR bytes between start and mid position,记录xor的结果，然后将start and mid
positions 这个范围传个server2.
在server2 上同对这个范围内的byte XOR
比较两个XOR的结果。
1. 相同，那么寻找mid + 1 to end 范围内的byte
2. 不同，寻找 start to mid 范围内的byte
虽然这样double了XOR的次数，但是减少了传输的压力。
不知道这个思路是否和出题者的意图接近，请指正。

s*12012-03-04 08:03

39 楼

冒昧问一下楼上，如果带宽小的话，你一次传输 start到mid的byte数也是很大的额，
误差率会很大啊。。。。。。
求高人给出解答额。。。。。。

d*i2012-03-04 08:03

40 楼

我说的是把position传过去，然后对另外一个server上两个positions之间的bytes XOR
,我没说传送两个positions之间的byte

【在 s*****1 的大作中提到】

: 冒昧问一下楼上，如果带宽小的话，你一次传输 start到mid的byte数也是很大的额，
: 误差率会很大啊。。。。。。
: 求高人给出解答额。。。。。。

s*d2012-03-04 08:03

41 楼

和dafeilei的想法类似诶，Amazon发了篇论文Dynamo有提到：
Hash trees or Merkle trees
http://en.wikipedia.org/wiki/Hash_tree
==================
如果有带宽小的问题，那么就要结合binary search的思想。
In server 1.
XOR bytes between start and mid position,记录xor的结果，然后将start and mid
positions 这个范围传个server2.
在server2 上同对这个范围内的byte XOR
比较两个XOR的结果。
1. 相同，那么寻找mid + 1 to end 范围内的byte
2. 不同，寻找 start to mid 范围内的byte
虽然这样double了XOR的次数，但是减少了传输的压力。
不知道这个思路是否和出题者的意图接近，请指正。