一亩三分地论坛

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

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

OpenX 1st round interview

[复制链接] |试试Instant~ |关注本帖
stephaniede 发表于 2016-9-1 07:17:30 | 显示全部楼层 |阅读模式

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

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

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

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% 然后出题。. visit 1point3acres.com for more.
实现一个getRandom(int[] array)   e.g: int[] array = [12, 17 ,15, 48] not sorted obviously
int getRandom(int[] array) {
    // Your code goes here... 1point3acres.com/bbs
}

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

1st Follow-up:

Given int[] array = [12, 17, 15, 48];
         int[] freq = [ 1, 3, 6, 1];
Requirement: no memory restriction. Core part code O(1) RT.. (You know it... call API)  
So that 12 will have probability of 1/10, 17 has probability of 3/10, 15 has 6/10 , 48 has 1/10.

2nd Follow-up:

Given int[] array = [12, 17, 15, 48];. 1point3acres.com/bbs
         int[] freq = [1, 3000, 500, 3];
这个时间来不及了。就说了下思路。我感觉我说错了。。大家有好的解法么

. 1point 3acres 璁哄潧
补充内容 (2016-9-5 18:35):.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ暂时没有想到2nd followup的解法,求大神帮忙看看

评分

1

查看全部评分

ntooto 发表于 2016-9-6 03:19:10 | 显示全部楼层
请问楼主申的是哪个职位?
回复 支持 反对

使用道具 举报

fish444555 发表于 2016-9-6 04:55:20 | 显示全部楼层
我觉得我思路太简单了,简单到follow1 跟follow2一样解法,感觉应该有错,如果发现请指出
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一问就是获取数组长度n, 然后调用 idx = getRandom(1, n), 直接获取arr[idx - 1],-google 1point3acres

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

使用道具 举报

 楼主| stephaniede 发表于 2016-9-6 09:32:15 | 显示全部楼层
ntooto 发表于 2016-9-5 12:19.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问楼主申的是哪个职位?
. 1point 3acres 璁哄潧
感觉挂了,Senior software engineer -full stack
回复 支持 反对

使用道具 举报

 楼主| stephaniede 发表于 2016-9-6 09:34:04 | 显示全部楼层
fish444555 发表于 2016-9-5 13:55
我觉得我思路太简单了,简单到follow1 跟follow2一样解法,感觉应该有错,如果发现请指出

第一问就是获 ...

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

使用道具 举报

phantom 发表于 2016-9-6 10:31:57 | 显示全部楼层
第一个follow up和第二个follow up的区别在哪里啊?。。。就是权重可能变得很大?
回复 支持 反对

使用道具 举报

 楼主| stephaniede 发表于 2016-9-6 10:35:00 | 显示全部楼层
phantom 发表于 2016-9-5 19:31. 鍥磋鎴戜滑@1point 3 acres
第一个follow up和第二个follow up的区别在哪里啊?。。。就是权重可能变得很大?

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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