《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4928|回复: 26
收起左侧

Google 电面

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

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

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

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

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


1st Question:
Given a content of a book, get the most freq word in the content
. visit 1point3acres.com for more.

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

    . From 1point 3acres bbs

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.1point3acres缃
请问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吗? 有什么更好的方法?
第二题 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? 楼主用的什么方 ...

第一题,典型的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. 鍥磋鎴戜滑@1point 3 acres
第一题,典型的map reduce

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

使用道具 举报

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

或者tf idf
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-7-29 01:33:26 | 显示全部楼层
Ivor761 发表于 2015-7-25 06:53. 1point 3acres 璁哄潧
第一题,典型的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? 是不是遍历这个链表就行了?

会有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
这个题有人有思路嘛?. visit 1point3acres.com for more.
貌似是一个很经典的略难的题目。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我觉得只求最大的一个的话,用trie肯定就解出来了,就是在建立完trie的时候就解出来了。
如果求top K 呢?  是不是需要trie和min-heap搭配起来做?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-29 07:57:48 | 显示全部楼层
第二题是一个树吧。不过每树结点记录自己的father就行了。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
看是不是在一个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.鏈枃鍘熷垱鑷1point3acres璁哄潧
觉得第二题因该不能只用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 | 显示全部楼层
请问楼主,电话面试是纯电话沟通吗?还是有视频或者在某个网站上出的题目?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 03:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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