G電面大家參詳一下怎麼個狀況 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G電面大家參詳一下怎麼個狀況

G電面大家參詳一下怎麼個狀況# JobHunting - 待字闺中

b*a2012-05-21 07:05

1 楼

一個疑似老印，兩個題
有一個map的interface，要實現get, put, remove, getRandom
可以用任何語言我用的java 然後可以用任何java api
我就直接用了一個hashmap
remove那個我說return是要boolean還是object 他說up to you，我就隨便搞了個
boolean
如果hashset.remove(k)是null，就return false 結果他指出來如果那個k對於的value
本來就是null怎麼辦我剛說that could be a problem 他就說that's fine 沒讓我接
著改
第二個有n台機器第一台有一個大文件size f，寫pseudo code怎麼transmit到所有機
器上然後問了時間複雜度
剩下就問問現在的工作喜歡做什麼樣的工作
感覺也沒問什麽算法尤其第一個不知道考點在哪
大家能給分析下不

y*u2012-05-21 07:05

2 楼

第一题不对。。。
第一题我onsite也碰到了，应该用hashmap+array

value

【在 b**a 的大作中提到】

: 一個疑似老印，兩個題
: 有一個map的interface，要實現get, put, remove, getRandom
: 可以用任何語言我用的java 然後可以用任何java api
: 我就直接用了一個hashmap
: remove那個我說return是要boolean還是object 他說up to you，我就隨便搞了個
: boolean
: 如果hashset.remove(k)是null，就return false 結果他指出來如果那個k對於的value
: 本來就是null怎麼辦我剛說that could be a problem 他就說that's fine 沒讓我接
: 著改
: 第二個有n台機器第一台有一個大文件size f，寫pseudo code怎麼transmit到所有機

w*x2012-05-21 07:05

3 楼

台湾人也上mitbbs???

d*u2012-05-21 07:05

4 楼

google电面答2题的有人拿过offer么？

v*a2012-05-21 07:05

5 楼

截止目前为止，版上有人给出过第二题答案么

d*u2012-05-21 07:05

6 楼

bittorrent原理

【在 v***a 的大作中提到】

: 截止目前为止，版上有人给出过第二题答案么

t*h2012-05-21 07:05

7 楼

膜拜面g的牛人

一個疑似老印，兩個題有一個map的interface，要實現get, put, remove, getRandom
可以用任何語言我用的java 然後可以用任何java api........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56

【在 b**a 的大作中提到】

w*x2012-05-21 07:05

8 楼

第一题我一开始想是不是不能用现有的structure要自己用c语言实现一个map, 那样的
话就来不及了. 额外array的话是不是用一个vector存储所有的key,但是删除的时候key
对应的value里包括这个key在array里的index, 然后用array里最后一个元素替换这个
index, 然后再更新替换过去的key在map里对应value的index, 再把vector size减一

w*x2012-05-21 07:05

9 楼

第二题是不是作stream line, 就是维护一个queue, 一个recv buffer, 一个send
buffer, queue加锁,

d*u2012-05-21 07:05

10 楼

map要用树结构。stl的map就是红黑树。如果我是面试的，只要你提到红黑树，这题就
让你过了，毕竟是第一轮电面。

key

【在 w****x 的大作中提到】

: 第一题我一开始想是不是不能用现有的structure要自己用c语言实现一个map, 那样的
: 话就来不及了. 额外array的话是不是用一个vector存储所有的key,但是删除的时候key
: 对应的value里包括这个key在array里的index, 然后用array里最后一个元素替换这个
: index, 然后再更新替换过去的key在map里对应value的index, 再把vector size减一

J*r2012-05-21 07:05

11 楼

知道是红黑树，未必知道实现细节，也许考查的就是怎么实现

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

: map要用树结构。stl的map就是红黑树。如果我是面试的，只要你提到红黑树，这题就
: 让你过了，毕竟是第一轮电面。
:
: key

b*a2012-05-21 07:05

12 楼

這樣啊當時也沒想到這麼多在getRandom的時候我是先getValues然後得到一個array
然後在生成一個隨機數不知道這樣行不行

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

: 第一题不对。。。
: 第一题我onsite也碰到了，应该用hashmap+array
:
: value

