一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2780|回复: 31
收起左侧

新鲜的G家面筋

[复制链接] |试试Instant~ |关注本帖
shumin0809 发表于 2016-3-16 03:45:07 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
新鲜热辣的谷歌面筋。估计炮灰了。答得很放,面试官也都心不在焉。但是是时候回馈广大同胞了。. Waral 鍗氬鏈夋洿澶氭枃绔,

. from: 1point3acres.com/bbs
设计查询系统(最大值,最小值,最新加入值)
class System {
  int getMax();
  int getMin()
  int getRecent()
  
  void add(long time, int price)
  void update(long time, int price)
  void remove(long time);      
}

例子如下
add(1,4) max:4, min:4, recent:4
add(4,7) max:7, min:4, recent:7
.鐣欏璁哄潧-涓浜-涓夊垎鍦
add(2,5) max:7, min:4, recent:7
etc..

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


. 1point 3acres 璁哄潧


评分

2

查看全部评分

ryancooper 发表于 2016-4-27 01:52:45 | 显示全部楼层
jy_121 发表于 2016-4-26 12:03
感谢回复。我是看你之前说使用双向链表的话remove就是O(1),但是又改索引的话,因为是treemap所以是logn ...

你如果不用双向链表,只用单链表的话那么remove的时候就算你提供要remove的结点的指针,但是因为没有前向指针,你必须从链表头找到该结点的前一个结点,这样才能把该节点删掉。如果用单链表的话,链表的remove复杂度就会变成O(n),就算你treemap的复杂度是logn,总的时间复杂度会退化成线性的
回复 支持 1 反对 0

使用道具 举报

hitowings 发表于 2016-3-16 05:35:17 | 显示全部楼层
楼主怎么设计的?有时间复杂度要求么?感觉可以用BST
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-16 06:15:12 | 显示全部楼层
hitowings 发表于 2016-3-16 05:35
楼主怎么设计的?有时间复杂度要求么?感觉可以用BST

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

用BST也可以,但是如果要你实现的话,不就是自己给自己找麻烦吗。
回复 支持 反对

使用道具 举报

 楼主| shumin0809 发表于 2016-3-16 06:30:24 | 显示全部楼层
kinggarden2001 发表于 2016-3-16 06:15
我觉得用Hashmap + sorted list 可以,如果要recent也要快的话再存一份数据到queue里。
. more info on 1point3acres.com
用BST也可以, ...
. from: 1point3acres.com/bbs
我的想法应该跟你一样 用hashmap实现各种operation。然后用sorted list 找最大最小。. Waral 鍗氬鏈夋洿澶氭枃绔,
但是估计沟通得不好 面试官基本没怎么鸟我。面试差不多40分钟就急着挂电话了。唉=.=
回复 支持 反对

使用道具 举报

aaronnicholas 发表于 2016-3-16 06:41:11 | 显示全部楼层
add(2,5) max:7, min:4, recent:7 这个recent 不是应该是5 么?
回复 支持 反对

使用道具 举报

 楼主| shumin0809 发表于 2016-3-16 07:02:33 | 显示全部楼层
aaronnicholas 发表于 2016-3-16 06:41. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
add(2,5) max:7, min:4, recent:7 这个recent 不是应该是5 么?

不是的。most recent 不是指最新加入。而是指最近的(根据time 来定, 越大代表越近)。在这里面 4是最大的,所以它对应的值7是most recent value.
回复 支持 反对

使用道具 举报

aaronnicholas 发表于 2016-3-16 07:59:27 | 显示全部楼层
shumin0809 发表于 2016-3-16 07:02
不是的。most recent 不是指最新加入。而是指最近的(根据time 来定, 越大代表越近)。在这里面 4是最大 ...

那这样的话是不是一个TreeMap 就可以找到most recent time
然后一个LinkedHashMap 根据price sort就可以得到最大最小值了
回复 支持 反对

使用道具 举报

aaronnicholas 发表于 2016-3-16 07:59:35 | 显示全部楼层
shumin0809 发表于 2016-3-16 07:02
不是的。most recent 不是指最新加入。而是指最近的(根据time 来定, 越大代表越近)。在这里面 4是最大 ...

那这样的话是不是一个TreeMap 就可以找到most recent time. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后一个LinkedHashMap 根据price sort就可以得到最大最小值了
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-16 10:02:38 | 显示全部楼层
我是不是想简单了,用一个hashMap<time, value>和三个整形变量max,min,recent不能解决么?
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-16 10:18:21 | 显示全部楼层
lby1989825 发表于 2016-3-16 10:02
我是不是想简单了,用一个hashMap和三个整形变量max,min,recent不能解决么?

