c*****e
发帖数: 67 | 1 有一个无限数据流不断输送整数，要求设计函数获取第k%的数，时间复杂度是logn。
例如1,2,3,4,5,...,10, get(6%)的结果是6. | e***l
发帖数: 710 | | c*****e
发帖数: 67 | 3 我有提到是balanced的BST。
面试官好像是觉得我的方法不对。
【在 e***l 的大作中提到】
: BST不balance, 查找时间可以退化为n
| b***e
发帖数: 1419 | 4 This is not different from the median in stream problem. Just use 2 heaps,
one min, the other max. When k = 50, the two heals are of the same size.
In more general cases, adjust the heap size accordingly.
【在 c*****e 的大作中提到】
: 有一个无限数据流不断输送整数，要求设计函数获取第k%的数，时间复杂度是logn。
: 例如1,2,3,4,5,...,10, get(6%)的结果是6.
| f*****e
发帖数: 2992 | 5 2^32个整数，8GB内存，每个node存pair就行了。
【在 c*****e 的大作中提到】
: 我有提到是balanced的BST。
: 面试官好像是觉得我的方法不对。
| S********e
发帖数: 74 | 6 这适用于k值固定的情况吧，如果每次的k值不一样好像还要用bst阿
,
【在 b***e 的大作中提到】
: This is not different from the median in stream problem. Just use 2 heaps,
: one min, the other max. When k = 50, the two heals are of the same size.
: In more general cases, adjust the heap size accordingly.
| b***e
发帖数: 1419 | 7 I understand the question as with a fixed k.
【在 S********e 的大作中提到】
: 这适用于k值固定的情况吧，如果每次的k值不一样好像还要用bst阿
:
: ,
| l******6
发帖数: 340 | 8
I am thinking of these words:
"
有一个无限数据流不断输送整数，
"
Would it possible that we can't store the whole thing with raw data?
【在 b***e 的大作中提到】
: I understand the question as with a fixed k.
| d********e
发帖数: 239 | 9 这和lz的方法比
有啥好处，O(1)?
【在 b***e 的大作中提到】
: I understand the question as with a fixed k.
| e***l
发帖数: 710 | 10 如何从bst里面找到k-th大的数?
【在 c*****e 的大作中提到】
: 我有提到是balanced的BST。
: 面试官好像是觉得我的方法不对。
| A*********c
发帖数: 430 | 11 That's the right question to ask.
我觉得coderfe解法的主要问题是没有解决这个问题。
Tree不balance，你相对好说，用balanced Implementation。
关键是这个kth in BST naive的算法你要做inorder, 而且是每次query Kth都要做一次
traversal。
这个题目的实际意义一定是处理无限数据流的频繁查询的问题, 所以多次query
每次都traversal是不行的。
除非你augment你的BTS data structure, 每个节点加入左右子树子结点个数的信息，第
一你得说明白怎么augment，第二查询复杂度还是log(n)。
所以我second狂且的solution。每次adjust heap size是O(1), 插入O(log(n)), query
O(1）。
而且少了上面所说的所有的overhead。
【在 e***l 的大作中提到】
: 如何从bst里面找到k-th大的数?
| n******n
发帖数: 567 | | c******0
发帖数: 260 | 13 为什么你说 “每次adjust heap size是O(1), 插入O(log(n)), queryO(1）。
而且少了上面所说的所有的overhead。” 在heap 里查找第K个数是怎么做到 O(1)的？？
我认为楼上fatalme的 2^32 size 的array 才是对的。不过，没必要存pair。我面试遇
到过类似的题，挂掉了。后来 HR 发邮件给我说了答案，就是这种解法。
，第
query
【在 A*********c 的大作中提到】
: That's the right question to ask.
: 我觉得coderfe解法的主要问题是没有解决这个问题。
: Tree不balance，你相对好说，用balanced Implementation。
: 关键是这个kth in BST naive的算法你要做inorder, 而且是每次query Kth都要做一次
: traversal。
: 这个题目的实际意义一定是处理无限数据流的频繁查询的问题, 所以多次query
: 每次都traversal是不行的。
: 除非你augment你的BTS data structure, 每个节点加入左右子树子结点个数的信息，第
: 一你得说明白怎么augment，第二查询复杂度还是log(n)。
: 所以我second狂且的solution。每次adjust heap size是O(1), 插入O(log(n)), query
| c********g
发帖数: 30 | 14 严格考虑无限数据流的前提，我觉得没有精确解。
比如你的说的2^32数组的方法，count的数量会溢出。
两个heap的方法也不能存下无限的数据。
在无限数据流的前提下，只能加上一个假设，数据点是独立同分布的，
然后随即sample N的数据，之后在用2^32数组去求近似解。
？？
【在 c******0 的大作中提到】
: 为什么你说 “每次adjust heap size是O(1), 插入O(log(n)), queryO(1）。
: 而且少了上面所说的所有的overhead。” 在heap 里查找第K个数是怎么做到 O(1)的？？
: 我认为楼上fatalme的 2^32 size 的array 才是对的。不过，没必要存pair。我面试遇
: 到过类似的题，挂掉了。后来 HR 发邮件给我说了答案，就是这种解法。
:
: ，第
: query
|
|