d*u2012-05-21 07:05

13 楼

可以问问细节，但要人家凭空implement红黑树，这也太难招人了。

【在 J*********r 的大作中提到】

: 知道是红黑树，未必知道实现细节，也许考查的就是怎么实现

b*a2012-05-21 07:05

14 楼

不是台灣人。。。就是不喜歡簡體字而已

【在 w****x 的大作中提到】

: 台湾人也上mitbbs???

y*u2012-05-21 07:05

15 楼

不能用tree结构，这题，呵呵
我也提了red-black tree，老中大妈一脸不高兴
你的繁体字看得真累。。。

array

【在 b**a 的大作中提到】

: 這樣啊當時也沒想到這麼多在getRandom的時候我是先getValues然後得到一個array
: 然後在生成一個隨機數不知道這樣行不行

b*a2012-05-21 07:05

16 楼

我一開始就說是用java 那也不是紅黑樹了呀

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

: map要用树结构。stl的map就是红黑树。如果我是面试的，只要你提到红黑树，这题就
: 让你过了，毕竟是第一轮电面。
:
: key

b*a2012-05-21 07:05

17 楼

能不能具體說說

【在 w****x 的大作中提到】

: 第二题是不是作stream line, 就是维护一个queue, 一个recv buffer, 一个send
: buffer, queue加锁,

y*u2012-05-21 07:05

18 楼

第二题也不难，p2p的东西就太复杂了
简单一点的chunk文件，先传metadata,然后相互穿，类似于broadcast...最后每个机器
自己重组

【在 b**a 的大作中提到】

: 能不能具體說說

d*x2012-05-21 07:05

19 楼

re..

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

: 可以问问细节，但要人家凭空implement红黑树，这也太难招人了。

w*x2012-05-21 07:05

20 楼

map太抽象了, 可以用RB-tree也可以用hash, 这题考在getRandom和其他操作都要O(1)

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

: map要用树结构。stl的map就是红黑树。如果我是面试的，只要你提到红黑树，这题就
: 让你过了，毕竟是第一轮电面。
:
: key

w*x2012-05-21 07:05

21 楼

因该不要求你知道领域知识, 有没有common一点的

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

: 第二题也不难，p2p的东西就太复杂了
: 简单一点的chunk文件，先传metadata,然后相互穿，类似于broadcast...最后每个机器
: 自己重组

y*u2012-05-21 07:05

22 楼

rb-tree我觉得不行
rb tree是linklist+bst的实现
而这个O(1), rb tree没法做到，最多log n...

题就

【在 w****x 的大作中提到】

:
: 因该不要求你知道领域知识, 有没有common一点的

w*x2012-05-21 07:05

23 楼

我觉得可以说两种解决方案:
1. 1号传给2号 --> 1号传3号, 同时2号传4号 ... 这样扩散
2. 1号传2号, 2号收到一部分没收完再传3号, 3号再4号, 都是同时进行的
限制就是网络带宽, 不过可以用switch来解决, 所以考虑带宽的话2是不是比较好

【在 b**a 的大作中提到】

: 能不能具體說說

v*a2012-05-21 07:05

24 楼

看来还没人给过正确的

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

: bittorrent原理

w*x2012-05-21 07:05

25 楼

我没说用rb-tree,
你看看我前面说的用vector和hash_map的实现行不行

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

: rb-tree我觉得不行
: rb tree是linklist+bst的实现
: 而这个O(1), rb tree没法做到，最多log n...
:
: 题就

w*x2012-05-21 07:05

26 楼

正确的是啥?

【在 v***a 的大作中提到】

: 看来还没人给过正确的

v*a2012-05-21 07:05

27 楼

这个不是公网传的，大型server center能用 p2p 么，
一台server一般有好几个张G级网卡连着呢，
核心的机器都是光纤直接连出去的, p2p chunk文件建立协议的的时间都可以传完这个
文件了

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

: 第二题也不难，p2p的东西就太复杂了
: 简单一点的chunk文件，先传metadata,然后相互穿，类似于broadcast...最后每个机器
: 自己重组

y*u2012-05-21 07:05

28 楼

