一亩三分地论坛

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

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

Google电面第二轮

[复制链接] |试试Instant~ |关注本帖
mayingjie116 发表于 2015-2-11 06:10:33 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

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

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

x
就一道题

这样的,两个input,第一个是一个机器的total_mem,第二个是一堆job,每个job包含starting_time,duration,mem_needed,mem_needed就是说这个工作需要这么多的memeory。要求是输出bool,表示是否在任意时间内,所有重叠工作的memory总和都不能超过total_mem。也就是测试这个机器的total_mem够不够大。

求思路,求解答。
Linzertorte 发表于 2015-2-11 07:17:14 | 显示全部楼层
首先其实这个内存使用变化是离散的,就是说类似一个直方图,而不是抛物线。

一个job变成两个事件点. more info on 1point3acres.com
Event{.鐣欏璁哄潧-涓浜-涓夊垎鍦
    bool is_in;
    int time;-google 1point3acres
    int mem_used;
}

比如job 从 0开始 10结束,用了200mem. from: 1point3acres.com/bbs
Event{true,0,200}, Event{false,10,200}
按照time排序,time相同,is_in = false的优先。

然后你扫过去, is_in=true的你就加mem,is_in=false的你就-mem.每个事件点,你会加或减一次,每加或减一次后,就check是不是超过总的。

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

Linzertorte 发表于 2015-2-12 03:59:08 | 显示全部楼层
mj2009 发表于 2015-2-11 07:27
suppose input is a list of jobs, each job is a triple (start_time, duration, memory)

list = []

你这个排序会出问题。你要保证end的先减。否则你会误以为交界点超载。
回复 支持 1 反对 0

使用道具 举报

yapingchen1990 发表于 2015-2-11 06:35:48 | 显示全部楼层
是merge interval的变种, 我没说错吧。。。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-2-11 06:40:36 | 显示全部楼层
排好序之后,line sweep就行了。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-2-11 06:48:16 | 显示全部楼层
Linzertorte 发表于 2015-2-11 06:40
排好序之后,line sweep就行了。

为什么上班的时候可以刷面经
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2015-2-11 07:08:28 | 显示全部楼层
Linzertorte 发表于 2015-2-11 06:40
排好序之后,line sweep就行了。
. 1point 3acres 璁哄潧
是的,能否说说line sweep里怎么做吗?
回复 支持 反对

使用道具 举报

 楼主| mayingjie116 发表于 2015-2-11 07:10:47 | 显示全部楼层
yapingchen1990 发表于 2015-2-11 06:35
是merge interval的变种, 我没说错吧。。。

对,和那题挺像的,但是输出不一样
回复 支持 反对

使用道具 举报

mj2009 发表于 2015-2-11 07:27:32 | 显示全部楼层
suppose input is a list of jobs, each job is a triple (start_time, duration, memory).1point3acres缃

list = []
start = 0
end = 1. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
for i in input:
  list.append((i[0], start, memory)). visit 1point3acres.com for more.
  list.append((i[0]+duration, end, memory))list = sorted(list, operator.itemgetter(0))
# sweep part:. 1point 3acres 璁哄潧
max_so_far = 0
for i in list:
  if i[1] == start:
    max_so_far += i[2]
    if max_so_far > total_memory: return False
  if i[1] == end:
    max_so_far -= i[2]
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
return True
回复 支持 反对

使用道具 举报

mj2009 发表于 2015-2-12 04:13:18 | 显示全部楼层
Linzertorte 发表于 2015-2-12 03:59.鏈枃鍘熷垱鑷1point3acres璁哄潧
你这个排序会出问题。你要保证end的先减。否则你会误以为交界点超载。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
确实,还要另外写个sort,把end也考虑进去。
回复 支持 反对

使用道具 举报

bobingmm 发表于 2015-3-16 07:29:05 | 显示全部楼层
每个job有一个time interval, sorted according to start time, loop each interval, for each interval, loop previous interval to see if previous jobs ended. Calculate memory and compare with total memory. Time complexity will be O(n^2). 没有前面提供的优化~
回复 支持 反对

使用道具 举报

Justice 发表于 2015-3-16 07:38:45 | 显示全部楼层
维护两个 priority_queue,第一个按照 start time 排序,第二个按照end time排序。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
把所有job放进第一个 queue,第二个刚开始空。每次比较两个queue的开头来更新时间。
if (Q1.top() < Q2.top) Q1.pop();mem+;Q2.push()
if (Q2.top() <= Q1.top) Q2.pop();mem-;
任意时刻 mem > 要求,return 0;
最后 return 1;
复杂度 (N*log(N))
回复 支持 反对

使用道具 举报

timtam85 发表于 2015-3-16 09:52:03 | 显示全部楼层
一个思路:merge interval的思路加上一个window。先按照start time排序,然后第一个就相当于window的left,然后边移动右边界边计算local mem usage,如果遇到当前的start time大于left object的end time,就往右移动left同时更新local mem usage
回复 支持 反对

使用道具 举报

leo524891010 发表于 2015-6-16 15:19:14 | 显示全部楼层
Linzertorte 发表于 2015-2-11 07:17
首先其实这个内存使用变化是离散的,就是说类似一个直方图,而不是抛物线。

一个job变成两个事件点

这个想法很是精妙
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-25 13:42:41 | 显示全部楼层
Linzertorte 发表于 2015-2-11 07:17
首先其实这个内存使用变化是离散的,就是说类似一个直方图,而不是抛物线。

一个job变成两个事件点
.鏈枃鍘熷垱鑷1point3acres璁哄潧
想法太妙!忍不住点赞!
我想到的是segment tree, 不过time&space都不如这个算法
回复 支持 反对

使用道具 举报

chenyy0527 发表于 2015-6-28 01:40:36 | 显示全部楼层
timtam85 发表于 2015-3-16 09:52
一个思路:merge interval的思路加上一个window。先按照start time排序,然后第一个就相当于window的left, ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这样感觉会有问题。有的job开始得晚结束得早,那么你在移动左边界的时候就会被开始得早结束得晚的job卡主,从而没办法继续检查。
当然你也可以要求全部检查,但是这样也就失去了边界的意义,因为你不记得下次应该从哪里开始
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-6-28 02:13:25 | 显示全部楼层
其实就是Weighted Job Schedule的变种吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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