A facebook question from careercup

  • 2

    This is a question from careercup:

    You are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
    Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.
    E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.

    Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.

    Among the proposed solutions, I think the best is quickselect ( query time complex: O(b-a), space complex: no extra space, preprocessing time complex: none)

    I am confused by this questions since there seems no way to improve the query time complex by doing any preprocessing.

    Anybody have any insight on how to use preprocessing to improve the query TC? Thanks.

  • 0

    There's a trivial way to improve it to O(1)... just precompute the answers to all possible queries.

    Quick googling found this. Says O(log n) query time and O(n log n) preprocessing time. And contains references to other approaches.

  • 0
    This post is deleted!

  • 1

    The problem can be solved by creating a segment tree and storing the sorted array for every interval. This can be done in O(n^2). There are ~2n nodes in total in the interval tree. For every interval, sorted output can be created from its children in O(n) just like its done in merge sort. So preprocessing takes O(n^2) time and O(nlogn) space.
    For every request can be broken down in intervals. For ex- an array of size 16 and request [4-12], request can be broken down into intervals [4-7],[8-11] and [12]. We need to find the Kth statistic of these sorted arrays. In general, a query can be broken down into atmax logn intervals. TC of finding Kth statistic of H sorted arrays of total size n is logn *H. Here H is logn hence, TC to serve a request is O(logn *logn).

  • 0

    Thanks for all answers. It is very helpful. Here is another link I just found: http://stackoverflow.com/questions/26296624/order-statistic-on-intervals

  • 0

    Isn't this problem similar to finding Kth largest element in an unsorted array ? In our case, the unsorted array starts from [a:b] of the original array. In that case the complexity of each query can be done in O(b - a + 1) ?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.