Facebook Interview Question SDE1s
Country: United States
// k is the targetSum
int minSubArrayLen(int *a, int n, int k) {
int minLen = 9999;
int curSum = 0;
int len = 0, i = 0;
while(i < n) {
if (a[i] > k) {
curSum = 0;
minLen = 1;
break;
}
else if (a[i] < 0) {
/*
* curSum is going to decrease, so
* it will never be >=k. Reset the counters and start
*/
curSum = 0;
len = 0;
}
else if (curSum + a[i] >= k) {
/*
* including this number makes subarray sum >= k
* store the subarray len and update minLen
*/
curSum = 0;
minLen = std::min(minLen, len+1);
len = 0;
} else {
len++;
curSum = curSum + a[i];
}
i++;
}
return minLen;
}
Not sure that it is actually O(n), but it is a solution.
How about this one (python):
def subs(l,x,s=0,e=0,curr_sum=0):
if s == len(l):
return (0xffff, -1)
if e == len(l):
if curr_sum >= x:
return min((e-s, s), subs(l,x,s+1,e,curr_sum - l[s]), key=lambda n: n[0])
# In order to handle negative values
return subs(l,x,s+1,e,curr_sum - l[s])
if curr_sum >= x:
return min((e-s,s), subs(l,x,s+1,e+1, curr_sum - l[s] + l[e]), subs(l, x, s+1, e, curr_sum - l[s]), key=lambda n: n[0])
return subs(l, x, s, e+1, curr_sum + l[e])
As I said, I'm not sure it is actually O(n), is it?
Thinking aloud here:
1. Go through the array list and create a hash map O(n) with key: length of sub-array and value: is the array itself
2. and then look-up minimum key O(n), if we need the subarray we can return the value
total O(n)
My solution using DP. I constructed a 2D table which caches sums of all subarrays, then just compares intermediate sums with the target.
For example, the 2D array for the given example of
[ 5, 4, -8, 16 ]
is below
[ 5, 9, 1, 17 ]
[ 0, 4, -4, 12 ]
[ 0, 0, -8, 8 ]
[ 0, 0, 0, 16 ]
The code:
public static int minLengthSubarrayWithSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
final int n = nums.length;
final int[][] cache = new int[n][n];
int minLength = Integer.MAX_VALUE;
// Sum continuously for first row
cache[0][0] = nums[0];
for (int i = 1; i < n; i++) {
cache[0][i] = cache[0][i - 1] + nums[i];
}
// Sum the rest
for (int r = 1; r < n; r++) {
for (int c = r; c < n; c++) {
cache[r][c] = cache[r][c - 1] + nums[c];
}
}
// Find the min length
for (int r = 0; r < n; r++) {
for (int c = r; c < n; c++) {
if (cache[r][c] >= target) {
minLength = Math.min(minLength, c - r + 1);
}
}
}
return minLength;
}
I didn't spend any time optimizing this at all, but it's likely that some of the loops can be combined. This algorithm uses quadratic space and time
Here is my proposal. I've divided the code into three steps for readability. This can be achieved in one iteration as well.
Time and space complexity O(n).
int minSubArrLen(vector<int>& arr, int k){
int n = arr.size();
unsigned int res = -1 //max unsigned int;
vector<int> subSum(n);
vector<int> subLen(n);
subSum[0] = arr[0];
subLen[0] = 1;
int y=0;
//Kadane's algorithm to produce all max sum sub-arrays anding at each index.
for(int i=1; i<n; ++i){
if(arr[i] >= k) //Will work also w/o it. Just an optimization.
return 1;
if(subSum[i-1] > 0){
subSum[i] = subSum[i-1] + arr[i];
subLen[i] = subLen[i-1] + 1;
}
else{
subSum[i] = arr[i];
subLen[i] = 1;
}
}
//For every sub-array which sum is more than k, try to trim it from the front:
for(int i=0; i<n; ++i){
if(subSum[i] > k){
if(y <= i - subLen[i]){
while(subSum[i]-subSum[y]>k)
y++;
}
else{
y=i;
while(y>=0 && subSum[i]-subSub[y]<k){
y--;
}
}
subLen[i] = i - y;
}
}
//Choose the minimum length sub array
unsigned minLength =-1;
for(int i=0; i<n; ++i){
if(subSum[i]>=k && subLen[i] < minLength)
minLength = subLen[i];
}
return minLength;
}
void findSmallestContgArr(int[] arr, int len, int num, int& start, int& end) {
auto j = 0, sum = 0, minLength = INT_MAX;
for (int i = 0; i < len; i++) {
while (sum < num && j < len) {
sum += arr[j];
j++;
}
if (sum >= num) { // we have a solution
if (j - i < minLength) {
minLength = j - i;
start = i;
end = j;
}
}
sum -= arr[i];
}
if (minLength == INT_MAX) { // Didn't find a solution
start = -1;
end = -1;
}
}
The smallest piece of code to solve it in O(n) using perl is as follows:-
#my @intArray = qw(5 4 -8 16);
#my $lookupInt = 10;
my @intArray = qw(4 4 2 -6 4 10 2);
my $lookupInt = 16;
print STDOUT "Input \@intArray=[",join(",",@intArray),"] and \$lookupInt=[",$lookupInt,"] output of \&getSamllSubArray ~[",join (",", @{getSamllSubArray( \@intArray, $lookupInt )}),"]\n";
sub getSamllSubArray{
my ( $arrayRef, $lookupValue ) = @_ ;
my $sum = 0;
my @smallestArray = ();
foreach (sort {$b <=> $a} @{$arrayRef}) {
$sum += $_;
push ( @smallestArray, $_ );
if ( $sum >= $lookupValue ) {
last;
}
}
return [@smallestArray];
}
Test Output -
Input @intArray=[4,4,2,-6,4,10,2] and $lookupInt=[16] output of &getSamllSubArray ~[10,4,4]
Input @intArray=[5,4,-8,16] and $lookupInt=[10] output of &getSamllSubArray ~[16]
Using perl, we can achieve the O(n) for just a few piece of code base
=======================================================
my @intArray = qw(4 4 2 -6 4 10 2);
my $lookupInt = 16;
print STDOUT "Input \@intArray=[",join(",",@intArray),"] and \$lookupInt=[",$lookupInt,"] output of \&getSamllSubArray ~[",join (",", @{getSamllSubArray( \@intArray, $lookupInt )}),"]\n";
sub getSamllSubArray{
my ( $arrayRef, $lookupValue ) = @_ ;
my $sum = 0;
my @smallestArray = ();
foreach (sort {$b <=> $a} @{$arrayRef}) {
$sum += $_;
push ( @smallestArray, $_ );
if ( $sum >= $lookupValue ) {
last;
}
}
return [@smallestArray];
}
Output of the above code-base -
Input @intArray=[4,4,2,-6,4,10,2] and $lookupInt=[16] output of &getSamllSubArray ~[10,4,4]
Input @intArray=[5,4,-8,16] and $lookupInt=[10] output of &getSamllSubArray ~[16]
This code is running with O(n^2), but works as expected.
public static int miniSubArrayLen(int[] nums, int s) {
int returnVal = -1;
for (int i = 0; i < nums.length; i++) {
int currentSum = nums[i];
int subArrLen = 1;
for (int j = i + 1; j < nums.length; j++) {
if (s > currentSum) {
currentSum += nums[j];
}
++subArrLen;
if (currentSum >= s && (returnVal == -1 || returnVal > subArrLen)) {
returnVal = subArrLen;
break;
}
}
}
return returnVal;
}
This code works in O(n^2)
public static int miniSubArrayLen(int[] nums, int s) {
int returnVal = -1;
for (int i = 0; i < nums.length; i++) {
int currentSum = nums[i];
int subArrLen = 1;
for (int j = i + 1; j < nums.length; j++) {
if (s > currentSum) {
currentSum += nums[j];
}
++subArrLen;
if (currentSum >= s && (returnVal == -1 || returnVal > subArrLen)) {
returnVal = subArrLen;
break;
}
}
}
return returnVal;
}
def minimalSubArraySum(array: Array[Int], value: Int): Int = {
var left = 0
var right = 0
var sum = 0
var result = Integer.MAX_VALUE
while (right < array.length) {
if (sum >= value && result > (right - left)) result = right - left
sum += array(right)
right += 1
if (sum > value) {
sum -= array(left)
left += 1
}
}
while (left < right) {
if (sum >= value && result > (right - left)) result = right - left
sum -= array(left)
left += 1
}
if (result == Integer.MAX_VALUE) -1
else result
}
Python:
=======================
l = [1,4,2,5,-4,8,-2]
sum1 = 10
l.sort()
l.reverse()
for i in range(len(l)):
if l[i] >= sum1: #We are checking if biggest element is bigger,
print l[:i+1]
break
sum1 = sum1 - l[i] # if not then we have add that biggest element with second big element. so, just subtract the biggest element and check if remaining is bigger than next big element.
public static int smallestSubarray(int arr[], int target) {
int minLen = Integer.MAX_VALUE;
int end = 0;
int rollingSum = 0;
Map<Integer, Integer> pos = new HashMap<Integer, Integer>();
while (end < arr.length) {
rollingSum = rollingSum + arr[end];
if (pos.containsKey(rollingSum % 16) && rollingSum >= target) {
minLen = Math.min(minLen, end - (pos.get(rollingSum % 16)));
}
pos.put(rollingSum % 16, end);
end++;
}
return minLen;
}
Python solution :
Time complexity : O(n)
- DyingLizard December 19, 2017def smallestSubarray(nums, target): curr_sum, start, min_len = 0,0, sys.maxint for idx, num in enumerate(nums): if curr_sum + num >=target: curr_sum += num while curr_sum >=target and start<=idx: min_len = min(min_len, idx-start+1) curr_sum, start = curr_sum-nums[start], start+1 else: curr_sum += num return min_len if min_len!=sys.maxint else -1 def main(): # smallesSubarray sum nums,target = [1,2,3,4,5,6,7,8,9],45 print('Smallest subarray {} '.format(smallestSubarray(nums,target)))