Google interview

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

zhaishaodan 发表于 2015-6-15 01:45
用两个map， 一个maps word to count, 另一个maps count to word集合。
worst case: insert O(logn), getT ...

用map的实质是在用红黑树    你的时间复杂度计算是错的

HashMap< String , Integer > + MinHeap

请问一下是说 全部insert了 再求topK吗！

milanelllo13 发表于 2015-7-30 11:19
请问一下是说 全部insert了 再求topK吗！

Yes. They already insert all, then we get topk

分享一下我的思路哈 :)

1. #include <iostream>
   
2. #include <sstream>
   
3. #include <unordered_map>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. 
   
7. bool comparator (const std::unordered_map<std::string,int>::iterator &lhs,
   
8.                  const std::unordered_map<std::string,int>::iterator &rhs) {
   
9.   return lhs->second < rhs->second;
   
10. };
    
11. 
    
12. int main() {
    
13. 
    
14.   std::unordered_map<std::string,int> word2Freq;
    
15.   std::vector<std::unordered_map<std::string,int>::iterator> maxFreqHeap;
    
16. 
    
17.   std::string line = "a a a b c d d d d";
    
18.   std::cout << "input string = " << line << std::endl;
    
19. 
    
20.   std::istringstream iss(line);
    
21.   std::string wd;
    
22.   while (iss >> wd) {
    
23.     std::unordered_map<std::string,int>::iterator it = word2Freq.find(wd);
    
24.     if (it == word2Freq.end()) {
    
25.       word2Freq[wd] = 1;
    
26.       maxFreqHeap.push_back(word2Freq.find(wd));
    
27.       std::push_heap(maxFreqHeap.begin(),maxFreqHeap.end(),comparator);
    
28.     } else {
    
29.       word2Freq[wd]++;
    
30.       std::make_heap(maxFreqHeap.begin(),maxFreqHeap.end(),comparator);
    
31.     }
    
32.   }
    
33. 
    
34.   int k = 2;
    
35.   std::cout << "max k = " << k << std::endl;
    
36. 
    
37.   while (!maxFreqHeap.empty() && k-- > 0) {
    
38.     std::cout << maxFreqHeap.front()->first << std::endl;
    
39.     std::pop_heap(maxFreqHeap.begin(),maxFreqHeap.end(),comparator);
    
40.     maxFreqHeap.pop_back();
    
41.   }
    
42. 
    
43.   return 0;
    
44. }
    

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lxia 发表于 2015-8-5 16:20
为什么不能用两个hashmap?
map m1 寸string出现次数。
map  m2存 出现某个次数的string列表

我也是这么做的。分享一下我的代码吧。

1. class Name implements Comparable<Name> {
   
2.         String name;
   
3.         int fre;
   
4. 
   
5.         public Name(String str, int val) {
   
6.             name = str;
   
7.             fre = val;
   
8.         }
   
9. 
   
10.         public int compareTo(Name e1) {
    
11.             if (e1.fre == this.fre) {
    
12.                 return e1.name.compareTo(this.name);
    
13.             }
    
14.             return e1.fre - this.fre;
    
15.         }
    
16.     }
    
17. 
    
18.     public static TreeSet<Name> set = new TreeSet<Name>();
    
19.     public static HashMap<String, Integer> map = new HashMap<String, Integer>(1000);
    
20. 
    
21.     public void init(String[] name) {
    
22.         for (String str: name) {
    
23.             if (map.containsKey(str)) {
    
24.                 map.put(str, map.get(str) + 1);
    
25.             } else {
    
26.                 map.put(str, 1);
    
27.             }
    
28.         }
    
29. 
    
30.         for (String str: map.keySet()) {
    
31.             Name e1 = new Name(str, map.get(str));
    
32.             set.add(e1);
    
33.         }
    
34. 
    
35.     }
    
36. 
    
37.     public void insert(String query) {
    
38.         if (map.containsKey(query)) {
    
39.             set.remove(new Name(query, map.get(query)));
    
40.             map.put(query, map.get(query) + 1);
    
41.             Name e1 = new Name(query, map.get(query));
    
42.             set.add(e1);
    
43.         } else {
    
44.             map.put(query, 1);
    
45.             Name e1 = new Name(query, 1);
    
46.             set.add(e1);
    
47.         }
    
48.     }
    
49. 
    
50.     public void topK(int k) {
    
51.         for (Name e: set) {
    
52.             if (k > 0) {
    
53.                 System.out.print(e.name + " ");
    
54.                 k -= 1;
    
55.             }
    
56.         }
    
57.         System.out.println();
    
58.     }

复制代码

核心问题就是在一个无序数组里找topK的那些元素，最佳解法应该是quick select，O(n)时间