Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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.
suppose you don't have O(n^2) memory.
also how do you fetch index k - are all subarrays in hash map sorted?
@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.
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).
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!
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];
}
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)
Could you provide code or some explanation please? Why request is log^2(n) and not just log(n) as in segment trees?
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)
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))
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];
}
}
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);
}
}
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];
}
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));
}
}
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]
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;
}
/**
@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;
}
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
}
}
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)
}
}
}
}
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)
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);
}
}
}
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);
}
}
}
}}
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);
}
}
}
}}
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;
}
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];
}
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).
Create all posssible sorted subways in a matrix or vector of vector, and then for each query
- Anonymous October 05, 2015we can get the required answer in O(1) time with taking the right subset and kith index in that subset.