logo
Redian新闻
>未名空间
>EB23 - 劳工卡
>
EB2-EB3 降级的两个140
avatar
EB2-EB3 降级的两个140# EB23 - 劳工卡
g*r
1 楼
google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
午饭，觉得吃的一般啊，比twitter的差些。
第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
有bug, 当时想就废了.
第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
第二题，直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动
n步，再回到原点的概率是多少, 可以写程序实现。
这两题我答得挺好的，才进入状态。。
第五轮。
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以。
twitter onsite
我觉得twitter onsite的题目我都写对了，面试官没有发现任何bug，本来希望还蛮大
的，但还是被拒了。但反馈说了2点。 1是思路代码写得太快了
，我挺无语的，我写之前都和面试官说了下我的idea啊, 等确认了再写的，题做多了也
不行啊。。2是系统设计能力欠缺。
第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
第二题，就是那个爬梯子的题目了.
第二轮，就是设计一个手机上的下棋的游戏，涉及到客户端服务器端.
第三轮，Subsets problem. 然后扯项目经验.
中午吃饭，twitter的伙食真的很好，比google要强多了。
第四轮，扯扯项目经验，然后给2个sorted array, 求kth largest.
第五轮，n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min heap的方
法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开销，写了
代码。
mirror a binary tree.
第六轮 我觉得这个可能是个我杯具的原因之一吧，老印老板问的问题都很奇怪，比如
从cache, ram, disk读一个字节需要多少时间。 1个200G的文件在硬盘上是如何存储的
，我没在我简历上说这些啊.
反正2家都杯具还是有点郁闷的，后悔没先其它公司先练练，到google的时候刚开始写
白板都没状态. 没有很难的题目，基本题练好就行了。twitter是家非常好的公司，但
是会很忙，我2次电话面试都因为面试官救火而重新安排的.
但愿这些能给后来的兄弟一些帮助啦。
avatar
w*e
2 楼
应该是同一个A#吧。找不到EB2的I140了。
avatar
j*s
3 楼
嗯，很详细啊，lz能记得这么多真不容易。希望楼主好运。
avatar
w*e
4 楼
顶一下。
A# 一样吗?

【在 w****e 的大作中提到】
: 应该是同一个A#吧。找不到EB2的I140了。
avatar
s*2
5 楼
感谢lz面经
avatar
l*a
6 楼
先顶后看
扫了一下，感觉写的有点粗

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
c*s
7 楼
Big big bless!
avatar
g*r
8 楼
谢谢各位兄弟啊，可惜2个都杯具了
avatar
g*j
9 楼
请问这三题怎么做的？
第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
有bug, 当时想就废了.
这个地方你有什么bug?
第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这个怎么做？对space有要求么？如果对space没有要求，直接扫描就可以吧？
第二题，直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动
n步，再回到原点的概率是多少, 可以写程序实现。
怎么写程序实现？模拟？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
g*j
10 楼
没事，失败是成功之母

【在 g*******r 的大作中提到】
: 谢谢各位兄弟啊，可惜2个都杯具了
avatar
g*r
11 楼
那题我递归中数组索引写的有问题，当时真不在状态，他一提示我还没发现。
环的那个空间没要求，用hash_map就行
那个机器人移动的就是写个递归啊，移动n步，计算回到原点的次数，除以所有的可能
性。

2

【在 g***j 的大作中提到】
: 请问这三题怎么做的？
: 第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
: 有bug, 当时想就废了.
: 这个地方你有什么bug?
: 第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
: 索引 0 1 2 3 4
: 值 3 2 1 4 0
: 数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
: -> 1， 求最长环的长度.
: 这个怎么做？对space有要求么？如果对space没有要求，直接扫描就可以吧？
avatar
b*e
12 楼
晕，代码写快了还成缺点了。
avatar
A*t
13 楼
挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
司面一遍总有一个碰上的。

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
j*2
14 楼

什么东西find, insert, delete,getrandom? vector?

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
w*x
15 楼
顶!
avatar
j*2
16 楼
google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
g*r
17 楼
呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。

【在 A*****t 的大作中提到】
: 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
: 司面一遍总有一个碰上的。
avatar
g*r
18 楼
http://www.sureinterview.com/shwqst/1019005
这里有介绍.

【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
avatar
g*r
19 楼
组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
错误，没绕过来。

吗？

【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
avatar
j*2
20 楼
谢谢！！
真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！

