新出炉的狗家电二面

听起来像是一个中国姐姐（口音）给我出的题也很简单啊。
只不过我脑子死的很。。。想半天想不出来。。。。

姐姐还给我好多个提示。

我用的是python

题：
given an array=[1,2,3,4,5], so the sum will be 15 in total.
return random number from the array based on the probability.
e.g. 1->1/15
       2->2/15
所以每次run random(array) output will be different.
2就会有2/15次的机会成为

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

[size=13.3333px]感觉自己基础不是很好啊：PPPPP。大神看了能不能告知一般test case会要什么才对啊。？？？求告知~~~
[size=13.3333px]就这样，祝各位好运。我也要振作起来了！！！！！

1. public static int find(int[] array){
   
2.                 int[] sum=new int[array.length];
   
3.                 sum[0]=array[0];
   
4.                 for(int i=1;i<array.length;i++)sum[i]=array[i]+sum[i-1];
   
5.                 int start=0;
   
6.                 int end=sum.length-1;
   
7.                 int location=-1;
   
8.                 int target=(int)(Math.random()*(sum[array.length-1]-sum[0]+1))+sum[0];
   
9.                 while(start<end){
   
10.                         int mid=start+(end-start)/2;
    
11.                         if(sum[mid]==target){
    
12.                                 location=mid;
    
13.                                 break;
    
14.                         }else if(sum[mid]<target) {
    
15.                                 start=mid+1;
    
16.                         }else{
    
17.                                 end=mid;
    
18.                         }
    
19.                 }
    
20.                 if(location==-1)location=start;
    
21.                 if(location==0)return sum[0];
    
22.                 else return sum[location]-sum[location-1];
    
23.                
    
24.         }

复制代码

partial sum 然后二分找区间？

楼主你是女性程序员吧？

楼主怎么做的？

存partial sums， 可以做到logn

是我没理解题意吗。。。。先排序，把一样的值数出来分别多少个，然后一个vector保留累积的sum(长度是 不同的值的个数，但是sum要算每个值的所有个数)，然后每次求rand(0,1)，看落在哪里行不行

补充内容 (2016-10-7 01:02):
。。并不需要排序

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Reservoir Sampling

xihaokai1 发表于 2016-10-7 00:22
存partial sums， 可以做到logn

言简意赅，点到关键…

对了，后面有说， 不管Time。space如何改进？。