一亩三分地论坛

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

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

Google电面,跪了

[复制链接] |试试Instant~ |关注本帖
ekco 发表于 2014-12-11 04:22:12 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 |Other

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

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

x
刚刚结束了Google的电话面试,面试官是个姐妹儿,上来说一个算法题一个design题,一下就凉了, design完全没准备啊。。。
1. Given a collection of boarding passes, the starting city and the destination city, decide if one can get to the destination from the start city.

   graph:
    MIA -> DC
    DC -> NYC
    DC-> MIA. 鍥磋鎴戜滑@1point 3 acres

    def can_reach(graph, MIA, NYC)
    很简单的dfs,但是写的时候还是bug百出,最重要的graph里可能的环也忘了处理,问我给几个test cases,bug到我自己不忍直视。。。
    感觉要是自己写的话会好很多,一边跟她讲话一边写就脑洞大开,不知道在想啥了

2. Design a service to shortern url.. From 1point 3acres bbs
    完全没想法,问给你一个original url怎么generate短的url,会有millions of users怎么存储?.1point3acres缃
    我说 要存在hard disk上而不是memory,然后自己又很二的说了hashtable, 她问disk上的hashtable怎么讲?
    我支支吾吾了一顿,她说要从database取出来然后转成hashtable吗?我这才记起database这回事。

总之自己弱爆了,第一题够懒,第二题直接是embarrassing。。。
拖拖跪了,刷了将近一个月的leetcode基本没用,gooogle还是以后再说吧
.鐣欏璁哄潧-涓浜-涓夊垎鍦



补充内容 (2014-12-10 15:31):.鐣欏璁哄潧-涓浜-涓夊垎鍦
关于第二题看这里http://stackoverflow.com/questio ... ode-a-url-shortener
suonan 发表于 2014-12-11 04:32:41 | 显示全部楼层
patpat, move on吧
第一题bfs对loop的处理可能更方便些,用个set就可以。 tiny url是经典题目。。
回复 支持 反对

使用道具 举报

yinping4256 发表于 2014-12-11 05:58:39 | 显示全部楼层
你的题目比我的难得多。。。到底是咋回事啊!
回复 支持 反对

使用道具 举报

leyhzm 发表于 2014-12-24 03:07:46 | 显示全部楼层
楼主你说给几个test case是你自己想的还是对方给你达?
还有,test是目测么?还是有ide测?
回复 支持 反对

使用道具 举报

 楼主| ekco 发表于 2014-12-24 04:53:32 | 显示全部楼层
leyhzm 发表于 2014-12-23 14:07
楼主你说给几个test case是你自己想的还是对方给你达?
还有,test是目测么?还是有ide测?

让你给, 然后自己talk through,没有ide啊,因为用的google doc
回复 支持 反对

使用道具 举报

z3581640 发表于 2014-12-24 10:31:31 | 显示全部楼层
第一题的话BFS比较好,因为可以找到最短路径, 而DFS不能保证最短路径

如果follow up的话,用A Star比较好, evaluation 的话跟机票价格或者距离成反比
回复 支持 反对

使用道具 举报

mj2009 发表于 2014-12-25 08:11:32 | 显示全部楼层
有点难,看lz是phd申请的吧。第一题dfs递归可以,先建一个hash edgelist,避免loop就遍历了就把边删掉。第二题是经典system design,不过在店面里出也有点奇葩。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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