當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2355|回复: 23
收起左侧

狗狗挂经

[复制链接] |试试Instant~ |关注本帖
marky 发表于 2017-12-3 14:41:32 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Fail | fresh grad应届毕业生

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

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

x
内推先是直接收了拒信,内推的学姐帮忙argue要了面试,再感谢一次~因为学校的原因跳过了电面,直接Onsite. 一亩-三分-地,独家发布
1. add bold tag,这题好像LC已经收录了
2. 水涨船高,给你一个matrix,你在左上角,坐在一个船上,想要到右下角,但matrix每个位置都有一定的高度,只有水没过那个高度你才能同行,寻找最早能够从左上角坐标(0,0)到右下角坐标(n-1, n-1)的那一天,水每天涨 1 个单位。这题用变化的BFS 和 DFS都可解,自己脑抽选了DFS,时间复杂度还说成了 n2。
3. 类似course schedule 的题,拓扑可秒. 1point3acres
4. 给两个 string, 寻找 最小的 Damerau–Levenshtein distance (定义详见wiki,概括下来就是比edit distance多一个 transpose 操作), 输出 shortest path。最难的一题,没做出来,现在给我做我也做不出来。


技不如人,甘拜下风。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

hychin 发表于 2017-12-4 09:18:16 | 显示全部楼层
水涨船高其实就是LC417,稍微有点改动,做法一样
回复 支持 1 反对 1

使用道具 举报

yuebingyang 发表于 2018-2-13 02:44:17 | 显示全部楼层
charlie.wuhan 发表于 2018-1-9 02:12
水涨船高这题和LC417不是一道题啊,这题意思不就是找到一条左上到右下的path使得路径上最大的值最小么。
.1point3acres网
...

个人觉得水涨船高那题应该是leetcode 778, swim in rising water吧。
link: https://leetcode.com/problems/swim-in-rising-water/description/
回复 支持 1 反对 0

使用道具 举报

charlie.wuhan 发表于 2018-1-9 02:12:35 | 显示全部楼层
水涨船高这题和LC417不是一道题啊,这题意思不就是找到一条左上到右下的path使得路径上最大的值最小么。

补充内容 (2018-1-9 02:13):
DFS比BFS好做

补充内容 (2018-1-9 02:18):.本文原创自1point3acres论坛
说反了……BFS比DFS好做,类似dijkstra
回复 支持 1 反对 0

使用道具 举报

edyyy 发表于 2017-12-3 14:57:07 | 显示全部楼层
谢谢楼主分享。我觉得狗家题确实难,过不过只能看运气了
回复 支持 反对

使用道具 举报

nathan007 发表于 2017-12-4 03:44:21 | 显示全部楼层
楼主能分享一下时间线吗 谢谢!
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-4 04:17:30 | 显示全部楼层
nathan007 发表于 2017-12-4 03:44
楼主能分享一下时间线吗 谢谢!

内推-> 两周后OA -> 一个月后Onsite -> 一周拒信
回复 支持 反对

使用道具 举报

soranokisekimh1 发表于 2017-12-4 04:23:55 | 显示全部楼层
谢谢分享。学校的原因跳过电面,是指学校很好还是学校离G很近..
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-4 04:35:38 | 显示全部楼层
soranokisekimh1 发表于 2017-12-4 04:23
谢谢分享。学校的原因跳过电面,是指学校很好还是学校离G很近..

某技校特殊福利
回复 支持 反对

使用道具 举报

cszhazha 发表于 2017-12-4 08:38:32 | 显示全部楼层
楼主可以具体解释一下第二题的做法吗?没有相处好的思路。bfs的话是依据什么把周围的点加进queue里,万分感谢!
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-5 06:23:18 | 显示全部楼层
hychin 发表于 2017-12-4 09:18-google 1point3acres
水涨船高其实就是LC417,稍微有点改动,做法一样

