Snapchat新鲜面经

一个小时前电话面完Snapchat，是个老美，但又不像小白，可能是小墨吧。首先问了问简历上的项目，主要是问了一个多线程的东西。问了个大概，不是很细（我连一个函数的名字都忘了，但是什么功能还是记得很清楚的。他说没关系，我知道你在说什么东西）。
然后是coding，我用了Java。问题很简单，但是第一次面试，毫无经验，在没有IDE的条件下各种不适应，还要手动import，而且之后还出了一个语法bug，还是面试官出手解决。所以上面经之前，首先给还没面过的各位找工友们一个建议：多练练在txt上直接写吧。。。。

题目是实现一个无向无权图（简单吧。。。。），要求能增加一条边

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

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

之，希望已经不大。只能贡献一下面经了。。。。


补充内容 (2016-7-19 06:15):
其实最后那个思路也不对。我觉得最正确的应该是用一个hashset，hashset的元素是Arraylist。arraylist两项是较小节点和较大节点。用adjList，每个节点一个hashset也可保证各项操作常数时间。但memory消耗太大。

follow up按照edge输出的话，每个node就会重复输出多次，比如 "1 2,1 3,1 4,2 3,2 4" 我觉得这个可以这样存: "1 2 3 4,2 3 4"   以逗号隔开分组，每组第一个是一个node，后面跟着的是比这个node大的所有node。

freemail165 发表于 2016-11-14 04:14
跟环有什么关系，比方说用map实现的话，就像前面说的那样，
1 2 3 4 # 2 3 4 # 就可以表示有edge 12,12, ...

我在网上看到的serialize图的方法，比如树是
     1
   2  3
4 5 6 7
我看到网上比较通用的serialize的方法是1 2 4) 5)) 3 6) 7)))
其实就是一种preorder traverse 类似于图的DFS
但是图如果DFS 的话可能会遇到环，当然要标记访问过的节点，如果遇到环就不往下走了

liurudahai 发表于 2016-11-13 09:27
图可以用树的那个方法SERIALIZE，只是遇到环的时候要标记一下，另外我想问一下，你说的那个压缩一半的算法 ...

跟环有什么关系，比方说用map实现的话，就像前面说的那样，
1 2 3 4 # 2 3 4 # 就可以表示有edge 12,12,14,23,24
private Map<Integer,Set<Integer>> edgeMap;

当需求发生变化时实现也要随之变化。
你说的问题确实需要重新考虑，但是又省内存，又干什么都高效。不见得可以实现吧？

楼主面的是SDET岗位吗？

楼主能不能详细说一下这道题的题目要求？

wilbur_zzz 发表于 2016-7-19 07:23
楼主面的是SDET岗位吗？

啥是SDET岗位？

wilbur_zzz 发表于 2016-7-19 07:23
楼主面的是SDET岗位吗？

啥是SDET岗位？

daniel_hl 发表于 2016-7-19 07:54
follow up按照edge输出的话，每个node就会重复输出多次，比如 "1 2,1 3,1 4,2 3,2 4" 我觉得这个可以这样存 ...

说的对啊！

谎言之躯 发表于 2016-7-19 08:08
楼主能不能详细说一下这道题的题目要求？

定义一个UndirectedUnweightedGraph类，首先要自己定义构造函数的参数，然后定义以下函数：addEdge(), hasEdge(), numberOfEdges()

zhuhai_ZFC 发表于 2016-7-19 08:50
定义一个UndirectedUnweightedGraph类，首先要自己定义构造函数的参数，然后定义以下函数：addEdge(), ha ...

楼主，请问下input是什么呀？

xl7 发表于 2016-7-19 10:19
楼主，请问下input是什么呀？

其实这是面试官要我自己想清楚的，不是他告诉我的。