Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

Create all posssible sorted subways in a matrix or vector of vector, and then for each query
we can get the required answer in O(1) time with taking the right subset and kith index in that subset.

- Anonymous October 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

For pre-processing, We can use HashMap with the combination of array of lists
We create and store lists for each index of given array and for each lengths.

For instance, in map[0], we would store [0-1],[0-2].. so on, then retrieving is just O(1), how? Lets say, a = 2, b = 5 and k = 2. Then in the map we go to map[a](2 in our case), we fetch index (b-a-1) from the list of arrays, 5-2-1 = 2 in our case, once we have the array, we fetch index k of that array.

- justaguy October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

suppose you don't have O(n^2) memory.
also how do you fetch index k - are all subarrays in hash map sorted?

- emb October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@emb, during the pre-processing step, we sort the arrays after fetching the array from the hashmap, then fetch the index.

Regarding not having O(n^2) memory, not sure, people below here have mentioned QuickSelect, but that's for retrieving the Kth smallest element. If I understand the example given in the question correctly, the question is asking to just fetch the Kth index not the "Kth smallest". I understand Kth-order statistics is Kth-smallest, but example says Kth index, so I answered based on that.

Anyway, if it is K-th smallest, then yes, QuickSelect is better solution with bounds from a to b.

- justaguy October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant, we sort the arrays when we are "storing the arrays in the hashMap " not after fetching the array, then it will be O(n).

- justaguy October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just ignore the part in my comment where I'm talking about K-th order statistic. I've been multi-tasking and didn't pay much attention that I was questioning my own answer haha!

- justaguy October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Call Quick select, but bound it on indices a and b

- SK October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

QuickSelect does not completely sort the range, and the problem says to return both the sorted range and the Kth element in the sorted range, doesn't it? Unless I misunderstood the problem.

- blckembr October 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use Quick Select, it runs in O(n) time, and gives you the kth order statistic.

- Anonymous October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It runs in O(k) where is the range length. If preprocessing cannot improve time complexity (e.g. O(lgk)), I don't see why we need it.

- jiangok2006 October 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Create an array indexArray that contains, for each index i, the position at which i occurs.
E.g. if our initial permutation is {3 4 2 5 1 0}, indexArray becomes {5 4 2 0 1 3} (i.e., 0 is at position 5 thus indexArray[0] = 5, etcetera).

Now suppose we need the k-th order statistic of a range [begin, end]. We now iterate through indexArray, and each time we encounter a value within the range [begin, end], the index tells us which number is there. Moreover, the order in which we encounter these numbers, is sorted! Thus, if we need the 2nd order statistic of the range [1,4] (i.e. the sub array {4 2 5 1} we go through indexArray. The first number that is within that range is 4, which is at position 2 (the 0th order statistic). The second we encounter is 2, which is at position 2 (the 1st order statistic). The third we encounter is 1, which is at position 4 (the 2nd order statistic).

Preprocessing time is N. Query time is also N. No need to sort, create trees, hash maps or whatever else was suggested.

Crucial here is that the input array is a permutation, and not an array containing arbitrary values!

- TR October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a 2D array of lists, dp[N][N], where dp[i][j] contains the sorted list of subarray [i, j]. dp[i][j] can be constructed easily from dp[i][j-1] in O(N) time so overall time complexity is O(N^3).

- windrunner October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, implementation

int getKthElementFromSortedSubarray(vector<int> arr, int a, int b, int k) {
	vector<int> subarray;

	if (a < 0 || b < 0 || a >= b || k > (b - a) || a >= arr.size() || b > arr.size()) return -1;

	subarray.assign(arr.begin() + a, arr.begin() + b);
	sort(subarray.begin(), subarray.end());
	return subarray[k];
}

- kyduke October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can use segment tree to solve the problem. In every node we will store part of the array in sorted order, in this case we can build segment tree in O(nlogn), and answer each query in O(log^2n). memory usage will be O(nlogn)

- Darkhan.Imangaliev October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you provide code or some explanation please? Why request is log^2(n) and not just log(n) as in segment trees?

- emb October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is wrong with segment tree? Why the -1 vote?
it is not going to be Log(N) as in segment tree, because usually segment trees are used to combine single values stored at nodes, for example sums of sub ranges, min of range, etc. In this case I am assuming Darkhan's intention was to store sorted sub range which needs to be potentially merged with another sub-range on the same level. I am not sure what O(log^2n) is. My calculation came to O(N). Space is correctly O(nlogn), imagine each item stored in all of its parents (that's at max the height of the full binary tree - logN)

