骨骼 onsite

LZ 在哪个site 面的？ 最后一个面试官 一开始出的两题是什么啊

守望者bird 发表于 2018-10-28 06:49
hashmap key那个是一个方法，但是问题在于，如果range 普遍较大，空间复杂度会很高，而且每个位置都得存 ...

请问第一个mid point和gap lists分别是指的什么呀

BeStrong2017 发表于 2018-10-28 09:22
LZ 在哪个site 面的？ 最后一个面试官 一开始出的两题是什么啊

汇率转换和我面试的第一道题

BeStrong2017 发表于 2018-10-28 09:22
LZ 在哪个site 面的？ 最后一个面试官 一开始出的两题是什么啊

字数，字数，是在mtv

守望者bird 发表于 2018-10-28 06:10
你有一个词典(new, to, tonight, total, today, tasd,rfe,ref,wef,hn,wfwe)，就是一个人输入几个字母(相 ...

楼主这题感觉就是LC 原题流丝尔 Auto complete

0_- 发表于 2018-10-28 06:39
楼主的意思是第二题的follow up答案应该是
B C?

第三题，按start排序了以后，感觉没必要按start二分了。因为还是要拿一个一个range来和给的点比，看看是不是end >= point吧。

请问一下楼主 第二题的“最大非重复孩子数”这个是什么意思啊？是指孩子里面不会有被重复告知的个数嘛？楼主给的例子答案是否应该为C？谢谢

守望者bird 发表于 2018-10-28 06:49
hashmap key那个是一个方法，但是问题在于，如果range 普遍较大，空间复杂度会很高，而且每个位置都得存 ...

sorry， 我没能看懂你说的二分+优化的方法，能不能详细解释一下或者举个例子？
我有一种不同的做法：将每个range拆成两部分，比如[start, end]这个范围，拆成(start, (1, rangeid)), (end, (-1, rangeid))这两个pair，然后给所有的pair排序
排序之后从头开始扫描，到每个pair处更新目前为止有多少个range还没有结束((1, rangeid)出现过了但是(-1,rangeid)还没有出现)
那么每到一个位置我们都知道覆盖前一个位置与前面一个位置的range有哪些，同时看哪些点在当前这个subrange里面就可以了(这部分可以优化，因为给定的所有点也可以排序并从头扫描)
时间复杂度在O(nlgn)
举个例子啊(1,9) (4, 10) 拆分之后就是(1,(1,0)), (4,(1,1)), (9,(-1, 0)), (10,(-1, 1))

守望者bird 发表于 2018-10-28 06:07
第二题的follow up类似于，假设A告诉B一件事就是A->B， 给定一串A->B, A->C, A->D, A->E, E->D, E->F, B- ...

请问楼主，所谓的非重复节点可不可以理解为：
一个节点B是A的非重复孩子节点，就是从B到A的路径上的所有的点，都只有一个父节点？
还是说这要一个节点C能从不同的节点A以及B沿着不同的路径走到C就算是重复节点？

bdhmwzfa 发表于 2018-10-28 14:10
请问楼主，所谓的非重复节点可不可以理解为：
一个节点B是A的非重复孩子节点，就是从B到A的路径上的所有 ...

或者说，把一个节点干掉，那么N个节点完全收不到消息了，求最大的N？