口袋宝石三轮电面

有几个问题想请教lz 多谢
matrix 是bfs+hashset吗？ 有啥需要注意的吗？
bst parent是说只给Parent ，如果有右子树就找右子树 min，没有就看curr node是不是Parent的右子树，是的话返回curr node parent的parent，否则返回curr node 的Parent吗？ 只给root就是lc 285原题？
counting sort是啥意思？记录数目吗？ 可以用in place解法吗？
random number generator可以说些细节吗？ 可以给个input output的例子吗？是x->x-1/maxint就行吗？ 后面那个List 和stream没明白啥意思，可以解释下吗？

白丁117 发表于 2016-12-30 07:59
有几个问题想请教lz 多谢
matrix 是bfs+hashset吗？ 有啥需要注意的吗？
bst parent是说只给Parent ，如 ...

1. 我是用了一个boolean[] 但本质一样 没啥注意的就是写起来比较麻烦
2. 要一直找到第一个取右字数的parent
3. 要求 inplace
4. 我觉得说的挺明白的 input是5的话，随机输出0-4
[1,2,4, 5] k = 2 随机输出两个数 list和stream一样 不过stream不知道总共有4个数

2 是说只要curr是右子树就继续向parent走，直到curr为左子树，返回此时curr的Parent? 想问下比较2个treenode直接用“=”吗（curr是left/right）？
4 是说list是[1,2,4,5] 等概率生成 随便2个数字，比如[1,2] [2,4]就算做对了？ stream 是[1,2,4,5,5,2,4,1,1...]这种？也是[1,2] [2,4]吗？ 有啥区别吗？这个还是有些不懂...

谢谢lz

白丁117 发表于 2016-12-30 13:26
2 是说只要curr是右子树就继续向parent走，直到curr为左子树，返回此时curr的Parent? 想问下比较2个treenod ...

2  这种细节问题看到题你就懂啦：）
4  stream里总共4个数 但你不知道总共4个

请问lz, RNG的那题在stream的情况下该怎么做呢？

lcx813 发表于 2017-1-4 02:16
请问lz, RNG的那题在stream的情况下该怎么做呢？

reservoir sampling

DaBottle 发表于 2017-1-4 04:46
reservoir sampling

噢噢，谢谢楼主！

请问楼主可以详细解释下第二轮的第三题吗？

DaBottle 发表于 2017-1-18 23:20
他似乎没有问我压缩的问题。。我觉得可以用一个int里面的32个bit来代表key

我是用int表示keys的，如果a-z都考虑会显示heap error，rows*cols*2^26 确实太大。
可以问下你怎么记录访问过的状态吗？比较细节的

白丁117 发表于 2017-1-18 23:50
我是用int表示keys的，如果a-z都考虑会显示heap error，rows*cols*2^26 确实太大。
可以问下你怎么记录 ...

没遇到过heap error 我就是用int来表示的 后26bit每一个bit表示是不是拥有某个key