Google | Phone Screen | India | Reject

Anonymous User

1346

Two Pointers Google India Phone Screening Interview

Length of the minimum consecutive subarray with sum = K
Input K = 5, buckets = {1 2 2 5 4 1}
Output 1

int minBucketsWithSumK(int k, vector<int> buckets) {
  if (buckets.empty() || k <= 0) {
    return 0;
  }
  
  int size = buckets.size();
  int j = 0, i = 0, sum = 0;
  int result = INT_MAX;
  
  while (i < size) {
    // First Running i until sum < k
    while (sum < k && i < size) {
      sum += buckets[i];
      i++;
    }

    // Then, Running j until sum > k
    while (sum > k && j < i) {
      sum -= buckets[j];
      j++;
    }    
  
    if (sum == k) {
      result = min(result, i-j);
    }
  }
  
  return result;
}

The above code will give an ifinite loop for above input as once i = 3 and j = 0 and sum = 5, it will go in an ifinite solution.

int minBucketsWithSumK(int k, vector<int> buckets) {
  if (buckets.empty() || k <= 0) {
    return 0;
  }
  
  int size = buckets.size();
  int j = 0, i = 0, sum = 0;
  int result = INT_MAX;
  
  while (i < size) {
    // First Running i until sum < k
    while (sum < k && i < size) {
      sum += buckets[i];
      i++;
    }

    // Then, Running j until sum > k
    while (sum > k && j < i) {
      sum -= buckets[j];
      j++;
    }    
  
    if (sum == k) {
      result = min(result, i-j);
	 
	 // UPDATE: move i to the next index and update sum
	  if (i < size) {
        sum += buckets[i++];
      }
    }
  }
  
  return result;
}

Adding the above update in the code solves the purpose, but is not a neat way. Can anyone provide an alternate way to fix the above code using same two inner loops logic?

Comments (8)