g*******r
发帖数: 44 | 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次电话面试都因为面试官救火而重新安排的.
但愿这些能给后来的兄弟一些帮助啦。 |
j*****s
发帖数: 189 | 2 嗯，很详细啊，lz能记得这么多真不容易。希望楼主好运。 |
s*****2
发帖数: 68 | |
l*****a
发帖数: 14598 | 4 先顶后看
扫了一下，感觉写的有点粗
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
c********s
发帖数: 817 | |
g*******r
发帖数: 44 | |
g***j
发帖数: 1275 | 7 请问这三题怎么做的？
第三轮，扯点工作经验，然后考了从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的一道题。
|
g***j
发帖数: 1275 | 8 没事，失败是成功之母
【在 g*******r 的大作中提到】
: 谢谢各位兄弟啊，可惜2个都杯具了
|
g*******r
发帖数: 44 | 9 那题我递归中数组索引写的有问题，当时真不在状态，他一提示我还没发现。
环的那个空间没要求，用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没有要求，直接扫描就可以吧？
|
b***e
发帖数: 383 | |
|
|
A*****t
发帖数: 275 | 11 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
司面一遍总有一个碰上的。
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
j******2
发帖数: 362 | 12
什么东西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的一道题。
|
w****x
发帖数: 2483 | |
j******2
发帖数: 362 | 14 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的一道题。
|
g*******r
发帖数: 44 | 15 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
【在 A*****t 的大作中提到】
: 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
: 司面一遍总有一个碰上的。
|
g*******r
发帖数: 44 | 16 http://www.sureinterview.com/shwqst/1019005
这里有介绍.
【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
|
g*******r
发帖数: 44 | 17 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
错误，没绕过来。
吗？
【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
|
j******2
发帖数: 362 | 18 谢谢！！
真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
【在 g*******r 的大作中提到】
: http://www.sureinterview.com/shwqst/1019005
: 这里有介绍.
|
B*******1
发帖数: 2454 | 19 楼主多少年工作经验了啊？
【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
|
g*******r
发帖数: 44 | 20 加油。我面试一个感觉是国人都很好，都找的很好的题问的。twitter电话面试时一个
哥们还心照不宣地问我这题是不是见过，呵呵。
印度哥们就很坏，读写锁那个那哥们见我有错的就拍照。。
【在 j******2 的大作中提到】
: 谢谢！！
: 真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
|
|
|
g*******r
发帖数: 44 | 21 1年多一点
【在 B*******1 的大作中提到】
: 楼主多少年工作经验了啊？
|
j******2
发帖数: 362 | 22 我觉得所谓“常规题”的范围在扩大！而且扩大速度超过我的复习速度！ |
A*****t
发帖数: 275 | 23 你在哪家工作？我也骑驴找马，目前Google过了hire committee
【在 g*******r 的大作中提到】
: 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
|
A****e
发帖数: 310 | 24 谢谢lz分享啊～
我觉得特别累的情况下马上面一天确实很辛苦。但是G的那个印度人，挺坏的。。。还
拍照，雷。。。
T家的第6论，完全不懂。。。 |
k****r
发帖数: 807 | |
h*******e
发帖数: 1377 | 26 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~ |
o***d
发帖数: 313 | 27 客户端那题莫非是问这个?
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的一道题。
|
p*****2
发帖数: 21240 | 28 d鈥唂鈥唖
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
p*****2
发帖数: 21240 | 29 dfs
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
s********k
发帖数: 6180 | 30 读写锁要求是什么？是不是很多读比较少写，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. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
|
|
|
A****e
发帖数: 310 | 31 请大牛明示！
【在 p*****2 的大作中提到】
: dfs
|
g*******r
发帖数: 44 | 32 我确实是搞系统开发的，不过这面试是答得惨啊.
【在 h*******e 的大作中提到】
: 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
|
g*******r
发帖数: 44 | 33 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
度方面想，我现在都不明白啊.
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
g*******r
发帖数: 44 | 34 http://stackoverflow.com/questions/8635963/read-write-lock-impl
这个答案应该是老印想要的.
【在 s********k 的大作中提到】
: 读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
: 都被block?
: 按照qt的reference，写了一个
: class ReadWriteMutex
: {
: public:
: ReadWriteMutex(int maxReaders = 32)
: : semaphore(maxReaders)
: {
: }
|
p*****2
发帖数: 21240 | 35
计算两个number
一共有多少种可能性，其中有多少是回到远点，其实就是brute force
【在 A****e 的大作中提到】
: 请大牛明示！
|
g*******r
发帖数: 44 | 36 对，就是2爷说的这个意思.
【在 p*****2 的大作中提到】
:
: 计算两个number
: 一共有多少种可能性，其中有多少是回到远点，其实就是brute force
|
l*****a
发帖数: 559 | 37 是不是这么一个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<<(double)cnt / (double)totalCnt<
【在 g*******r 的大作中提到】
: 对，就是2爷说的这个意思.
|
q******8
发帖数: 848 | |
g*******r
发帖数: 44 | 39 就是这样的程序啊。老中面试官人好，没有让我用数学方法求结果.
【在 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;
: }
|
p******o
发帖数: 125 | 40 索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这题怎么做啊？ |
|
|
o***d
发帖数: 313 | 41 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;
: }
|
f********4
发帖数: 988 | 42 对于悲剧实在是习惯就好，而且很快就发现一扇门关了另一扇窗就开了，相信自己最重
要。时间问题 |
A****e
发帖数: 310 | 43 二爷你说的是机器人那道题啊～
我还以为你说的是客户端请求每秒钟只发送10个的那个呢
请问那个客户端的怎么做呀？
是像27楼说的那样用timer call back func吗？
【在 p*****2 的大作中提到】
: dfs
|
A****e
发帖数: 310 | 44 同困惑，怎么从平均速度的角度考虑啊?
因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
这是充分条件，不是必要条件。
所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
等高人出来指点。
【在 g*******r 的大作中提到】
: 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
: 度方面想，我现在都不明白啊.
|
A****e
发帖数: 310 | 45 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
你的简历上有表现出有多线程相关的经验吗？
还是被老印黑了？
还是大家都觉得这个属于常规题？。。。
【在 g*******r 的大作中提到】
: http://stackoverflow.com/questions/8635963/read-write-lock-impl
: 这个答案应该是老印想要的.
|
t********e
发帖数: 1169 | 46 楼主大牛拉， 电面都能聊上spanner了肯定level不低 |
g*******r
发帖数: 44 | 47 这个我在简历中提到多线程了，我平时工作中用到多线程了。读写锁的实现你要是看过
就还好了，没看过的话有点弯弯的，我那天写起来总是有问题。
【在 A****e 的大作中提到】
: 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
: 你的简历上有表现出有多线程相关的经验吗？
: 还是被老印黑了？
: 还是大家都觉得这个属于常规题？。。。
|
w****x
发帖数: 2483 | 48 机器人算概率那题， 不久是左移和右移的number要相等吗？
不就是一道概率题吗：
N is odd => 0
N is even => (1/2)^N * C(N) (N/2) |
l*****a
发帖数: 14598 | 49 题中没说要相等
【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
|
p*g
发帖数: 141 | 50 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;
: }
|
|
|
h********0
发帖数: 74 | 51 牛人 !!
我只走到：
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)
|
c***s
发帖数: 192 | 52 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的一道题。
|
c***s
发帖数: 192 | 53 这个有公式吧：
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
|
c***s
发帖数: 192 | 54 估计是以1秒为单位，如果在这一秒内已经接受10个请求了，就不再接受请求？
【在 A****e 的大作中提到】
: 同困惑，怎么从平均速度的角度考虑啊?
: 因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
: 这是充分条件，不是必要条件。
: 所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
: 等高人出来指点。
|
S******0
发帖数: 71 | 55
这题太过分了！
【在 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文件系统（假设一个
|
c***s
发帖数: 192 | 56 这题就是纯操作系统的题。
存文件的题目我们当年期末考试的时候还考过。
不过考试中是给定了block的大小和地址长度的。
【在 S******0 的大作中提到】
:
: 这题太过分了！
|
w********p
发帖数: 948 | 57 看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说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的一道题。
|
e***s
发帖数: 799 | 58 如何判断一棵树是BST
这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX |
c***s
发帖数: 192 | 59 那你就long类型，^_^
【在 e***s 的大作中提到】
: 如何判断一棵树是BST
: 这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
|
e***s
发帖数: 799 | 60 楼主，请问这个G第五轮怎么答靠谱啊？
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以 |
|
|
r*********n
发帖数: 4553 | 61
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么
: 多谢
|
g*******r
发帖数: 44 | 62 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次电话面试都因为面试官救火而重新安排的.
但愿这些能给后来的兄弟一些帮助啦。 |
j*****s
发帖数: 189 | 63 嗯，很详细啊，lz能记得这么多真不容易。希望楼主好运。 |
s*****2
发帖数: 68 | |
l*****a
发帖数: 14598 | 65 先顶后看
扫了一下，感觉写的有点粗
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
c********s
发帖数: 817 | |
g*******r
发帖数: 44 | |
g***j
发帖数: 1275 | 68 请问这三题怎么做的？
第三轮，扯点工作经验，然后考了从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的一道题。
|
g***j
发帖数: 1275 | 69 没事，失败是成功之母
【在 g*******r 的大作中提到】
: 谢谢各位兄弟啊，可惜2个都杯具了
|
g*******r
发帖数: 44 | 70 那题我递归中数组索引写的有问题，当时真不在状态，他一提示我还没发现。
环的那个空间没要求，用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没有要求，直接扫描就可以吧？
|
|
|
b***e
发帖数: 383 | |
A*****t
发帖数: 275 | 72 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
司面一遍总有一个碰上的。
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
j******2
发帖数: 362 | 73
什么东西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的一道题。
|
w****x
发帖数: 2483 | |
j******2
发帖数: 362 | 75 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的一道题。
|
g*******r
发帖数: 44 | 76 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
【在 A*****t 的大作中提到】
: 挺好的，小公司练手对大公司帮助不大，以你现在的水平估计就是看运气，那几家大公
: 司面一遍总有一个碰上的。
|
g*******r
发帖数: 44 | 77 http://www.sureinterview.com/shwqst/1019005
这里有介绍.
【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
|
g*******r
发帖数: 44 | 78 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
错误，没绕过来。
吗？
【在 j******2 的大作中提到】
: google onsite 的1和2都完全没有clue阿。是什么组阿？这个mutex是很常规的东东吗？
|
j******2
发帖数: 362 | 79 谢谢！！
真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
【在 g*******r 的大作中提到】
: http://www.sureinterview.com/shwqst/1019005
: 这里有介绍.
|
B*******1
发帖数: 2454 | 80 楼主多少年工作经验了啊？
【在 g*******r 的大作中提到】
: 组是Ads 和 Search. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
|
|
|
g*******r
发帖数: 44 | 81 加油。我面试一个感觉是国人都很好，都找的很好的题问的。twitter电话面试时一个
哥们还心照不宣地问我这题是不是见过，呵呵。
印度哥们就很坏，读写锁那个那哥们见我有错的就拍照。。
【在 j******2 的大作中提到】
: 谢谢！！
: 真不知道什么时候才能把题都看完记住！而且还能看上去不象看过的！！
|
g*******r
发帖数: 44 | 82 1年多一点
【在 B*******1 的大作中提到】
: 楼主多少年工作经验了啊？
|
j******2
发帖数: 362 | 83 我觉得所谓“常规题”的范围在扩大！而且扩大速度超过我的复习速度！ |
A*****t
发帖数: 275 | 84 你在哪家工作？我也骑驴找马，目前Google过了hire committee
【在 g*******r 的大作中提到】
: 呵呵，骑驴找马出去面试不容易啊，下次面试估计得2个月以后了。
|
A****e
发帖数: 310 | 85 谢谢lz分享啊～
我觉得特别累的情况下马上面一天确实很辛苦。但是G的那个印度人，挺坏的。。。还
拍照，雷。。。
T家的第6论，完全不懂。。。 |
k****r
发帖数: 807 | |
h*******e
发帖数: 1377 | 87 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~ |
o***d
发帖数: 313 | 88 客户端那题莫非是问这个?
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的一道题。
|
p*****2
发帖数: 21240 | 89 d鈥唂鈥唖
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
p*****2
发帖数: 21240 | 90 dfs
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
|
|
s********k
发帖数: 6180 | 91 读写锁要求是什么？是不是很多读比较少写，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. 这个读写锁的实现我面试前本来想看的，结果没看。然后就有些
: 错误，没绕过来。
:
: 吗？
|
A****e
发帖数: 310 | 92 请大牛明示！
【在 p*****2 的大作中提到】
: dfs
|
g*******r
发帖数: 44 | 93 我确实是搞系统开发的，不过这面试是答得惨啊.
【在 h*******e 的大作中提到】
: 好码工,你是做什么的阿:) 问你系统方面的题似乎明显感觉比较多~~~
|
g*******r
发帖数: 44 | 94 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
度方面想，我现在都不明白啊.
【在 o***d 的大作中提到】
: 客户端那题莫非是问这个?
: http://www.mitbbs.com/article_t/JobHunting/32061423.html
: 机器人那题答案是?我觉得完全是概率题阿,用递归怎么算?
: 比如: 第一步,往左或者右,50%,第二步,同样,那么两步后,回到原点概率50%...
: 我上两次面试都是半夜1点钟到hotel,呵呵
|
g*******r
发帖数: 44 | 95 http://stackoverflow.com/questions/8635963/read-write-lock-impl
这个答案应该是老印想要的.
【在 s********k 的大作中提到】
: 读写锁要求是什么？是不是很多读比较少写，read可以同时进行？但是写的时候所有读
: 都被block?
: 按照qt的reference，写了一个
: class ReadWriteMutex
: {
: public:
: ReadWriteMutex(int maxReaders = 32)
: : semaphore(maxReaders)
: {
: }
|
p*****2
发帖数: 21240 | 96
计算两个number
一共有多少种可能性，其中有多少是回到远点，其实就是brute force
【在 A****e 的大作中提到】
: 请大牛明示！
|
g*******r
发帖数: 44 | 97 对，就是2爷说的这个意思.
【在 p*****2 的大作中提到】
:
: 计算两个number
: 一共有多少种可能性，其中有多少是回到远点，其实就是brute force
|
l*****a
发帖数: 559 | 98 是不是这么一个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<<(double)cnt / (double)totalCnt<
【在 g*******r 的大作中提到】
: 对，就是2爷说的这个意思.
|
q******8
发帖数: 848 | |
g*******r
发帖数: 44 | 100 就是这样的程序啊。老中面试官人好，没有让我用数学方法求结果.
【在 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;
: }
|
|
|
p******o
发帖数: 125 | 101 索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这题怎么做啊？ |
o***d
发帖数: 313 | 102 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;
: }
|
f********4
发帖数: 988 | 103 对于悲剧实在是习惯就好，而且很快就发现一扇门关了另一扇窗就开了，相信自己最重
要。时间问题 |
A****e
发帖数: 310 | 104 二爷你说的是机器人那道题啊～
我还以为你说的是客户端请求每秒钟只发送10个的那个呢
请问那个客户端的怎么做呀？
是像27楼说的那样用timer call back func吗？
【在 p*****2 的大作中提到】
: dfs
|
A****e
发帖数: 310 | 105 同困惑，怎么从平均速度的角度考虑啊?
因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
这是充分条件，不是必要条件。
所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
等高人出来指点。
【在 g*******r 的大作中提到】
: 我去面试前见过链接上这题，答的时候也往这边靠，但面试官说不对，偏要我向平均速
: 度方面想，我现在都不明白啊.
|
A****e
发帖数: 310 | 106 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
你的简历上有表现出有多线程相关的经验吗？
还是被老印黑了？
还是大家都觉得这个属于常规题？。。。
【在 g*******r 的大作中提到】
: http://stackoverflow.com/questions/8635963/read-write-lock-impl
: 这个答案应该是老印想要的.
|
t********e
发帖数: 1169 | 107 楼主大牛拉， 电面都能聊上spanner了肯定level不低 |
g*******r
发帖数: 44 | 108 这个我在简历中提到多线程了，我平时工作中用到多线程了。读写锁的实现你要是看过
就还好了，没看过的话有点弯弯的，我那天写起来总是有问题。
【在 A****e 的大作中提到】
: 读写锁这个好难啊，完全不懂多线程的表示一头雾水。。。
: 你的简历上有表现出有多线程相关的经验吗？
: 还是被老印黑了？
: 还是大家都觉得这个属于常规题？。。。
|
w****x
发帖数: 2483 | 109 机器人算概率那题， 不久是左移和右移的number要相等吗？
不就是一道概率题吗：
N is odd => 0
N is even => (1/2)^N * C(N) (N/2) |
l*****a
发帖数: 14598 | 110 题中没说要相等
【在 w****x 的大作中提到】
: 机器人算概率那题， 不久是左移和右移的number要相等吗？
: 不就是一道概率题吗：
: N is odd => 0
: N is even => (1/2)^N * C(N) (N/2)
|
|
|
p*g
发帖数: 141 | 111 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;
: }
|
h********0
发帖数: 74 | 112 牛人 !!
我只走到：
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)
|
c***s
发帖数: 192 | 113 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的一道题。
|
c***s
发帖数: 192 | 114 这个有公式吧：
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
|
c***s
发帖数: 192 | 115 估计是以1秒为单位，如果在这一秒内已经接受10个请求了，就不再接受请求？
【在 A****e 的大作中提到】
: 同困惑，怎么从平均速度的角度考虑啊?
: 因为如果大于0.1秒就扔掉，这样一定可以保证任何一秒钟内的请求都不会大于10个。
: 这是充分条件，不是必要条件。
: 所以，他是不是其实是想把问题简化，而我们因为想想出“正确解”，所以想复杂啦？
: 等高人出来指点。
|
S******0
发帖数: 71 | 116
这题太过分了！
【在 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文件系统（假设一个
|
c***s
发帖数: 192 | 117 这题就是纯操作系统的题。
存文件的题目我们当年期末考试的时候还考过。
不过考试中是给定了block的大小和地址长度的。
【在 S******0 的大作中提到】
:
: 这题太过分了！
|
w********p
发帖数: 948 | 118 看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说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的一道题。
|
e***s
发帖数: 799 | 119 如何判断一棵树是BST
这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX |
c***s
发帖数: 192 | 120 那你就long类型，^_^
【在 e***s 的大作中提到】
: 如何判断一棵树是BST
: 这个题如果做？如果最左边的node是INT_MIN或者最右边的node是INT_MAX
|
|
|
e***s
发帖数: 799 | 121 楼主，请问这个G第五轮怎么答靠谱啊？
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以 |
r*********n
发帖数: 4553 | 122
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么
: 多谢
|
h****p
发帖数: 87 | |
H****r
发帖数: 2801 | 124 第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
这题你咋答的？
★ 发自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的一道题。
|
k**8
发帖数: 186 | |
s*********s
发帖数: 318 | |
s**x
发帖数: 7506 | |
h****p
发帖数: 87 | |
H****r
发帖数: 2801 | 129 第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
果数组很长，如何优化.
这题你咋答的？
★ 发自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的一道题。
|
k**8
发帖数: 186 | |
|
|
s*********s
发帖数: 318 | |
s**x
发帖数: 7506 | |
y*****3
发帖数: 451 | 133 同问。。
【在 H****r 的大作中提到】
: 第一轮, 第一题，一个数组，求连续（每个元素挨着的）的最长递增子序列的长度，如
: 果数组很长，如何优化.
: 这题你咋答的？
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
c********e
发帖数: 186 | |
l*n
发帖数: 529 | 135 你们这是在挖坟啊，呵呵。这题应该是没办法从算法上改善了，因为无论如何每个袁术
好歹都得看一遍吧，所以优化的方法只有多核了，切成几块每块单独处理，然后考虑相
邻块的头尾看是不是要做merge。
【在 y*****3 的大作中提到】
: 同问。。
|
A*********c
发帖数: 430 | 136 三国饭你好
【在 l*n 的大作中提到】
: 你们这是在挖坟啊，呵呵。这题应该是没办法从算法上改善了，因为无论如何每个袁术
: 好歹都得看一遍吧，所以优化的方法只有多核了，切成几块每块单独处理，然后考虑相
: 邻块的头尾看是不是要做merge。
|
A*********c
发帖数: 430 | 137 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的一道题。
|
p*****e
发帖数: 537 | 138 请问这道题怎么做？“如何实现find, insert, delete, getRandom 都是O(1)” |
c********p
发帖数: 1969 | |
s*****i
发帖数: 32 | 140 G的
第五轮。
就讨论如何一个程序大多数情况下运行的好好的，有时有问题，可能的原因.
感觉答的还可以。
怎么做？
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
|
|
m******n
发帖数: 187 | 141 今天还和一个朋友谈到Google伙食如何不好。。。
请问什么是爬梯子？
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
E******g
发帖数: 204 | 142 mark
【在 g*******r 的大作中提到】
: google 店面
: 就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
: spanner那篇论文.
: twitter 店面
: 第一轮.
: 1.如何判断一棵树是BST.
: 2.用2个栈实现队列。
: 第二轮
: 1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
: 2. 关于图的简单BFS的一道题。
|