【在 g*******r 的大作中提到】
: http://www.sureinterview.com/shwqst/1019005
: 这里有介绍.
avatar
B*1
21 楼
楼主多少年工作经验了啊？

【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
avatar
g*r
22 楼
加油。我面试一个感觉是国人都很好，都找的很好的题问的。twitter电话面试时一个
哥们还心照不宣地问我这题是不是见过，呵呵。
印度哥们就很坏，读写锁那个那哥们见我有错的就拍照。。

【在 j******2 的大作中提到】
: 谢谢！！
: 真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
avatar
g*r
23 楼
1年多一点

【在 B*******1 的大作中提到】
: 楼主多少年工作经验了啊？
avatar
j*2
24 楼
我觉得所谓“常规题”的范围在扩大！而且扩大速度超过我的复习速度！
avatar
A*t
25 楼
你在哪家工作？我也骑驴找马，目前Google过了hire committee

【在 g*******r 的大作中提到】
: 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
avatar
A*e
26 楼
谢谢lz分享啊～
我觉得特别累的情况下马上面一天确实很辛苦。但是G的那个印度人，挺坏的。。。还
拍照，雷。。。
T家的第6论，完全不懂。。。
avatar
k*r
27 楼
不错啊，zan
avatar
h*e
28 楼
好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
avatar
o*d
29 楼
客户端那题莫非是问这个?
http://www.mitbbs.com/article_t/JobHunting/32061423.html
机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
我上两次面试都是半夜1点钟到hotel,呵呵

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
p*2
30 楼
d鈥唂鈥唖

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
p*2
31 楼
dfs

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
s*k
32 楼
读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
都被block?
按照qt的reference，写了一个
class ReadWriteMutex
{
public:
ReadWriteMutex(int maxReaders = 32)
: semaphore(maxReaders)
{
}

void lockRead() { semaphore++; }
void unlockRead() { semaphore--; }
void lockWrite() {
QMutexLocker locker(&mutex);
for (int i = 0; i < maxReaders(); ++i)
semaphore++;
}
void unlockWrite() { semaphore -= semaphore.total(); }
int maxReaders() const { return semaphore.total(); }

private:
QSemaphore semaphore;
QMutex mutex;
};

【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
avatar
A*e
33 楼
请大牛明示！

【在 p*****2 的大作中提到】
: dfs
avatar
g*r
34 楼
我确实是搞系统开发的，不过这面试是答得惨啊.

【在 h*******e 的大作中提到】
: 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
avatar
g*r
35 楼
我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
度方面想，我现在都不明白啊.

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
g*r
36 楼
http://stackoverflow.com/questions/8635963/read-write-lock-impl
这个答案应该是老印想要的.

【在 s********k 的大作中提到】
: 读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
: 都被block?
: 按照qt的reference，写了一个
: class ReadWriteMutex
: {
: public:
: ReadWriteMutex(int maxReaders = 32)
: : semaphore(maxReaders)
: {
: }
avatar
p*2
37 楼

计算两个number
一共有多少种可能性，其中有多少是回到远点，其实就是brute force

【在 A****e 的大作中提到】
: 请大牛明示！
avatar
g*r
38 楼
对，就是2爷说的这个意思.

【在 p*****2 的大作中提到】
:
: 计算两个number
: 一共有多少种可能性，其中有多少是回到远点，其实就是brute force
avatar
l*a
39 楼
是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
totalCnt){
if(n == 0){
totalCnt++;
if(x == 0){
cnt++;
}
return;
}
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
}
cout<
【在 g*******r 的大作中提到】
: 对，就是2爷说的这个意思.
avatar
q*8
40 楼
珍贵的面经，感谢
avatar
g*r
41 楼
就是这样的程序啊。老中面试官人好，没有让我用数学方法求结果.

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
p*o
42 楼
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这题怎么做啊？
avatar
o*d
43 楼
nice, thanks

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
f*4
44 楼
对于悲剧实在是习惯就好，而且很快就发现一扇门关了另一扇窗就开了，相信自己最重
要。时间问题
avatar
A*e
45 楼
二爷你说的是机器人那道题啊～
我还以为你说的是客户端请求每秒钟只发送10个的那个呢
请问那个客户端的怎么做呀？
是像27楼说的那样用timer call back func吗？

【在 p*****2 的大作中提到】
: dfs
avatar
A*e
46 楼
同困惑，怎么从平均速度的角度考虑啊?
因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
这是充分条件，不是必要条件。
所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
等高人出来指点。