一个hashtable,两个stack分别存最大和最小,借鉴leetcode minStack这道题应该可以
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-16 11:17:40 | 显示全部楼层
lby1989825 发表于 2016-3-16 10:18. visit 1point3acres.com for more.
一个hashtable,两个stack分别存最大和最小,借鉴leetcode minStack这道题应该可以

那Update怎么办呢?
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-3-16 11:22:37 | 显示全部楼层

update和remove是差不多一样的处理啊
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-16 12:24:53 | 显示全部楼层
lby1989825 发表于 2016-3-16 11:22
update和remove是差不多一样的处理啊

楼上的意思估计是stack中间的元素被update怎么办
回复 支持 反对

使用道具 举报

 楼主| shumin0809 发表于 2016-3-16 14:32:07 | 显示全部楼层
lby1989825 发表于 2016-3-16 11:22. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
update和remove是差不多一样的处理啊

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴stack 是不太好的。我一开始想stack就被否定了=.= 因为update很麻烦。
回复 支持 反对

使用道具 举报

wsrrzxl 发表于 2016-3-18 07:28:10 | 显示全部楼层
大家觉得hashmap加三个heap怎么样
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-3-23 01:15:05 | 显示全部楼层
wsrrzxl 发表于 2016-3-18 07:28
大家觉得hashmap加三个heap怎么样

感觉不行,比如最大值的heap从上到下分别存的是7,7,4,现在要删除(4,7),最大值现在应该是5,但是heap里面没有存5
回复 支持 反对

使用道具 举报

Czon 发表于 2016-3-26 03:28:25 | 显示全部楼层
为啥treeMap不行
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-5 09:52:07 | 显示全部楼层
觉得之前的楼上说的三个heap应该是可行的吧
回复 支持 反对

使用道具 举报

ryancooper 发表于 2016-4-5 10:52:51 | 显示全部楼层
最简单粗暴的做法就是可以这么来设计,底层storage可以用doubly linked list(remove的时候可以O(1)),存的是time和value的pair。然后用两个map对time field和value field分别建index,这样所有mutation操作都能bound在O(logn),所有get操作都是O(1)
代码随便写了写,每个方法都写上了简化实现的假设,maybe有可能有corner case,但是这个是我觉得最容易直观的思考方向了
  1. class System { // assume time being used is unique. Waral 鍗氬鏈夋洿澶氭枃绔,
  2. public:
  3.     int getMax() {. from: 1point3acres.com/bbs
  4.         return priceIndex_.rbegin()->first;. visit 1point3acres.com for more.
  5.     }
  6.     鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.     int getMin() {
  8.         return priceIndex_.begin()->first;
  9.     }. 1point 3acres 璁哄潧
  10.    
  11.     int getRecent() {
  12.         return timeIndex_.rbegin()->second->second;
  13.     }
  14.    
  15.     void printCurrentStat() {
  16.         printf("max: %d\t min: %d\t recent: %d\n", getMax(), getMin(), getRecent());
  17.     }
  18.     .1point3acres缃
  19.     void add(long time, int price) {
  20.         // assume the time being added here is a distinct value
  21.         const auto& it = list_.emplace(list_.end(), time, price);
  22.         timeIndex_[time] = it;
  23.         priceIndex_[price] += 1;
  24.     }. more info on 1point3acres.com
  25.    
  26.     void update(long time, int price) {. from: 1point3acres.com/bbs
  27.         // assume the time being updated here exists
  28.         auto& it = timeIndex_[time];
  29.         auto& oldPrice = it->second;. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.         if (--priceIndex_[oldPrice] == 0) {
  31.             priceIndex_.erase(oldPrice);
  32.         }
  33.         oldPrice = price;
  34.         priceIndex_[oldPrice] += 1;
  35.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.    
  37.     void remove(long time) {
  38.         // assume the time being updated here exists
  39.         auto& it = timeIndex_[time];
  40.         int price = it->second;
  41.         list_.erase(it);
  42.         timeIndex_.erase(time);
  43.         if (--priceIndex_[price] == 0) {. 鍥磋鎴戜滑@1point 3 acres
  44.             priceIndex_.erase(price);
  45.         }
  46.     }
  47.     鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  48. private:
  49.     list<pair<long, int>> list_;
  50.     map<long, list<pair<long, int>>::iterator> timeIndex_;. from: 1point3acres.com/bbs
  51.     map<int, int> priceIndex_;
  52. };
复制代码

补充内容 (2016-4-5 10:54):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对于priceIndex,map表示的含义是price和其出现次数
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-26 07:06:07 | 显示全部楼层
heap的话是不是删除比较麻烦,能不能用treemap?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表