这样。。还是题没刷够
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-5 06:42:55 | 显示全部楼层
marky 发表于 2017-12-5 06:23-google 1point3acres
这样。。还是题没刷够
. 留学申请论坛-一亩三分地
LC需要刷熟才能辨识出这种变形体的本质
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-5 10:27:35 | 显示全部楼层
cszhazha 发表于 2017-12-4 08:38
楼主可以具体解释一下第二题的做法吗?没有相处好的思路。bfs的话是依据什么把周围的点加进queue里,万分感 ...

我当时是这么想的,后来回来也没有验证正确性:
1. 先把起点加进queue
2. 每当queue 里的点周围的点高度小于等于水高就可以 把周围点push 进 queue
3. 如果周围的点还有没push进queue的,这个点保留在queue里(push回去).留学论坛-一亩-三分地
一直等到有一天终点进了queue就可以了
回复 支持 反对

使用道具 举报

2388260384 发表于 2017-12-5 14:15:03 | 显示全部楼层
hychin 发表于 2017-12-4 09:18
水涨船高其实就是LC417,稍微有点改动,做法一样
来源一亩.三分地论坛.
求大佬提示下 没想明白这两题的相关性
回复 支持 反对

使用道具 举报

2388260384 发表于 2017-12-5 14:16:18 | 显示全部楼层
marky 发表于 2017-12-5 10:27. 留学申请论坛-一亩三分地
我当时是这么想的,后来回来也没有验证正确性:. 围观我们@1point 3 acres
1. 先把起点加进queue
2. 每当queue 里的点周围的点高 ...

感觉这题DFS较好,复杂度大约是2^n~3^n之间。BFS的复杂度应该还与最大天数相关
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-5 15:01:04 | 显示全部楼层
2388260384 发表于 2017-12-5 14:16
感觉这题DFS较好,复杂度大约是2^n~3^n之间。BFS的复杂度应该还与最大天数相关

都想复杂了,所谓的最少天数就是指在从左上角出发一直往上走做能覆盖的地方和从右下角出发一直往上走做能覆盖的地方,两者交界的那个地方的最低点就是最少天数了
回复 支持 反对

使用道具 举报

wz375951019 发表于 2017-12-6 01:18:43 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. visit 1point3acres for more.. visit 1point3acres for more.
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南

补充内容 (2017-12-6 01:20):
第二题 用dijkstra 不行吗?用dijkstra的时候一直记录最大值。这个船每天只能移动一次吗?
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-6 11:22:25 | 显示全部楼层
wz375951019 发表于 2017-12-6 01:18
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点 ...

每天可以移动无数次
回复 支持 反对

使用道具 举报

 楼主| marky 发表于 2017-12-6 11:22:55 | 显示全部楼层
hychin 发表于 2017-12-5 15:01
都想复杂了,所谓的最少天数就是指在从左上角出发一直往上走做能覆盖的地方和从右下角出发一直往上走做能 ...

嗯 你说的对。。。并没有很复杂,就是这题题干长
回复 支持 反对

使用道具 举报

sophietian1024 发表于 2017-12-28 11:03:16 | 显示全部楼层
marky 发表于 2017-12-6 11:22
嗯 你说的对。。。并没有很复杂,就是这题题干长

我没有明白,为什么是从左上角和右下角向上走呢?可以再详细说一下嘛?
回复 支持 反对

使用道具 举报

浴火擎灯 发表于 2018-1-1 05:02:51 | 显示全部楼层
hychin 发表于 2017-12-5 15:01
都想复杂了,所谓的最少天数就是指在从左上角出发一直往上走做能覆盖的地方和从右下角出发一直往上走做能 ...
. 1point 3acres 论坛
比如
[0,3,0,3,0]
[0,3,0,3,0]这种情况呢? 好像没有交点, 求大佬指点。。
回复 支持 反对

使用道具 举报

foggerwoody 发表于 2018-1-1 07:29:32 | 显示全部楼层
我理解的第二是这样的
每一天做一个bfs/dfs, 并把终点放到startSet里面。
第一天把所有的高度小于等于【0,0】点的点都找出来, 并把路径的终点放到一个 startSet里面
第二天 以startSet里面的点为起点, 高度为 小于等于【0.0】 + 1, 重复bfs/dfs
以此类推直到找到【n-1,n-1】
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-20 21:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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