c********n
发帖数: 26 | 1 一位加拿大香港人面的
given a stream of hashtags, find out most frequent hashtag within last W
number of hashtags
应该就是 max sliding window 的变种
挂了 ... |
t*********i
发帖数: 20 | |
U***A
发帖数: 849 | |
c******w
发帖数: 1108 | 4 用一个circular array存most recent W hashtags
用一个size不超过W的doubleLinkedList of
DLL_Node{
String hashtag;
int frequency;
DLL_Node prev, next;
}
存circular array里的unique hashtag和对应的frequency。并按frequency排序。
用一个HashMap来通过hashtag找到doubleLinkedList里对应的node。
扫进来一个已有的（或新的）hashtag，找到（或create）对应的node，frequency++，
然后比较prev.frequency。如果 > 就swap。repeat till <=
对被挤走的hashtag，frequency--,然后比较next.frequency。如果 < 就swap。repeat
till >=。 为0则remove。 |
w**********o
发帖数: 140 | |
b**********5
发帖数: 7881 | 6 not the same problem
【在 w**********o 的大作中提到】
: http://www.geeksforgeeks.org/find-the-maximum-repeating-number-
: O(n) time and O(1) extra space.
: 順便求Twitter內推.
|
n*****5
发帖数: 984 | |
c*****m
发帖数: 271 | 8 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
【在 n*****5 的大作中提到】
: 用heap保持数量， 用hashmap找点。
|
s******d
发帖数: 9806 | 9 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
bucket（因为frequency只有加减1）。
node。
【在 c******w 的大作中提到】
: 用一个circular array存most recent W hashtags
: 用一个size不超过W的doubleLinkedList of
: DLL_Node{
: String hashtag;
: int frequency;
: DLL_Node prev, next;
: }
: 存circular array里的unique hashtag和对应的frequency。并按frequency排序。
: 用一个HashMap来通过hashtag找到doubleLinkedList里对应的node。
: 扫进来一个已有的（或新的）hashtag，找到（或create）对应的node，frequency++，
|
n*****5
发帖数: 984 | 10 谢谢补充，你说的对。
【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
|
|
|
c******w
发帖数: 1108 | 11 这个优化确实好!之前我就在想要是有一堆hashtags的frequency都一样那update就太
expensive了.
用bucket的话doubleLinkedList里面的node应该就是
DLL_Node{
DLL_Node prev, next;
HashSet hashtags;
int frequency;
}
这样一来每次update都只需要O(1)的操作.time complexity肯定比用heap要好了.
【在 s******d 的大作中提到】
: 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
: 某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
: bucket（因为frequency只有加减1）。
:
: node。
|
U***A
发帖数: 849 | |
g****v
发帖数: 971 | 13 先建一个size为W的circular array，然后建立一个heap。
circular array的元素map to heap中的元素。
这样insert新元素的时候，复杂度是O(lgW)。 |
c********n
发帖数: 26 | 14 一位加拿大香港人面的
given a stream of hashtags, find out most frequent hashtag within last W
number of hashtags
应该就是 max sliding window 的变种
挂了 ... |
t*********i
发帖数: 20 | |
U***A
发帖数: 849 | |
c******w
发帖数: 1108 | 17 用一个circular array存most recent W hashtags
用一个size不超过W的doubleLinkedList of
DLL_Node{
String hashtag;
int frequency;
DLL_Node prev, next;
}
存circular array里的unique hashtag和对应的frequency。并按frequency排序。
用一个HashMap来通过hashtag找到doubleLinkedList里对应的node。
扫进来一个已有的（或新的）hashtag，找到（或create）对应的node，frequency++，
然后比较prev.frequency。如果 > 就swap。repeat till <=
对被挤走的hashtag，frequency--,然后比较next.frequency。如果 < 就swap。repeat
till >=。 为0则remove。 |
w**********o
发帖数: 140 | |
b**********5
发帖数: 7881 | 19 not the same problem
【在 w**********o 的大作中提到】
: http://www.geeksforgeeks.org/find-the-maximum-repeating-number-
: O(n) time and O(1) extra space.
: 順便求Twitter內推.
|
n*****5
发帖数: 984 | |
|
|
c*****m
发帖数: 271 | 21 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
【在 n*****5 的大作中提到】
: 用heap保持数量， 用hashmap找点。
|
s******d
发帖数: 9806 | 22 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
bucket（因为frequency只有加减1）。
node。
【在 c******w 的大作中提到】
: 用一个circular array存most recent W hashtags
: 用一个size不超过W的doubleLinkedList of
: DLL_Node{
: String hashtag;
: int frequency;
: DLL_Node prev, next;
: }
: 存circular array里的unique hashtag和对应的frequency。并按frequency排序。
: 用一个HashMap来通过hashtag找到doubleLinkedList里对应的node。
: 扫进来一个已有的（或新的）hashtag，找到（或create）对应的node，frequency++，
|
n*****5
发帖数: 984 | 23 谢谢补充，你说的对。
【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
|
c******w
发帖数: 1108 | 24 这个优化确实好!之前我就在想要是有一堆hashtags的frequency都一样那update就太
expensive了.
用bucket的话doubleLinkedList里面的node应该就是
DLL_Node{
DLL_Node prev, next;
HashSet hashtags;
int frequency;
}
这样一来每次update都只需要O(1)的操作.time complexity肯定比用heap要好了.
【在 s******d 的大作中提到】
: 找frequency的部分用bucket（double linked）更好一些。每个node就是frequency是
: 某一个值的所有hashtag，这样每次操作只需要移动到相邻的bucket，或者创建新的
: bucket（因为frequency只有加减1）。
:
: node。
|
U***A
发帖数: 849 | |
g****v
发帖数: 971 | 26 先建一个size为W的circular array，然后建立一个heap。
circular array的元素map to heap中的元素。
这样insert新元素的时候，复杂度是O(lgW)。 |
f********c
发帖数: 147 | 27 这样改了DLL_NODE之后，HashMap也要相应修改是吗？
【在 c******w 的大作中提到】
: 这个优化确实好!之前我就在想要是有一堆hashtags的frequency都一样那update就太
: expensive了.
: 用bucket的话doubleLinkedList里面的node应该就是
: DLL_Node{
: DLL_Node prev, next;
: HashSet hashtags;
: int frequency;
: }
: 这样一来每次update都只需要O(1)的操作.time complexity肯定比用heap要好了.
|
S*******w
发帖数: 24236 | 28 太难了 题目都看不懂
【在 c********n 的大作中提到】
: 一位加拿大香港人面的
: given a stream of hashtags, find out most frequent hashtag within last W
: number of hashtags
: 应该就是 max sliding window 的变种
: 挂了 ...
|
i*******e
发帖数: 7 | 29 用bucket是不是可以放弃double linked list直接上array就好了，array size = W，
index = frequency - 1. 这样是不是省点事？hashmap works as inverted index,
key = hashtag, value = index of bucket array
【在 c******w 的大作中提到】
: 这个优化确实好!之前我就在想要是有一堆hashtags的frequency都一样那update就太
: expensive了.
: 用bucket的话doubleLinkedList里面的node应该就是
: DLL_Node{
: DLL_Node prev, next;
: HashSet hashtags;
: int frequency;
: }
: 这样一来每次update都只需要O(1)的操作.time complexity肯定比用heap要好了.
|
c****8
发帖数: 76 | 30 想问问如果用heap的话，如何在hashtag在window中消失的时候（也就是frequency为0
的时候）删除head里的这个hashtag节点呢？
【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
|
|
|
j**********3
发帖数: 3211 | |
