狗狗店面1018

Job Hunting Interview
, , , , , ,
1

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

Design a class to return a query based on its probability.
Input: dictionary with key = query_name, value = probability
Eg. {a: 0.5, b: 0.2, c: 0.2, d: 0.1}
Output: a or b or c or d with probability stated in the input

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

2

这题就是一道数学题，见过就不难了。
a: 0.5, b: 0.2, c: 0.2, d: 0.1
转换成整数，a:5, b:2, c:2, d:1

Create 一个array 出现几次就有几个元素 arr = [a,a,a,a,a,b,b,c,c,d];
Random rd = new Random;
int index = rd.nextInt(arr.length());
return arr[index];

3

貌似可以做哦，

4

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

5 

// refer to https://tinyurl.com/ybjqfpqy       https://tinyurl.com/ycsc9nlz

import java.util.*;
public class getWithRandom {
    public static void main(String[] args){
        Map<String, Double> myMap = new HashMap<>();
        myMap.put("a", 0.55);
        myMap.put("b", 0.1);
        myMap.put("c", 0.2);
        myMap.put("d", 0.15);
        DistributedRandomStringGenerator q = new DistributedRandomStringGenerator(myMap);
        List<String> ans = new ArrayList<>();
        for(int i=0; i<10000; i++)
            ans.add(q.getRandomString());
 // verify our result
        Map<String, Integer> countMap = new HashMap<>();
        for(String n : ans)
            countMap.put(n, 1 + countMap.getOrDefault(n, 0));

        for(Map.Entry<String, Integer> entry : countMap.entrySet())
            System.out.println(entry.getKey() + ": " + ((double)entry.getValue() / ans.size()));
    }


}

class DistributedRandomStringGenerator{
    private Random rand;
    private double[] cumulative;
    private String[] sArray;
    DistributedRandomStringGenerator(Map<String, Double> probMap){
        rand = new Random();
        cumulative = new double[probMap.size()];
        sArray = new String[probMap.size()];
        int i = 0;
        for(Map.Entry<String, Double> entry : probMap.entrySet()){
            // we don''t want those string whose probability is less than or equal to zero
            if(entry.getValue() > 0){
                sArray[i] = entry.getKey();
                cumulative[i] = entry.getValue() + (i > 0 ? cumulative[i - 1] : 0);
                i++;
            }
        }
    }

    String getRandomString(){
        double r = rand.nextDouble();
        int index = binarySearch(r);
        return sArray[index];
    }

    private int binarySearch(double r){
        int low = 0, high = cumulative.length - 1;
        while(low + 1 < high){
            int mid = low + ((high - low) >> 1);
            if(cumulative[mid] == r)
                return mid;
            else if(cumulative[mid] < r)
                low = mid;
            else
                high = mid;
        }
        if(r > cumulative[low])
            return high;
        return low;
    }
}
6

哇 谢谢层主

7

给您了

8

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

9

{a: 0.5, b: 0.2, c: 0.2, d: 0.1} 为例，可不可以：1.按50%概率决定是否要a，如果决定要，return a 2.如果决定不要，按0.2/(1-0.5)的概率决定要不要b, 如要，return b. 3.如果不要b，按0.2/(1-0.5-0.2)的概率决定要不要c，以此类推…这样总体来说选a概率是1/2, 选b的概率是1/2 * 2/5 = 1/5, 选c的概率是1/2 * 3/5 * 2/3 = 1/5…

10

我觉得你说得对。LC有一道题就是类似的，如果都按数目放进去会超过memory limit。（应该是900）
但其实不用累加啊，他们的和肯定是1。生成一个0-1的浮点数然后看在哪个区间是不是就可以了？

补充内容 (2018-11-10 02:18):
不好意思我才懂了你说累加的意思是为了用二分查找。谢谢谢谢！