只说n台机器啊
可能就和gfs那样的烂机器
如果server的话，nonblocking-call+bypass user buffer可以吗？比如
sendfile

机器

【在 v***a 的大作中提到】

: 这个不是公网传的，大型server center能用 p2p 么，
: 一台server一般有好几个张G级网卡连着呢，
: 核心的机器都是光纤直接连出去的, p2p chunk文件建立协议的的时间都可以传完这个
: 文件了

y*u2012-05-21 07:05

29 楼

我觉得可以。。。

【在 w****x 的大作中提到】

:
: 正确的是啥?

d*u2012-05-21 07:05

30 楼

这题我去yahoo被面过，也是一个印度人问的，我提到类似bittorrent概念之后他就让
我过了。

【在 v***a 的大作中提到】

z*e2012-05-21 07:05

31 楼

第一个你应该还需要写一个getRandom的实现方法
考点应该在keyset();还有values();还有random();这三个上
然后针对keyset这个collection，要toarray，然后要用math.randon()取出一个随机数
然后转换这个随机数到某个整数，然后再从toarry的结果list中给get出来

value

【在 b**a 的大作中提到】

c*p2012-05-21 07:05

32 楼

第二题是用gossip algorithm吧？

value

【在 b**a 的大作中提到】

l*a2012-05-21 07:05

33 楼

我认为让你过了不等于是正确答案
其实他也面了g,因为这道题悲剧
他也乡知道正确答案，旧作为面世题问了很多人
感觉你说的不错，估计下次他就拿你这个作为答案了

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

: 这题我去yahoo被面过，也是一个印度人问的，我提到类似bittorrent概念之后他就让
: 我过了。

p*22012-05-21 07:05

34 楼

toarray的复杂度多少？

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

: 第一个你应该还需要写一个getRandom的实现方法
: 考点应该在keyset();还有values();还有random();这三个上
: 然后针对keyset这个collection，要toarray，然后要用math.randon()取出一个随机数
: 然后转换这个随机数到某个整数，然后再从toarry的结果list中给get出来
:
: value

v*a2012-05-21 07:05

35 楼

就这知识面，+1分，如果bittorrent给1分的话，我感觉gossip protocol可以3分了，
满分10分的话
gossip protocol 也是p2p的一种，LogN复杂度很好了，但是它是针对未知网络结构的，
对于数据中心，拓扑结构非常固定，你再random gossip，那带宽的额外开销就太大了

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

: 第二题是用gossip algorithm吧？
:
: value

p*22012-05-21 07:05

36 楼

的，
膜拜我的偶像。

【在 v***a 的大作中提到】

: 就这知识面，+1分，如果bittorrent给1分的话，我感觉gossip protocol可以3分了，
: 满分10分的话
: gossip protocol 也是p2p的一种，LogN复杂度很好了，但是它是针对未知网络结构的，
: 对于数据中心，拓扑结构非常固定，你再random gossip，那带宽的额外开销就太大了

v*a2012-05-21 07:05

37 楼

啊？GFS的机器烂？那他们网卡什么级别的

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

: 只说n台机器啊
: 可能就和gfs那样的烂机器
: 如果server的话，nonblocking-call+bypass user buffer可以吗？比如
: sendfile
:
: 机器

w*x2012-05-21 07:05

38 楼

的，
Google考这玩艺不是考知识面, 是考传说中的思路

【在 v***a 的大作中提到】

y*u2012-05-21 07:05

39 楼

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 one
switch, and all 16 client machines to the other. The two
switches are connected with a 1 Gbps link.

【在 v***a 的大作中提到】

: 啊？GFS的机器烂？那他们网卡什么级别的

v*a2012-05-21 07:05

40 楼

，，，，，03年的paper

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

: 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

y*u2012-05-21 07:05

41 楼

连作者都说inexpensive server了。。。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 v***a 的大作中提到】

: ，，，，，03年的paper

r*g2012-05-21 07:05

42 楼

能详细说说这题的考点吗？俺老是往parallel computing里的cluster上想，比如N个机
器可以config成一个ring，也可以config成mesh，mesh有2D，又有3D的，然后根据文件
切割多少份，每份多大，计算transfer时间多少。。但是好像这不是考点吧。。

的，

【在 v***a 的大作中提到】