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 ?

- ObiWanKinobi October 14, 2012 | Flag Reply
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 ?

- DarkKnight October 14, 2012 | Flag Reply
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.

- avico81 October 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{
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]);
	}
}

- switch2switch October 15, 2012 | Flag
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])
					{
						temp.add(nums[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;
					}
					
				
				}
			}
			
		}
	}
}

- Pankaj Gadge October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Saumil October 14, 2012 | Flag
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)

- Pankaj Gadge October 14, 2012 | Flag
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..)

- Vivek October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka October 16, 2012 | Flag
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

- nixfish October 14, 2012 | Flag Reply
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?

- Anonymous October 14, 2012 | Flag Reply
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;
    }

}

- Mario October 14, 2012 | Flag Reply
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).

- peter tang October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- xl October 15, 2012 | Flag
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[] answer = new int[min_diff+1];
int index = 0;
for(i = j;i<=j+min_diff;i++){
answer[index++] = a[i];
System.out.println(a[i]);
}

return answer;
}

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

}

- jenish.shah October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- BoredCoder October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- BoredCoder October 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jenish.shah October 16, 2012 | Flag
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

- Anonymous October 18, 2012 | Flag Reply
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++;
}

- aceorochi October 18, 2012 | Flag Reply
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++;
}

- Anonymous October 18, 2012 | Flag Reply
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.

- Bo October 18, 2012 | Flag Reply
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).

- Neo October 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a correction..not like binary search.

- Neo October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Chen October 20, 2012 | Flag
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)

Please suggest.

- Trying.. November 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ACP Pradyuman November 17, 2012 | Flag
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.

- Anonymous December 24, 2012 | Flag Reply
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;
  }

- dm January 15, 2013 | Flag Reply
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");

- Anonymous January 28, 2013 | Flag Reply
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);
		}
	}

- Negar July 16, 2013 | Flag Reply
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) {
        [rtArray addObjectsFromArray:[array subarrayWithRange:NSMakeRange(currentBegin, currentEnd-currentBegin+1)]];
    }
    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
)

- Senry December 10, 2013 | Flag Reply
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?

- bluemoon January 26, 2014 | Flag Reply
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

- just_do_it March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- just_do_it March 14, 2015 | Flag
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;
  
}

- Anne September 29, 2015 | Flag Reply
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;
  
}

- Anne September 29, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More