Google interview

love1point 发表于 2015-4-2 19:13
Hi, I did not find it in Chapter Hard, could you have the screenshot for me? Thank you very much

Hi, that is chapter 18~~~

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

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

1. import java.util.*;
   
2. public class TopK {
   
3.         public static void topK(int[] array, int k){
   
4.                 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   
5.                 for(int num : array){
   
6.                         if(map.containsKey(num)){
   
7.                                 map.put(num, map.get(num)+1);
   
8.                         }
   
9.                         else{
   
10.                                 map.put(num, 1);
    
11.                         }
    
12.                 }
    
13.                 PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(k+1, new
    
14.                                 Comparator<Map.Entry<Integer, Integer>>(){
    
15.                         public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b){
    
16.                                 if(a == null)
    
17.                                         return 1;
    
18.                                 else if(b == null)
    
19.                                         return -1;
    
20.                                 else
    
21.                                         return a.getValue() - b.getValue();
    
22.                         }
    
23.                 });
    
24.                 for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    
25.                         if(queue.size()<k){
    
26.                                 queue.add(entry);
    
27.                         }
    
28.                         else{
    
29.                                 if(entry.getValue()>queue.peek().getValue()){
    
30.                                         queue.poll();
    
31.                                         queue.add(entry);
    
32.                                 }
    
33.                         }
    
34.                 }
    
35.         while(queue.size()>0){
    
36.                 System.out.println(queue.poll().getKey());
    
37.         }
    
38.         }
    
39.         public static void main(String args[]){
    
40.                 int[] array = {1,2,4,5,3,2,1,1,2,3,5,6,6,6,6};
    
41.                 topK(array, 3);
    
42.         }
    
43. }

复制代码

siren01 发表于 2015-4-3 22:45

请收下我的膝盖，多谢

我当时没写完，你以前有碰到过这题吗，你写了多久啊

love1point 发表于 2015-4-4 03:14
请收下我的膝盖，多谢

我当时没写完，你以前有碰到过这题吗，你写了多久啊

额...以前写的，没事，就是你要是对Map.Entry<K, V> 熟了就自然好写了

siren01 发表于 2015-4-4 04:35
额...以前写的，没事，就是你要是对Map.Entry 熟了就自然好写了

恩，不要鄙视我，我从来没用过Map.Entry<K, V>

我感觉如果调用top(k)的次数很多的话，每次不管是用priority queue o(nlogn) 或者用快排 o(n)时间复杂度都很高啊。如果n很大，每一次相当于重新查找。这样不是很费时间吗？

楼主究竟是MS还是PHD？看你自我介绍都说是PHD，面经里都写master

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. class TopK {
   
5.     private:
   
6.         struct node {
   
7.             string id;
   
8.             int cnt;
   
9.             node(string _id, int _cnt) : id(_id), cnt(_cnt) {}
   
10.         };
    
11. 
    
12.         unordered_map<string, int> mp;
    
13.         vector<node> v;
    
14. 
    
15.     public:
    
16.         void insert(string s) {
    
17.             if (mp.find(s) == mp.end()) {
    
18.                 v.push_back(node(s, 1));
    
19.                 int idx = v.size() - 1;
    
20.                 mp[s] = idx;
    
21.             } else {
    
22.                 int idx = mp[s], j;
    
23.                 ++v[idx].cnt;
    
24.                 node tmp = v[idx];
    
25.                 for (j = idx - 1; j >= 0; --j) {
    
26.                     if (v[j].cnt < tmp.cnt) {
    
27.                         v[j+1] = v[j];
    
28.                         mp[v[j+1].id] = j + 1;
    
29.                     } else {
    
30.                         break;
    
31.                     }
    
32.                 }
    
33.                 v[j+1] = tmp;
    
34.                 mp[tmp.id] = j+1;
    
35.             }
    
36.         }
    
37.         
    
38.         vector<string> topk(int n) {
    
39.             vector<string> res;
    
40.             for (int i = 0; i < n && i < v.size(); ++i) {
    
41.                 res.push_back(v[i].id);
    
42.             }
    
43.             return res;
    
44.         }
    
45. };
    
46. 
    
47. int main() {
    
48.     TopK tk;
    
49.     vector<string> v;
    
50.     tk.insert("bob");
    
51.     tk.insert("joe");
    
52.     tk.insert("bob");
    
53.     tk.insert("jane");
    
54.     tk.insert("joe");
    
55.     tk.insert("bob");
    
56.     tk.insert("jack");
    
57.     v = tk.topk(2);
    
58.     for (auto a : v)
    
59.         cout << a << " ";
    
60.     cout << endl;
    
61.     return 0;
    
62. }
    

复制代码

C++版，topk时间复杂度O(k)，每次插入在最坏的情况下需要调整n次，但是需要调整n次说明前n-1项的出现次数是相等的，这种情况还是很少的。每次插入的均摊复杂度应该远远小于n。

用两个map， 一个maps word to count, 另一个maps count to word集合。
worst case: insert O(logn), getTopk O(k).
代码如下很短：

1. class TopN{
   
2. public:
   
3.         void insert(const string& query){
   
4.                 int count = ++word2count[query];
   
5.                 count2words[count-1].erase(query);
   
6.                 if(count2words[count-1].empty()) count2words.erase(count-1);
   
7.                 count2words[count].insert(query);
   
8.         }
   
9.         vector<string> getTop(int n){
   
10.                 vector<string> top;
    
11.                 for(map<int, set<string>, greater<int> >::iterator i = count2words.begin(); i != count2words.end(); i++){
    
12.                         for(set<string>::iterator j = i->second.begin(); j != i->second.end(); j++){
    
13.                                 top.push_back(*j);
    
14.                                 if(top.size() == n) return top;
    
15.                         }
    
16.                 }
    
17.                 return top;
    
18.         }
    
19. private:
    
20.         map<string, int> word2count;
    
21.         map<int, set<string>, greater<int> > count2words;
    
22. };

复制代码