Random Pick (Java)
java\nclass MajorityChecker {\n    private int[] a;\n    private Map<Integer, List<Integer>> map = new HashMap<>();\n\n    public MajorityChecker(int[] a) {\n  
```java\nclass MajorityChecker {\n    private int[] a;\n    private Map<Integer, List<Integer>> map = new HashMap<>();\n\n    public MajorityChecker(int[] a) {\n        this.a = a;\n        int n = a.length;\n        for (int i=0; i<n; i++) {\n            map.putIfAbsent(a[i], new ArrayList<>());\n            map.get(a[i]).add(i);\n        }\n    }\n    \n    private int getOccurence(int l, int r, int x) {\n        List<Integer> list = map.get(x);\n        int i = Collections.binarySearch(list, l);\n        int j = Collections.binarySearch(list, r);\n        if (i < 0) i = ~i;\n        if (j < 0) j = ~j - 1;\n        if (i == list.size()) return 0;\n        return j - i + 1;\n    }\n    \n    private int getRandom(int a, int b){\n        return (int)(Math.random() * (b-a+1)) + a;\n    }\n    \n    public int query(int left, int right, int threshold) {\n        for (int i=1; i<=20; i++) {\n            int x = a[getRandom(left, right)];\n            if (getOccurence(left, right, x) >= threshold) return x;\n        }\n        return -1;\n    }\n}\n```
[]