一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2548|回复: 26
收起左侧

Google 电面

[复制链接] |试试Instant~ |关注本帖
LiloD 发表于 2015-7-24 04:08:41 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
因为之前一直不知道一亩三分地这个论坛,所以这个3月份电面的题大家就看看参考好了。
. more info on 1point3acres.com

1st Question:. 1point 3acres 璁哄潧
Given a content of a book, get the most freq word in the content


2st Question:
Given these operations:
[size=14.6666666666667px]Update triplets:
[size=14.6666666666667px]  <”set_manager”, “A”, “B”>: indicates that A is the direct manager of B
[size=14.6666666666667px]  <“set_peer”,”A”, “B”>: indicates that A and B have the same direct manager


[size=14.6666666666667px]  <”set_manager”, “A”, “B”>: indicates that A is the direct manager of B. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
[size=14.6666666666667px]Query triplet:
[size=14.6666666666667px]  <“query_manager”,”A”, “B”>: print true/false A is in the management chain of B



Design Data Structure which implements these operations.

评分

2

查看全部评分

Linzertorte 发表于 2015-8-6 01:05:12 | 显示全部楼层
lxia 发表于 2015-8-5 17:55
第二题不是union set?
set manager(A,B) p=A;

我觉得你想复杂 了。 并查集是一个 计算 rank 和 带有路径压缩优化的 树。
你这个路径压缩就只能找到根,无法知道两个人是不是在同一chain上了。
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2015-7-24 10:39:51 | 显示全部楼层
请问LZ 两个operation 是exclusive的吗? 如果set Manager(C,A) and set Manager(C,B). A,B 有共同的director, data structure 要自动完成吗 ?
回复 支持 反对

使用道具 举报

 楼主| LiloD 发表于 2015-7-24 22:57:41 | 显示全部楼层
say543 发表于 2015-7-24 10:39
请问LZ 两个operation 是exclusive的吗? 如果set Manager(C,A) and set Manager(C,B). A,B 有共同的directo ...

每一个人只会有一“direct” manager, 如果你先set_manager(C,A) 然后再 set_peer(A,B) 那么B的direct manager也应该是C
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-25 00:15:25 | 显示全部楼层
[size=14.6666666666667px] 是什意思?
回复 支持 反对

使用道具 举报

 楼主| LiloD 发表于 2015-7-25 00:19:34 | 显示全部楼层
hulahu 发表于 2015-7-25 00:15
[size=14.6666666666667px] 是什意思?

不好意思 我复制粘贴多出来的东西。。。。 =。=b 和题目无关。。。。
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-7-25 00:32:05 | 显示全部楼层
第一题 hashtable + 遍历hashtable吗? 有什么更好的方法?. from: 1point3acres.com/bbs
第二题 tree + hashtable? 楼主用的什么方法?
回复 支持 反对

使用道具 举报

dreamergao 发表于 2015-7-25 03:26:52 | 显示全部楼层
楼主,第二题怎么定义在management chain?
回复 支持 反对

使用道具 举报

Ivor761 发表于 2015-7-25 06:53:29 | 显示全部楼层
hyliu0000 发表于 2015-7-25 00:32
第一题 hashtable + 遍历hashtable吗? 有什么更好的方法?
第二题 tree + hashtable? 楼主用的什么方 ...

. 鍥磋鎴戜滑@1point 3 acres第一题,典型的map reduce
回复 支持 反对

使用道具 举报

 楼主| LiloD 发表于 2015-7-25 07:26:59 | 显示全部楼层
hyliu0000 发表于 2015-7-25 00:32. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题 hashtable + 遍历hashtable吗? 有什么更好的方法?
第二题 tree + hashtable? 楼主用的什么方 ...

我是用有向图做的 不过写的很辛苦 感觉不是最佳的解法
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-25 08:49:48 | 显示全部楼层
Ivor761 发表于 2015-7-25 06:53-google 1point3acres
第一题,典型的map reduce

第一题不是spark的默认example, word count么..
回复 支持 反对

使用道具 举报

readman 发表于 2015-7-25 08:50:26 | 显示全部楼层
Ivor761 发表于 2015-7-25 06:53
. 1point3acres.com/bbs第一题,典型的map reduce

或者tf idf
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-7-29 01:33:26 | 显示全部楼层
Ivor761 发表于 2015-7-25 06:53
第一题,典型的map reduce

如何mapreduce?
鏉ユ簮涓浜.涓夊垎鍦拌鍧. mapper:
puts word 1
reducer:
word count?.1point3acres缃

然后呢?
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-7-29 01:42:12 | 显示全部楼层
LiloD 发表于 2015-7-25 07:26. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我是用有向图做的 不过写的很辛苦 感觉不是最佳的解法

我看前面你说每个人只会有一个direct manager。 那是不是说其实这就是个链表? 相当于只有一个next pointer? 是不是遍历这个链表就行了?
. From 1point 3acres bbs
会有a -> b -> c->a这种情况吗?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-29 07:06:31 | 显示全部楼层
Given a content of a book, get the most freq word in the content
这个题有人有思路嘛?
貌似是一个很经典的略难的题目。
我觉得只求最大的一个的话,用trie肯定就解出来了,就是在建立完trie的时候就解出来了。-google 1point3acres
如果求top K 呢?  是不是需要trie和min-heap搭配起来做?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-29 07:57:48 | 显示全部楼层
第二题是一个树吧。不过每树结点记录自己的father就行了。-google 1point3acres
看是不是在一个chain里,一直往上看father就行了。
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-30 21:34:56 | 显示全部楼层
觉得第二题因该不能只用tree 每一个Node class 要记录manager  node 同时也要记住peer list 用来support set_manager 和set_peer operations 我会用hashSet<Node> 来record  欢迎讨论...
回复 支持 反对

使用道具 举报

 楼主| LiloD 发表于 2015-7-30 23:14:30 | 显示全部楼层
say543 发表于 2015-7-30 21:34
觉得第二题因该不能只用tree 每一个Node class 要记录manager  node 同时也要记住peer list 用来support se ...

我就是Node节点既有一个father指针 指向manager 又有一个set来维护peers
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-31 00:30:57 | 显示全部楼层
say543 发表于 2015-7-30 21:34
觉得第二题因该不能只用tree 每一个Node class 要记录manager  node 同时也要记住peer list 用来support se ...

manager就是father.set peer的时候,比如 set peer a,b  你只要找b.father = a.father就行了。
回复 支持 反对

使用道具 举报

paulchim 发表于 2015-7-31 00:55:16 | 显示全部楼层
请问楼主,电话面试是纯电话沟通吗?还是有视频或者在某个网站上出的题目?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 20:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表