- blckembr October 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with this approach. Time to build segment tree is O(nlog(n)) and memory also O(nlog(n)). I dont understand what O(log^2n) is. But I would say that in worst case we need to merge 2 arrays from each of the log(n) levels. Each merge step would require a max of n comparisons. So query requires O(nlog(n))

- siddharth.bhadkamkar February 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

One way is to preprocess in O(n^3) time to get the answer for all n^3 inputs, then request in O(1) time.

public static class PermutationStatistic {
        int[] array;
        int[][][] R;
        public PermutationStatistic(int[] arr) {
            array = arr;
            R = new int[arr.length][arr.length + 1][arr.length];
            preprocess();
        }

        // O(n^3)
        public void preprocess() {
            // Base case
            for (int i = 0; i < array.length; i++) {
                R[i][i + 1][0] = array[i];
            }
            // Dynamic programming
            for (int i = 0; i < array.length; i++) {
                for (int j = i + 2; j <= array.length; j++) {
                    int value = array[j - 1];
                    int index = 0;
                    boolean found = false;
                    for (int k = 0; k < j - i; k++) {
                        if (!found) {
                        	if (index >= j - i - 1) {
                        		R[i][j][k] = value;
                        	} else {
                                int oldValue = R[i][j - 1][index];
                                if (oldValue < value) {
                                    R[i][j][k] = oldValue;
                                    index++;
                                } else {
                                    R[i][j][k] = value;
                                    found = true;
                                }
                        	}
                        } else {
                            R[i][j][k] = R[i][j - 1][index++];
                        }
                    }
                }
            }
        }

        public int request(int a, int b, int k) {
            return R[a][b][k];
        }
    }

- Anonymous October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package careercup;

import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;

public class PrepSort
{
  private static class Entry implements Comparable<Entry>
  {
    public int index;
    public int value;

    public Entry(int index, int value)
    {
      this.index = index;
      this.value = value;
    }

    public int compareTo(Entry e)
    {
      int c = Integer.compare(value, e.value);
      if (c == 0)
      {
        c = Integer.compare(index, e.index);
      }
      return c;
    }
  }

  private int[] array;
  private List<Integer>[][] lists;

  public PrepSort(int[] array)
  {
    this.array = array;
  }

  @SuppressWarnings("unchecked")
  public void prepare()
  {
    lists = new List[array.length][];
    for (int a = 0; a < array.length; a++)
    {
      lists[a] = new List[array.length - a];
      for (int b = 0; b < array.length - a; b++)
      {
        lists[a][b] = new LinkedList<>();
      }
    }
    Entry[] entries = new Entry[array.length];
    for (int i = 0; i < array.length; i++)
    {
      entries[i] = new Entry(i, array[i]);
    }
    Arrays.sort(entries);
    for (Entry e : entries)
    {
      for (int a = 0; a <= e.index; a++)
      {
        for (int b = e.index - a; b < array.length - a; b++)
        {
          lists[a][b].add(e.value);
        }
      }
    }
  }

  public int request(int a, int b, int k)
  {
    if (b <= a)
    {
      throw new IllegalArgumentException("b must be greater than a");
    }
    if (a < 0)
    {
      throw new IllegalArgumentException("a must be greater than or equal to zero");
    }
    if (b > array.length)
    {
      throw new IllegalArgumentException("b must be less than the length of the array");
    }
    if (k < 0 || k > b - a - 1)
    {
      throw new IllegalArgumentException("k must be between zero and the length of the array - 1");
    }
    if (lists == null)
    {
      prepare();
    }
    return lists[a][b - a - 1].get(k);
  }
}

- Anonymous October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java implementation : using insertion sort to sort the sub array

