一亩三分地论坛

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

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

Google 电面新题

[复制链接] |试试Instant~ |关注本帖
米奇要努力 发表于 2015-11-20 05:43:25 | 显示全部楼层 |阅读模式

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

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

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

x
11/19 新题:. From 1point 3acres bbs
interviewer先来聊了一会, 问了想做什么,back-end, front-end, balabalaa 问了一些general的兴趣问题,然后开始面试。

第一题: 给一个network of computers, each computer only see its neighbors and can send package to them. Design a protocol to tell hwo many computer are in the network.
第二题: square a very long number. For an example, the number 12 is represented in array  as [2,1], 12^2 = 144, the output should be [4,4,1]



本帖被以下淘专辑推荐:

plich 发表于 2015-11-21 22:05:40 | 显示全部楼层
yanguango 发表于 2015-11-21 03:13
用 DFS 怎么把后面的结果传到之前访问的路径中的节点去呢

方法和用DFS保存二叉树所有root to leaf path类似

比如1->2->3. 鍥磋鎴戜滑@1point 3 acres

void DFS(unordered_set<graphNode*> &visited,graphNode *currentNode);
从1 开始,把1 加到visited里面
然后1 有neighbour 2, 递归到2.
------把2加到visited里面. visit 1point3acres.com for more.
------2有neighbour 1和3,可是1在visted里面,所以递归到3
----------把3加入到visited里面. 1point3acres.com/bbs
----------3的所有neighbour都是visited,返回

这样visited里面会有三个节点. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

如果可以自己设计graphNode的话,用void DFS(int &result, graphNode *current,int requestID);就行了,这样的结构更接近一个网络协议
回复 支持 1 反对 0

使用道具 举报

farm 发表于 2015-11-20 05:49:07 | 显示全部楼层
第二题array里面存的数是倒过来的?
第一题每个电脑都要知道总数目in the network么?
回复 支持 反对

使用道具 举报

 楼主| 米奇要努力 发表于 2015-11-20 05:53:09 | 显示全部楼层
farm 发表于 2015-11-20 05:49
第二题array里面存的数是倒过来的?
第一题每个电脑都要知道总数目in the network么?

array里存的数是倒过来的 from low to high. 鍥磋鎴戜滑@1point 3 acres
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是实现一个protocol, 实现任何一台computer都可以知道网络中有多少computer。
回复 支持 反对

使用道具 举报

farm 发表于 2015-11-20 06:23:48 | 显示全部楼层
米奇要努力 发表于 2015-11-20 05:53
array里存的数是倒过来的 from low to high

就是实现一个protocol, 实现任何一台computer都可以知道 ...

噢,这样子,第一题怎么做的啊?
回复 支持 反对

使用道具 举报

with_god 发表于 2015-11-20 06:34:11 | 显示全部楼层
第一题 估计是个 BFS,  package 里面如下   变量  一个  global count 计算 目前 visited 的计算机总数,  一个 变量标志本计算机是否已经被访问过,  这样一个 BFS就可以计算所有的计算机了。  
回复 支持 反对

使用道具 举报

tinir 发表于 2015-11-20 06:58:16 | 显示全部楼层
第二题除了像multiply string那样有更快地解答嚒 谢谢!
回复 支持 反对

使用道具 举报

 楼主| 米奇要努力 发表于 2015-11-20 09:17:57 | 显示全部楼层
tinir 发表于 2015-11-20 06:58
第二题除了像multiply string那样有更快地解答嚒 谢谢!

第二题我的方法就是我们平时手算乘法的方式,abc*abc = ac bc cc + ab bb cb + aa ab ac 时间复杂度是O(n^2)
回复 支持 反对

使用道具 举报

 楼主| 米奇要努力 发表于 2015-11-20 09:19:29 | 显示全部楼层
farm 发表于 2015-11-20 06:23
噢,这样子,第一题怎么做的啊?