【在 g*******r 的大作中提到】
: 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
: 度方面想，我现在都不明白啊.
avatar
A*e
47 楼
读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
你的简历上有表现出有多线程相关的经验吗？
还是被老印黑了？
还是大家都觉得这个属于常规题？。。。

【在 g*******r 的大作中提到】
: http://stackoverflow.com/questions/8635963/read-write-lock-impl
: 这个答案应该是老印想要的.
avatar
t*e
48 楼
楼主大牛拉， 电面都能聊上spanner了肯定level不低
avatar
g*r
49 楼
这个我在简历中提到多线程了，我平时工作中用到多线程了。读写锁的实现你要是看过
就还好了，没看过的话有点弯弯的，我那天写起来总是有问题。

【在 A****e 的大作中提到】
: 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
: 你的简历上有表现出有多线程相关的经验吗？
: 还是被老印黑了？
: 还是大家都觉得这个属于常规题？。。。
avatar
w*x
50 楼
机器人算概率那题， 不久是左移和右移的number要相等吗？
不就是一道概率题吗：
N is odd => 0
N is even => (1/2)^N * C(N) (N/2)
avatar
l*a
51 楼
题中没说要相等

【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
avatar
p*g
52 楼
1.如果往左/右的概率是 p/1-p
这个程序应该怎么写?
2. 总觉得这种recursive的不如递推的好
3. 觉得那两行
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
不需要乘 0.5么
多谢

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
h*0
53 楼
牛人 !!
我只走到：
P[n][0] = 0 when n is odd
= 2 * P[n-1][1] when n is even
P[n][k] = P[n-1][k+1] + P[n-1][k-1] ( 0< k )
你一提醒 才想到
C(n, 0) + C(n, 1) + --- + C(n, n) = 2^n.
顺便多说几句思路， （ 被解惑乐， 解人惑乐 ）
-n, --------,-1, 0, 1, 2, ------n
n=0 1
n=1 1, 0, 1,
n=2 1, 0, 2, 0, 1, ( 注意 0 的左右是对称的)
n=3 0, 3, 0, 1
n=4 6, 0, 4, 0, 1
n=5 0,10, 0, 5, 0, 1
n=6 20,0,15, 0, 6, 0, 1
----
Define P[n][k] as the number that the robot is in k after n steps, total it'
s 2^n. so the possibility it's P[n][k]/2^n

【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
avatar
c*s
54 楼
Twitter的最后一题应该是估算吧：
cache的读写时间大概是几个时钟周期，也就是1ns左右。
RAM大概比cache慢一个量级，那读一个字节就是10ns左右，
假如数据所在页面的地址不在TLB里，那就要至少增加一次RAM的读写，时间可能就是几
十纳秒。
Disk的读写就是纯估算了，假设一个机械硬盘顺序读的速度100MB/s,
那么读一个字节的时间大概是 4096 / (100 * 10^6) s = 40 us (假设一个block是
4096字节，读操作是瓶颈).
如果磁头不在数据所在的磁道上，那还需要加上一个磁头移动时间。
200GB的文件应该是问文件头是怎么存的，如果是类Unix的i-node文件系统（假设一个
block是4096字节），
应该是一个block里有一个数组，数组的前面几个值保存文件信息和指向文件头几个
block （~10 * 4KB = 40 KB）。
后面3个值，一个指向一个block，这个block保存接下来文件数据存的地址。(512 * 4
KB = 2 MB)
倒数第二个值指向另一个block，这个block指向另一堆block (512 * 2 MB = 1 GB)
最后一个是3重block 指针 (512 * 1 GB = 512 GB)。
最后的block size和block地址的长度可能会有变化，计算中地址长度是8B。

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
c*s
55 楼
这个有公式吧：
if n = odd, P = 0;
else P = n!/(n/2)!/(n/2)!/2^n;

【在 h********0 的大作中提到】
: 牛人 !!
: 我只走到：
: P[n][0] = 0 when n is odd
: = 2 * P[n-1][1] when n is even
: P[n][k] = P[n-1][k+1] + P[n-1][k-1] ( 0< k )
: 你一提醒 才想到
: C(n, 0) + C(n, 1) + --- + C(n, n) = 2^n.
: 顺便多说几句思路， （ 被解惑乐， 解人惑乐 ）
: -n, --------,-1, 0, 1, 2, ------n
: n=0 1
avatar
c*s
56 楼
估计是以1秒为单位，如果在这一秒内已经接受10个请求了，就不再接受请求？

