Google Onsite面经

第五题

unordered_map<timestamp, price> t1;
map<price, unordered_set<timestamp>> t2;

既然有人挖坟，就试着写了下。。。
第五题：

1. class StockTracking {
   
2. public:
   
3.   StockTracking() {}
   
4.   void update(int timestamp, double price) {
   
5.     if (timestamps.count(timestamp)) {
   
6.       auto itt = timestamps[timestamp];
   
7.       prices.erase(itt);
   
8.     }
   
9.     auto it = prices.insert(price);
   
10.     timestamps[timestamp] = it;
    
11.   }
    
12.   void remove(int timestamp) {
    
13.     if (timestamps.count(timestamp) == 0)
    
14.       return;
    
15.     auto it = timestamps[timestamp];
    
16.     prices.erase(it);
    
17.     timestamps.erase(timestamp);
    
18.   }
    
19.   double getCurrentPrice() {
    
20.     auto it = timestamps.end();
    
21.     --it;
    
22.     return *(it -> second);
    
23.   }
    
24.   double getLowPrice() {
    
25.     return *prices.begin();
    
26.   }
    
27.   double getHighPrice() {
    
28.     auto it = prices.end();
    
29.     --it;
    
30.     return *it;
    
31.   }
    
32. private:
    
33.   map<int, multiset<double>::iterator> timestamps;  
    
34.   multiset<double> prices;
    
35. };
    

复制代码

这段code潜在问题是double不能用来计价

第二题的第一问就是简单Union Find，因为在双向链表中，到达关系是等价关系（满足自反，对称，传递性，就不证了），故可用Union Find来做。
Followup其实有个trick, # of connected components = # of nodes - # of edges，如果单链表无环；

1. int CC(vector<ListNode*> ptrs) {
   
2.   unordered_map<ListNode*, ListNode*> children;
   
3.   unordered_set<ListNode*> ptrSet(ptrs.begin(), ptrs.end());
   
4.   for (auto p: ptrs) {
   
5.     if (ptrSet.count(p -> next)) {
   
6.       children[p] = p -> next;
   
7.     }
   
8.   }
   
9.   return ptrs.size() - children.size();
   
10. }
    

复制代码

有环的貌似是Airbnb的面经题

bigbearlake 发表于 2017-3-26 16:19
第四题代码 union find ,另一种方法是建一个图，然后dfs

哥们，你这个题目做错了吧？这个不是并查集，看这个输入，userA: X@gmail.com, Y@gmail.com; userB: X@gmail.com, Z@gmail.com。你这个并查集直接输出1了，但是结果是2。

楼主，问下，第五题要用treemap，但是python没有treemap。python的人岂不是坑爹了？

第五题为何不用segment tree呢？一天一共24*3600秒

没有系统设计？楼主是什么背景呀？面的哪个组呢