一亩三分地论坛

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

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

Uber面经 死透透的

[复制链接] |试试Instant~ |关注本帖
BostonYang 发表于 2016-4-15 05:08:53 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完,Security组,就一道题,返回加权随机字母, 输入两个array,["a", "b", "c"], [1,2,3], 后面是前一个的权重,返回一个基于权重的随机字母。。。。就这么简单,题没啥说的,我想说的是,烙印啊,我和你有仇啊,全程听他在咳嗽, 信号超级差加上面试官浓厚的印度口音加上楼主自身听力不行,啥也听不懂啊,这是我目前面过的最差体验,好几次想中途挂电话。。。。

. From 1point 3acres bbs
补充内容 (2016-4-17 01:27):
follow up是调用many times如何优化。。。。

评分

1

查看全部评分

harryhu0705 发表于 2016-4-17 04:52:11 | 显示全部楼层
handsomecool 发表于 2016-4-17 04:21
我也是用第二个解法,不废内存,查找时用二分法,map直接用lower_bound就行了, 如果interviewer非要你写 ...

是啊,我觉得就是见一个hashmap,key是a,b,c,d, value是cumulative weight,然后二分查找
回复 支持 1 反对 0

使用道具 举报

池大侠 发表于 2016-4-17 02:33:21 | 显示全部楼层
Mark6 发表于 2016-4-16 17:26
那如果权重的值很大呢。。或者比如是:0.1237,0.2176,0.410932。。。这样的,然后所有的权重加起来等于 ...

既然是approach..肯定先考虑一个可行的。。 你先说可以这样做。。。 然后再说这个方法的upside 和downside..
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如这题 0.1237 + 0.2176 + 0.4109 = m
. from: 1point3acres.com/bbs
那a 产生的范围就是  [0, 0.1237)/m    b产生的范围是 [0.1237, 0.2176)/m c 产生的 就是[0.2176, 0.4109]/m.鐣欏璁哄潧-涓浜-涓夊垎鍦

这样可以pre process 既然是只preprocess 一次就不存在内存的问题啊 除非这个数组真的很大。。 那就拿两机器
算一遍merge两个hashtable 。-google 1point3acres


回复 支持 1 反对 0

使用道具 举报

池大侠 发表于 2016-4-17 01:32:07 | 显示全部楼层
i don't get it..
感觉是 index = random.randint(1,6)
index = 1 返回a
index = [2,3] 返回b
index [4,5,6] 返回 c
应该就是这样吧。。。。。 O(1) time O(1) space...



类似的还有 用foo function只能生成1-5 问怎么用foo 等proba 生成 1-7
回复 支持 0 反对 1

使用道具 举报

caiqi8877 发表于 2016-4-15 11:30:47 | 显示全部楼层
额,什么叫基于权重的随机字母,不太明白
回复 支持 反对

使用道具 举报

 楼主| BostonYang 发表于 2016-4-15 23:49:44 | 显示全部楼层
caiqi8877 发表于 2016-4-15 11:30.鐣欏璁哄潧-涓浜-涓夊垎鍦
额,什么叫基于权重的随机字母,不太明白

拿我的例子来说, 返回"a"的概率是1/6, "b"是2/6, "c"是3/6
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2016-4-16 01:00:07 | 显示全部楼层
面google面过一样的题
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-4-16 09:21:26 | 显示全部楼层
根据达到某个key的概率和生成排序后的map, 然后用map.upper_bound(rand())就可以吧?

一开始生成map要O(n)
之后每次得到随机字母要O(log(n))
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-4-16 10:22:53 | 显示全部楼层
一朋友也是烙印面,居然开免提,也是听不清,真是给跪了。。。请问LZ是多久拿到Uber的电面的呀?前些天内推完全没消息。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-16 10:38:58 | 显示全部楼层
狂暴CNM地 发表于 2016-4-16 01:00
面google面过一样的题

在Twitter也面到了一样的题。。。
回复 支持 反对

使用道具 举报

 楼主| BostonYang 发表于 2016-4-16 20:58:28 | 显示全部楼层