private static int my_sort(int [] list, int a, int b, int k)
{
int [] result = new int [b - a];
for (int i = a; i < b; i++)
result[i - a] = list[i];

for (int i = 1 ; i < result.length; i++)
{
int number = result[i];
int tmp = i - 1;
for (; tmp >= 0 && result[tmp] >= number; tmp--)
result[tmp + 1] = result[tmp];
result[tmp + 1] = number;
}
return result[k];
}

- skategui October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterate over from arr[a] to arr[b] and build minHeap. Start removing elements while preserving Heap property until reaching Kth element.

- sk October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use max heap to keep track of top k elements between a and b. If the size increases beyond k, remove head. In the end head is the k-th element we need. This will be done in O(m log(m) ) time where m = b-a. If the sub-range is small compared to original array, then this is good. Space is O(k). Assuming k << n where n is total size of array, this solutions looks good.

public class GetKth {

    int[] array;

    public GetKth(int [] input) {
      this.array = input;
    }

    int request(int a, int b, int k) {
      Comparator<Integer> comp = new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
          return o2.compareTo(o1);
        }
      };
      PriorityQueue<Integer> heap = new PriorityQueue<>(k+1, comp);

      for(int i = a; i < b; i++) {
        heap.add(array[i]);
        if(heap.size() > k) {
          heap.remove();
        }
      }
      return heap.peek();
    }

    public static void main(String[] args) {
        int [] array = new int [] {3,4,5,0,1,2};
        GetKth prog = new GetKth(array);
        System.out.println("request returned: " + prog.request(2, 5, 2));
        
    }
  }

- HG October 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

k_map = None


def prepare_k_map(permutation):
    global k_map
    k_map = [[0 for x in range(len(permutation))] for x in range(len(permutation))]
    for i in range(len(permutation)):
        for j in range(len(permutation)):
            k_map[i][j] = sorted(permutation[i:j])


def request(a, b, k):
    global k_map
    if not (a < len(k_map)):
        return None
    if not (b < len(k_map)):
        return None
    ab = k_map[a][b]
    if not (k < len(ab)):
        return None
    return ab[k]

- rizTaak October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution with running time of O(N). Space complexity is also O(N).

prepare takes O(nlogn) due to the quicksort.

find () takes O(N).

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct node {
	int value;
	int pos;
	bool include;
	node (int v, int p): value(v), pos(p), include(false){}
	node(int v): value(v), pos(-1), include(false){}
};

vector<node> org;
vector<node> sorted;

bool compare(node prev, node after)
{
	return prev.value < after.value;
}

void prepare(int * input, int len)
{
	for (int i = 0; i < len; i++)
	{
		org.push_back(node(input[i]));
		sorted.push_back(node(input[i], i));	
	}

	std::sort(sorted.begin(), sorted.end(), compare);

	for (int i = 0; i< len; i++)
	{
		org[sorted[i].pos].pos = i;
	}
}

int find (int s, int e, int pos)
{
	int result = INT_MIN;
	int order = 0;
	for (int i = s; i < e; i++)
	{
		sorted[org[i].pos].include = true;
	}

	for (int i = 0; i < sorted.size(); i++)
	{
		if (!sorted[i].include)
			continue;
		if (order == pos)		
			result = sorted[i].value;
		order++;
		sorted[i].include = false;
	}
	return result;	
}

int main()
{
	int input[6] = {3,4,5,0,1,2};

	prepare(input, 6);

	cout<<"find(2,5,2) = "<< find(2,5,2) <<endl;

	return 1;

}

- hankm2004 October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
   @return sorted(arr[a:b])[k]
   @complexity: runtime - O(n)
                space   - O(n)
*/
int processRequest(int A[], int size, int a, int b, int k)
{
  int tempArray[size];
  memset(tempArray, 0, sizeof(tempArray));
  for(int i=a; i<=b; i++)
    tempArray[A[i]]=1;   
              
  for (int i=0; i< size; i++)
  {
    if (tempArray[i])
    {
      if (!k)
        return i;
      k--;
    }
  }
  return -1;
}

- venkatesh.duggirala December 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

groovy
the request is a simple get by key

class RequestOnArray {

    def array = [3, 4, 5, 0, 1, 2]
    def Map<List<Integer>, List<Integer>> sliceMap

