[Java] Solution using weighted intervals
Algorithm:\nPreprocessing: \n1. Generate all whitelisted intervals in form [start, end];\n2. Generate array of weights of these intervals, where weight is the l
**Algorithm:**\nPreprocessing: \n1. Generate all whitelisted intervals in form `[start, end]`;\n2. Generate array of weights of these intervals, where weight is the length of interval;\n3. Calculate prefix sum for the weights, so each sum is the number of elements in this and all previous intervals (required for picking interval with weight)l.\n\nPick:\n1. Choose a random number from `[0, number of whitelisted numbers)`;\n2. Find an interval where that number falls in (as intervals are weighted, probability of chosing an interval is equal to the number of elements in it);\n3. Choose a random number from that interval.\n\nI used binary search for finding weighted interval. I simply searched for the first interval with prefixed weight (i.e. sum of its weight and all previous ones) is greater than chosen number.\n\n```\nclass Solution {\n    \n    List<int[]> intervals;\n    int[] a;\n\n    public Solution(int n, int[] blacklist) {\n        Arrays.sort(blacklist);\n        int min = 0, max = n - 1;\n        intervals = new ArrayList<>();\n        for (int i: blacklist) {\n            if (i - min > 0) {\n                intervals.add(new int[] {min, i - 1});\n                max = i - 1;\n            }\n            \n            min = i + 1;\n        }\n        \n        if (min < n) {\n            intervals.add(new int[] {min, n - 1});\n            max = n - 1;\n        }\n        \n        a = new int[intervals.size()];\n        a[0] = intervals.get(0)[1] - intervals.get(0)[0] + 1;\n        for (int i = 1; i < a.length; ++i) {\n            a[i] = intervals.get(i)[1] - intervals.get(i)[0] + 1 + a[i - 1];\n        }\n    }\n    \n    public int pick() {\n        int n = (int)(Math.random() * a[a.length - 1]);\n        int l = 0, r = a.length - 1;\n        while (l < r) {\n            int m = (l + r) / 2;\n            if (n < a[m]) {\n                r = m;\n            } else {\n                l = m + 1;\n            }\n        }\n        \n        int[] interval = intervals.get(l);\n        return (int)(Math.random() * (interval[1] - interval[0] + 1) + interval[0]);\n    }\n}\n\n/**\n * Your Solution object will be instantiated and called as such:\n * Solution obj = new Solution(n, blacklist);\n * int param_1 = obj.pick();\n */\n```
['Binary Tree', 'Java']