Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

classic knapsack problem
dp[i][j][s] - means whether it's possible to get sum s after consideration of i elements and taking exactly j of them.
Overall complexity (N^2 * SUM)

- Darkhan.Imangaliev August 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sounds good.

- RecruitingForSandvineCanada August 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity is (N * M * SUM).

- NoOne December 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The runtime should be O(n^m)

- coredo August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's a JS recursive solution:

function findSubset (n, m, sum, subset) {
  if (sum === 0 || n.length < 1) return subset;
  var n0 = n.shift();
  if (n0 === sum) {
    subset.push(n0);
    return subset;
  }
  else if (n0 < sum) {
    subset.push(n0);
    return findSubset(n, m-1, sum - n0, subset);
  }
  else return findSubset(n, m, sum, subset);
}

- codacho August 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the fact that addition is commutative to solve this. You don't need to try a number again if you used it higher up the recursion layer, and found it didn't work. But you do for each different prefix set of numbers.

public class SubsetSum
{
	
	public SubsetSum()
	{
		
	}
    
	@Test
    public void testThis()
    {
        NavigableSet<Integer> remaining = new TreeSet<>();
        Set<Integer> inUse = new HashSet<>();
        
        remaining.add(1);
        remaining.add(5);
        remaining.add(8);
        remaining.add(3);
        remaining.add(9);
        remaining.add(11);

        // want 23 out of 3.

        Set<Integer> result = calculateSubSetSum(remaining, inUse, 0, 23, 3);
        for (Integer i: result)
        {
        	System.out.println(i);
        }

    }

	// Return a set of additions if successful, otherwise null.
	public Set<Integer> calculateSubSetSum(NavigableSet<Integer> remaining, Set<Integer> inUse, int sum, int goal, int M)
	{

		if (M > remaining.size())
		{
			return null;
		}
		Set<Integer> listOfDiscardedInts = new HashSet<Integer>();
	    if (M == 1)
	    {
	        if (remaining.contains(goal-sum))
	        {
	            // SUCCESS!!!!
	            inUse.add(goal-sum);
	            return inUse;
	        } else {
	            return null;
	        }
	    }
	    else {
	        while (remaining.size() > 0)
	        {
	            // Always safe to take the lowest value.
	            Integer i = remaining.pollFirst();
	            // We can safely remove this int, and not return it until the end.
	            inUse.add(i);
	            listOfDiscardedInts.add(i);
	            Set<Integer> result = calculateSubSetSum(remaining, inUse, 
				sum + i, 
				goal, M-1);
				if (result != null)
				{
				    // We got a result!
				    return result;
				}
				// No result, try the next addition.
				inUse.remove(i);
	        }
        }
	    for (int i: listOfDiscardedInts)
	    {
	    	remaining.add(i);
	    }
	    return null;
    }
}

- Andy August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is great code, but it only works if we assume the input array does not have any repeated elements. For example, if the following input array were turned into a TreeSet, you'd lose all the duplicated 3's and it would fail.

int[] input = new int[] { 3, 3, 3, 5, 6, 7};
int M = 3;
int SUM = 9;

- Anonymous August 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursively move the input array and build each possible subset by recursively including and not-including the number at the current index.

public static ArrayList<Integer>subset(int[] input, int targetSum, int targetSize, 
			ArrayList<Integer> currentSet, int currentSum, int currentIndex) {
		if (currentSum > targetSum) {
			return null;
		}
		if (currentIndex == input.length) {
			return null;
		}
		if (currentSet.size() == targetSize) {
			if (currentSum == targetSum) {
				return currentSet;
			} else {
				return null;
			}
		}
		
		ArrayList<Integer> withCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
		withCurrentIndexSubset.add(input[currentIndex]);
		withCurrentIndexSubset = subset(input, targetSum, targetSize, withCurrentIndexSubset,
				currentSum + input[currentIndex], currentIndex++);
		
		ArrayList<Integer> withoutCurrentIndexSubset = (ArrayList<Integer>) currentSet.clone();
		withoutCurrentIndexSubset = subset(input, targetSum, targetSize, withoutCurrentIndexSubset,
				currentSum, currentIndex++);
		
		if (withCurrentIndexSubset != null) {
			return withCurrentIndexSubset;
		} else {
			return withoutCurrentIndexSubset;
		}

	}

