Facebook Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
3
of 5 vote

usually, a subarray is a continous subarray; if not continous, one usually says subsequence. Thus there are O(n^2) such subarrays. One can now test all of those, or move a sliding window and solve it in O(n) if there are only positive integers in the array.

for the given sample to briefly verify interpretation and explain algo by sample

start=0, end=0: {2} --> count = count + 1 = 1
start=0, end=1: {2,3} --> count = count + 2 = 3, from {2,3} or from {3}
start=0, end=2: {2,3,6} --> 2*3*6 > 10, start = 1
start=1, end=2: {3,6} --> 3*6 > 10, start = 2
start=2, end=2: {6} --> 6, count = count + 1 = 4, from {6}

for only positive integers with no "0"'s this would be:

int countSubArrayProductLessThanK(const vector<int>& arr, int k)
{
	if (arr.size() < 0) return 0;
	int start = 0;
	int end = 1;
	long long prod = arr[0];
	int count = 0;
	while (start < end && end <= arr.size()) {
		if (prod <= k) {
			count += end - start;
			if (end < arr.size()) prod *= arr[end];
			end++;
		} else {
			prod /= arr[start++];
		}
	}
	return count;
}

if there are 0's exclude them from product and count them in the window. If more than 1 zero exists, the product will be 0. With negatives it's a bit trickier because the adjustment of the windows size doesn't work the same way anymore. Any ideas?

- Chris October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the first solution (from ChrisK) has a bug. For example for array {2, 3, 4, 6} with k=13, the output from the above code is 5, where as actual output should be 6.

while(end < arr.size()) {
	prod *= arr[end++];
	if(prod <= k) count += end-start+1;
	else {
		prod /= arr[start++];
		if (prod <= k) count++; <<---- Add this line
	}
	if(start > end) end++;
}

Also, could you explain the logic of
count += end-start+1 <<--- How does this work ?

- kiran October 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK In addition, my problem was the English, I am not a native speaker, but looking at your description I see what I missed: "product" is not "sum" as I mistakenly thought.... :P

- PenChief October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
int subarrays(int arr[], int i, int len, int prod) {
if (i>=len) return 0;

return (arr[i] < prod ? (1 + subarrays(arr, i+1, len, prod/arr[i])) : 0) + subarrays(arr, i+1, len, prod);
}
}

- Recursive solution October 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int subarrays(int arr[], int i, int len, int prod) {
  if (i>=len) return 0;
  
  return (arr[i] < prod ? (1 + subarrays(arr, i+1, len, prod/arr[i])) : 0) + subarrays(arr, i+1, len, prod);
}

- Recursive solution October 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Got a nice O(n log n) solution using binary search. It uses cumulative product array as support, O(n) extra space, if it's not allowed to destroy the input.

After pre computing cumulative product array, it's possible to get the product from i to j in O(1). For each i, if A[i] < k, use binary search to find the largest j such that product from i to j is less than k, using the fact that cumulative array is non decreasing.

Implementation is in ES6 with pure functions.

// O(n)
const getCumulativeProduct = (A) => {
  const cumulative = [];
  A.forEach((val, i) => {
    if (i === 0){
      cumulative.push(val);
    }
    else {
      cumulative.push(cumulative[i - 1] * val);
    }
  });
  return cumulative;
};

// O(1)
const getProduct = (start, end, cumulative) => {
  let product = cumulative[end];
  if (start > 0){
    product /= cumulative[start - 1];
  }
  return product;
};

// O(log n)
// Precondition A[start] < k
const findLongestInterval = (start, cumulative, k) => {
  const n = cumulative.length;
  let a = start;
  let b = n - 1;
  while (a <= b){
    const mid = Math.floor((a + b) / 2);
    const product = getProduct(start, mid, cumulative);
    if (product >= k){
      // mid is not a potential solution
      b = mid - 1;
    }
    else if (mid === n - 1 || getProduct(start, mid + 1, cumulative) >= k){
      return mid;
    }
    else {
      a = mid + 1;
    }
  }
};

// O(n log n)
const solve = (A, k) => {
  const cumulative = getCumulativeProduct(A);
  let solution = 0;
  A.forEach((val, i) => {
    if (val < k){
      const end = findLongestInterval(i, cumulative, k);
      solution += end - i + 1;
    }
  });
  return solution;
}

console.log(solve([2, 3, 6], 10));

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

