一亩三分地论坛

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

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

uber电面

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

2016(4-6月) 码农类 硕士 全职@Uber - 网上海投 - 技术电面 |Pass在职跳槽

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

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

x
uber第一轮电面
输入一组数据,用户名字,登录时间,登出时间,输出用户个数在所有登录/登出时间
例如
input = [
['A', 1.1, 2.3],
['B', 1.3, 3.4]
]
output= [
[1.1, 1],
[1.3, 2],. from: 1point3acres.com/bbs
[2.3, 1],
[3.4, 0]
]

评分

2

查看全部评分

leyhzm 发表于 2016-6-27 10:28:30 | 显示全部楼层
遍历输入,存成哈细表,key是时间,value是这个时候登陆的人数(登陆+1,退出-1)。然后按key排序哈细表,loop输出当前value和之前所有value的和就是答案把(只要纪录一个当前总和,然后加上当前值就是)~.1point3acres缃
回复 支持 3 反对 0

使用道具 举报

wtcupup 发表于 2016-6-7 21:04:12 | 显示全部楼层
Meeting room 变种?
回复 支持 反对

使用道具 举报

 楼主| greenbanana 发表于 2016-6-7 21:06:41 | 显示全部楼层
wtcupup 发表于 2016-6-7 21:04
Meeting room 变种?
. more info on 1point3acres.com
应该是的
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-7 22:19:28 | 显示全部楼层

nlgn的复杂度?
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-7 23:00:48 | 显示全部楼层
用户名会重复吗?如果不会的话可以先把input read进来之后,对登录/登出时间时间做离散化
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-7 23:04:32 | 显示全部楼层
用户名会重复吗?如果不会的话可以先把input read进来之后,对登录/登出时间时间做离散化 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后用binary indexed tree维护每个用户,在登录时间set 1,登出时间set -1,时间点上的人数就是sum一下就好了. 1point 3acres 璁哄潧

例如lz的例子,离散化后:
[1.1, 1.3, 2.3, 3,4],下标用1~4表示
binary indexed tree维护的操作就是:
update(1, 1), update(2, 1), update(3, -1), update(4, -1)
答案就是sum(1), ...., sum(4)

time: o(nlogn), space: o(n)
回复 支持 反对

使用道具 举报

 楼主| greenbanana 发表于 2016-6-8 12:16:02 | 显示全部楼层
Altynai 发表于 2016-6-7 23:04
用户名会重复吗?如果不会的话可以先把input read进来之后,对登录/登出时间时间做离散化
然后用binary in ...

用户名不会重复
我当时就是把时间存到一个list of list里,再访问一次这个list就好了,但需要排序原始input(输入是乱序的),所以复杂度是nlogn
. Waral 鍗氬鏈夋洿澶氭枃绔,
例如
[[1.1, 1], [1.3, 1], [2.3, -1], [3.4, -1]]

需要特别注意的是多个用户同时登陆或者登出
回复 支持 反对

使用道具 举报

lirovise 发表于 2016-6-13 09:29:25 | 显示全部楼层
可以把所有登入时间存入一个数组login[] 登出时间存入logout[], 分别排序。用一个counter计数,然后两个index指向两个数组头,每次下一个最接近的时间点在login就counter++,下一个最近的时间点在logout就count--. 思路是想象一个时间轴,然后一个一个把登入登出时间标上去,每次标下一个时间点的时候看看当前的counter,然后根据下一个时间点是登入还是登出来更新counter。
.1point3acres缃
后天面uber..感谢楼主的两篇面经!
回复 支持 反对

使用道具 举报

 楼主| greenbanana 发表于 2016-6-14 10:15:46 | 显示全部楼层
lirovise 发表于 2016-6-13 09:29. From 1point 3acres bbs
可以把所有登入时间存入一个数组login[] 登出时间存入logout[], 分别排序。用一个counter计数,然后两个ind ...

祝面试顺利!
回复 支持 反对

使用道具 举报

z306133123 发表于 2016-6-27 12:33:14 | 显示全部楼层
请问LZ投的是哪一个岗位?Software Engineer - University 2016吗?打算试试,不知道会不会给电面机会,求分享些经验
回复 支持 反对

使用道具 举报

shentc 发表于 2016-6-30 16:48:34 | 显示全部楼层
谢谢楼主 楼主好人
回复 支持 反对

使用道具 举报

Yoyo00 发表于 2016-7-1 04:07:07 | 显示全部楼层
leyhzm 发表于 2016-6-27 10:28
遍历输入,存成哈细表,key是时间,value是这个时候登陆的人数(登陆+1,退出-1)。然后按key排序哈细表 ...

Up this. We can use a TreeMap to save the <key, value> pair, and there will be no need to sort the hash map manually.
回复 支持 反对

使用道具 举报

huwenchang8 发表于 2016-8-19 13:47:49 | 显示全部楼层
leyhzm 发表于 2016-6-27 10:28
遍历输入,存成哈细表,key是时间,value是这个时候登陆的人数(登陆+1,退出-1)。然后按key排序哈细表 ...
.1point3acres缃
这个牛逼。。
回复 支持 反对

使用道具 举报

superbeet 发表于 2016-9-11 14:55:56 | 显示全部楼层
Sorted + Sweep Line
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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