【笔试题】

机试题目注意: 请不要轻视这题目,完成得高质量,绝对不容易。

请独立完成,其他注意事项见下方 FAQ。

请将完成的笔试题以"姓名-后端开发-完成所需时间"格式命名

要求:以下题目答题是 30 分钟,旨在考察面试者多方面的能力。请尽可能多答,

算法题可以任何编程语言的代码(欢迎加关键注释),也可以写出大概想法(得分会减少)。

题目:我们做了一个活动,根据用户的积分来抽奖,用户的积分都保存在一个数组里面

arr = [20, 34, 160, 2...],数组下标就是用户的 ID,则这里:

ID 为 0 的用户的积分是 arr[0] 等于 20 分。

ID 为 1 的用户的积分是 arr[1] 等于 34 分。

请你设计一个抽奖算法,随机抽出一位中奖用户,要求积分越高中奖概率越高。

返回值是中奖用户的 ID

PS: 1<= arr.length <= 50000 且 1<= arr[i] <= 50000

代码写出算法,

并分析其时间复杂度,

为其编写尽量多 unit test。

FAQ:

我可以上网吗?-- 可以,make yourself comfortable。

我可以问别人吗? -- 请独立完成,if you lie , we’ll know sooner or later。

我超过 30 分钟怎么办?请尽量按时提交。如果超过 30 分钟,请标注下完成用时。

我做不完怎么办?没关系请尽量按点顺序完成

完成后,命名好邮件,请发PDF文档,发到邮箱:pat@footprint.network