- Ben-G August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The runtime of this algorithm is O(2^n) even if targetSize is very low, let's say 2.

- coredo August 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the C++ version of solution using DFS.
It is using permutation algorithm with fixed length.
I am not proud of this solution though. Will post better.

Time complexity is O(N^M) where N is # of numbers in the array and M is the fixed subset.

Any critics or suggestions are welcomed.

#include<iostream>
#include<list>
using namespace std;

bool dfs(int left, list<int>&found, int max_depth, bool* marked, int *input, int len)
{
  if (found.size() == max_depth)
  {
    if (left == 0)
    {
      return true;
    }
    return false;
  }

  for (int i = 0; i < len; i++)
  {
    if (!marked[i] && input[i] <= left)
    {
      left -= input[i];
      marked[i] = true;
      found.push_back(input[i]);
      if (dfs(left, found, max_depth, marked, input, len))
      {
        return true;
      }
      left+= input[i];
      marked[i]= false;
      found.pop_back();
    }
  }
  return false;
}

list<int> find_sub_set(int * input, int max_size, int sum, int len)
{
  bool *marked = new bool[len];
  int left = sum;

  list<int> found;
  for (int i = 0; i < len; i++)
  {
    if (!marked[i] && input[i] <= left)
    {
      marked[i] = true;
      left -= input[i];
      found.push_back(input[i]);
      if (dfs(left, found, max_size, marked, input, len))
      {
        break;
      }
      marked[i] = false;
      left += input[i];
      found.pop_back();
    }
  }
  return found;
}

int main()
{
  int input[5] = {1,2,4,5,9};
  list<int> result = find_sub_set(input, 2, 9, 5);
  list<int>::iterator iter;
  for (iter = result.begin(); iter != result.end(); iter++)
    cout <<(*iter)<<", ";
  cout<<endl;
  return 1;
}

- hankm2004 August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] ArraySubSum(int[] input, int num, int sum)
{
            return SubSum(input, num, sum, 0);
}

public static int[] SubSum(int[] input, int num, int sum, int idx)
{

            
            for (int i = idx; i < input.Length; i++)
            {
                if (num == 1 && input[i] == sum)
                    return new int[1] { input[i] };
                else if (num > 1)
                {
                    int[] a = new int[num];
                    a[0] = input[i];
                    var p = SubSum(input, num - 1, sum - input[i], i + 1);
                    for (int k = 0; k < p.Length; k++)
                    {
                        a[k + 1] = p[k];
                    }
                    if (Sum(a) == sum)
                        return a;

                }

            }
            return new int[0];
}

public static int Sum(int[] arr)
        {
            int sum = 0;
            for(int i=0;i<arr.Length;i++)
            {
                sum += arr[i];
            }
            return sum;
        }

Using c#

- newdevin August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

stackoverflow.com/questions/31803275/sum-exactly-using-k-elements-solution

#include <stdio.h>
    #define SIZE(a) sizeof(a)/sizeof(a[0])
    int binary[100];
    int a[] = {1, 2, 5, 5, 100};

    void show(int* p, int size) {
            int j;
            for (j = 0; j < size; j++)
                    if (p[j])
                            printf("%d\n", a[j]);
    }

    void subset_sum(int target, int i, int sum, int *a, int size, int K) {
            if (sum == target && !K) {
                    show(binary, size);
            } else if (sum < target && i < size) {
                    binary[i] = 1;
                    foo(target, i + 1, sum + a[i], a, size, K-1);
                    binary[i] = 0;
                    foo(target, i + 1, sum, a, size, K);
            }
    }

    int main() {
            int target = 10;
            int K = 2;
            subset_sum(target, 0, 0, a, SIZE(a), K);
    }

