r*****n
发帖数: 2 | 1 onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
是fresh master.
两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
解题意。
有一种新型存储设备，特点是：
1. 价格贵，稳定性高
2. 可读写，但写入的内容不能修改
如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
呢。
4轮Onsite 3个印度人一个欧洲人。都是从简单的题开始，不停改改改。都讨论了项目
经验，还问得很细。写完代码都是要照相的，我有个题是开始写得挺干净，后来条件加
加加就改花了，然后interviewer掏出手机拍了一张。。我觉得是不是可以在写完第一
版之后就请他拍一张先。。。
1.一个binary search变体。 写完之后开始抠代码，说如果把终止条件从low<=high 改
成low
到这种问题是应该事先总结好的。我当时只是针对那个题在讨论，没有总结一下。
http://blog.sina.com.cn/s/blog_b9285de20101h88j.html
2.一个doc里有很多word. 在很多doc里面快速找出符合条件的一对pair ,
条件是它们有且只有一个相同的word. Doc很多，不能全部放入内存。从概率上应该从
哪种doc先下手找
Doc1
Doc2
Doc3
找到
3.一个input stream, 实现peek, read, write.
我先假设这个stream是个内存里的数组,写了peek read write 函数
加条件说Input stream可以是数据库，文件，STDIN，stream不能一次读入内存。
我跟这个interviewer沟通不是太好。加条件的时候我很糊涂，我说是考java里怎么实
现文件和数据库的读写吗？他说我只是辅助你来设计的，我不能告诉你怎么实现。我又
换着问了几遍说我没理解题意。他说不能hint你太多。我最后就写了一个input类，说
可以接受各种类型输入。我猜是考OO设计吧。
Good Luck to everyone! |
p*****p
发帖数: 379 | |
j********x
发帖数: 2330 | |
t********6
发帖数: 348 | 4 why input stream can be written? thank you. |
d*s
发帖数: 699 | |
g*****o
发帖数: 1637 | 6 m
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
B*******1
发帖数: 2454 | 7 bless,能够进hc证明你的分数已经过线了。
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
p*****2
发帖数: 21240 | 8 最近G的面经确实要更难一些呀。怪不得800题大牛气的不做题了 |
e**s
发帖数: 134 | 9 good! Thanks for sharing!
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
f*******t
发帖数: 7549 | |
|
|
v*****u
发帖数: 406 | |
Q*******e
发帖数: 939 | 12 看来g家也要被三给占领了
xdjm加油啊
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
o****d
发帖数: 2835 | 13 问下 binary search
i+(j-i)/2 和 (i+j)/2 在什么时候有区别？
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
h***i
发帖数: 1970 | 14 永远不要用(i+j)/2，可能溢出
【在 o****d 的大作中提到】
: 问下 binary search
: i+(j-i)/2 和 (i+j)/2 在什么时候有区别？
|
o****d
发帖数: 2835 | 15 除了溢出还有什么区别吗？ （溢出只是早晚的事）
【在 h***i 的大作中提到】
: 永远不要用(i+j)/2，可能溢出
|
b********e
发帖数: 43 | 16 第二题我的想法是把所有的doc按照size大小排序然后分别从两头开始比较， 因为符合
条件的最大概率应该是最短的doc里面有且只有一个与最长doc相同的word.
不知道是否正确。 |
r*****n
发帖数: 2 | 17 没有write，我写错了。谢啦！
【在 d*s 的大作中提到】
: 同问，input写入有什么意义么？
|
h***i
发帖数: 1970 | 18 谁说的， i+(j-i)/2 永远不会溢出。
【在 o****d 的大作中提到】
: 除了溢出还有什么区别吗？ （溢出只是早晚的事）
|
o****d
发帖数: 2835 | 19 you are right.
找了一个溢出之外的解释
当low high不是指数组index的时候 有可能是负数
然后除2之后 会碰到潜在的问题
参考
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
"You may also wonder as to why mid is calculated using mid = lo + (hi-lo)/2
instead of the usual mid = (lo+hi)/2. This is to avoid another potential
rounding bug: in the first case, we want the division to always round down,
towards the lower bound. But division truncates, so when lo+hi would be
negative, it would start rounding towards the higher bound."
【在 h***i 的大作中提到】
: 谁说的， i+(j-i)/2 永远不会溢出。
|
K********y
发帖数: 47 | 20 第二道概率题是不是可以这么想：假定一共有N个word，每个出现的概率为f(W_i)（=
count(W_i) / total # words）。如果doc_i的长度为L_i，它包含W_i的概率是1-(1-f(
W_i))^L_i。所以doc_1和doc_2有one and only one common word的概率是
sum_over_W_i ( (1-(1-f(W_i))^L1)*(1-(1-f(W_i))^L2) * product_over_W_j!=i ( 1
- (1-(1-f(W_j))^L1)*(1-(1-f(W_j))^L2) )
如果粗略地假定所有word出现频率相等，f(W_i) = 1/N，并假定L_i * f(W_i) << 1，
则以上概率等于
N*L1/N * L2/N * (1-L1/N*L2/N)^(N-1) = L1*L2/N * (1-L1*L2/N/N)^(N-1)
当L1*L2 ~ N时概率最大，所以应该先选择L~sqrt(N)长度的文件。
如果两个文件长度不等，一个太大一个太小可能导致以上近似不成立。 |
|
|
M******7
发帖数: 30 | |
r*********n
发帖数: 4553 | 22 都binary search了，什么时候会出现lo hi不是index或者什么时候lo, hi会是负数呢？
2
,
【在 o****d 的大作中提到】
: you are right.
: 找了一个溢出之外的解释
: 当low high不是指数组index的时候 有可能是负数
: 然后除2之后 会碰到潜在的问题
: 参考
: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
: "You may also wonder as to why mid is calculated using mid = lo + (hi-lo)/2
: instead of the usual mid = (lo+hi)/2. This is to avoid another potential
: rounding bug: in the first case, we want the division to always round down,
: towards the lower bound. But division truncates, so when lo+hi would be
|
c******3
发帖数: 60 | 23 谢谢分享！
【在 r*****n 的大作中提到】
: onsite之后有个interviewer旅游去了，4周之后才拿到feedback，提交HC之后又一周没
: 动静了，给recruiter发信也不回。实在等得心烦。发个面经就算挂了然后move on吧。
: 是fresh master.
: 两轮电面，都是经典题。写完2个题还有点时间，讨论了一个设计题，我到现在也不理
: 解题意。
: 有一种新型存储设备，特点是：
: 1. 价格贵，稳定性高
: 2. 可读写，但写入的内容不能修改
: 如何利用它的特点设计一个存储系统。在聊天过程中增加了一些条件，如果有个人写了
: 个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的
|
