## Facebook Interview Question for Software Engineers

• 2

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.

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, 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.

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?

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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!

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

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

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

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.

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 = 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!

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

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];
}``````

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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

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] = 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];
}
}``````

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

``````package careercup;

import java.util.List;
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++)
{
}
}
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++)
{
}
}
}
}

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);
}
}``````

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];
}

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.

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++) {
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));

}
}``````

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]``````

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 = {3,4,5,0,1,2};

prepare(input, 6);

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

return 1;

}``````

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;
}``````

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
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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)
}
}
}
}``````

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]

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]``````

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 - b).
map((x) => x);
}

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)``````

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);
}
}
}

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);
}
}
}
}}

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);
}
}
}
}}

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;
}``````

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];
}``````

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Segment trees

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.

### 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.