一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1125|回复: 16
收起左侧

狗狗挂经

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

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

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

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

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


技不如人,甘拜下风。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

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. 鍥磋鎴戜滑@1point 3 acres
楼主能分享一下时间线吗 谢谢!

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

hychin 发表于 2017-12-5 06:42:55 | 显示全部楼层
marky 发表于 2017-12-5 06:23
这样。。还是题没刷够
. more info on 1point3acres.com
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就可以了.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

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
我当时是这么想的,后来回来也没有验证正确性:
1. 先把起点加进queue
2. 每当queue 里的点周围的点高 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉这题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!
-google 1point3acres
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南

补充内容 (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
都想复杂了,所谓的最少天数就是指在从左上角出发一直往上走做能覆盖的地方和从右下角出发一直往上走做能 ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-16 01:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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