- aka August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you meant "subset_sum" instead of "foo"

- hallock August 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

and int binary[100] should be (after a) int binary[SIZE(a)]

- simona December 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a quick JS recursion function

function findSubset (n, m, sum, subset) {
  if (sum === 0 || n.length < 1) return subset;
  var n0 = n.shift();
  if (n0 === sum) {
    subset.push(n0);
    return subset;
  }
  else if (n0 < sum) {
    subset.push(n0);
    return findSubset(n, m-1, sum - n0, subset);
  }
  else return findSubset(n, m, sum, subset);
}

- codacho August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a simple, elegant and efficient solution (similar to the knapsack problem) if the array only contains non-negative integers. My guess is that condition was part of the problem and was omitted in the question posted on the site.

- someone August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the list and iterate over of each element and build a list of tuples containing the minSum and maxSum that can be made when the number is included in the desired subset

iterate of the resulting "sum" list to see which bucket the given sum fits in; eliminate the number from list if its corresponding minSum > sum or maxSum < sum and make a filtered list

recursively do the above method on the remaining list until minSum == sum or maxSum==sum or we run out of elements in the list

def subset_helper(ls, n):
   subl = []
   min = sum(ls[:n-1])
   max = sum(ls[-(n-1):])
   for i, j in enumerate(ls):
      if i < n - 1:
         vmin = min + ls[n-1]
      else:
         vmin = min + j
      if i > len(ls) - (n):
         vmax = max + ls[len(ls)-n]
      else:
         vmax = max + j
      subl.append((vmin, vmax))
   return subl

def find_subset(ls, s, n):
   print ls, s, n
   if len(ls) < n:
      return "Failed 1"
   elif len(ls) == n:
      if sum(ls) == s:
         return ls
      else:
         return "Failed 2"
   subl = subset_helper(ls, n)
   print subl
   invmin = None
   invmax = None
   for i, v in enumerate(subl):
      print i, v
      if v[0] > s:
         invmax = i
         break
      elif v[0] == s:
         print 'Found subset at using min:', i
         if i <= (n-1):
            return ls[:n]
         else:
            return ls[:(n-1)] + [ls[i]]
      if v[1] < s:
         invmin = i
      elif v[1] == s:
         print "Found subset at using max:", i
         if i > len(ls) - n:
            return ls[-n:]
         else:
            return ls[-(n-1):] + [ls[i]]
      print invmin, invmax

   if invmin is not None and invmax is not None and invmin == invmax:
      return "Failed 3"

   invmin = invmin or -1
   invmax = invmax or len(ls) + 1
   print 'invmin,invmax', invmin, invmax
   return find_subset(ls[invmin+1:invmax], s, n)

if __name__ == '__main__':
   l = [0, 4, 5, 6, 14, 13, 1]
   s = 14
   n = 3
   ls = sorted(l)
   print find_subset(ls, s, n)

- Hari August 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Starting from the lowest possible sum, work your way up by changing your subset sum by as little as possible. This is done by having a sorted draft subset then swapping the largest element for a slightly bigger element until it's too big then undo the swap and move onto a smaller element in your draft subset. This is basically brute forcing but the extra break in the loop skips the possible subsets where the sum is already too large.

