推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1029|回复: 6
收起左侧

OpenX 1st round interview

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

2016(7-9月) 码农类 硕士 全职@OpenX - 网上海投 - 技术电面 |Otherfresh 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, 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:
. more info on 1point3acres.com
Given int[] array = [12, 17, 15, 48];
         int[] freq = [1, 3000, 500, 3];
这个时间来不及了。就说了下思路。我感觉我说错了。。大家有好的解法么

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

评分

1

查看全部评分

ntooto 发表于 2016-9-6 03:19:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
请问楼主申的是哪个职位?
回复 支持 反对

使用道具 举报

fish444555 发表于 2016-9-6 04:55:20 | 显示全部楼层
关注一亩三分地微博:
Warald
我觉得我思路太简单了,简单到follow1 跟follow2一样解法,感觉应该有错,如果发现请指出

第一问就是获取数组长度n, 然后调用 idx = getRandom(1, n), 直接获取arr[idx - 1],. From 1point 3acres bbs
. 1point 3acres 璁哄潧
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
请问楼主申的是哪个职位?

感觉挂了,Senior software engineer -full stack
回复 支持 反对

使用道具 举报

 楼主| stephaniede 发表于 2016-9-6 09:34:04 | 显示全部楼层
fish444555 发表于 2016-9-5 13:55.1point3acres缃
我觉得我思路太简单了,简单到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. more info on 1point3acres.com
第一个follow up和第二个follow up的区别在哪里啊?。。。就是权重可能变得很大?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-24 16:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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