Amazon SDE 2 - Coding Challenge - Difficulty (Medium)
2015

You are given an array A, create an another array B all or subarrays of A.

[ Note - Subarrays B are formed by removing zero or more elements from the front or/and back of the original array without changing the order of the remaining element ]

Do a Bitwise OR on the subarrays and get the Kth smallest element

Inputs :
A = [1, 2, 3]
K = 6

Output:
3

Explanation:

  1. Given array A = [1, 2, 3], generate a Array B using A
    B = [ 1, (1, 2), (1, 2, 3), 2, (2, 3), 3]

  2. Now do Bitwise OR among the subarrays, which gives you
    B = [1, 3, 3, 2, 3, 3]

  3. Atlast get the Kth smallest element of B, if K = 6 , from sorted B we will get
    B=[1, 2, 3, 3, 3, 3]
    6th smallest element is 3

Now I am able to solve the problem in Worst Case time complexity, which is below.
But what will be optimized approach for the problem

public static List<Integer> worstCase(int[] A, int K) {
        List<Integer> _or = new ArrayList<>();
        
        for(int i = 0; i < A.length; i++) {
            _or.add(A[i]);
            int prevOr = A[i];
            for(int j = i + 1; j < A.length; j++) {
                prevOr = prevOr | A[j];
                _or.add(prevOr);
            }
        }
        Collections.sort(_or);
        Integer output = _or.get(K);
        return _or;
    }
Comments (7)