Clone Graph 的两个follow up

follow up1: 如果不用hashmap 该怎么做？
follow up2: 如果图很大该怎么做？

没有什么思路。谢谢各位大神指教。

insideout 发表于 2017-1-12 07:20
谢谢你的回答。

1. 能不能说 2d array 最适合 distributed的在多个machine 复制呢？  hashmap的貌似 ...

1. 2d array很明显可以在多个machine上并行计算，hashMap要keep一个hashmap比较不适合多个machine和并行计算,  当然hashMap也可以distributed, 这样问题会increase the scope of the problem, 你需要请教一下面试官能不能用这个方法来做. 一般来说我不喜欢这个解法，因为这样introduce more problems into our current one, right ? 工作中就会有越来越多的第三方的service, 最后能可能导致product 不能按时deliver.

2. 如果图有明显的聚集特点，比如，你的linked connection,很可能是学校的联系人一坨，工作过的一个公司一坨，那copy图的时候可以每一坨copy一次, 当然这都是预先知道图的特性，在工作时，问清是不是有这些特点也是对于解决问题有很好的帮助，其实无论是不是稀松或者indense， 面试官可以想知道的是你有没有这些可以根据某些特征来找到更好解决问题的办法，至于是不是稀松或者有特征，需要和面试官交流来得到一个比较好的解法。或者说有些既不是学校的也不是工作的，那你就可以不copy这些node, 问一问面试官能不能允许一定的错误率,这会让面试官觉得你很有做一个industry工程师的思维。

3. 图的COPY，一般来说用BFS, 所以如果从DFS来讲，会造成一些明显的比如进入black whole这些问题，所以只是机械地讲从BFS就用DFS，显得你在面试时有点饥不择食，在工作中就是会瞎干，让senior engineer觉得你这人干活不靠谱，DFS的话公司的机器搞坏不说，问题估计一辈子都解决不了。
In summary, 我这些是提供我的一些思路，但具体问题，你还是需要多和面试官察言观色，看他/她到底是想把你导向哪个方向再具体展开~ Good Luck~

yuanxiehuang 发表于 2017-1-12 10:04
图的遍历一个简单的应用就是爬虫，不过写过爬虫的人都知道一个很common的问题就是如果碰到要爬eg. www.go ...

感谢！受教
也许不太相关，不过自己维护栈并不是不切实际的做法，实际上iterative的dfs和bfs代码的差别很小，主要就是出入queue的顺序，fifo queue或者lifo queue。dfs最主要的问题就是遇到无限深图，像你说的网页一直爬下去，bfs就是空间开得很大；所以还有折衷的depth limited dfs，bidirectional bfs啥的。写算法的人要意识到自己在做什么吧，如果你的搜索空间巨大，全部搜完用什么都爆栈。而且像functional programming都全部用递归

不用HashMap还有dfs的做法，图很大没思路。

不用哈希表的话是无环的吗？

1. 不用hashmap,可以用2d array 来表示图，这样就能copy了，
2. 要问清图是稀松图还是indense的图，一般就从distributed这个图在多个machine来答，问题可以从每copy 10k个然后换一台machine继续copy来答，细节上可以再研究，但意思就是这个意思.

yuanxiehuang 发表于 2017-1-12 02:48
1. 不用hashmap,可以用2d array 来表示图，这样就能copy了，
2. 要问清图是稀松图还是indense的图，一般 ...

谢谢你的回答。

1. 能不能说 2d array 最适合 distributed的在多个machine 复制呢？  hashmap的貌似不方便做分布式复制？

2. 稀松土和 indense图 对于复制上的区别是什么？

mark一下，pocket gems 面经里就有这题，我还没有考虑过follow up

顶顶顶顶顶顶顶顶顶顶顶顶

mark..........

yuanxiehuang 发表于 2017-1-12 07:42
1. 2d array很明显可以在多个machine上并行计算，hashMap要keep一个hashmap比较不适合多个machine和并行 ...

2d array 如何做。。。你是说把输入的节点改成一个2darray吗？那输入就要跟面试官交流了？