## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Doesn't subarray normally refer to a contiguous subarray? Or are we talking about subsequences here, which may not be contiguous ?

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

Assumption : All Numbers, Keys are +ve
Sliding Window Method

``````int low = 0;
int high = 0;
int minimum = int.MaxValue;
int sum = 0;
while (low < size)
{
while (sum < key && high < size)
{
sum += a[high];
high++;
}
if (sum >= key && sum < minimum)
minimum = sum;
sum -= a[low];
low++;
}``````

Does anyone have a solution for positive and negative numbers ?

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

I think the question meant to find the min subarray (in length, i.e. two cells are better than 3) rather than min value of subarray as your code suggests (i.e. sum=key is better than sum=key+2).

Anyway if I'm mistaking, this could also be a good question for practice.

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

``````{
void main(){

int arr[]={3,5,2,7,5,3,8,3,9,8,4,2};
int L = sizeof(arr)/sizeof(int);

int i=0,n=0,sum=0,X=12;
int temp_n=100,temp_i=0,temp_sum=100;

while(i<L){

while(sum<=X ){
sum+=arr[i+n];
n++;
}

if(n<temp_n && sum<=temp_sum &&temp_n!=0){			//3,5,2,7,5,3,8,3,9,8,4,2
temp_i=i;
temp_n=n;
temp_sum=sum;
}

sum-=arr[i];
i++;
if(n>0)
n--;
}

for(int j=temp_i;j<=temp_n+temp_i-1; j++){
printf("%d - ",arr[j]);
}
}``````

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

So, here is the working version of the code that will print all sub arrays whose sum of the elements is more than the key.

Time complexity is O(n2) using recursion. Not sure, how to do with O(n)

``````import java.util.ArrayList;

public class SubArray {
static int key = 2;
static int count = 0;
public static void main(String args[])
{
int[] nums = {1,2,3};

printSubset(nums);
}

public static void printSubset(int[] nums)
{
for(int i = 0; i < nums.length; i++)
{
boolean[] ifPrint = new boolean[nums.length];
printSubset(nums, ifPrint, 0, i);
}
}

public static void printSubset(int[] nums, boolean[] ifPrint, int start, int remain)
{
int sum = 0;
if(remain == 0)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
System.out.print("{");
for(int i=0; i < ifPrint.length; i++)
{
if(ifPrint[i])
{
System.out.print(nums[i]+",");
}
}
System.out.print("}\n");

for(int i=0; i < temp.size(); i++)
{
sum += temp.get(i);
}
if(sum > key)
System.out.println("My Array"+temp);
}
else
{
if(start+remain > nums.length)
;
else
{
for(int i = 0; i < nums.length; i++)
{
if(!ifPrint[i])
{
ifPrint[i] = true;

printSubset(nums, ifPrint, i+1, remain-1);

ifPrint[i] = false;
}

}
}

}
}
}``````

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

Dont you think its O(n2). your method has n iteration and the method is called n times... correct me if in am wrong...

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

That's what I said, right. n * n = n^2. Sorry, I cannot type a square ;). So, time complexity is O(n*n)

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

I believe there is an answer I solved this question in two attempts :
1) In first attempt I sort the array in decreasing order and then take the sum of each element starting from the largest till the sum is greater than key value.
complexity given I used merge sort is : nlogn + r where r is the size of subset

2) Second attempt is a follows :
Take each element of array and push it into a binary tree . An keep the total sum at top node. One the sum exceed given value.
Now either this the is the solution or there are element with values greater than existing values... So for now on for each insert iteratively remove lowest from the tree till total sum is less than given value. .. (and that solves it in one iteration..)

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

Why do we need to use binary tree for your second approach?We can use the same thing with an array.

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

Are there extra conditions like all numbers are positive. Otherwise, it is possible there is no answer. E.g. key is positive, and all numbers in the array are negative

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

is there a situation that a1 + a3 + a4 is smaller than a3 + a4 + a5，the alogrithm seems not calculate the value of a1+a3+a4?

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

``````int[] arr = {}; // read from the input
int key = <read from the input>;
int sum = 0;
int minArrayLength = Integer.maximum;
for (int i = 0; i < arr.length; i++) {
sum = 0;
for (int j = i; j < arr.length; j++) {
sum+= arr[j];
if (sum >= key) break;
}

if (sum >= key) {
int subArrayLength = (j - i)  + 1;
if (minArrayLength > subArrayLength)  minArrayLength = subArrayLength;
}

}``````

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

``````int ARRAY, ARR_LEN, KEY; // passed in
int subArrStartIndex = 0, subArrLen = 0, sum = 0;

for (int i = 0; i < ARR_LEN; ++ i){
sum += ARRAY[i];

if (sum < key){
subArrLen ++;
} else {
sum -= ARRAY[subArrStartIndex];
subArrStartIndex ++;
}
}``````

This is to find one of the longest sub-arrays whose sum is just no less than KEY. And it's O(n).

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

your algorithm does not work. try {2, -2, 3} with key=1

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

