Facebook Interview Question
SDE1sCountry: United States
for the first one,
iterate the array and use hashmap to record A[i] -> min(i, value) and check (i - map[A[i] - 1]) for the largest diff
use O(n) memory and O(n) space
for the second one,
first use hashmap to record A[i] -> i, sort the array as B, replace the value in B with their original index in A. the traverse the array and update the smallest index and largest index (note when smallest is updated the largest is updated to the same value) . then return largest - smallest.
use O(nlgn) time and O(n) space.
eg.
A: 3 4 5 6 0 1 2
B: 4 5 6 0 1 2 3
smallest: 4 4 4 0 0 0 0
largest : 4 5 6 0 1 2 3
diff: 0 1 2 2 2 2 3
then return max diff = 3(i=0, j=3)
Python Solution for the first part:
def largeArrayDiff(nums):
dic, max_dis = dict(), -1
for idx, num in enumerate(nums):
if num-1 in dic:
max_dis = max(max_dis,idx-dic[num-1])
if num not in dic:
dic[num]=idx
print('Max distance {}'.format(max_dis))
return max_dis
def main():
#largeArrayDiff
nums = [1,3,5,7,14,12,15,2,3]
#largeArrayDiff(nums)
1.O(n2) solution
->For each number, start from end checking if it's A[i] + 1 and greater than the max difference found till then, if so ..update it....
2.O(n) solution with O(n) memory
->Use HashMap to store all numbers and its indices.
->In second array traversal, for each number, check if map contains A[i] + 1, and update max difference.
The naive O(N^2) solution would be to loop thru each i, and then loop backwards for each j, and output an (i, j) pair for the first j such that A[j] = A[i] + 1.
function bruteForce(A){
const N = A.length;
const pairs = [];
for (let i = 0; i < N; i++){
for (let j = N - 1; j >= 0; j--){
if (A[j] === A[i] + 1){
pairs.push([i, j]);
break;
}
}
}
return pairs;
}
/*
[1, 0]
[2, 5]
[3, 1]
[4, 6]
[5, 6]
[6, 1]
*/
console.log(bruteForce([5, 4, 1, 3, 2, 2, 3]));
By using O(N) extra space we can get an O(N) time solution. Go thru A, and for each i, store in a hash table M the (A[i], i) key-value pair. So after pre processing, M[x] contains the rightmost index in A that contains x.
function linearSolution(A){
const pairs = [];
const M = new Map();
A.forEach((value, i) => M.set(value, i));
A.forEach((value, i) => {
if (M.has(value + 1)){
const j = M.get(value + 1);
pairs.push([i, j]);
}
});
return pairs;
}
/*
[1, 0]
[2, 5]
[3, 1]
[4, 6]
[5, 6]
[6, 1]
*/
console.log(linearSolution([5, 4, 1, 3, 2, 2, 3]));
Regarding the follow up, it can be solved using a Min Heap. Let H a Min Heap, insert all the values into H along with their index in A. Each element in H would look like (value, index), but only the value is considered for the sorting of H.
Then, for each j from N - 1 down to 0, pop top element (x, i) from H, while A[j] > x, output a pair (i, j) for each popped element. Building H takes O(N) time and extra space. Since each value from A is popped at most once, and pop operation takes O(log N) time, total time complexity is O(N log N).
Below is working implementation in Java.
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
static class HeapElement {
int value;
int index;
HeapElement(int value, int index){
this.value = value;
this.index = index;
}
}
static class HeapElementComparator implements Comparator<HeapElement> {
@Override
public int compare(HeapElement first, HeapElement second){
return first.value - second.value;
}
}
static class Pair {
int i;
int j;
Pair(int i, int j){
this.i = i;
this.j = j;
}
}
static List<Pair> getPairs(int[] A){
int N = A.length;
List<Pair> pairs = new ArrayList<>();
Comparator<HeapElement> comparator = new HeapElementComparator();
PriorityQueue<HeapElement> H = new PriorityQueue<>(comparator);
for (int i = 0; i < N; i++){
HeapElement el = new HeapElement(A[i], i);
H.add(el);
}
for (int j = N - 1; j >= 0; j--){
while (A[j] > H.peek().value){
HeapElement top = H.poll();
int i = top.index;
Pair p = new Pair(i, j);
pairs.add(p);
}
}
return pairs;
}
public static void main (String[] args) {
int[] A = {5, 4, 1, 3, 2, 2, 3};
List<Pair> pairs = getPairs(A);
/*
(2, 6)
(4, 6)
(5, 6)
(3, 1)
(6, 1)
(1, 0)
*/
for (Pair p: pairs){
System.out.println(String.format("(%d, %d)", p.i, p.j));
}
}
}
Python solution : O(n)
A = [0, 2, 6, 7, 10, 3 , 1 , 4 , 11 , 8 , 1]
# new list B to get max index value of A[i] + 1th item
B = list(reversed(A))
# list of tuples to hold index values (i,j)
l = []
for i in A:
if (i+1) in A and A.index(i+1) > A.index(i):
l.append((A.index(i), (len(A)-B.index(i+1)-1)))
print((i,i+1), l[len(l)-1])
print(l)
1. keep hash map record: A[i] -> i
- zyfo2 November 09, 2017traverse A, return max (i - map(A[i] -1))
O(n) space O(n) time
2. keep hash map record: A[i] -> i
sort A as B, then replace value with A[B[i]] which set B[i] to the origin index in A
then traverse B and update smallest and largest index and return largest diff
(note when smallest is updated largest is set to the same value)
eg:
A: 3 4 5 6 0 1 2
B: 4 5 6 0 1 2 3
smallest: 4 4 4 0 0 0 0
largest: 4 5 6 0 1 2 3
max: 0 1 2 2 2 2 3
thus return 3(i=3, j=6)
O(nlgn) time, O(n) space