## Facebook Interview Question for SDE1s

• 0

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;
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?

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 ?

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

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

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

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

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

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 tail = 0;
int total = 1;
int count = 0;
if(total < k){
}
else{
total/=array[tail];
tail++;
}
}
}
}
return count;
}``````

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

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.

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;// current prod is arr 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;
}``````

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

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

O(n) solution

``````int count_subarrays_product_less_than_k(const std::vector<int> v, int k) {
int prev_end = 0;
int start = 0;
int end = 0;
int count = 0;
int curr_product = 1;
while (end < v.size()) {
if (curr_product * v[end] < k) {
curr_product *= v[end];
}
else {
int len = end - start;
count += (len) * (len - 1) / 2 + len;
int overlap_len = std::max(prev_end - start, 0);
count -= (overlap_len) * (overlap_len - 1) / 2 + overlap_len;
prev_end = end;
curr_product *= v[end];
while (curr_product >= k) {
curr_product /= v[start];
++start;
}
}
++end;
}
int len = end - start;
count += (len) * (len - 1) / 2 + len;
int overlap_len = len - std::max(prev_end - start, 0);
count -= (overlap_len) * (overlap_len - 1) / 2 + overlap_len;
return count;
}``````

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?

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

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

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.