狗狗店面1018

新鲜店面面经，美国小哥话很多很和善。

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

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

很简单的design题（为什么狗狗店面现在是这种level。。），不过没什么做这种题的经验，答得比较糟糕吧（毕竟最后被good luck了），那就good luck on my other applications吧！攒人品啦！！

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

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

貌似可以做哦，

来自一亩三分地官方APP

如果可以帮到正在准备面试的你，跪求高抬贵手，随手加米呀！求职季都不容易。。。

1. // refer to https://tinyurl.com/ybjqfpqy       https://tinyurl.com/ycsc9nlz
   
2. 
   
3. import java.util.*;
   
4. public class getWithRandom {
   
5.     public static void main(String[] args){
   
6.         Map<String, Double> myMap = new HashMap<>();
   
7.         myMap.put("a", 0.55);
   
8.         myMap.put("b", 0.1);
   
9.         myMap.put("c", 0.2);
   
10.         myMap.put("d", 0.15);
    
11.         DistributedRandomStringGenerator q = new DistributedRandomStringGenerator(myMap);
    
12.         List<String> ans = new ArrayList<>();
    
13.         for(int i=0; i<10000; i++)
    
14.             ans.add(q.getRandomString());
    
15. // verify our result
    
16.         Map<String, Integer> countMap = new HashMap<>();
    
17.         for(String n : ans)
    
18.             countMap.put(n, 1 + countMap.getOrDefault(n, 0));
    
19. 
    
20.         for(Map.Entry<String, Integer> entry : countMap.entrySet())
    
21.             System.out.println(entry.getKey() + ": " + ((double)entry.getValue() / ans.size()));
    
22.     }
    
23. 
    
24. 
    
25. }
    
26. 
    
27. class DistributedRandomStringGenerator{
    
28.     private Random rand;
    
29.     private double[] cumulative;
    
30.     private String[] sArray;
    
31.     DistributedRandomStringGenerator(Map<String, Double> probMap){
    
32.         rand = new Random();
    
33.         cumulative = new double[probMap.size()];
    
34.         sArray = new String[probMap.size()];
    
35.         int i = 0;
    
36.         for(Map.Entry<String, Double> entry : probMap.entrySet()){
    
37.             // we don't want those string whose probability is less than or equal to zero
    
38.             if(entry.getValue() > 0){
    
39.                 sArray[i] = entry.getKey();
    
40.                 cumulative[i] = entry.getValue() + (i > 0 ? cumulative[i - 1] : 0);
    
41.                 i++;
    
42.             }
    
43.         }
    
44.     }
    
45. 
    
46.     String getRandomString(){
    
47.         double r = rand.nextDouble();
    
48.         int index = binarySearch(r);
    
49.         return sArray[index];
    
50.     }
    
51. 
    
52.     private int binarySearch(double r){
    
53.         int low = 0, high = cumulative.length - 1;
    
54.         while(low + 1 < high){
    
55.             int mid = low + ((high - low) >> 1);
    
56.             if(cumulative[mid] == r)
    
57.                 return mid;
    
58.             else if(cumulative[mid] < r)
    
59.                 low = mid;
    
60.             else
    
61.                 high = mid;
    
62.         }
    
63.         if(r > cumulative[low])
    
64.             return high;
    
65.         return low;
    
66.     }
    
67. }
    

复制代码

woshiqingwa 发表于 2018-10-21 12:03
这题就是一道数学题，见过就不难了。
a: 0.5, b: 0.2, c: 0.2, d: 0.1
转换成整数，a:5, b:2, c:2, d:1

哇 谢谢层主

woshiqingwa 发表于 2018-10-21 12:03
这题就是一道数学题，见过就不难了。
a: 0.5, b: 0.2, c: 0.2, d: 0.1
转换成整数，a:5, b:2, c:2, d:1

给您加米了

dengzeyu147 发表于 2018-10-22 12:19
给您加米了

我觉得累加然后二分查找随机数所在区间的方法比较好，按照比例generate array然后random取里面的元素space要求太高。也不定能handle所有小数

您好！
本帖隐藏的内容需要积分高于 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