public static int[] findSub(int[] nums, int n, int m, int sum) {
		Arrays.sort(nums);
		printArray(nums);
		System.out.println("----------");
		int[] subset = Arrays.copyOfRange(nums, 0, m); // Extract the first M smallest elements
		int difference;
		int original;
		int debugCounter = 0;
		for (int i = m - 1; i >= 0; i--) {
			for (int j = m + 1; j < n; j++) {
				printArray(subset);
				System.out.println(i + " Sum = " + sum(subset));
				difference = sum - sum(subset);
				if (difference == 0)
					return subset;
				if (Arrays.binarySearch(subset, nums[j]) >= 0) {
					continue;
				}
				original = subset[i];
				subset[i] = nums[j];
				if (sum - sum(subset) < 0) {
					subset[i] = original;
					break;
				}
			}
		}
		return subset;
		
	}
	public static int sum(int[] nums) {
		int sum = 0;
		for (int i : nums) {
			sum += i;
		}
		return sum;
	}
	
	public static void printArray(int[] nums) {
		for (int i : nums) {
			System.out.println(i);
		}
	}
}

- Anonymous August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php


function findSubSet($inputs, $m, $sum) {
    $length = count($inputs);
    if ($length < $m) return null;

    if ($m == 0) return [];

    sort($inputs);

    for( $i = 0; $i <= $length - $m; $i ++) {
        $subset = array_slice($inputs, $i, $m);
        $tmpSum = array_sum($subset);
        if ($tmpSum == $sum) {
            return $subset;
        }
        else if ($tmpSum > $sum) break;
    }

    return null;
}



var_dump(findSubSet([7,1,2,3,4,5,6,7,7,7], 4, 14));

- Henry September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: O(n(n+1)/2)=n*n
Space: n(n+1)/2 // to store the limited number of subsets

n=length(A)
sets=[ ]
for (i=0 to n-1)
    newsets = [ ]
    newsets.add( setof(A[i])
    if(M == 1 && setof(A[i]) == SUM) print and break
    foreach set in sets
        s1 = sets[j].add(A[i])
        if(s1.size == M && sum(s1)==SUM) print and break
        newsets.add(s1); // we can also skip adding s1 if s1.size>M
     sets.clear()   // we dont need the old sets as we cant add next item to them
     sets.addAll(newsets)

Lets say A= {1,2,3,4,5}
M=3
SUM=12


A[i] newsets sets
-----------------------------------------------------------------------------
1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

in last iteration we have {3,4,5} whose sum is 12 and size is 3.

Now we went through A only once, but for each elements we iterated over sets which is i times hence n(n+1)/2.
In the last iteration we stored n(n+1)/2 items which is the max

- Pragalathan M September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A[i]                      newsets                                       sets
-----------------------------------------------------------------------------
1                         {1}                                           {1}
2                         {2}, {1,2}                                    {2}, {1,2}
3                         {3}, {2,3}, {1,2,3}                           {3}, {2,3}, {1,2,3}
4                         {4}, {3,4}, {2,3,4}, {1,2,3,4}                {4}, {3,4}, {2,3,4}, {1,2,3,4}
5                         {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}   {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

- Pragalathan M September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

[−2,1,−3,4,−1,2,1,−5,4]

a=0
-2

int maxSubArray(int[] array, int sum) {

if(array==null) || array.length==0)
return 0;

int max=array[a];
int maxsofar=array[a];
if(sum==max)
return;

for(int a =1; a<array.length; a++)
maxsofar=getMax(maxsofar+array[a],array[a]);
max=getmax(max,maxsofar);
if(max==sum) {
break;
return true;
}
if(max>sum)
maxsofar=array[i];
max=array[i];
}
}

- Deepak Dhakal September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can the below code work for this requirement? I'm new to programming, so might be missing something

def diff(arr,k):
    import itertools
    return [ i for i in itertools.combinations(arr,2) if abs(i[0]-i[1])==k ]

- Murali October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def k_subset_sum(numbers, k, total):
    sorted_numbers = sorted(numbers, reverse=True)
    return k_subset_sum_internal(sorted_numbers, k, total, [])


def k_subset_sum_internal(numbers, k, total, current_list):
    if k == 0:
        if sum(current_list) == total:
            return current_list
        else:
            return None
    sum_so_far = sum(current_list)
    upper_bound = total - sum_so_far - (k - 1)
    for num in numbers:
        if num <= upper_bound:
            current_list.append(num)
            result = k_subset_sum_internal(numbers, k - 1, total, current_list)
            if result is not None:
                return result
            current_list.pop()
    return None

