10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 4463|回复: 14
收起左侧

uber电面

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

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

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

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

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

评分

2

查看全部评分

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

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

 楼主| greenbanana 发表于 2016-6-8 12:16:02 | 显示全部楼层
Altynai 发表于 2016-6-7 23:04
用户名会重复吗?如果不会的话可以先把input read进来之后,对登录/登出时间时间做离散化
然后用binary in ...
. 1point3acres.com/bbs
用户名不会重复
我当时就是把时间存到一个list of list里,再访问一次这个list就好了,但需要排序原始input(输入是乱序的),所以复杂度是nlogn. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. from: 1point3acres.com/bbs
例如. from: 1point3acres.com/bbs
[[1.1, 1], [1.3, 1], [2.3, -1], [3.4, -1]]

需要特别注意的是多个用户同时登陆或者登出
回复 支持 1 反对 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 变种?
. 1point 3acres 璁哄潧
应该是的
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-7 22:19:28 | 显示全部楼层
greenbanana 发表于 2016-6-7 21:06. 1point 3acres 璁哄潧
应该是的

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一下就好了

例如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).鏈枃鍘熷垱鑷1point3acres璁哄潧
答案就是sum(1), ...., sum(4)

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

使用道具 举报

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

后天面uber..感谢楼主的两篇面经!
回复 支持 反对

使用道具 举报

 楼主| greenbanana 发表于 2016-6-14 10:15:46 | 显示全部楼层
lirovise 发表于 2016-6-13 09:29
可以把所有登入时间存入一个数组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排序哈细表 ...

这个牛逼。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-21 13:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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