    RequestOnArray() {
        sliceMap = toSliceMap(array)
    }

    static void main(String... args) {
        def requestOnArray = new RequestOnArray()
        println requestOnArray.request(2, 5, 2)
    }

    Integer request(int sliceStart, int sliceEnd, int index) {
        sliceMap.get(array.subList(sliceStart, sliceEnd)).get(index)
    }

    private Map<List<Integer>, List<Integer>> toSliceMap(List<Integer> array) {
        Map<List<Integer>, List<Integer>> sliceMap = new HashMap<>()
        for (int i = 0; i < array.size(); i++) {
            for (int j = i+1; j < array.size()+1; j++) {
                def slice = array.subList(i, j)
                def sortedSlice = new ArrayList(slice).sort()
                sliceMap.put(slice, sortedSlice)
            }
        }
        sliceMap
    }
}

- simona.valenti.0 December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ops...sorry, no need to redefile sliceMap inside toSliceMap()!!

- simona.valenti.0 December 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

groovy bis!

class RequestOnArray {

    def array = [3, 4, 5, 0, 1, 2]
    def Map<List<Integer>, List<Integer>> sliceMap

    RequestOnArray() {
        preprocess(array)
    }

    static void main(String... args) {
        def requestOnArray = new RequestOnArray()
        println requestOnArray.request(2, 5, 2)
    }

    Integer request(int sliceStart, int sliceEnd, int index) {
        sliceMap.get(array.subList(sliceStart, sliceEnd)).get(index)
    }

    private void preprocess(List<Integer> array) {
        sliceMap = new HashMap<>()
        for (int i = 0; i < array.size(); i++) {
            for (int j = i+1; j < array.size()+1; j++) {
                def slice = array.subList(i, j)
                def sortedSlice = new ArrayList(slice).sort()
                sliceMap.put(slice, sortedSlice)
            }
        }
    }
}

- simona.valenti.0 December 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def request2(a,b,k,arr):
tmp = [True]*len(arr)
for f in arr[0:a]:
tmp[f] = False
for b in arr[b:]:
tmp[b] = False
cnt = 0
for t in tmp:
if t == True:
cnt += 1
if cnt == k:
return arr[cnt]

- Anonymous December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def request2(a,b,k,arr):
    tmp = [True]*len(arr)
    for f in arr[0:a]:
        tmp[f] = False
    for b in arr[b:]:
        tmp[b] = False
    cnt = 0
    for t in tmp:
        if t == True:
            cnt += 1
            if cnt == k:
                return arr[cnt]

- Hiroshi December 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the code to consume just copy of the space for indexes.
In worst case scenario request will need two full linear scans on arrays.

In practice with equally distributed requests that should be even lower.


JavaScript/ES6

var data = [3,4,5,0,1,2];

var positionsCache = [];

function preprocess () {
	positionsCache = data.map((x, idx) => [x, idx]).
						 sort((a,b) => a[0] - b[0]).
						 map((x) => x[1]);
}

function request (a, b, k) {
	var i;
	var minValue = data[a], maxValue = data[a];

	for (i = a; i < b; i++) {
		if (data[i] > maxValue)
			maxValue = data[i];
		if (data[i] < minValue)
			minValue = data[i];
	}

	var encounter = 0;
	for (i = minValue; i <= maxValue; i++) {
		if (positionsCache[i] < b && positionsCache[i] >= a)
			encounter++;

		if (encounter == k + 1)
			return data[positionsCache[i]];
	}
}

preprocess()
request(2,5,2)

- gasparch February 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with O(N^2) preprocessing and O(logN) query:
Let suff[i][j] - number of elements smaller than i (0 <= i < N) on suffix ending in position j (0 <= j < N). To answer the query we need find maximum element x from range 0...N-1 for which number of smaller elements in arr[a:b] equals to k. We can do it using binary search. We always find element which is in arr[a:b] because for x + 1 number of smaller elements > k (k + 1, because x is accounted).

Here is an implementation in Java:

import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}

int[][] suff = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
suff[i][j] = arr[j] < i ? 1 : 0;
if (j > 0) {
suff[i][j] += suff[i][j - 1];
}
}
}