【在 A****e 的大作中提到】
: 同困惑，怎么从平均速度的角度考虑啊?
: 因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
: 这是充分条件，不是必要条件。
: 所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
: 等高人出来指点。
avatar
S*0
57 楼

这题太过分了！

【在 c***s 的大作中提到】
: Twitter的最后一题应该是估算吧：
: cache的读写时间大概是几个时钟周期，也就是1ns左右。
: RAM大概比cache慢一个量级，那读一个字节就是10ns左右，
: 假如数据所在页面的地址不在TLB里，那就要至少增加一次RAM的读写，时间可能就是几
: 十纳秒。
: Disk的读写就是纯估算了，假设一个机械硬盘顺序读的速度100MB/s,
: 那么读一个字节的时间大概是 4096 / (100 * 10^6) s = 40 us (假设一个block是
: 4096字节，读操作是瓶颈).
: 如果磁头不在数据所在的磁道上，那还需要加上一个磁头移动时间。
: 200GB的文件应该是问文件头是怎么存的，如果是类Unix的i-node文件系统（假设一个
avatar
c*s
58 楼
这题就是纯操作系统的题。
存文件的题目我们当年期末考试的时候还考过。
不过考试中是给定了block的大小和地址长度的。

【在 S******0 的大作中提到】
:
: 这题太过分了！
avatar
w*p
59 楼
看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说bug free
电面第一题，看了下答案。思路上和我想的差不多。find O(1) 只有hash了， insert,
getRandom, 要用array
delete O(2) 在array 里可以。
不过当时电话里写这题的code，真的头大。
楼主遇到的题都是貌似不难，下手不易的题。
谢谢楼主分享。再接再厉，拿到好的offer.

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
e*s
60 楼
如何判断一棵树是BST
这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
avatar
c*s
61 楼
那你就long类型，^_^

【在 e***s 的大作中提到】
: 如何判断一棵树是BST
: 这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
avatar
e*s
62 楼
楼主，请问这个G第五轮怎么答靠谱啊？
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以
avatar
r*n
63 楼

you can still use counting method to come up with a closed-form formula
if we have to write program, we can do the following. assume p is rational,
i.e. p = n/m for some integer n and m. use dfs, in each recursion call dfs n
times for the left turn and m-n times for the right turn. in the end, count
# of dfs reaching 0 and all # of dfs, and divide
if p is irrational, we can approximate p using a rational number with
arbitrary precision.

【在 p*g 的大作中提到】
: 1.如果往左/右的概率是 p/1-p
: 这个程序应该怎么写?
: 2. 总觉得这种recursive的不如递推的好
: 3. 觉得那两行
: probabilty(n - 1, x - 1, cnt, totalCnt);
: probabilty(n - 1, x + 1, cnt, totalCnt);
: 不需要乘 0.5么
: 多谢
avatar
g*r
64 楼
google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
午饭，觉得吃的一般啊，比twitter的差些。
第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
有bug, 当时想就废了.
第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
第二题，直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动
n步，再回到原点的概率是多少, 可以写程序实现。
这两题我答得挺好的，才进入状态。。
第五轮。
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以。
twitter onsite
我觉得twitter onsite的题目我都写对了，面试官没有发现任何bug，本来希望还蛮大
的，但还是被拒了。但反馈说了2点。 1是思路代码写得太快了
，我挺无语的，我写之前都和面试官说了下我的idea啊, 等确认了再写的，题做多了也
不行啊。。2是系统设计能力欠缺。
第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
第二题，就是那个爬梯子的题目了.
第二轮，就是设计一个手机上的下棋的游戏，涉及到客户端服务器端.
第三轮，Subsets problem. 然后扯项目经验.
中午吃饭，twitter的伙食真的很好，比google要强多了。
第四轮，扯扯项目经验，然后给2个sorted array, 求kth largest.
第五轮，n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min heap的方
法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开销，写了
代码。
mirror a binary tree.
第六轮 我觉得这个可能是个我杯具的原因之一吧，老印老板问的问题都很奇怪，比如
从cache, ram, disk读一个字节需要多少时间。 1个200G的文件在硬盘上是如何存储的
，我没在我简历上说这些啊.
反正2家都杯具还是有点郁闷的，后悔没先其它公司先练练，到google的时候刚开始写
白板都没状态. 没有很难的题目，基本题练好就行了。twitter是家非常好的公司，但
是会很忙，我2次电话面试都因为面试官救火而重新安排的.
但愿这些能给后来的兄弟一些帮助啦。
avatar
j*s
65 楼
嗯，很详细啊，lz能记得这么多真不容易。希望楼主好运。
avatar
s*2
66 楼
感谢lz面经
avatar
l*a
67 楼
先顶后看
扫了一下，感觉写的有点粗

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
c*s
68 楼
Big big bless!
avatar
g*r
69 楼
谢谢各位兄弟啊，可惜2个都杯具了
avatar
g*j
70 楼
请问这三题怎么做的？
第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
有bug, 当时想就废了.
这个地方你有什么bug?
第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这个怎么做？对space有要求么？如果对space没有要求，直接扫描就可以吧？
第二题，直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动
n步，再回到原点的概率是多少, 可以写程序实现。
怎么写程序实现？模拟？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
g*j
71 楼
没事，失败是成功之母