Below is the code. I think this will work for O(n) because in this case every element will be traversed at the max 2 times. Please let me know if you find bug in this.

public class MinSubArrayWithK {
static int[] printSubArray(int[] a,int k){
int min_diff=a.length-1;
int sum = 0,i= 0,j=0;
for(i =0;i<a.length;i++){
sum += a[i];
if(sum >= k){
while(sum - a[j] >= k){
sum -= a[j];
j++;
}
int diff = i - j ;
if(diff < min_diff){
min_diff = diff;
}
}
}
int index = 0;
for(i = j;i<=j+min_diff;i++){
System.out.println(a[i]);
}

}

public static void main(String[] argv){
int[] a = {3,5,2,7,5,3,8,3,9,8,4,2};
printSubArray(a,12);
}

}

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

I don't think it is a O(n) algo. Rather its a O(n^2) algo, where you are iterating over the entire length i and for each i you are computing the least subarray starting with a[i]...So this is basically a O(n^2) algo!

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

Sorry..You are adding a[i] in each step, and you take out a[j]'s from the other end till the subarray sum is above k. So the complexity will depend on the no of a[j]'s taken out at each step by the while loop which cannot be guaranteed to be of constant time..So it is still O(n^2).

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

Yeah that is what I wanted to say so in my program no matter whatever condition is any element of the array will be traversed at the max 2 times.
Isnt this called 2O(n) and eventually o(n). O(n2) is totally different I think.

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

Int sum = 0;