我觉得可能用set存node,DFS BFS 都可以。
回复 支持 反对

使用道具 举报

 楼主| 米奇要努力 发表于 2015-11-20 09:20:41 | 显示全部楼层
with_god 发表于 2015-11-20 06:34
第一题 估计是个 BFS,  package 里面如下   变量  一个  global count 计算 目前 visited 的计算机总数,  ...

我刚开始就说bfs 被打枪了  最后面试官说是dfs   
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-20 09:51:02 | 显示全部楼层
问一下第一题里面没有global变量吧?所有能存的数据都在package里?那一遍DFS应该是找不到总数的吧(遍历完了以后每一个电脑也不知道自己记录的是不是最大?)
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-20 10:04:15 | 显示全部楼层
stonezms 发表于 2015-11-20 09:51. 鍥磋鎴戜滑@1point 3 acres
问一下第一题里面没有global变量吧?所有能存的数据都在package里?那一遍DFS应该是找不到总数的吧(遍历完 ...

递归的时候把那个set传参就好了

而实际上这个传参的过程也就对应着数据包的流动
回复 支持 反对

使用道具 举报

lightmark 发表于 2015-11-20 10:09:41 | 显示全部楼层
第一题不是routing里面的link state protocol就可以做么?
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-20 10:10:35 | 显示全部楼层
米奇要努力 发表于 2015-11-20 09:19.鏈枃鍘熷垱鑷1point3acres璁哄潧
我觉得可能用set存node,DFS BFS 都可以。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
个人观点,DFS的call stack操作正好对应数据包的流动。. visit 1point3acres.com for more.
多走一层递归就意味着把数据包往未遍历的节点传递。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
return则代表把数据包往已遍历的节点返回。
. From 1point 3acres bbs中间操作代表修改数据包的内容。
最后出发点是可以收到一个数据包的。

至于BFS么……你可以记录一个节点的指针,代码可以直接去找那个节点,可是数据包飞不过去
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-20 10:32:47 | 显示全部楼层
lightmark 发表于 2015-11-20 10:09
第一题不是routing里面的link state protocol就可以做么?

感觉按照LSP的思路写的话总体上看会更接近BFS遍历
是这样么?
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-20 10:33:40 | 显示全部楼层
plich 发表于 2015-11-20 10:10
个人观点,DFS的call stack操作正好对应数据包的流动。
多走一层递归就意味着把数据包往未遍历的节点传 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
是的,我的意思是一个DFS应该是不行的,得从每个结点DFS一遍吧?
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-20 10:37:47 | 显示全部楼层
stonezms 发表于 2015-11-20 10:33
是的,我的意思是一个DFS应该是不行的,得从每个结点DFS一遍吧?

并不需要……节点数存在数据包里就行了……
写成代码的话就是个传参

补充内容 (2015-11-20 10:38):-google 1point3acres
没说清……是传递引用……想着passing reference说着传参……
回复 支持 反对

使用道具 举报

imxiaobo 发表于 2015-11-20 10:47:42 | 显示全部楼层
第一题 应当是每个节点保存拓扑图 每当收到相邻节点的拓扑更新 和本地比较 如果有新的更新 就更新本地 然后再把更新后的拓扑图发给相邻节点 最终 每个节点都有完整的拓扑 再count一下vertex。

回复 支持 反对

使用道具 举报

yanguango 发表于 2015-11-21 03:13:59 | 显示全部楼层
plich 发表于 2015-11-20 10:10
个人观点,DFS的call stack操作正好对应数据包的流动。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
多走一层递归就意味着把数据包往未遍历的节点传 ...

用 DFS 怎么把后面的结果传到之前访问的路径中的节点去呢
回复 支持 反对

使用道具 举报

echo33 发表于 2015-11-21 04:48:51 | 显示全部楼层
第一题不是union-find吗?传送数据包的两个节点union啊
然后path compression更新root
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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