新鲜的G家面筋

新鲜热辣的谷歌面筋。估计炮灰了。答得很放，面试官也都心不在焉。但是是时候回馈广大同胞了。


设计查询系统(最大值，最小值，最新加入值)

class System {

  int getMax();

  int getMin()

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

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

nt:7

etc..

能帮大家的就到这里了。祝未来好运:)

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

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

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

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

1. class System{
   
2.         TreeMap<Integer,Integer> time_map = new TreeMap();
   
3.         TreeMap<Integer,HashSet<Integer>> value_map = new TreeMap();
   
4.         int getMax(){
   
5.                 if(value_map.size() == 0)
   
6.                         throw new Exception();
   
7.                 return value_map.lastKey();
   
8.         }
   
9.         int getMin(){
   
10.                 if(value_map.size() == 0)
    
11.                         throw new Exception();
    
12.                 return value_map.firstKey();
    
13.         }
    
14.         int getRecent(){
    
15.                 if(time_map.size() == 0)
    
16.                         throw new Exception();
    
17.                 return value_map.lastKey();
    
18.         }
    
19. 
    
20.         void add(long time, int price){
    
21.                 time_map.put(time,price);
    
22.                 if(!value_map.containsKey(price))
    
23.                         value_map.put(price,new HashSet());
    
24.                 value_map.get(price).put(time);
    
25.         }
    
26.         void update(long time, int price){
    
27.                 remove(time); // remove old value
    
28.                 add(time,price); // add new value
    
29.         }
    
30.         void remove(long time){
    
31.                 if(!time_map.containsKey(time))
    
32.                         throw new Exception();
    
33.                 int value = time_map.get(time);
    
34.                 time_map.remove(time);
    
35.                 value_map.get(value).remove(time);
    
36.                 if(value_map.get(value).size() == 0)// remove the set if empty
    
37.                         value_map.remove(value);
    
38.         }
    
39. }

复制代码

楼主怎么设计的？有时间复杂度要求么？感觉可以用BST

hitowings 发表于 2016-3-16 05:35
楼主怎么设计的？有时间复杂度要求么？感觉可以用BST

我觉得用Hashmap + sorted list 可以，如果要recent也要快的话再存一份数据到queue里。

用BST也可以，但是如果要你实现的话，不就是自己给自己找麻烦吗。

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

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

add(2,5) max:7, min:4, recent:7 这个recent 不是应该是5 么？

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

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

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

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

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

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

我是不是想简单了，用一个hashMap<time, value>和三个整形变量max，min，recent不能解决么？

lby1989825 发表于 2016-3-16 10:02
我是不是想简单了，用一个hashMap和三个整形变量max，min，recent不能解决么？

一个hashtable，两个stack分别存最大和最小，借鉴leetcode minStack这道题应该可以