Snapchat新鲜面经

小A要当码农 发表于 2016-10-10 01:31
同问啊， 啥叫增加一条边。。那我直接增加和目标节点的一条边不就好了？

图里有点，边
你说什么叫增加一条边呢？

目标节点是什么意思？

freemail165 发表于 2016-10-10 05:49
图里有点，边
你说什么叫增加一条边呢？

"题目是实现一个无向无权图（简单吧。。。。），要求能增加一条边、判断两个节点之间是否存在直接边、返回边的条数。"。  “要求能增加一条边”的意思是我们可以随意在两个节点之间增加一条边嘛？ 不是要判断两个节点是否直接相连嘛， 那我就在这两个节点之间加一条边？ 一定是我哪里理解错了。。。

图可以用树的那个方法SERIALIZE，只是遇到环的时候要标记一下，另外我想问一下，你说的那个压缩一半的算法，只把边存在标号小的那个节点的临接列表里，那么如果有个FOLLOW UP给你一个节点标号，让你遍历这个图，比如这个节点标号是个大节点，那不是遍历的时候会少走一些边？

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;

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

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-14 04:20
我在网上看到的serialize图的方法，比如树是
     1
   2  3

其实还是看需求吧，这题只是让你自己实现一个满足需求的数据结构。
就是一个map既可解决
然后问题变成如何serialize map...

没必要硬套一些现成的东西

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

补充内容 (2016-11-14 04:28):
比较常见的方法是
1 2 4 # # 5 # # 3 6 # # 7 # #

用set会不会不好保存多个边，比如2-3 2-3出现两次这种？

我感觉snapchat的followup question都比较凶残