一亩三分地论坛

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

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

snapchat跪经+面经合辑

[复制链接] |试试Instant~ |关注本帖
zzh730 发表于 2016-6-12 00:19:42 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
1. 国人大哥
  * binary tree to double linked list
  * 设计一个支持range query的数据结构,存的是类似`2016-3-15-09:30-service1`这样的结构,就是date加上用了哪个service的记录,然后给个时间区间求某个service用了多少次,没写代码,就说想法
2. 棒子小哥, single thread log 以及followup, 面经高频
3. 国人小哥,
  * LC path sum 1, 2. more info on 1point3acres.com
  * 3d grid,每个点有高度, 给起点和终点,求一个直升机起点到终点高度和最小的路径,注意一点是直升机只能上升不能下降
4. 国人大神,一堆数里加`()+ *`, 求最大值,followup 求back trace求最大值的string表达式


准备了好久还是跪了,把自己总结的sc面经拿出来回馈地里

面经们.zip

154.91 KB, 阅读权限: 1, 下载次数: 391, 下载积分: 大米 -1 升

评分

4

查看全部评分

yebinnews 发表于 2016-6-12 12:41:30 | 显示全部楼层
第四题应该怎么做呢,没有好的思路
回复 支持 反对

使用道具 举报

diyutianshi 发表于 2016-6-12 16:12:59 | 显示全部楼层
第四题裸DP吧,f[i, j]表示从i到j的数字能形成的最大值。
回复 支持 反对

使用道具 举报

 楼主| zzh730 发表于 2016-6-12 22:47:17 | 显示全部楼层
diyutianshi 发表于 2016-6-12 16:12
第四题裸DP吧,f表示从i到j的数字能形成的最大值。

对的,其实是三维dp,dp[j] = max(max(dp[i+k]+dp[i+k+1][j], dp[i+k]*dp[i+k+1][j]),dp[j])

补充内容 (2016-6-12 22:48):
dp(I,J), i打不出来。。。
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-6-13 02:44:50 | 显示全部楼层
第4题的followup思路应该是得到了最大值结果以后backtrack吧? 不过感觉还是偏难啊
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-6-17 10:11:51 | 显示全部楼层
range query的数据结构 楼主怎么设计的?

直升机起点到终点高度和最小的路径  这题啥意思啊?

谢谢楼主了!

回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-6-17 10:26:11 | 显示全部楼层
single thread log 以及followup, 面经高频

这题楼主咋搞的?
回复 支持 反对

使用道具 举报

 楼主| zzh730 发表于 2016-6-18 04:01:36 | 显示全部楼层
duduhaha 发表于 2016-6-17 10:11
range query的数据结构 楼主怎么设计的?

直升机起点到终点高度和最小的路径  这题啥意思啊?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
range query最简单就是hashmap了,一个一个查,优化可以用binary index tree/segment tree, kd-tree也可以


补充内容 (2016-6-18 04:03):. more info on 1point3acres.com
 直升机那道题其实就是个2d array,array[j] 存的就是高度了,他给了任意两点,求直升机从一点起飞飞到另一点的高度之和,约束条件是飞机只能保持在原有高度或者往上飞,不能往下飞
回复 支持 反对

使用道具 举报

 楼主| zzh730 发表于 2016-6-18 04:04:11 | 显示全部楼层
duduhaha 发表于 2016-6-17 10:26
single thread log 以及followup, 面经高频

这题楼主咋搞的?

完整的题目在我总结的面经里,用stack
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-6-18 15:55:08 | 显示全部楼层
我在我的帖子[算法题] 面经/LintCode/LeetCode题目想法和代码分享里上传了我个人的第三轮题目,第四轮题目及follow up的看法和C++源代码。分别在17,18楼。
回复 支持 反对

使用道具 举报

jellyld 发表于 2016-6-19 13:57:18 | 显示全部楼层
感谢分享,下载下来研究一下!
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-6-19 18:39:54 | 显示全部楼层
zzh730 发表于 2016-6-18 04:04.鐣欏璁哄潧-涓浜-涓夊垎鍦
完整的题目在我总结的面经里,用stack
. Waral 鍗氬鏈夋洿澶氭枃绔,
不好找啊,在什么位置??
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-6-20 03:04:55 | 显示全部楼层
zzh730 发表于 2016-6-18 04:01
range query最简单就是hashmap了,一个一个查,优化可以用binary index tree/segment tree, kd-tree也可 ...

多谢楼主回复。  直升机那题应该用dfs遍历同时维持一个min hights和path, 一直更新这两个就好了额?
回复 支持 反对

使用道具 举报

 楼主| zzh730 发表于 2016-6-20 22:01:59 | 显示全部楼层
dg7743 发表于 2016-6-18 15:55
我在我的帖子[算法题] 面经/LintCode/LeetCode题目想法和代码分享里上传了我个人的第三轮题目,第四轮题目 ...

当时要是做到这种程度肯定就hire了
回复 支持 反对

使用道具 举报

 楼主| zzh730 发表于 2016-6-20 22:02:23 | 显示全部楼层
duduhaha 发表于 2016-6-20 03:04
多谢楼主回复。  直升机那题应该用dfs遍历同时维持一个min hights和path, 一直更新这两个就好了额?

楼上有个总结写的特别好,你可以瞅瞅
回复 支持 反对

使用道具 举报

shenroong 发表于 2016-6-30 08:53:02 | 显示全部楼层
zzh730 发表于 2016-6-18 04:04. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
完整的题目在我总结的面经里,用stack

谢谢楼主,看见题目,但是没看见follow up,请问follow up是多线程吗?
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-8-2 08:51:13 | 显示全部楼层
感谢分享,下载下来研究一下!
回复 支持 反对

使用道具 举报

rasperrypie 发表于 2016-8-8 03:05:19 | 显示全部楼层
3d grid,每个点有高度, 给起点和终点,求一个直升机起点到终点高度和最小的路径,注意一点是直升机只能上升不能下降. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
-google 1point3acres
这题不该用dijkstra吗?每次取可以飞行点中高度最小的点,更新这个最矮点周围的点,并把周围点也放到可行点中。用一个heap维护可行点,每次取最小的。原因是,只有最矮的点可以保证不会被其他点更新
回复 支持 反对

使用道具 举报

qiaoli1 发表于 2016-10-5 08:51:34 | 显示全部楼层
同意楼上的 感觉dijkstra就可以,而且每次放进heap里面的一定是该点最小值,只需要再多加一个visit set来track node有没有加进来
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-10 04:48:15 | 显示全部楼层
求问楼主, 第四题follow up的话,怎么判断哪里该加括号呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 00:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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