Facebook Interview Question for SDE1s


Country: United States




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

1. keep hash map record: A[i] -> i
traverse 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

- zyfo2 November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- zyfo2 November 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- DyingLizard December 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Somal February 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

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

- Anonymous November 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- praveenp November 06, 2017 | 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