Pocket Gems - 电面1

Why Pocket Gems?
What games do you like?
(Red Black Tree (O(NLogK)) | Heap (O(NLogK)) | Buc

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

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

休息好点

补充内容 (2017-5-6 02:01):
第二天收到电面2 感觉这家公司是不断地练面试官的感觉 哎

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_map>
   
4. #include <map>
   
5. #include <algorithm>
   
6. #include <iterator>
   
7. using namespace std;
   
8. 
   
9. vector<int> sol(vector<int>& list, int k) {
   
10.   if (k <= 0) {
    
11.     return {};
    
12.   }
    
13.   unordered_map<int, int> h;
    
14.   for (const auto &i : list) {
    
15.     h[i]++;
    
16.   }
    
17.   multimap<int, int> rbtree;
    
18.   for (const auto &i : h) {
    
19.     if (rbtree.size() < size_t(k)) {
    
20.       rbtree.insert(make_pair(i.second, i.first));
    
21.       continue;
    
22.     }
    
23.     if (begin(rbtree)->first < i.second) {
    
24.       rbtree.erase(begin(rbtree));
    
25.       rbtree.insert(make_pair(i.second, i.first));
    
26.     }
    
27.   }
    
28.   vector<int> result;
    
29.   for (const auto &i : rbtree) {
    
30.     result.push_back(i.second);
    
31.   }
    
32.   reverse(begin(result), end(result));
    
33.   return result;
    
34. }
    
35. 
    
36. int main() {
    
37.   vector<int> list = {2, 3, 4, 2, 5, 2, 4};
    
38.   int k = 1;
    
39.   vector<int> result = sol(list, k);
    
40.   for (const auto &i : result) {
    
41.     cout << i <<  '\t';
    
42.   }
    
43.   cout << '\n';
    
44.   k = 2;
    
45.   result = sol(list, k);
    
46.   for (const auto &i : result) {
    
47.     cout << i <<  '\t';
    
48.   }
    
49.   cout << '\n';
    
50.   return 0;
    
51. }

复制代码

补充内容 (2017-5-5 07:48):
Red Black Tree 写法 注意输出的时候需要reverse

补充内容 (2017-5-5 07:50):
Time Complexity O(NLogK)

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

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

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

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

第一个题就写了三种做法？真厉害

mchzh 发表于 2017-5-5 08:08
第一个题就写了三种做法？真厉害

我没办法直接抄的

楼主太厉害了！红黑树我都不明白该怎么实现，可以就用heap和bucket吗

让3个都实现？这也有点太无理

danielwx 发表于 2017-5-5 09:49
楼主太厉害了！红黑树我都不明白该怎么实现，可以就用heap和bucket吗

可以的 bucket 是follow up 还好我当场找到答案 抄成功