数据砖店面 挂经 求大米

今天早上面的，hr一小时就发了邮件说挂了 非常效率。

地里原题。有一个系统，里面记录着每个customer产生的revenue，要你实现3个API：

1. insert(revenue): 一个新customer，产生了revenue，返回新customer的ID。customerID是自增ID，第一次insert是0，第二次是1，以此类推
2. insert(revenue, referrerID): 现有ID为referrerID的customer refer了一个新customer，产生了reven

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

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

ay里insert两个数就好（新customer的revenue和referrer的updated revenue)，整体复杂度是O(N^2)，在call第三个API特别多的时候这个反而是更快的。^^以上N为总客户个数。

当然可能有更好的数据结构，我水平有限就不瞎说了

为啥复杂度是O(n^2)？假设sorted array用treemap<revenue, set<CustomerId>> 来实现的话，
insert: O(logn)
search: O(logn + k) ?

匿名用户 发表于 2022-4-8 09:57
思路就是用Java TreeMap，以上是我写的代码

Line 39 有问题，这样就不是return K个数了

1. import org.junit.jupiter.api.Assertions;
   
2. import org.junit.jupiter.api.Test;
   
3. 
   
4. import java.util.*;
   
5. 
   
6. 
   
7. public class CustomerRevenue {
   
8.     private int cid = 1;
   
9.     private final TreeMap<Integer, HashSet<Integer>> revenueMap = new TreeMap<>();
   
10.     private final HashMap<Integer, Integer> cidMap = new HashMap<>();
    
11. 
    
12.     public void insert(int revenue) {
    
13.         cidMap.put(cid, revenue);
    
14.         revenueMap.computeIfAbsent(revenue, v -> new HashSet<>()).add(cid);
    
15.         cid++;
    
16.     }
    
17. 
    
18.     public void insert(int revenue, int referralId) {
    
19.         cidMap.put(cid, revenue);
    
20.         cid++;
    
21.         if (cidMap.containsKey(referralId)) {
    
22.             int referralRevenue = cidMap.get(referralId);
    
23.             if (revenueMap.containsKey(referralRevenue)) {
    
24.                 revenueMap.get(referralRevenue).remove(referralId);
    
25.                 if (revenueMap.get(referralRevenue).size() == 0) {
    
26.                     revenueMap.remove(referralRevenue);
    
27.                 }
    
28.                 revenueMap.computeIfAbsent(referralRevenue + revenue, e -> new HashSet<>()).add(referralId);
    
29.                 cidMap.put(referralId, referralRevenue + revenue);
    
30.             }
    
31.         }
    
32.     }
    
33. 
    
34.     public List<Integer> getKLowestRevenue(int k, int targetRevenue) {
    
35.         List<Integer> result = new ArrayList<>();
    
36.         int current = targetRevenue;
    
37.         for (int i = 0; i < k; i++) {
    
38.             int key = revenueMap.higherKey(current);
    
39.             result.addAll(revenueMap.get(key));
    
40.             current = key;
    
41.         }
    
42.         return result;
    
43.     }
    
44. 
    
45.     @Test
    
46.     public void testCustomerRevenue() {
    
47.         this.insert(100); // 1
    
48.         this.insert(100); // 2
    
49.         this.insert(200); // 3
    
50.         this.insert(200); // 4
    
51.         this.insert(300); // 5
    
52.         this.insert(400); // 6
    
53. 
    
54.         Assertions.assertIterableEquals(List.of(3, 4, 5, 6), getKLowestRevenue(3, 100));
    
55. 
    
56.         this.insert(100, 2); // 7
    
57.         Assertions.assertIterableEquals(List.of(2, 3, 4, 5, 6), getKLowestRevenue(3, 100));
    
58.     }
    
59. }

复制代码

思路就是用Java TreeMap，以上是我写的代码

您好！
本帖隐藏的内容需要积分高于 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

ckc_cmu 发表于 2021-10-30 15:08
跪求TreeMap search 如何是O（logn + k)
感觉TreeMap用higherEntry这个API的话每次调用都是O（logn），总 ...

我也觉得是logN + K，tree里面的iterator很难O(1)时间去下个点

匿名用户 发表于 2022-4-8 09:57
思路就是用Java TreeMap，以上是我写的代码

如果getKLowestRevenue()里面set的size大于k，结果可能会有问题

感谢lz分享！好奇为啥挂了？

get_k_lowest用binary search。

1. class Revenue {
   
2. public:
   
3.   Revenue() : id(0) {}
   
4. 
   
5.   int insert(int revenue) {
   
6.     r[id] = revenue;
   
7.     ids[revenue].insert(id);
   
8.     return id++;
   
9.   }
   
10. 
    
11.   int insert(int revenue, int referrer_id) {
    
12.     r[id] = revenue;
    
13.     ids[revenue].insert(id);
    
14. 
    
15.     // update referrer's revenue.
    
16.     ids[r[referrer_id]].erase(referrer_id);
    
17.     r[referrer_id] += revenue;
    
18.     ids[r[referrer_id]].insert(referrer_id);
    
19. 
    
20.     return id++;
    
21.   }
    
22. 
    
23.   vector<int> get_k_lowest(int k, int target) {
    
24.     // ids.upper_bound() finds first element > target.
    
25.     // use ids.lower_bound() if want first element >= target.
    
26.     map<int, unordered_set<int>>::iterator iter = ids.upper_bound(target);
    
27. 
    
28.     vector<int> result;
    
29.     while (result.size() < k && iter != ids.end()) {
    
30.       unordered_set<int>::iterator it = iter->second.begin();
    
31.       while (result.size() < k && it != iter->second.end()) {
    
32.         result.push_back(*it++);
    
33.       }
    
34.       iter++;
    
35.     }
    
36.     return result;
    
37.   }
    
38. 
    
39. private:
    
40.   int id;
    
41.   unordered_map<int, int> r;          // r[id] = revenue
    
42.   map<int, unordered_set<int>> ids;   // ids[revenue] = set of ids with revenue.
    
43. };
    

复制代码