一亩三分地论坛

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

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

新鲜的狗狗面试

[复制链接] |试试Instant~ |关注本帖
encorechow 发表于 2016-9-20 10:33:50 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - Other - HR筛选 技术电面 |Otherfresh grad应届毕业生

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

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

x
新人面经贴店面开始时间是今天下午1点,紧张了一上午到最后几分钟感觉脑袋都要冒烟 废话不多说。直接上题. Waral 鍗氬鏈夋洿澶氭枃绔,
题目相当于是带着马甲的merge interval。 问假如有一台机器可以被很多用户通过ssh使用。每个用户使用之后需要report他们使用的time slot。For example:用户A reported [6am, 8am), 用户B reported [1pm, 4pm), 用户C reported [2pm, 6pm)。问这一天还有多少available的time slot。返回所有available的time slot。题目不算难可能因为楼主是new grad。磕磕碰碰也算是解出来了。 follow up brain storm问如何在O(n)内解决。发发面经攒人品。求过求过!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 58, 订阅: 6
mingzhou1987 发表于 2016-9-20 12:56:08 | 显示全部楼层
merge interval + missing range?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-9-20 12:59:10 | 显示全部楼层
想多了,应该就是merge interval。
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-20 13:14:03 | 显示全部楼层
不需要想复杂哈哈,还是一个简化版的merge interval - -
回复 支持 反对

使用道具 举报

omega094 发表于 2016-9-20 13:38:57 | 显示全部楼层
直接开一个length 为 24 的array 然后涂格子就可以。。。。
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-20 13:39:56 | 显示全部楼层
因为一天只有从 0am 到 24pm 所以可以用bucket sort的思路得到 O(n) 的答案对吧?
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-20 13:40:44 | 显示全部楼层
是的。。。开24的array算是follow up。。。
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-20 13:42:58 | 显示全部楼层
Sayings 发表于 2016-9-20 13:39
因为一天只有从 0am 到 24pm 所以可以用bucket sort的思路得到 O(n) 的答案对吧?

我不太了解bucket sort是什么,不过一般跟sort扯上都是nlogn吧。。。想到O(n)申明一个24长度的array就可以了。。把list of list里出现的时间点set成1然后遍历这个array找是0的点。。。
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-20 13:50:37 | 显示全部楼层
encorechow 发表于 2016-9-20 13:42
我不太了解bucket sort是什么,不过一般跟sort扯上都是nlogn吧。。。想到O(n)申明一个24长度的array就可 ...

嗯。。bucket sort就是这个填格子的思路。。O(n) :)
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-20 14:00:00 | 显示全部楼层
Sayings 发表于 2016-9-20 13:50
嗯。。bucket sort就是这个填格子的思路。。O(n) :)

了解了:P, 楼主比较水知道的少哈哈哈
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-9-20 14:09:40 | 显示全部楼层
mingzhou1987 发表于 2016-9-19 20:59
想多了,应该就是merge interval。

难道不需要merge 完以后取不是interval的区间吗?
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-20 14:18:39 | 显示全部楼层
samuelling 发表于 2016-9-20 14:09
难道不需要merge 完以后取不是interval的区间吗?

你的merge的时候其实就已经可以直接取available的time slot了,就是说如果end1 < start2, 那么end1和start2就是available的time slot. 更好的解法还是O(n)说的那个bucket sort。
回复 支持 反对

使用道具 举报

bobofarm 发表于 2016-9-21 01:28:37 | 显示全部楼层
use a line to scan from beginning to the end.
回复 支持 反对

使用道具 举报

samuelling 发表于 2016-9-21 03:58:15 | 显示全部楼层
bobofarm 发表于 2016-9-20 09:28
use a line to scan from beginning to the end.

so-called sweep line algorithm
回复 支持 反对

使用道具 举报

PennyLoveLife 发表于 2016-9-22 01:45:26 | 显示全部楼层
请问用户report的时间段是已经按照start开始时间排序好的吗?
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-9-22 02:02:45 | 显示全部楼层
问个naive的问题。这个机器既然可以在同一时间被多个用户使用(比如B和C),那么,available的time slot定义就有点问题了。比如,merge B和C后得到[1pm, 6pm),但是这并不代表这个时间段内不能有其他用户再用了呀。用户D也可以在[2pm, 3pm) 使用吧?还是我哪里理解的有问题?谢谢答复!
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-9-22 04:18:02 | 显示全部楼层
littlebearull 发表于 2016-9-22 02:02
问个naive的问题。这个机器既然可以在同一时间被多个用户使用(比如B和C),那么,available的time slot定 ...

我和你有一样的疑问啊
回复 支持 反对

使用道具 举报

 楼主| encorechow 发表于 2016-9-23 14:03:33 | 显示全部楼层
littlebearull 发表于 2016-9-22 02:02
问个naive的问题。这个机器既然可以在同一时间被多个用户使用(比如B和C),那么,available的time slot定 ...

我感觉他的意思仅仅是说这一天有多少时间段没有被使用过吧,可能是楼主听的没太懂- -
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-9-23 22:57:23 | 显示全部楼层
encorechow 发表于 2016-9-23 14:03. Waral 鍗氬鏈夋洿澶氭枃绔,
我感觉他的意思仅仅是说这一天有多少时间段没有被使用过吧,可能是楼主听的没太懂- -
-google 1point3acres
谢谢回复!嗯嗯,这样的话,就make sense了,
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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