Buttercola: Twitter: Top k frequent words in a string
http://www.1point3acres.com/bbs/thread-143017-1-1.html
给一组string "a a b b c c beta beta beta alpha"
n = 2;
要求返回一个List<String> 含有的是出现次数最多的n个， 也就是说如果n=1 list中只有出现次数最多的那个也就是beta, 如果是n=2， list当中出现beta, a b c， 因为a b c都出现两次，算是第二出线多的。. from: 1point3acres.com/bbs
所以就是n是几，就返回几个数吧，按出现频率来。
开始的思路是, hashmap, + array存出现次数，再arrays.sort()，在获取hashmap当中的key, 印度小哥说不好， 你再想想，我马上说用一个int max 来记录出现次数最多的，找到最多的然后再找第二多的。. 1point3acres.com/bbs
小哥说，不错，这个方法处理数据不大的时候是可以得，接着问，能不能用one pass的形式？
想了一会，疑问句："PriorityQueue？" 小哥说，嗯，说说吧，就是每个出现单词出现的次数都扔进priorityQueue里面，它自动排序嘛-google 1point3acres
小哥说，那你打代码吧
这里还有一个情况是每一个word之间都是有空格的，两个pointer, start end一个数空格 一个不数空格来获取每一个word。
打完之后，发现小哥说了句："that looks good for me" 心里搜一个口气。
最后小哥又让我写了几个Unit test。. Waral 鍗氬鏈夋洿澶氭枃绔�,
我就随便考虑了三种请况。 1. s = null || "" 2. s = "a b b" n =1 3. s = "a b b a b c" n =2. Waral 鍗氬鏈夋洿澶氭枃绔�,
然后用assert(result.get(i从0到N)).equals(目标单词)
小哥说不错。
求人品，要求不多，让我去onsite见识一下场面就可以了。
（准备的豆子问题没有考，也没有自我介绍，上来就码，弄题意弄了将近十分钟，一是信号不算天好，二是印度口音懂的人都懂）
Understand the problem:
这个题目比较麻烦的地方是要求输出具有相同词频的所有string. 比如 n = 2
是要求输出第一大和第二大的所有词。对于这个例子，输出就是
beta (first largest)
a b c (second largest)
所以如果只用 HashMap + PriorityQueue的话不太容易找出来所有前 K 大的数，因为有重复 (e.g. a a b b c c)。并且重复的数不是一起读到PriorityQueue里的。
一个方法是先对所有的输入做词频统计，然后建立倒排索引(inverted index), 同时用 min Heap 来统计 top K 的词频。因为倒排索引可以把所有同样词频的数放到一起，而且在PriorityQueue里面只存词频，因为倒排索引里面已经记录了相应词频的String 是哪些了。
给一组string "a a b b c c beta beta beta alpha"
n = 2;
要求返回一个List<String> 含有的是出现次数最多的n个， 也就是说如果n=1 list中只有出现次数最多的那个也就是beta, 如果是n=2， list当中出现beta, a b c， 因为a b c都出现两次，算是第二出线多的。. from: 1point3acres.com/bbs
所以就是n是几，就返回几个数吧，按出现频率来。
开始的思路是, hashmap, + array存出现次数，再arrays.sort()，在获取hashmap当中的key, 印度小哥说不好， 你再想想，我马上说用一个int max 来记录出现次数最多的，找到最多的然后再找第二多的。. 1point3acres.com/bbs
小哥说，不错，这个方法处理数据不大的时候是可以得，接着问，能不能用one pass的形式？
想了一会，疑问句："PriorityQueue？" 小哥说，嗯，说说吧，就是每个出现单词出现的次数都扔进priorityQueue里面，它自动排序嘛-google 1point3acres
小哥说，那你打代码吧
这里还有一个情况是每一个word之间都是有空格的，两个pointer, start end一个数空格 一个不数空格来获取每一个word。
打完之后，发现小哥说了句："that looks good for me" 心里搜一个口气。
最后小哥又让我写了几个Unit test。. Waral 鍗氬鏈夋洿澶氭枃绔�,
我就随便考虑了三种请况。 1. s = null || "" 2. s = "a b b" n =1 3. s = "a b b a b c" n =2. Waral 鍗氬鏈夋洿澶氭枃绔�,
然后用assert(result.get(i从0到N)).equals(目标单词)
小哥说不错。
求人品，要求不多，让我去onsite见识一下场面就可以了。
（准备的豆子问题没有考，也没有自我介绍，上来就码，弄题意弄了将近十分钟，一是信号不算天好，二是印度口音懂的人都懂）
Understand the problem:
这个题目比较麻烦的地方是要求输出具有相同词频的所有string. 比如 n = 2
是要求输出第一大和第二大的所有词。对于这个例子，输出就是
beta (first largest)
a b c (second largest)
所以如果只用 HashMap + PriorityQueue的话不太容易找出来所有前 K 大的数，因为有重复 (e.g. a a b b c c)。并且重复的数不是一起读到PriorityQueue里的。
一个方法是先对所有的输入做词频统计，然后建立倒排索引(inverted index), 同时用 min Heap 来统计 top K 的词频。因为倒排索引可以把所有同样词频的数放到一起，而且在PriorityQueue里面只存词频，因为倒排索引里面已经记录了相应词频的String 是哪些了。
Read full article from Buttercola: Twitter: Top k frequent words in a string
No comments:
Post a Comment