一亩三分地论坛

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

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

Facebook 电面 10/24

[复制链接] |试试Instant~ |关注本帖
destinyomgwz 发表于 2016-10-26 22:30:02 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
面试官是一个非常好且羞射的印度小哥,上来他先自我介绍,然后问了下我的兴趣,想做什么。之后就开始做题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
两道题,题目不难,就是第二道不算leetcode原题,但也挺简单。
第一题 leetcode原题 firstBadVersion。很快写完之后,小哥问我如果这题recursive做怎么样,我正琢磨着要不要写,他又问优缺点是啥。我就说recursive做这道题不好,要用stack memory,如果stack太深的话还有可能stack overflow。然后他沉吟了片刻,正当我以为他要出各种地里说的follow up时,他直接说下一道了.... from: 1point3acres.com/bbs

第二题 最单纯的两点之间最短路径,但是没实际的图,告诉你每个点uniquely labeled而且是有向图没回路, 然后就两给两个API,
一个叫 getChildren(int num), 返回这个点通向的所有点。
还有个一个叫getParent(),这个function有些诡异,返回的是所有没有incoming nodes的点。
让你实现 List<Integer> shortedPath(int start, int end)。LZ当时百思不得其解这个getParent()有啥用,用BFS做完之后,强行用上这个function,说在做之前先判断下end在不在getParent()返回的list里...如果是就直接返回了。小哥说That's good...也不知道是不是他的本意。follow up问我DFS能不能做,我当时心想这难道要让我写吗,就说DFS不好,不适合做最短路径,会绕路。小哥就说You're right。. 1point3acres.com/bbs

.鐣欏璁哄潧-涓浜-涓夊垎鍦做完题问了问小哥加州风光如何...小哥说加州树少,他喜欢树。Anyway, 小哥人特别好。而且之前曾经和一个连印度人都嘲笑口音的印度人组过队,自觉印度口音还能听,反倒小哥有时候听不懂我...我这渣口语。

昨天半夜拿到的onsite,发个面经回报地里。


评分

2

查看全部评分

hadesi816 发表于 2016-10-27 00:11:52 | 显示全部楼层
请问楼主bfs你是怎么得到路径的? 是在bfs过程中把每一层存到map里面,然后当找到第一个终点之后,反向search map找到路径么?
回复 支持 反对

使用道具 举报

 楼主| destinyomgwz 发表于 2016-10-27 00:21:29 | 显示全部楼层
hadesi816 发表于 2016-10-27 00:11
请问楼主bfs你是怎么得到路径的? 是在bfs过程中把每一层存到map里面,然后当找到第一个终点之后,反向sear ...

是的,用一个map来存点和是从哪个点过来的,BFS到终点就停,然后一个loop从终点开始把整个路径加到结果里
回复 支持 反对

使用道具 举报

jyt0532 发表于 2016-10-27 09:19:28 | 显示全部楼层
第二題挺有意思 感謝分享!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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