【在 g*******r 的大作中提到】
: 谢谢各位兄弟啊，可惜2个都杯具了
avatar
g*r
72 楼
那题我递归中数组索引写的有问题，当时真不在状态，他一提示我还没发现。
环的那个空间没要求，用hash_map就行
那个机器人移动的就是写个递归啊，移动n步，计算回到原点的次数，除以所有的可能
性。

2

【在 g***j 的大作中提到】
: 请问这三题怎么做的？
: 第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
: 有bug, 当时想就废了.
: 这个地方你有什么bug?
: 第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
: 索引 0 1 2 3 4
: 值 3 2 1 4 0
: 数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
: -> 1， 求最长环的长度.
: 这个怎么做？对space有要求么？如果对space没有要求，直接扫描就可以吧？
avatar
b*e
73 楼
晕，代码写快了还成缺点了。
avatar
A*t
74 楼
挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
司面一遍总有一个碰上的。

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
j*2
75 楼

什么东西find, insert, delete,getrandom? vector?

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
w*x
76 楼
顶!
avatar
j*2
77 楼
google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
g*r
78 楼
呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。

【在 A*****t 的大作中提到】
: 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
: 司面一遍总有一个碰上的。
avatar
g*r
79 楼
http://www.sureinterview.com/shwqst/1019005
这里有介绍.

【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
avatar
g*r
80 楼
组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
错误，没绕过来。

吗？

【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
avatar
j*2
81 楼
谢谢！！
真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！

【在 g*******r 的大作中提到】
: http://www.sureinterview.com/shwqst/1019005
: 这里有介绍.
avatar
B*1
82 楼
楼主多少年工作经验了啊？

【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
avatar
g*r
83 楼
加油。我面试一个感觉是国人都很好，都找的很好的题问的。twitter电话面试时一个
哥们还心照不宣地问我这题是不是见过，呵呵。
印度哥们就很坏，读写锁那个那哥们见我有错的就拍照。。

【在 j******2 的大作中提到】
: 谢谢！！
: 真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
avatar
g*r
84 楼
1年多一点

【在 B*******1 的大作中提到】
: 楼主多少年工作经验了啊？
avatar
j*2
85 楼
我觉得所谓“常规题”的范围在扩大！而且扩大速度超过我的复习速度！
avatar
A*t
86 楼
你在哪家工作？我也骑驴找马，目前Google过了hire committee

【在 g*******r 的大作中提到】
: 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
avatar
A*e
87 楼
谢谢lz分享啊～
我觉得特别累的情况下马上面一天确实很辛苦。但是G的那个印度人，挺坏的。。。还
拍照，雷。。。
T家的第6论，完全不懂。。。
avatar
k*r
88 楼
不错啊，zan
avatar
h*e
89 楼
好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
avatar
o*d
90 楼
客户端那题莫非是问这个?
http://www.mitbbs.com/article_t/JobHunting/32061423.html
机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
我上两次面试都是半夜1点钟到hotel,呵呵

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
p*2
91 楼
d鈥唂鈥唖

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
p*2
92 楼
dfs

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
s*k
93 楼
读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
都被block?
按照qt的reference，写了一个
class ReadWriteMutex
{
public:
ReadWriteMutex(int maxReaders = 32)
: semaphore(maxReaders)
{
}

void lockRead() { semaphore++; }
void unlockRead() { semaphore--; }
void lockWrite() {
QMutexLocker locker(&mutex);
for (int i = 0; i < maxReaders(); ++i)
semaphore++;
}
void unlockWrite() { semaphore -= semaphore.total(); }
int maxReaders() const { return semaphore.total(); }

private:
QSemaphore semaphore;
QMutex mutex;
};

