骨骼跪经 10月

eeeeeeeo 发表于 2018-10-12 13:32
想问问楼主 linkedlist那道题如果是N1 N3 N5 N4 N9的话是return 3还是4呀？ 中间N3 N5 N4是算一部分吗？ 谢 ...

3, 字数字数字数

wenyi189 发表于 2018-10-13 10:39
3, 字数字数字数

那能再问问楼主这道题当时你的做法吗？好像不是很看得懂怎么用Set扫一遍做 TAT

补充内容 (2018-10-13 14:15):
想问问如果是 N3 N1 N5 N9 N4是不是也是返回3呀？如果是的话我好像就知道了，谢谢！

eeeeeeeo 发表于 2018-10-13 00:12
那能再问问楼主这道题当时你的做法吗？好像不是很看得懂怎么用Set扫一遍做 TAT

补充内容 (2018-10-13 14 ...

N3 N1 N5 N9 N4 是返回3, 因为N1是一段, N3, N4, N5是一段, N9是一段. 所有3段返回3. 用set是为了方便查找

第五轮的follow up可以用最小生成树算法做吗？

wenyi189 发表于 2018-10-14 03:04
N3 N1 N5 N9 N4 是返回3, 因为N1是一段, N3, N4, N5是一段, N9是一段. 所有3段返回3. 用set是为了方便查 ...

其实还有一点想搞明白。
连续的点在input里面可以是不连续的么？
比如

n2 n8 n1 n3 n5 n9 n4

这种case输入应该是 5 还是 1 呢？

0_- 发表于 2018-10-17 17:34
其实还有一点想搞明白。
连续的点在input里面可以是不连续的么？
比如

对, input是array of nodes. 可以你是举的例子. 这个情况应该返回2. 因为n1 n2 n3 n4 n5是一段, n8 n9是一段.

第三轮. 不知道什么国家的大哥. 问了Java基础知识. 题目带时间戳的hashmap. 面经题. 讨论clean up的实现. 感觉答得不好. 希望比O(n)快
这轮算是design了吧？
hashmap 什么操作需要比O(n)快？ 普通的insert和get 不都是常量吗？

a0106660 发表于 2018-10-9 08:06
第三轮 自动清理比O(n)快,  不知道楼主有啥想法吗?
用LRU 的方法可以做到 O(k), k 是 # of expired tasks. ...

不用这么复杂吧，里面再用一个HashMap<Key, TimeStamp> 然后在其它正常操作的时候检查ttl是否expire来决定是否需要删除，这样lazy clean up的操作还是常量吧

第五题是不是一个weighted graph

补充内容 (2018-10-27 02:31):
第五题先每个target dfs 找到到其他target 最近的距离，用这个距离做边，就变成一个weighted graph的最小生成树的问题吧，如果路径最小，可以保证没有环，有环就会有重复的无用路径。

补充内容 (2018-10-27 02:33):
说错了，BFS..