Facebook Interview Question SDE1s
Country: United States
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 ?
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));
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;
}
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;
}
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.
@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;
}
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;
}
}
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;
}
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];
}
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