print k_subset_sum([6,4,5,2,3,1], 4, 10)

- rizTaak October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A Java solution:

public static Set<Integer> findSubsetSizeK( int[] set, int sum, int m ) {
		Set<Integer> subset = new HashSet<>( m );
		if ( set == null || set.length < m ) { 
			return subset;
		}
		return findSubsetSizeK( set, set.length-1, sum, m, subset );
	}
	
	public static Set<Integer> findSubsetSizeK( int[] set, int n,  int sum, int m, Set<Integer> subset ) {
		if ( getSum( subset ) == sum && m == 0 ) {
			return subset;
		} else if ( m == 0 || n < 0 ) {
			return null;
		}
		if ( set[n] < sum ) {
			subset.add( set[n] );
			Set<Integer> subsetWithElement = findSubsetSizeK( set, n-1, sum, m-1, subset );
			if ( subsetWithElement != null ) {
				return subsetWithElement;
			} else {
				subset.remove( set[n] );
				return findSubsetSizeK( set, n-1, sum, m, subset );
			}
		} else {
			return findSubsetSizeK( set, n-1, sum, m, subset );
		}
	}
	
	private static int getSum( Set<Integer> set ) {
		int sum = 0;
		for ( int element : set ) {
			sum += element;
		}
		return sum;
	}

	
	public static void main( String[] args ) {
		int[] set = { 3, 34, 4, 12, 5, 2 };
		int sum = 19; // {12,5,2}
		int m = 3; 
		System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum + 
				" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
		System.out.println();
		
		sum = 17;  // {3,12,2}
		System.out.println( "A subset for " + Arrays.toString( set ) + " that sums up to " + sum + 
				" with exactly " + m + " elements is: " + findSubsetSizeK( set, sum, m ) );
		System.out.println();
	}

- DA January 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala : recursive solution with memorization
Complexity: N * M * SUM

def subset(ARR: Seq[Int], M: Int, SUM: Int): Seq[Seq[Int]] = {

    if (M > ARR.length) return Seq.empty

    val memo = mutable.Map.empty[(Seq[Int], Int, Int), Seq[Seq[Int]]]

    def run(arr: Seq[Int], m: Int, sum: Int): Seq[Seq[Int]] = memo.getOrElseUpdate((arr, m, sum), {
      if (arr.isEmpty) return Seq.empty

      val head = arr.head

      if (m == 1 && sum == head) return Seq(Seq(head))
      if (m == 1 && sum != head) return Seq.empty

      (1 until arr.length)
        .flatMap(i => run(arr.drop(i), m - 1, sum - head))
        .toSeq
        .map(head +: _)
    })

    (0 until ARR.length).flatMap(i => run(ARR.drop(i), M, SUM)).toSeq
  }

  println(subset(Seq(3, 3, 3, 4, 4, 1, 0, 9, 0), 3, 9))

- Anonymous March 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void PrintSubsets()
	{
		int source[] = {1,2,3,4,5,6};
		int currentSubset = (int)Math.pow(2, source.length)-1;
		int total=10;
		int tmp=0,noofones;
		int size=4;
		while(currentSubset>0)
		{noofones=0;
			int sum=0;
			StringBuilder sb=new StringBuilder();
			tmp=currentSubset;
			for(int k=0;k<source.length;k++)
			{
				if( (tmp&1)>0)
				{
					sum+=source[k];
					sb.append(source[k]);
					sb.append(" ");
					noofones++;
				}
					tmp>>=1;
			}
			if(sum==total && noofones==size)
				System.out.println(total+" = "+sb.toString());
		
			currentSubset--;
		}
		
	}

