Create independent intervals and sample
With blacklist passed in, one can imagine we are cutting [0, N) interval to different sub intervals and we are asked to uniform sample from these sub intervals.
With blacklist passed in, one can imagine we are cutting [0, N) interval to different sub intervals and we are asked to uniform sample from these sub intervals. So my proposed solution\n1. Build these sub intervals using List<Pair<Start, End>> inside the constructor\n2. Build a weighted prefix sum for these sub intervals\'s length. If the sub internvals are something like [0,1], [2,4] [5,9], this prefix sum array will be  like [0.2, 0.5, 1.0], \n3. Draw one double uniformly from [0,1], use binary search to find the correponding index in the weighted sum array and find the correponding interval. Then uniformly sample this interval.\n\nPaste code\n```\nimport java.util.*;\n\nclass Solution {\n\n    class Range {\n        int start;\n        int end;\n\n        public Range(int start, int end) {\n            this.start = start;\n            this.end = end;\n        }\n\n        public int getWidth() {\n            return this.end - this.start + 1;\n        }\n\n        @Override\n        public String toString() {\n            return "Range{" +\n                    "start=" + start +\n                    ", end=" + end +\n                    \'}\';\n        }\n    }\n\n    private List<Range> allowedInts;\n    private List<Double> weightedSum;\n    private Random random;\n\n    public Solution(int N, int[] blacklist) {\n        this.allowedInts = buildAllowedIntegers(N, blacklist);\n        int totalSize = N - blacklist.length;\n        this.weightedSum = new ArrayList<>();\n        for (int i = 0; i< this.allowedInts.size(); i++) {\n            Range range = this.allowedInts.get(i);\n            if(i == 0) {\n                this.weightedSum.add(range.getWidth() / ((double) totalSize));\n            } else {\n                this.weightedSum.add(range.getWidth() / ((double) totalSize)\n                        + this.weightedSum.get(this.weightedSum.size() - 1));\n            }\n        }\n        this.random = new Random();\n    }\n\n    private List<Range> buildAllowedIntegers(int N, int[] blacklist) {\n        Arrays.sort(blacklist);\n        List<Range> result = new ArrayList<>();\n        int previousStart = 0;\n        for (int i = 0; i < blacklist.length; i++) {\n            int element = blacklist[i];\n            if (element - 1 >= previousStart) {\n                result.add(new Range(previousStart, element - 1));\n            }\n            previousStart = element + 1;\n        }\n        if (previousStart <= N-1) {\n            result.add(new Range(previousStart, N-1));\n        }\n        return result;\n    }\n\n    public int pick() {\n       double prob = random.nextDouble();\n       // 0.2, 0.5, 0.8, 1.0\n       int binarySearchResult = Collections.binarySearch(weightedSum, prob);\n       int indexToInSert = -1;\n       if (binarySearchResult >= 0) {\n           indexToInSert = binarySearchResult;\n       } else {\n           indexToInSert = -(binarySearchResult + 1);\n       }\n       Range pickedRange = allowedInts.get(indexToInSert);\n       return random.nextInt( pickedRange.end - pickedRange.start + 1) + pickedRange.start;\n    }\n\n    public static void main(String[] args) {\n        Solution solution = new Solution(4, new int[]{0, 2});\n        solution.pick();\n    }\n}\n```
[]