For ( I = 0; I < n ; ++I) {
Sum+= a[i];
If (sum >= k){ prints found return;}
If (sum < 0) sum = 0; // negative value will reduce the running sum and we want to grow it

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

int sum = 0;
int minSum = INT_MAX;
int i = 0; j = 0;
while(ture){
sum += A[i]
if(sum >= key){
//Go back
int tmpSum = 0;
for(int k = i; k > j; k--){
tmpSum += A[k];
if(tmpSum >= key){
if(minSum > tmpSum) minSum = tmpSum;
break;
}
}
j = i;

//Go forward
sum = 0;
continue;
}
i++;
}

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

Missed one line...

int sum = 0;
int minSum = INT_MAX;
int i = 0; j = 0;
while(ture){
sum += A[i]
if(sum >= key){
minSum = MIN(sum, minSum);
//Go back
int tmpSum = 0;
for(int k = i; k > j; k--){
tmpSum += A[k];
if(tmpSum >= key){
if(minSum > tmpSum) minSum = tmpSum;
break;
}
}
j = i;

//Go forward
sum = 0;
continue;
}
i++;
}

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

1st. Go throught the whole string and find the biggest on

2ed. Build a bit array m which length eq to the biggest number

3rd. Match each number to m[number] =1. Others =0. Then this is a sorted array.

4th. Add from the biggest one and compare with the key.

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

Like binary search divide the array with elements greater than key on right and smaller than key on left. If there are elements on the right side output any of right side elements. otherwise do the same for key/2 and select 2 elements from right side elements (if there are any) and so on until you find the sub set. I think it would be O(nlogn).

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

Just a correction..not like binary search.

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

If you want a solution with O(nlogn), you can just sort the array in decreasing order and start making the sum from the first element.

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

Given an array and a key, sum min subarray whose sum is no less than key. O(n) Time needed

min subarray - array of length 1
sum not less than key, i.e. that element of array is > key
Traverse the array to find an element > key (smallest element > key can also be found)

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

What if the key is greater than the largest element in the array?

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

This is subset sum problem (variation of knapsack). So it cannot be done in O(n).
DP will result in O(nk). where k is key.

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

Solutions for both interpretations. However, they are more than O(n)

``````public static int minSumSubArray(int[] a, int key) {
int winSize = 0;
int minSum = Integer.MAX_VALUE;
int currentSum = 0;

for(int i = 0; i < a.length; i ++) {
currentSum+=a[i];
winSize++;
while(currentSum - a[i - winSize + 1] >= key) {
currentSum-=a[i - winSize + 1];
winSize--;
}
if(currentSum >= key && currentSum < minSum) {
minSum = currentSum;
}
}
return minSum;
}

public static int minSizeSubArray(int[] a, int key) {
int winSize = 0;
int minSize = Integer.MAX_VALUE;
int currentSum = 0;

for(int i = 0; i < a.length; i ++) {
currentSum+=a[i];
winSize++;
while(currentSum - a[i - winSize + 1] >= key) {
currentSum-=a[i - winSize + 1];
winSize--;
}

if(currentSum >= key && winSize < minSize) {
minSize = winSize;
}
}
return minSize;
}``````

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

<?php
\$array = array(11,4,-23,6,-5,4,77,6,-1,3,-65,4,8,7,9);
\$number = 40;
\$l=0;
\$r=0;
\$fr=0;
\$fl=0;
\$count = count(\$array);
\$cursum=0;
\$diff = PHP_INT_MAX;
for (\$i=0;\$i<\$count;\$i++)
{
\$cursum = \$cursum + \$array[\$i];
if (\$cursum >= \$number && ((\$cursum-\$number)<\$diff))
{
\$fl = \$l;
\$r = \$i;
\$fr = \$r;
\$diff = \$cursum-\$number;
}
if (\$cursum < 0)
{
\$cursum=0;
\$l=\$i+1;
}
}
echo ("closet - " . (\$number+\$diff) . "\n");
echo ("left - \$fl \n");
echo ("right - \$fr \n");

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

``````static class solution{
public static void main(String[] args){
int[] array = {1,2,5,5,2,3,5};
int key = 5;
int min = 100;
int sum = 0;
int block=0;
for(int i=0;i<array.length;i++){
sum+=array[i];
if(sum>key){
if(sum < min)
min = sum;
int sum2=0;
for(int j=i;j>block;j--){
sum2+=array[j];
if(sum2>key){
break;
}
}
if(sum2>key && sum2 < min)
min = sum2;
block = i;
}
}
System.out.println(min);
}
}``````

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

Here is code in Objective-C.

``````- (NSArray *)findMinSumSubarrayFromArray:(NSArray *)array withKey:(NSInteger)key {
//    Iterate from head to tail, with 2 indexs. Sum up numbers between the range of numbers.
//    1. Whenever the sum is no less than key, remember the range and sum.
//    2. Then the smaller index move on till the sum is less than key, every step we check if we get a closer sum, then the bigger index move on.
//    3. Whenever the sum is no less than key, compare the remembered sum, if smaller remember the range and sum.
//    4. repeat 1 to 3 till the smaller index reaches the end.
if ([array count]<=1) {
return array;
}

NSMutableArray *rtArray = [NSMutableArray array];
NSUInteger p = 0, q = 1, end = [array count];
NSInteger currentSum = NSIntegerMax;
NSInteger currentBegin = 0;
NSInteger currentEnd = 0;

while (p < end-1 || q < end-1) {
NSArray *subArray = [array subarrayWithRange:NSMakeRange(p, q-p+1)];
NSInteger sum = [[subArray valueForKeyPath:@"@sum.self"] integerValue];
if (sum >= key) {
if (sum < currentSum) {
currentBegin = p;
currentEnd = q;
currentSum = sum;
}
do {
p++;
subArray = [array subarrayWithRange:NSMakeRange(p, q-p+1)];
sum = [[subArray valueForKeyPath:@"@sum.self"] integerValue];
if (sum>=key && sum < currentSum) {//This is important in case we missed sum closer to key
currentBegin = p;
currentEnd = q;
currentSum = sum;
}
} while (sum>=key && p<q);
}
else {
if (q<end-1) {
q++;
}
else {//here is where p moves on
do {
p++;
subArray = [array subarrayWithRange:NSMakeRange(p, q-p+1)];
sum = [[subArray valueForKeyPath:@"@sum.self"] integerValue];
if (sum>=key && sum < currentSum) {//This is important in case we missed sum closer to key
currentBegin = p;
currentEnd = q;
currentSum = sum;
}
} while (sum>=key && p<q);
}
}
}
if (currentSum != NSIntegerMax) {
}
return rtArray;
}``````

``````NSArray *sumArray = [self findMinSumSubarrayFromArray:@[@(2), @(7), @(-3), @(8), @(-5), @(3), @(1), @(2), @(-3)] withKey:6];
NSLog(@"%@", sumArray);

(
"-3",
8,
"-5",
3,
1,
2
)``````

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

Can't we just modify Kadane's algorithm to determine the end point for the max sum so far to have reached a value greater than or equal to the key?

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

here are my thoughts for smallest subsequence with sum exceeding k

find the median, and sum all elements greater than median,
> if sum < k, look for k-sum in second half
> else prune second half, look for k in first half

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

by look for I meant "solve for smallest subsequence of numbers forming atleast"

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

// this code handles the negative integers and key

``````#include<stdio.h>

int min (int a, int b){

int c = (a<b)?a:b;
return c;
}

int min_key (int a, int b,int key){

int c = (a>b)?a:b;

if(c>key)
return c;

else
return a;
}

int minsum(int a[], int len, int key){

int i;

int min_arr=key-1;

int min_k=100000;

for(i=1;i<len;i++){

min_arr = min_key(a[i],min_arr+a[i],key);

while(min_arr<key)
{
i++;
min_arr = min_key(a[i-1],min_arr+a[i],key);
}

min_k = min(min_arr,min_k);

}

return min_k;

}``````

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

``````#include<stdio.h>

int min (int a, int b){

int c = (a<b)?a:b;
return c;
}

int min_key (int a, int b,int key){

int c = (a>b)?a:b;

if(c>key)
return c;

else
return a;
}

int minsum(int a[], int len, int key){

int i;

int min_arr=key-1;

int min_k=100000;

for(i=1;i<len;i++){

min_arr = min_key(a[i],min_arr+a[i],key);

while(min_arr<key)
{
i++;
min_arr = min_key(a[i-1],min_arr+a[i],key);
}

min_k = min(min_arr,min_k);

}

return min_k;

}``````

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.