《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2209|回复: 16
收起左侧

Google电面第二轮

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

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

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

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

x
就一道题

. 鍥磋鎴戜滑@1point 3 acres这样的,两个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 | 显示全部楼层
首先其实这个内存使用变化是离散的,就是说类似一个直方图,而不是抛物线。
. 1point 3acres 璁哄潧
一个job变成两个事件点
Event{
    bool is_in;
    int time;. from: 1point3acres.com/bbs
    int mem_used;. visit 1point3acres.com for more.
}

比如job 从 0开始 10结束,用了200mem
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. 1point 3acres 璁哄潧
排好序之后,line sweep就行了。

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

使用道具 举报

 楼主| mayingjie116 发表于 2015-2-11 07:08:28 | 显示全部楼层
Linzertorte 发表于 2015-2-11 06:40
排好序之后,line sweep就行了。

是的,能否说说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)

list = []
start = 0
end = 1
for i in input:. From 1point 3acres bbs
  list.append((i[0], start, memory))
  list.append((i[0]+duration, end, memory))list = sorted(list, operator.itemgetter(0))
# sweep part:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
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
你这个排序会出问题。你要保证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的开头来更新时间。. From 1point 3acres bbs
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变成两个事件点

想法太妙!忍不住点赞! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我想到的是segment tree, 不过time&space都不如这个算法
回复 支持 反对

使用道具 举报

chenyy0527 发表于 2015-6-28 01:40:36 | 显示全部楼层
timtam85 发表于 2015-3-16 09:52. 1point 3acres 璁哄潧
一个思路:merge interval的思路加上一个window。先按照start time排序,然后第一个就相当于window的left, ...

这样感觉会有问题。有的job开始得晚结束得早,那么你在移动左边界的时候就会被开始得早结束得晚的job卡主,从而没办法继续检查。
当然你也可以要求全部检查,但是这样也就失去了边界的意义,因为你不记得下次应该从哪里开始
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 16:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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