一亩三分地论坛

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

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

Google Intern 电面

[复制链接] |试试Instant~ |关注本帖
梦醒的我 发表于 2016-11-17 07:28:49 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
第一面:leetcode317一摸一样就改了下scenario,followup如果每一步的cost不是constant的怎么办

第二面:. from: 1point3acres.com/bbs
等了20分钟面试官还没打电话来。。。就发了个邮件给hr。。重新约到2小时以后。。
讲一个最challenging的project。
第一题给一个probability p,写一个function有p的概率输出1,1-p的概率输出0。。
第二题给很多edge,要你construct成tree,最后return这个tree的root,followup有哪些input的情况会导致non valid tree,怎么detect,followup2如果input很大怎么办。。我没答出来。。面试官说要用一个distributed hashmap然后问我会不会distributed systems。。。我说不。。。TAT. 1point 3acres 璁哄潧

最后两个面试官都是search team的。。这个有什么讲究吗。。。

评分

2

查看全部评分

zws1818918 发表于 2016-11-19 12:04:05 | 显示全部楼层
楼主第二题可以讲详细点吗?有点不太理解。。。
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-20 00:02:14 | 显示全部楼层
zws1818918 发表于 2016-11-19 12:04
楼主第二题可以讲详细点吗?有点不太理解。。。

就是假设有一个tree,每个node都有一个unique value,现在给你这个tree的所有edges,你可以知道每个edge的parent和child分别是什么,然后让你通过这些edge把原来的tree construct出来并return root。tree不是binary tree,一个node可以有不只两个child。要先写tree的class。
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-11-20 06:49:42 | 显示全部楼层
梦醒的我 发表于 2016-11-20 00:02
就是假设有一个tree,每个node都有一个unique value,现在给你这个tree的所有edges,你可以知道每个edge ...

好的!谢谢楼主了!想请问下tree的class该怎么定义呢?
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-20 10:07:16 | 显示全部楼层
zws1818918 发表于 2016-11-20 06:49
好的!谢谢楼主了!想请问下tree的class该怎么定义呢?

我写的就是一个val和一个set来存children
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-11-20 13:16:36 | 显示全部楼层
梦醒的我 发表于 2016-11-20 10:07
我写的就是一个val和一个set来存children

好的!谢谢楼主。 请问下这里指的non valid是什么情况呢?
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-21 07:25:14 | 显示全部楼层
zws1818918 发表于 2016-11-20 13:16
好的!谢谢楼主。 请问下这里指的non valid是什么情况呢?

就比如有cycle 或者是forest 而不是tree
回复 支持 反对

使用道具 举报

antonioybw 发表于 2016-11-21 10:03:06 | 显示全部楼层
请问一下 LZ   写 概率p输出1   1-p概率输出0的function 怎么实现呢?    可以调用Random内部函数吗  谢谢
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-21 11:33:35 | 显示全部楼层
antonioybw 发表于 2016-11-21 10:03
请问一下 LZ   写 概率p输出1   1-p概率输出0的function 怎么实现呢?    可以调用Random内部函数吗  谢谢

对 就用random函数 不知道面试官问这题目的是啥。。也没有followup
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-23 05:31:54 | 显示全部楼层
狗狗连intern都面Hard嘛。。。感觉贵了==
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-23 06:09:19 | 显示全部楼层
garycheck 发表于 2016-11-23 05:31
狗狗连intern都面Hard嘛。。。感觉贵了==

这是leetcode题吗?请问是哪一道呀。。
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-23 06:37:51 | 显示全部楼层
garycheck 发表于 2016-11-23 05:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
狗狗连intern都面Hard嘛。。。感觉贵了==

噢。。你说一面吗。。但毕竟是面经题。。就还好
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-23 08:17:45 | 显示全部楼层
LZ 二面第二题使用Union Find吗
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-23 08:50:05 | 显示全部楼层
梦醒的我 发表于 2016-11-23 06:09
这是leetcode题吗?请问是哪一道呀。。

不是317嘛,你说的...
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 2016-11-23 09:01:48 | 显示全部楼层
garycheck 发表于 2016-11-23 08:50
不是317嘛,你说的...
. 鍥磋鎴戜滑@1point 3 acres
嗯嗯。。是317。。我以为你说第二面的第二题。。第二面第二题我就用了hashmap,map value to node然后每次新的edge就先看看parent和child的value是不是在那个hashmap里。。如果不在的话construct新的,在的话就用原来的
回复 支持 反对

使用道具 举报

zws1818918 发表于 2016-11-24 16:11:57 | 显示全部楼层
请问楼主拿到offer了吗?
回复 支持 反对

使用道具 举报

jpeng7 发表于 7 天前 | 显示全部楼层
梦醒的我 发表于 2016-11-21 07:25. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就比如有cycle 或者是forest 而不是tree
. Waral 鍗氬鏈夋洿澶氭枃绔,
请问用你说的hashmap的方法怎么样知道有cycle或者forest了呀?
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 7 天前 | 显示全部楼层
zws1818918 发表于 2016-11-24 16:11
请问楼主拿到offer了吗?

还没消息 字数字数字数
回复 支持 反对

使用道具 举报

 楼主| 梦醒的我 发表于 7 天前 | 显示全部楼层
jpeng7 发表于 2016-11-29 05:37
请问用你说的hashmap的方法怎么样知道有cycle或者forest了呀?

最后要return root,如果有more than one root就是forest,test cycle的话就常规方法从root开始bfs之类的
回复 支持 反对

使用道具 举报

jpeng7 发表于 7 天前 | 显示全部楼层
梦醒的我 发表于 2016-11-29 06:16
最后要return root,如果有more than one root就是forest,test cycle的话就常规方法从root开始bfs之类的

哦哦~原来如此,我以为是构造过程中判断cycle呢,谢谢啦~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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