Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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 ?
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.
{
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]);
}
}
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;
}
}
}
}
}
}
Dont you think its O(n2). your method has n iteration and the method is called n times... correct me if in am wrong...
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..)
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;
}
}
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).
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);
}
}
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!
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).
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++;
}
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).
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.
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;
}
<?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");
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);
}
}
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
)
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
// 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;
}
#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;
}
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