## Facebook Interview Question for SDE1s

Country: United States

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

Python solution :
Time complexity : O(n)

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

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

@sachin, the moment you sort, the notion of subarray is gone (unless you record the original index somewhere). Your code will work if the question asked for the minimum "subset" instead of subarray...

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

@DyingLizard. [4,4,2,-6,4,10,2],16 produces 6, instead of 3.

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

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

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

@charan. A couple of test cases the code produces a wrong result for:
{3, 8, 8}, k=16 - result is 3, should be 2
{2, 7, 2, -3, 9, -7, -6, -5}, k=12 - result is 9999, should be 4

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

Not sure that it is actually O(n), but it is a solution.

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

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

@charan
k may be negative.
You code will fail already for a={-1}, k=-2.

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

for the above input, returned result is 1 which is valid since we have a subarray {-1} >= -2.

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

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)

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

How would you produce the sub-arrays before inserting the to hash-map?

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

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

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

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

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

CodeArtist:

Isn't trimming O(N) in the worst case? And since your algorithm runs trimming on each index, the worst case seems O(N^2).

I don't think an O(N) solution exists.

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

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

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

@DeathEater
Check this case:
arr = {-2,2,-2,1,1,1,1} k=2.

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

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]

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

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

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.