一亩三分地论坛

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

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

snapchat onsite跪经

[复制链接] |试试Instant~ |关注本帖
freesam 发表于 2016-9-13 13:33:00 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Snapchat - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
其他不说了,上来直接干货吧。。. 1point 3acres 璁哄潧
round 1:
求3个数的数组和加起来是target的3个数,输入颜色,输出True or False
颜色: [[2,18,20],[20,30,50],[28,54,33]]
target: [10,20,100]
问颜色数组里的颜色是否可以通过相加得到target颜色,每一个颜色只能取一次,且必须至少有一个颜色。
简单吧? DFS轻松解决
rouse 2:
sum2,求第一个正数数组里两个数加起来是target数, 比如[2,4,5,6,2,5,3,1] 加起来是10,答案[4,6],第一个的定义是后一个数的index是所有结果里的最小的。
用hash table轻松解决
sum3,求第一个正数数组里三个数加起来是target数, 比如[2,4,5,6,2,5,3,1] 加起来是10,答案[2,6,2],第一个的定义是后一个数的index是所有结果里的最小的。. From 1point 3acres bbs

稍微tricky一点,最后一个index从左往右边走即可。
链表删除相同的数,只保留一个。
hash table解决。
round 3:
N 个person和N 个bike在一个2维度数组里配对,一个person配对一个bike,要求所有配对的距离加起来和最小,面试官只要求讲思路。并提示greedy算法,
这题目我只给出了bruteforce的枚举法思路,时间复杂度是O(n!),面试官说还有greedy算法可以优化成O(n^2)复杂度,但事后我觉得此题用greedy 算法只能近似求解,面试官给出的解法根本就无法求解全局最优解嘛。 不知道有没有高手可以用O(n^2)解出来,打我的脸。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
round4:
word break,I&II. 1point3acres.com/bbs

除了round3的题目没给出最优解,其他都马上都给出了最后的解法。。。没想到今天还是受到拒信了,伤心。。。

评分

2

查看全部评分

runrain 发表于 2016-9-14 00:40:00 | 显示全部楼层
你是博士呀,可能要求不一样 拿的工资也不一样嘛 而且面试官可能会误导你 其实他就想你指出impossible
回复 支持 0 反对 1

使用道具 举报

cococecil 发表于 2016-9-14 05:06:38 | 显示全部楼层
max weighted bipartite matching用Hungarian最快是O(n^3),这题确实是面试官没想清楚(虽然这题点在一个平面上但是edge dist仍然是任意的没有可以简化的地方,比hungarian还快可以拿个奖了)。我猜面试官的想法是把edge dist都放在min heap里再一个一个取,但是比如2x2的图,dist(u0,v0)==1, dist(u0,v1)==2,dist(u1,v0)==98,dist(u1,v1)==100这个例子就该取2+98那两个edge。

感叹一下国人何苦为难国人,世界就是不公平的,楼主加油
回复 支持 1 反对 0

使用道具 举报

厉害的超人 发表于 2016-9-13 13:43:47 | 显示全部楼层
你什么时候面的?
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 13:44:41 | 显示全部楼层

上个星期
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-13 13:48:10 | 显示全部楼层

上周几?我上周三onsite,现在都还没有给我回复。当时还说周三晚上或周四就会给回复。
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 13:51:18 | 显示全部楼层
厉害的超人 发表于 2016-9-13 13:48. From 1point 3acres bbs
上周几?我上周三onsite,现在都还没有给我回复。当时还说周三晚上或周四就会给回复。

上周五面的
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-9-13 13:53:06 | 显示全部楼层

多谢!楼主这么厉害定会找到更好的。待会儿我还是把我的面经发了攒攒人品,估计还是没戏。
回复 支持 反对

使用道具 举报

waikai 发表于 2016-9-13 13:56:13 | 显示全部楼层
请问lz,第三轮的距离是(x-i)^2 + (y-j)^2这样求解来还是说|x-i|+|y-j|。
ps.第三轮画风真的和其他轮不同啊
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 13:58:11 | 显示全部楼层
waikai 发表于 2016-9-13 13:56
请问lz,第三轮的距离是(x-i)^2 + (y-j)^2这样求解来还是说|x-i|+|y-j|。. from: 1point3acres.com/bbs
ps.第三轮画风真的和其他轮不同 ...

(x-i)^2 + (y-j)^2 直线距离
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 14:02:53 | 显示全部楼层
厉害的超人 发表于 2016-9-13 13:53
多谢!楼主这么厉害定会找到更好的。待会儿我还是把我的面经发了攒攒人品,估计还是没戏。


bless祝大offer~
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-13 14:28:07 | 显示全部楼层
第三轮:. 1point 3acres 璁哄潧
http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

确定那个面试官不是在黑你?

补充内容 (2016-9-13 14:29):
估计看你是CS博士才出这题的吧
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 14:30:12 | 显示全部楼层
wtcupup 发表于 2016-9-13 14:28
第三轮:
http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

国人面的。。。。被黑了自己心里清楚就好了。。
回复 支持 反对

使用道具 举报

qiaoli1 发表于 2016-9-13 14:35:36 | 显示全部楼层
感觉是算法课讲得perfect match,参见https://en.wikipedia.org/wiki/Hungarian_algorithm. time complexity is polynomial.
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-13 16:16:42 | 显示全部楼层
wtcupup 发表于 2016-9-13 14:28
第三轮:
http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

转行的。。。。化工博士。。。。
回复 支持 反对

使用道具 举报

runrain 发表于 2016-9-14 00:45:41 | 显示全部楼层
wtcupup 发表于 2016-9-13 14:28
第三轮:
http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf

好像确实可以用greedy,他和匈牙利算法还不一样 他的cost是互相有关系的了, 应该可以再减少一个维度
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-9-14 01:12):
Greedy确实 不对 LZ能直接指出就会好很多
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-14 01:24:37 | 显示全部楼层
runrain 发表于 2016-9-14 00:40
你是博士呀,可能要求不一样 拿的工资也不一样嘛 而且面试官可能会误导你 其实他就想你指出impossible
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不是想误导我。。。是把题目做完后闲聊,我问他有没有更好的算法,面试官跟我说用一个priority_queue做,他也提到了greedy,更我说了一遍,压根没提到匈牙利算法,我回去后和朋友讨论,感觉他说的就是stable of marriage问题,然后觉得这根本只能近似求解嘛。。。。
回复 支持 反对

使用道具 举报

runrain 发表于 2016-9-14 02:06:33 | 显示全部楼层
freesam 发表于 2016-9-14 01:24
不是想误导我。。。是把题目做完后闲聊,我问他有没有更好的算法,面试官跟我说用一个priority_queue做, ...

所以 没有最优解?
回复 支持 反对

使用道具 举报

 楼主| freesam 发表于 2016-9-14 02:07:49 | 显示全部楼层
runrain 发表于 2016-9-14 02:06
所以 没有最优解?

面试官估计自己没想对。。。他以为greedy可以做。。
回复 支持 反对

使用道具 举报

omega094 发表于 2016-9-14 02:09:20 | 显示全部楼层
lz 好强!
感谢分享!!!!
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-9-14 04:01:03 | 显示全部楼层
楼主,第一个题没太看懂,:( 是颜色数组一共只有3组吗?比如target[0]=10,是说,从给定的三个颜色数组里,每个数组取一个数,相加=10. 类似的,再看20,看是否存在3个数相加=20吗?或者,楼主能给一个结果为True的target数组吗?谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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