- Bharaneedharan Dhanaraj April 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''
On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
'''

import sys
import copy

def findSum(numList, size, sum, start, tmpSum, tmpList):

    print str(tmpList)
    result = []
    if tmpSum == sum and len(tmpList) is size:
        return tmpList
    elif tmpSum > sum:
        return []
    elif len(tmpList) is size:
        return []

    for i in range(start, len(numList)):
        tmpSum += numList[i]
        tmpList.append(i)
        result = findSum(numList, size, sum, i+1, tmpSum, tmpList)
        if len(result):
            break;
        tmpSum -= numList[i]
        tmpList.remove(i)

    return result

def main():
    numList = [1, 2, 3, 4, 5]
    size = 4
    sum = 10
    result = findSum(numList, size, sum, 0, 0, [])

    if result:
        print 'Found subset of size ' + str(size) + ':' + str(result)
    else:
        print 'Not Found'

if __name__ == '__main__':
    sys.exit(main())

- bazzinga July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

time: O(2^n) since |powerset(xs)| = 2^|xs|
space: O(n)

sizedSubset :: Int -> Int -> [Int] -> Maybe [Int]
sizedSubset m s =
  List.find ((== s) . List.sum) . fmap (List.take m) . List.permutations

- Maddie November 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's a recursive solution in JS

function findSubset (n, m, sum, subset) {
  if (sum === 0 || n.length < 1) return subset;
  var n0 = n.shift();
  if (n0 === sum) {
    subset.push(n0);
    return subset;
  }
  else if (n0 < sum) {
    subset.push(n0);
    return findSubset(n, m-1, sum - n0, subset);
  }
  else return findSubset(n, m, sum, subset);

}

- codacho August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's a recursive solution in JS

function findSubset (n, m, sum, subset) {
  if (sum === 0 || n.length < 1) return subset;
  var n0 = n.shift();
  if (n0 === sum) {
    subset.push(n0);
    return subset;
  }
  else if (n0 < sum) {
    subset.push(n0);
    return findSubset(n, m-1, sum - n0, subset);
  }
  else return findSubset(n, m, sum, subset);
}

- codacho August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's a JS recursive solution:

function findSubset (n, m, sum, subset) {
  if (sum === 0 || n.length < 1) return subset;
  var n0 = n.shift();
  if (n0 === sum) {
    subset.push(n0);
    return subset;
  }
  else if (n0 < sum) {
    subset.push(n0);
    return findSubset(n, m-1, sum - n0, subset);
  }
  else return findSubset(n, m, sum, subset);
}

- codacho August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Test post

- codacho August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void main(String[] args) throws Exception {
    int[] a = {5,3,2,1,0,4,9,7,8};
    subSeqSumSizeM(a,3,5);
  }
  
  //On a given array with N numbers, find subset of size M (exactly M elements) that equal to SUM.
  private static void subSeqSumSizeM(int[] a, int m, int sum) {
   
    if(a == null || (a.length==0) || m<=0 || m>a.length)
      return;
    
    int answer = 0;
    
    for(int i=0; i<m; i++) {
      answer = answer + a[i];
    }
    
    for(int j=1; j<a.length-m; j++) {
      if(answer == sum)
        System.out.println((j-1)+ "-" + (j+m-2));
      
      answer = answer -a[j-1] + a[j+m-1];
    }    
  }

- Jeyabarani September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

- Anonymous September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def diff(arr,m,sumofset):
    import itertools
    return [ i for i in itertools.combinations(arr,m) if abs(i[0]-i[1])==sumofset ]

- Murali October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def diff(arr,m,k):
    ''' arr = array of n number
        m=size of subset
        k=SUM of the subset'''
    import itertools
    return [ i for i in itertools.combinations(arr,m) if sum(i)==k ]

- murali October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Algorithm - iterate over the array - remove all zero's and extract the subset M find the size.

- GFS August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can remove any numbers greater than SUM, but should not remove zeros. for example, N = [0,1,2,3], M = 2, SUM=1. The only valid subset is [0,1], where zero is needed.

- jiahuang August 03, 2015 | Flag


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