一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 1878|回复: 6
收起左侧

OpenX 1st round interview

[复制链接] |试试Instant~ |码农类general, 美国面经, openx, 面试经验
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (133)
 
 
2% (3)    👎

2016(7-9月) 码农类General 硕士 全职@OpenX - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
上周被放鸽子了。今天才面完。感觉一面简单。求二轮电面。。 给一个API 叫getRandom(int start, int end) with equal frequency to get any number in this range, for example getRandom(1,4) ,should get 1, 2 , 3, 4 each has a probability of 25% 然后出题。
实现一个getRandom(int[] array)   e.g: int[] array = [12, 17 ,15, 48] not sorted obviously
int getRandom(int[] array) {
    // Your code goes here..
}

Requirement: O(1) RT, and every element should have equal probability of 25% in this example.

1st Follow-up:

Given int[] array = [12, 17
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
  int[] freq = [1, 3000, 500, 3];
这个时间来不及了。就说了下思路。我感觉我说错了。。大家有好的解法么


补充内容 (2016-9-5 18:35):
LZ暂时没有想到2nd followup的解法,求大神帮忙看看

评分

参与人数 1大米 +50 收起 理由
candy_shmily + 50

查看全部评分


上一篇:Snapchat Video面试 AUG_31
下一篇:求问一道推特面经设计题
我的人缘0
ntooto 2016-9-6 03:19:10 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (24)
 
 
11% (3)    👎
请问楼主申的是哪个职位?
回复

使用道具 举报

我的人缘0
fish444555 2016-9-6 04:55:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (26)
 
 
0% (0)    👎
我觉得我思路太简单了,简单到follow1 跟follow2一样解法,感觉应该有错,如果发现请指出

第一问就是获取数组长度n, 然后调用 idx = getRandom(1, n), 直接获取arr[idx - 1],

1st, F-up
把上面的n 变成是频率的总和,例如例子是 n = 1 + 3 + 6 + 1, 然后同一问的方法,但是求出 idx 后,需要遍历 freq 数组,直到idx > freq 或到达最后元素为止,我感觉是 起码 O(n), 请LZ解释怎样O(1)
回复

使用道具 举报

我的人缘0
 楼主| stephaniede 2016-9-6 09:32:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (133)
 
 
2% (3)    👎
ntooto 发表于 2016-9-5 12:19
请问楼主申的是哪个职位?

感觉挂了,Senior software engineer -full stack
回复

使用道具 举报

我的人缘0
 楼主| stephaniede 2016-9-6 09:34:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (133)
 
 
2% (3)    👎
fish444555 发表于 2016-9-5 13:55
我觉得我思路太简单了,简单到follow1 跟follow2一样解法,感觉应该有错,如果发现请指出

第一问就是获 ...

对的,前两问都要O(n),我写的有歧义,那个O(1)指的是只能call 一次API,我当时不相信会这么简单。 觉得面试官想听第三问,感觉自己已跪。
回复

使用道具 举报

我的人缘0
phantom 2016-9-6 10:31:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (36)
 
 
5% (2)    👎
第一个follow up和第二个follow up的区别在哪里啊?。。。就是权重可能变得很大?
回复

使用道具 举报

我的人缘0
 楼主| stephaniede 2016-9-6 10:35:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (133)
 
 
2% (3)    👎
phantom 发表于 2016-9-5 19:31
第一个follow up和第二个follow up的区别在哪里啊?。。。就是权重可能变得很大?

如果都是新建一个array,用权重代表的值去扩充,那么这道题真的没什么可讨论的。 我觉得面试官想听新的思路
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-3 22:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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