【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
avatar
A*e
94 楼
请大牛明示！

【在 p*****2 的大作中提到】
: dfs
avatar
g*r
95 楼
我确实是搞系统开发的，不过这面试是答得惨啊.

【在 h*******e 的大作中提到】
: 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
avatar
g*r
96 楼
我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
度方面想，我现在都不明白啊.

【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
avatar
g*r
97 楼
http://stackoverflow.com/questions/8635963/read-write-lock-impl
这个答案应该是老印想要的.

【在 s********k 的大作中提到】
: 读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
: 都被block?
: 按照qt的reference，写了一个
: class ReadWriteMutex
: {
: public:
: ReadWriteMutex(int maxReaders = 32)
: : semaphore(maxReaders)
: {
: }
avatar
p*2
98 楼

计算两个number
一共有多少种可能性，其中有多少是回到远点，其实就是brute force

【在 A****e 的大作中提到】
: 请大牛明示！
avatar
g*r
99 楼
对，就是2爷说的这个意思.

【在 p*****2 的大作中提到】
:
: 计算两个number
: 一共有多少种可能性，其中有多少是回到远点，其实就是brute force
avatar
l*a
100 楼
是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
totalCnt){
if(n == 0){
totalCnt++;
if(x == 0){
cnt++;
}
return;
}
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
}
cout<
【在 g*******r 的大作中提到】
: 对，就是2爷说的这个意思.
avatar
q*8
101 楼
珍贵的面经，感谢
avatar
g*r
102 楼
就是这样的程序啊。老中面试官人好，没有让我用数学方法求结果.

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
p*o
103 楼
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这题怎么做啊？
avatar
o*d
104 楼
nice, thanks

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
f*4
105 楼
对于悲剧实在是习惯就好，而且很快就发现一扇门关了另一扇窗就开了，相信自己最重
要。时间问题
avatar
A*e
106 楼
二爷你说的是机器人那道题啊～
我还以为你说的是客户端请求每秒钟只发送10个的那个呢
请问那个客户端的怎么做呀？
是像27楼说的那样用timer call back func吗？

【在 p*****2 的大作中提到】
: dfs
avatar
A*e
107 楼
同困惑，怎么从平均速度的角度考虑啊?
因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
这是充分条件，不是必要条件。
所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
等高人出来指点。

【在 g*******r 的大作中提到】
: 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
: 度方面想，我现在都不明白啊.
avatar
A*e
108 楼
读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
你的简历上有表现出有多线程相关的经验吗？
还是被老印黑了？
还是大家都觉得这个属于常规题？。。。

【在 g*******r 的大作中提到】
: http://stackoverflow.com/questions/8635963/read-write-lock-impl
: 这个答案应该是老印想要的.
avatar
t*e
109 楼
楼主大牛拉， 电面都能聊上spanner了肯定level不低
avatar
g*r
110 楼
这个我在简历中提到多线程了，我平时工作中用到多线程了。读写锁的实现你要是看过
就还好了，没看过的话有点弯弯的，我那天写起来总是有问题。

【在 A****e 的大作中提到】
: 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
: 你的简历上有表现出有多线程相关的经验吗？
: 还是被老印黑了？
: 还是大家都觉得这个属于常规题？。。。
avatar
w*x
111 楼
机器人算概率那题， 不久是左移和右移的number要相等吗？
不就是一道概率题吗：
N is odd => 0
N is even => (1/2)^N * C(N) (N/2)
avatar
l*a
112 楼
题中没说要相等

【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
avatar
p*g
113 楼
1.如果往左/右的概率是 p/1-p
这个程序应该怎么写?
2. 总觉得这种recursive的不如递推的好
3. 觉得那两行
probabilty(n - 1, x - 1, cnt, totalCnt);
probabilty(n - 1, x + 1, cnt, totalCnt);
不需要乘 0.5么
多谢

