|
w****x
发帖数: 2483 | 2
我没说用rb-tree,
你看看我前面说的用vector和hash_map的实现行不行 |
|
|
v***a
发帖数: 365 | 4 这个不是公网传的，大型server center能用 p2p 么，
一台server一般有好几个张G级网卡连着呢，
核心的机器都是光纤直接连出去的, p2p chunk文件建立协议的的时间都可以传完这个
文件了 |
|
y**********u
发帖数: 6366 | 5 只说n台机器啊
可能就和gfs那样的烂机器
如果server的话，nonblocking-call+bypass user buffer可以吗？比如
sendfile
机器 |
|
|
d**u
发帖数: 1065 | 7 这题我去yahoo被面过，也是一个印度人问的，我提到类似bittorrent概念之后他就让
我过了。 |
|
z****e
发帖数: 54598 | 8 第一个你应该还需要写一个getRandom的实现方法
考点应该在keyset();还有values();还有random();这三个上
然后针对keyset这个collection，要toarray，然后要用math.randon()取出一个随机数
然后转换这个随机数到某个整数，然后再从toarry的结果list中给get出来
value |
|
c***p
发帖数: 221 | 9 第二题是用gossip algorithm吧？
value |
|
|
v***a
发帖数: 365 | 11 就这知识面，+1分，如果bittorrent给1分的话，我感觉gossip protocol可以3分了，
满分10分的话
gossip protocol 也是p2p的一种，LogN复杂度很好了，但是它是针对未知网络结构的，
对于数据中心，拓扑结构非常固定，你再random gossip，那带宽的额外开销就太大了 |
|
|
|
w****x
发帖数: 2483 | 14
的，
Google考这玩艺不是考知识面, 是考传说中的思路 |
|
y**********u
发帖数: 6366 | 15 GFS
6.1 Micro-benchmarks
We measured performance on a GFS cluster consisting
of one master, two master replicas, 16 chunkservers, and
16 clients. Note that this con guration was set up for ease
of testing. Typical clusters have hundreds of chunkservers
and hundreds of clients.
All the machines are con gured with dual 1.4 GHz PIII
processors, 2 GB of memory, two 80 GB 5400 rpm disks, and
a 100 Mbps full-duplex Ethernet connection to an HP 2524
switch. All 19 GFS server machines are connected to... 阅读全帖 |
|
|
y**********u
发帖数: 6366 | 17 连作者都说inexpensive server了。。。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
r********g
发帖数: 1351 | 18 能详细说说这题的考点吗？俺老是往parallel computing里的cluster上想，比如N个机
器可以config成一个ring，也可以config成mesh，mesh有2D，又有3D的，然后根据文件
切割多少份，每份多大，计算transfer时间多少。。但是好像这不是考点吧。。
的， |
|
|
j*****y
发帖数: 1071 | 20 这个 power of 3 怎么搞阿， 3进制？ |
|
d**********x
发帖数: 4083 | 21 如果是小数据类型的话，直接查表
如果是大整数的话，先计算
3^(2^n), 3^(2^(n-1)), ..., 然后试乘吧。
从大到小，每个数参与一次试乘，就能把指数的2进制形式试出来
也许有更好的办法，我这个是瞎蒙的 |
|
h*****7
发帖数: 60 | 22 沾人品 乱写一个3的幂睡觉。。
bool pow3(int a)
{
a = abs(a);
if (a==0) return false;
if (a==1) return true;
while (a == sqrt(a)*sqrt(a))
{
a = sqrt(a);
}
return (a%3 == 0) ? pow3(a/3) : false;
}
或者范围小就建表binary search |
|
|
|
|
|
|
|
|
|
|
s********k
发帖数: 6180 | 32 没有时间复杂度限制，很简单
bool pow3(int x){
while(x%3==0) x /=3;
return x==1;
} |
|
|
s********k
发帖数: 6180 | 34 那G家需要啥风格啊？你要说时间复杂度可以更好，那可以优化，但是如果没有这个要
求，简单风格难道不好？ |
|
|
|
|
s********k
发帖数: 6180 | 38 that's right.没考虑这个corner case |
|
d**********x
发帖数: 4083 | 39 看错了
这题目如果是32位int，没有任何好考的
因为32位int里面的3的n次幂不会超过32个
直接查表比什么都快。 |
|
|
|
g***j
发帖数: 1275 | 42 如果是相除的话，也最多除32次啊
那么查表的时间复杂度是多少？挨个比也需要时间吧？
看错了这题目如果是32位int，没有任何好考的因为32位int里面的3的n次幂不会超过32
个直接查表比什么都快。 |
|
s********k
发帖数: 6180 | 43 按照google的习惯，这个就是O(1)和O(N)的区别了。
32 |
|
|
|
d**********x
发帖数: 4083 | 46 查表可以2分
挨个比过去就败了
而且就像我一开始的反应。。。我觉得他可能问的是大整数
32 |
|
|
l*****a
发帖数: 559 | 48 第一题的“Find their order as well.”是什么意思？ |
|
o********4
发帖数: 45 | 49 就是那個是第1個duplicate, 那個是第2個duplicate,
比方說11455, 1是第1個, 5是第2個. |
|
|
