Snapchat on-site

Snapchat一共四轮laptop coding（要自带电脑），听说一般工作经验>3年的才会给design问题。中午一轮吃饭，不过听interviewer说一般不会给feedback。
面的不好，估计是要挂了


1. 给一个Friend list (undirected graph)，问A

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

猫先走还是老鼠先走，每次猫或鼠只能走一步，求最后猫能赢还是老鼠能赢。猫赢的条件是只要有一种猫能抓鼠的走法存在，鼠赢的条件是永远没法被猫抓到。后来想想其实挺简单的，只要dfs把所有情况跑一遍就行了

我感觉解法应该是（不知道对不对）

比如老鼠先走，找出所有可能走到的点，然后recurse下去，recurse下去的时候改猫走，然后把猫所有的走法recurse一遍

其中只要有一种情况出现猫能走到老鼠的点（比如说老鼠没有任何可走的点了），就return猫赢

如果所以的点都走过，猫还是没有赢，那么就基本可以判定猫是永远赢不了了，就return鼠赢

milton0825 发表于 2017-10-28 00:05
老鼠贏得條件是在被貓抓到之前先走到圖上的環上（前提是圖上有環）

赞同，除非有环或者猫和鼠最开始就不在同一个图上，即两个图不相连，其他情况猫最后都会逼得老鼠无路可走。

kevinxucs 发表于 2017-10-8 12:26
我感觉解法应该是（不知道对不对）

比如老鼠先走，找出所有可能走到的点，然后recurse下去，recurse下去 ...

你这样的话如果猫和老鼠走的步数不一样，但是重叠是不是也是不行

谢谢楼主分享，地4题怎么接？

同问下最后一题，谢谢。

最后一道题完全没有思路啊？

老鼠贏得條件是在被貓抓到之前先走到圖上的環上（前提是圖上有環）

第一题其实就直接union-find, 节点find过一次后query是否所属集合都是O(1)时间。

第四题楼主可以提供一下思路么

第四题是直接bfs然后看他们有没有相交么，有点类似word ladder？