【在 l*****a 的大作中提到】
: 是不是这么一个simulation。如果是的话，单纯用统计能否得出同样的答案。
: void probabilty(int n,int x,unsigned long long& cnt, unsigned long long&
: totalCnt){
: if(n == 0){
: totalCnt++;
: if(x == 0){
: cnt++;
: }
: return;
: }
avatar
h*0
114 楼
牛人 !!
我只走到：
P[n][0] = 0 when n is odd
= 2 * P[n-1][1] when n is even
P[n][k] = P[n-1][k+1] + P[n-1][k-1] ( 0< k )
你一提醒 才想到
C(n, 0) + C(n, 1) + --- + C(n, n) = 2^n.
顺便多说几句思路， （ 被解惑乐， 解人惑乐 ）
-n, --------,-1, 0, 1, 2, ------n
n=0 1
n=1 1, 0, 1,
n=2 1, 0, 2, 0, 1, ( 注意 0 的左右是对称的)
n=3 0, 3, 0, 1
n=4 6, 0, 4, 0, 1
n=5 0,10, 0, 5, 0, 1
n=6 20,0,15, 0, 6, 0, 1
----
Define P[n][k] as the number that the robot is in k after n steps, total it'
s 2^n. so the possibility it's P[n][k]/2^n

【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
avatar
c*s
115 楼
Twitter的最后一题应该是估算吧：
cache的读写时间大概是几个时钟周期，也就是1ns左右。
RAM大概比cache慢一个量级，那读一个字节就是10ns左右，
假如数据所在页面的地址不在TLB里，那就要至少增加一次RAM的读写，时间可能就是几
十纳秒。
Disk的读写就是纯估算了，假设一个机械硬盘顺序读的速度100MB/s,
那么读一个字节的时间大概是 4096 / (100 * 10^6) s = 40 us (假设一个block是
4096字节，读操作是瓶颈).
如果磁头不在数据所在的磁道上，那还需要加上一个磁头移动时间。
200GB的文件应该是问文件头是怎么存的，如果是类Unix的i-node文件系统（假设一个
block是4096字节），
应该是一个block里有一个数组，数组的前面几个值保存文件信息和指向文件头几个
block （~10 * 4KB = 40 KB）。
后面3个值，一个指向一个block，这个block保存接下来文件数据存的地址。(512 * 4
KB = 2 MB)
倒数第二个值指向另一个block，这个block指向另一堆block (512 * 2 MB = 1 GB)
最后一个是3重block 指针 (512 * 1 GB = 512 GB)。
最后的block size和block地址的长度可能会有变化，计算中地址长度是8B。

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
c*s
116 楼
这个有公式吧：
if n = odd, P = 0;
else P = n!/(n/2)!/(n/2)!/2^n;

【在 h********0 的大作中提到】
: 牛人 !!
: 我只走到：
: P[n][0] = 0 when n is odd
: = 2 * P[n-1][1] when n is even
: P[n][k] = P[n-1][k+1] + P[n-1][k-1] ( 0< k )
: 你一提醒 才想到
: C(n, 0) + C(n, 1) + --- + C(n, n) = 2^n.
: 顺便多说几句思路， （ 被解惑乐， 解人惑乐 ）
: -n, --------,-1, 0, 1, 2, ------n
: n=0 1
avatar
c*s
117 楼
估计是以1秒为单位，如果在这一秒内已经接受10个请求了，就不再接受请求？

【在 A****e 的大作中提到】
: 同困惑，怎么从平均速度的角度考虑啊?
: 因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
: 这是充分条件，不是必要条件。
: 所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
: 等高人出来指点。
avatar
S*0
118 楼

这题太过分了！

【在 c***s 的大作中提到】
: Twitter的最后一题应该是估算吧：
: cache的读写时间大概是几个时钟周期，也就是1ns左右。
: RAM大概比cache慢一个量级，那读一个字节就是10ns左右，
: 假如数据所在页面的地址不在TLB里，那就要至少增加一次RAM的读写，时间可能就是几
: 十纳秒。
: Disk的读写就是纯估算了，假设一个机械硬盘顺序读的速度100MB/s,
: 那么读一个字节的时间大概是 4096 / (100 * 10^6) s = 40 us (假设一个block是
: 4096字节，读操作是瓶颈).
: 如果磁头不在数据所在的磁道上，那还需要加上一个磁头移动时间。
: 200GB的文件应该是问文件头是怎么存的，如果是类Unix的i-node文件系统（假设一个
avatar
c*s
119 楼
这题就是纯操作系统的题。
存文件的题目我们当年期末考试的时候还考过。
不过考试中是给定了block的大小和地址长度的。

【在 S******0 的大作中提到】
:
: 这题太过分了！
avatar
w*p
120 楼
看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说bug free
电面第一题，看了下答案。思路上和我想的差不多。find O(1) 只有hash了， insert,
getRandom, 要用array
delete O(2) 在array 里可以。
不过当时电话里写这题的code，真的头大。
楼主遇到的题都是貌似不难，下手不易的题。
谢谢楼主分享。再接再厉，拿到好的offer.

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
e*s
121 楼
如何判断一棵树是BST
这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
avatar
c*s
122 楼
那你就long类型，^_^

【在 e***s 的大作中提到】
: 如何判断一棵树是BST
: 这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
avatar
e*s
123 楼
楼主，请问这个G第五轮怎么答靠谱啊？
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以
avatar
r*n
124 楼

you can still use counting method to come up with a closed-form formula
if we have to write program, we can do the following. assume p is rational,
i.e. p = n/m for some integer n and m. use dfs, in each recursion call dfs n
times for the left turn and m-n times for the right turn. in the end, count
# of dfs reaching 0 and all # of dfs, and divide
if p is irrational, we can approximate p using a rational number with
arbitrary precision.

【在 p*g 的大作中提到】
: 1.如果往左/右的概率是 p/1-p
: 这个程序应该怎么写?
: 2. 总觉得这种recursive的不如递推的好
: 3. 觉得那两行
: probabilty(n - 1, x - 1, cnt, totalCnt);
: probabilty(n - 1, x + 1, cnt, totalCnt);
: 不需要乘 0.5么
: 多谢
avatar
h*p
125 楼
mark
avatar
H*r
126 楼
第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
这题你咋答的？

★ 发自iPhone App: ChineseWeb 7.8

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
k*8
127 楼
赞
avatar
s*s
128 楼
牛人谈谈是如何准备的吧。
avatar
s*x
129 楼
mark
avatar
h*p
130 楼
mark
avatar
H*r
131 楼
第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
这题你咋答的？

★ 发自iPhone App: ChineseWeb 7.8

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
k*8
132 楼
赞
avatar
s*s
133 楼
牛人谈谈是如何准备的吧。
avatar
s*x
134 楼
mark
avatar
y*3
135 楼
同问。。

【在 H****r 的大作中提到】
: 第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
: 果数组很长，如何优化.
: 这题你咋答的？
:
: ★ 发自iPhone App: ChineseWeb 7.8
avatar
c*e
136 楼
pat pat
avatar
l*n
137 楼
你们这是在挖坟啊，呵呵。这题应该是没办法从算法上改善了，因为无论如何每个袁术
好歹都得看一遍吧，所以优化的方法只有多核了，切成几块每块单独处理，然后考虑相
邻块的头尾看是不是要做merge。

【在 y*****3 的大作中提到】
: 同问。。
avatar
A*c
138 楼
三国饭你好

【在 l*n 的大作中提到】
: 你们这是在挖坟啊，呵呵。这题应该是没办法从算法上改善了，因为无论如何每个袁术
: 好歹都得看一遍吧，所以优化的方法只有多核了，切成几块每块单独处理，然后考虑相
: 邻块的头尾看是不是要做merge。
avatar
A*c
139 楼
blees楼主.
安慰lz的同时提点建议，第六轮问的问题不奇怪，这些确实是比较重要的知识。
即使不知道它们的绝对速度也需要了解一下它们之间的相对速度。
具体参见how to learn programming in ten years.

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
p*e
140 楼
请问这道题怎么做？“如何实现find, insert, delete, getRandom 都是O(1)”
avatar
c*p
141 楼
mark
avatar
s*i
142 楼
G的
第五轮。
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以。
怎么做？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
m*n
143 楼
今天还和一个朋友谈到Google伙食如何不好。。。
请问什么是爬梯子？

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
avatar
E*g
144 楼
mark

【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
相关阅读
去年6月的体检表今年7月还可以用吗H4 EAD申请表的一问题请教奥本的数据显然有问题Perm 今天批了我上个月21号收到了485纸质收据，为什么没有收到手机短信和Email呢？这正常吗？本版在线记录是07年创下的么?记得以前有个历次VB Post日期和VB前进的统计，谁能搜得到这个帖子？明日君再来！降级看的是RD还是APPROVAL DATE?2012.1 TSC有绿的吗? 看到很多NSC比这个时间晚的都绿了!神经病的USCIS半夜12点半更新我去年的AP/EAD申请状态发包子盼绿太惨了7月VB什么时候出？TSC SR 回复485交了，等待中，大家来谈谈生物博后拿卡后能做什么工作吧包子求问副申请人485被拒之后，之前自己的140还有效吗==分享==发包子的利器--包子机Perm certified
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。