sheepmiemies 发表于 2016-4-16 10:22
. visit 1point3acres.com for more.一朋友也是烙印面,居然开免提,也是听不清,真是给跪了。。。请问LZ是多久拿到Uber的电面的呀?前些天内推 ...

我是推了好久了。。属于历史遗留的那一部分, 最近好像不招new gra了吧
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-4-16 23:43:17 | 显示全部楼层
BostonYang 发表于 2016-4-16 20:58
我是推了好久了。。属于历史遗留的那一部分, 最近好像不招new gra了吧

这样啊,那就比较合理了。。。是的现在这些明星startup好像也就snapchat在招最后一波new grad,可惜之前跪了。。。
回复 支持 反对

使用道具 举报

harryhu0705 发表于 2016-4-17 01:05:10 | 显示全部楼层
http://blog.csdn.net/ajian005/article/details/19301689
这篇文章感觉还不错,我不知道这个算法还有没优化,感觉可以加上二分查找。希望和大家一起讨论
回复 支持 反对

使用道具 举报

 楼主| BostonYang 发表于 2016-4-17 01:30:02 | 显示全部楼层
harryhu0705 发表于 2016-4-17 01:05
http://blog.csdn.net/ajian005/article/details/19301689 .鏈枃鍘熷垱鑷1point3acres璁哄潧
这篇文章感觉还不错,我不知道这个算法还有没 ...

很好的文章, 我的做法和思路一 一样的,建一个数组放所有元素,烙印接着问,如果调用很多次,如何优化,我觉得要预处理,但想不出什么好办法。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-17 02:10:38 | 显示全部楼层
池大侠 发表于 2016-4-17 01:32
i don't get it..
感觉是 index = random.randint(1,6)
index = 1 返回a

但是权重是作为参数输入到你的函数你的,不是固定的1,2,3。
回复 支持 反对

使用道具 举报

池大侠 发表于 2016-4-17 02:15:28 | 显示全部楼层
Mark6 发表于 2016-4-16 17:10. 1point 3acres 璁哄潧
但是权重是作为参数输入到你的函数你的,不是固定的1,2,3。

那也一样的啊。。  把权重加起来。。 就有随机数的范围了。。 其实是一样的。。。
这样就是要过一遍权重的array 但是如果一直调用的话肯定是o(1)
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-17 02:26:30 | 显示全部楼层
池大侠 发表于 2016-4-17 02:15
那也一样的啊。。  把权重加起来。。 就有随机数的范围了。。 其实是一样的。。。
这样就是要过一遍权重 ...
. From 1point 3acres bbs
那如果权重的值很大呢。。或者比如是:0.1237,0.2176,0.410932。。。这样的,然后所有的权重加起来等于1。。这种很吃内存,或者内存根本都不够肿么破。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-17 02:42:17 | 显示全部楼层
池大侠 发表于 2016-4-17 02:33
既然是approach..肯定先考虑一个可行的。。 你先说可以这样做。。。 然后再说这个方法的upside 和downsid ...

恩,产生一个随机数后,要确定它代表哪个字母,比如产生一个0.35随机数,然后要确定是输出b,搜索还是得O(logn),没法O(1)?. from: 1point3acres.com/bbs

补充内容 (2016-4-17 02:43):
哦,0.35好像应该输出c
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-4-17 04:21:50 | 显示全部楼层
harryhu0705 发表于 2016-4-17 01:05
http://blog.csdn.net/ajian005/article/details/19301689
这篇文章感觉还不错,我不知道这个算法还有没 ...

我也是用第二个解法,不废内存,查找时用二分法,map直接用lower_bound就行了, 如果interviewer非要你写个二分法,也不难。
回复 支持 反对

使用道具 举报

harryhu0705 发表于 2016-4-17 04:51:21 | 显示全部楼层
池大侠 发表于 2016-4-17 02:33
既然是approach..肯定先考虑一个可行的。。 你先说可以这样做。。。 然后再说这个方法的upside 和downsid ...
. more info on 1point3acres.com
如果数组存放不下的话,那么放两个机器来merge最终也没发放下hashtable吧?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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