int q = in.nextInt();
for (int i = 0; i < q; i++) {
int from = in.nextInt();
int to = in.nextInt() - 1;
int k = in.nextInt();

int l = 0;
int r = n - 1;
int ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int cnt = suff[mid][to];
if (from > 0) {
cnt -= suff[mid][from - 1];
}

if (cnt < k) {
l = mid + 1;
} else if (cnt > k) {
r = mid - 1;
} else {
l = mid + 1;
ans = mid;
}
}
System.out.println(ans);
}
}
}

- Acarus November 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with O(N^2) preprocessing and O(logN) query:


Let suff[i][j] - number of elements smaller than i (0 <= i < N) on suffix ending in position j (0 <= j < N) .


To answer the query we need find maximum element x from range 0...N-1 for which number of smaller elements in arr[a:b] equals to k. We can do it using binary search. We always find element which is in arr[a:b] because for x + 1 number of smaller elements > k (k + 1, because x is accounted).

Here is an implementation in Java:

{{
import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}

int[][] suff = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
suff[i][j] = arr[j] < i ? 1 : 0;
if (j > 0) {
suff[i][j] += suff[i][j - 1];
}
}
}

int q = in.nextInt();
for (int i = 0; i < q; i++) {
int from = in.nextInt();
int to = in.nextInt() - 1;
int k = in.nextInt();

int l = 0;
int r = n - 1;
int ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int cnt = suff[mid][to];
if (from > 0) {
cnt -= suff[mid][from - 1];
}

if (cnt < k) {
l = mid + 1;
} else if (cnt > k) {
r = mid - 1;
} else {
l = mid + 1;
ans = mid;
}
}
System.out.println(ans);
}
}
}
}}

- Acarus November 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with O(N^2) preprocessing and O(logN) query:


Let pref[i][j] - number of elements smaller than i (0 <= i < N) on prefix ending in position j (0 <= j < N) .


To answer the query we need find maximum element x from range 0...N-1 for which number of smaller elements in arr[a:b] equals to k. We can do it using binary search. We always find element which is in arr[a:b] because for x + 1 number of smaller elements > k (k + 1, because x is accounted).

Here is an implementation in Java:
{{
import java.util.Scanner;


public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}


int[][] pref = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
pref[i][j] = arr[j] < i ? 1 : 0;
if (j > 0) {
pref[i][j] += pref[i][j - 1];
}
}
}


int q = in.nextInt();
for (int i = 0; i < q; i++) {
int from = in.nextInt();
int to = in.nextInt() - 1;
int k = in.nextInt();


int l = 0;
int r = n - 1;
int ans = 0;
while (l <= r) {
int mid = l + (r - l) / 2;
int cnt = pref[mid][to];
if (from > 0) {
cnt -= pref[mid][from - 1];
}


if (cnt < k) {
l = mid + 1;
} else if (cnt > k) {
r = mid - 1;
} else {
l = mid + 1;
ans = mid;
}
}
System.out.println(ans);
}
}
}
}}

- Acarus November 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the only correct solution for this problem. During pre-computation step it reverses permutation, e.g. for each possible value 0, 1, 2, ... finds its index in the original array. To serve request we iterate over values in ascending order, e.g. 0, 1, 2, ... and check whether index[val] is in range [a, b). The first found value yeilds 0th statistics in question, second - 1st statistics, etc.

Processing request takes O(n) time since we just iterate over index array. Building index array during pre-computation step takes O(n):

for (int i = 0; i < n; i += 1) {
    int val = a[i];
    index[val] = i;
}

- Arkady Seletsky February 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

java, implementation

int getKthElementFromSortedSubarray(int[] arr, int a, int b, int k) {
		int[] subarray;
		
		if (a < 0 || b < 0 || a >= b || k > (b - a) || a >= arr.length || b > arr.length) return -1;
		
		subarray = new int[b - a];
		System.arraycopy(arr, a, subarray, 0, b - a);
		Arrays.sort(subarray);
		
		return subarray[k];
	}

- kyduke October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Te 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).

- Shane October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Segment trees

- Anonymous October 06, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More