[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2309|回复: 16
收起左侧

Google电面第二轮

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

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

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

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

x
就一道题. more info on 1point3acres

这样的,两个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变成两个事件点
Event{
    bool is_in;
    int time;. 1point3acres
    int mem_used;
}

比如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
排好序之后,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的变种, 我没说错吧。。。
-google 1point3acres
对,和那题挺像的,但是输出不一样
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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:-google 1point3acres
  list.append((i[0], start, memory)).本文原创自1point3acres论坛
  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:. more info on 1point3acres
    max_so_far += i[2]
    if max_so_far > total_memory: return False
  if i[1] == end:
    max_so_far -= i[2]. from: 1point3acres

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). 没有前面提供的优化~-google 1point3acres
回复 支持 反对

使用道具 举报

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. From 1point 3acres bbs
首先其实这个内存使用变化是离散的,就是说类似一个直方图,而不是抛物线。. more info on 1point3acres

一个job变成两个事件点

想法太妙!忍不住点赞!
我想到的是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卡主,从而没办法继续检查。. From 1point 3acres bbs
当然你也可以要求全部检查,但是这样也就失去了边界的意义,因为你不记得下次应该从哪里开始
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-25 23:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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