【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 710|回复: 3
收起左侧

Fetching minimum with O(1)

[复制链接] |试试Instant~ |关注本帖
multics 发表于 2015-10-24 02:35:26 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@ - 网上海投 - 技术电面 |Other其他

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
本人最近电面碰到一个问题卡壳,求教群内高手。提问题的是一印度主管。

设计一个分配process id的方案,假设process id 从1开始,每次要新的process id时,求以最快的方法从未分配的数目中取得最小的process id,process id在使用结束后会放回未分配队列。

用priority queue/mini heap不是正确答案,因为取走最小的同时重新调整要化O(logn)的时间。考虑O(1)的方案,可以用sorted array/list, 那是把整理的开销O(n)延迟到process id 返回时。有没有可能使取走最小的为O(1), 放回已用的process id 为O(logn) 或O(1)? 谢谢。. more info on 1point3acres.com
. Waral 鍗氬鏈夋洿澶氭枃绔,

withting 发表于 2015-10-24 02:43:45 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
难道是想问min stack?leetcode 原题
回复 支持 反对

使用道具 举报

zxl9171 发表于 2015-10-24 03:15:51 | 显示全部楼层
关注一亩三分地微博:
Warald
withting 发表于 2015-10-24 02:43
难道是想问min stack?leetcode 原题
. from: 1point3acres.com/bbs
不是minStack吧。minsatack只能知道最小,但是不能取走。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-24 09:27:32 | 显示全部楼层
应该可以用bitmap
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-21 23:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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