logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
Twitter 电面
avatar
Twitter 电面# JobHunting - 待字闺中
c*n
1 楼
一位加拿大香港人面的
given a stream of hashtags, find out most frequent hashtag within last W
number of hashtags
应该就是 max sliding window 的变种
挂了 ...
avatar
t*i
2 楼
哪位牛人能不能给讲讲解法?
avatar
U*A
3 楼
题目都没有看懂
avatar
c*w
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。
avatar
n*5
7 楼
用heap保持数量， 用hashmap找点。
avatar
c*m
8 楼
感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？

【在 n*****5 的大作中提到】
: 用heap保持数量， 用hashmap找点。
avatar
s*d
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++，
avatar
n*5
10 楼
谢谢补充，你说的对。

【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
avatar
c*w
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。
avatar
U*A
12 楼
是要说以下想法还是要写代码？
avatar
g*v
13 楼
先建一个size为W的circular array，然后建立一个heap。
circular array的元素map to heap中的元素。
这样insert新元素的时候，复杂度是O(lgW)。
avatar
c*n
14 楼
一位加拿大香港人面的
given a stream of hashtags, find out most frequent hashtag within last W
number of hashtags
应该就是 max sliding window 的变种
挂了 ...
avatar
t*i
15 楼
哪位牛人能不能给讲讲解法?
avatar
U*A
16 楼
题目都没有看懂
avatar
c*w
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。
avatar
n*5
20 楼
用heap保持数量， 用hashmap找点。
avatar
c*m
21 楼
感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？

【在 n*****5 的大作中提到】
: 用heap保持数量， 用hashmap找点。
avatar
s*d
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++，
avatar
n*5
23 楼
谢谢补充，你说的对。

【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
avatar
c*w
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。
avatar
U*A
25 楼
是要说以下想法还是要写代码？
avatar
g*v
26 楼
先建一个size为W的circular array，然后建立一个heap。
circular array的元素map to heap中的元素。
这样insert新元素的时候，复杂度是O(lgW)。
avatar
f*c
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要好了.
avatar
S*w
28 楼
太难了 题目都看不懂

【在 c********n 的大作中提到】
: 一位加拿大香港人面的
: given a stream of hashtags, find out most frequent hashtag within last W
: number of hashtags
: 应该就是 max sliding window 的变种
: 挂了 ...
avatar
i*e
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要好了.
avatar
c*8
30 楼
想问问如果用heap的话，如何在hashtag在window中消失的时候（也就是frequency为0
的时候）删除head里的这个hashtag节点呢？

【在 c*****m 的大作中提到】
: 感觉这样应该是对的，还得加一个queue记录最近的W个hashtag，每次有一个新的
: hashtag来时，queue.pop_front()，从hashmap中找到index，再在heap中更新吧？
avatar
j*3
31 楼
没看懂题，谁能解释一下
相关阅读
麻痹的弯曲公司加班都从来没有加班费。要不要归先放一边，感觉国内BAT面试要求都好高阿unidentified_title问个Design题，怎么设计网站上的“搜索”功能[求教]亚马逊onsite完后还要加面一轮电面，什么情况？小留不知亡国恨，公司忙过diwaliebay紧急招聘内推教大家一句西班牙语请大家大力帮助AmABB小英雄，內推工作大家猜猜我是谁FYI Apple最近各个部门都在招人我这些年混的不好，和没看到计算机发展的大趋势有很大关系eBay内推Google面经 + 湾区 Team Match求捞走离成功转码还有多远？ (转载)上班被同事黑Snap hit with more layoffs, plans to slow hiring in 2018offer求比较 a家还有spotify苹果前端工程师内推传说中的PIP不能签吧？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。