int countSubArrayProductLessThanK(const vector<int>& arr, int k) 
{
	int start = 0;
	int end = 0;
	long long prod = 1;
	int count = 0;
	while(end < arr.size()) {
		prod *= arr[end++];
		if(prod <= k) {
                    int range = end - start + 1;
                    count += range * (range - 1) / 2;
                } else {
		    while(prod >= k) {
                        prod /= arr[start++];
                    }
                    int range = end - start + 1;
                    count += range * (range - 1) / 2;
                }
	}
	return count;
}

- Kaidul Islam October 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use two pointers to keep track the 'tail' and 'head' of the subarray. O(n) complexity:

public int countSubArrays(int[] array, int k){
		int head = 0;
		int tail = 0;
		int total = 1;
		int count = 0;
		for(;head<array.length;head++){
			total*=array[head];
			if(total < k){
				count+=head - tail + 1;
			}
			else{
				while(total>=k && head >= tail){
					total/=array[tail];
					tail++;
				}
				if(head>=tail){
					count+=head - tail + 1;
				}
			}
		}
		return count;
	}

- jiahuang October 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int numOfArraysSmallerThanK(int[] nums,int k){
          int sum = 1;
          int count = 0;
          int start = 0;
          for(int i=0;i<nums.length;i++){
              sum*=nums[i];
              if(sum<k){
                  
                  count += i-start+1;
              }else{
                  while(sum>=k && start<=i){
                     sum/=nums[start];
                     start++;
                  }
                  count += i-start+1;
              }
          }
        
          return count;
    }

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

Numbers are in sorted order? If yes then check if the first element is less than the k then only continue

With the given problem I can divide it into 2 sub-problems like:
1. Getting all subarrays
2. Checking subarrays if their multiplication is less than k
This solution will work for both negative as well as positive integers.

- zeus bolt October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@kiran, I checked, there was a problem with the loop invariants when moving the window, I did write it in a coffee break and didn't thoroughly go through, it should be

int countSubArrayProductLessThanK(const vector<int>& arr, int k)
{
	if (arr.size() < 0) return 0;
	int start = 0; start of interval 
	int end = 1; // end of half open interval [start, end)
	long long prod = arr[0];// current prod is arr[0] for [0, 1)
	int count = 0; // no product found yet
	while (start < end && end <= arr.size()) {
		if (prod <= k) { // if product fits in
			count += end - start; // all subarrays with product < k ending in with element end-1
			if (end < arr.size()) prod *= arr[end]; // try to push end further and increase product
			end++;
		} else {
			prod /= arr[start++]; 
			// note: for the current end, I haven't found anything yet
			// I can't move end anymore, but i can move start until I pass end or until 
			// the product falls beyond k
		}
	}
	return count;
}

- Chris October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution countSubArrayProductLessThanK() does not process case when element in array is bigger than K correctly. Here is correct one:

int p1 = 0;
    int p2 = 0;
    int res = 0;
    int curr_v = 1;
    while (p2 < n) {
        if (curr_v * data[p2] <= m) {
            curr_v *= data[p2];
            res += (p2 - p1) + 1;
            ++p2;
        }
        else {
            if (p1 == p2) {
                ++p1;
                ++p2;
                assert(curr_v == 1);
                continue;
            }
            curr_v /= data[p1];
            ++p1;
        }
    }

- avv October 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Several questions:
- Is the array sorted?
- Do the sub-arrays must be of an adjacent elements?

Why am I asking?
Looking at the above example:

Arr = {2,3,6}

I can think of the following sub-arrays:

{2} < 10
{3} < 10
{6} < 10
{2,3} < 10
{3,6} < 10
{2,6} < 10

- PenChief October 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

DP Soln, O(N^2)

public static void main(String args[]){
        int[] arr = {2,3,6};
        int k = 10;
        int n = productSubArrCount(arr, k);
        System.out.println(n);
    }
   
   public static int productSubArrCount(int[] arr, int k){
    
        int n = arr.length;
        int[][] dp = new int[k+1][n+1];
        
        for(int i = 1; i <= k; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j-1];
                if(i >= arr[j-1] && arr[j-1] > 0 && i/arr[j-1] < (k+1))    
                    dp[i][j] += dp[i/arr[j-1]][j-1]+1;
            }
        }
        return dp[k][n];
    }

- sudip.innovates October 02, 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