Microsoft Interview Question for Software Engineer in Tests


Country: United States




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

What about a Combination algorithm a permutation algorithm will work as well but we need to get rid of duplicates

combine(new int[] { 1, 2, 3, 4, 5, 6 }, new List<int>(), 0);

        static void combine(int[] a, List<int> outstr, int index)
        {
            for (int i = index; i < a.Length; i++)
            {

                int count = 0;
                foreach (var item in outstr)
                    count += item;

                if ((a[i] + count) == 10)
                {
                    foreach (var item in outstr)
                        Console.Write("{0}", item);

                    Console.Write("{0}", a[i]);
                    Console.WriteLine();
                }


                outstr.Add(a[i]);
                combine(a, outstr, i + 1);
                outstr.Remove(a[i]);
            }
        }

result:
1234
136
145
235
46

- Valentino Marin March 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple, recursive approach, but the algorithm will run in exponential time.

- plasma April 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 16 vote

This is a very simple approach based on dynamic programming method :

the function could be launch by calling : findNumbers(list, 0, 0, goal, "");

static void findNumbers(int[] list, int index, int current, int goal, string result)
{ 
  if (list.Length < index || current>goal)
          return;
   for (int i = index; i < list.Length; i++) {
      if (current + list[i] == goal)   {
         Console.WriteLine(result + " " + list[i].ToString());
       }
       else if (current + list[i] < goal) {
           findNumbers(list, i + 1, current + list[i], goal, result + " " + list[i].ToString());
        }
  }
}

- developer.2020 March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

whats goal = ?

- question..? March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice 1 :)

- Nitin March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one

- catty March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

this is simple dfs, not dynamic programming

- upi March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What will be the complexity of this solution

- Anonymous May 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm also thinking about the complexity of algo. could you share it

- Anon May 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity should be O(n3)

- ashek1520 May 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity should be O(n3)

- ashek1520 May 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

In the worst case for every number you take you have 2 paths to go, one is directly to the next number using the for loop and the other is recursive call to the next number.
Therefore the complexity of the program is (2^n)

- Naveen Reddy Mandadi August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Nazzer,
What if I'm going to have the array like this {1, 1,1,1,1,1,1,1,1,1,1,2, 3, 4, 5, 6 };
Your method doesn't cover all subsets.

george

- george September 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity is O(2^n-1)....since we are considering all the possibilities ..

- er.dileshverma August 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ArrayList GetSubsets(int [] Set, int size, int sum, int index)
{
      ArrayList<ArrayList<int>> allSubsets;
      if( index == size ){
      allSubsets = new ArrayList<ArrayList<int>>();
      //allSubsets .add(new ArrayList());    // Add Empty subset
      return allSubsets ;
      }
  else {
     int first = Set[index];
    ArrayList otherSets = GetSubsets(Set, size, sum, index + 1);

    ArrayList<ArrayList<int>> allSets = new ArrayList<ArrayList<int>>();

     allsubsets = getSubsets(set, index + 1);
     int item = set.get(index);
    ArrayList<ArrayList<Integer>> moresubsets =  new ArrayList<ArrayList<Integer>>();
    for (ArrayList<Integer> subset : allsubsets) {
   if( IsValidSet( new ArrayList<Integer>(subset).add(item), sum) )
     {
       ArrayList<Integer> newsubset = new ArrayList<Integer>();
      newsubset.addAll(subset); //
      newsubset.add(item);
      moresubsets.add(newsubset);
     }
   }
   allsubsets.addAll(moresubsets);
  }
 return allsubsets;
        
}

public boolean IsValidSet(ArrayList set, int sum)
{
      int tempSum= 0;
      foreach(int elem : set)
            tempSum +=elem;
     
     return tempSum == sum;
}

- loosy.jhony March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

import java.util.*;
public class KNumberSubset {
private int number;
private int sum;
private LinkedList<Integer> subset;
private int[] numbers={1,2,3,4,5,6};
  public KNumberSubset(int[] numbers,int number) {
	// TODO Auto-generated constructor stub
	  this.numbers=numbers;
	  this.number=number;
	  sum=0;
	  subset=new LinkedList<Integer>();	 
}  
  public void findSubset(int startPoint)
  {
	  if(sum==number)
	  {
		  System.out.println(subset+" :: "+sum);
	  }
	  else
		  for(int i=startPoint;i<6;i++)
		  {
			  sum=sum+numbers[i];
			  if(sum>10)
			  {
				sum=sum-numbers[i];
				  break;				
			  }
			  subset.add((int)numbers[i]);
			  findSubset(i+1);			  
			  sum=sum-numbers[i];
			  subset.removeLast();
		  }
  }  
  public static void main(String args[])
  {
	  int[] numbers={1,2,3,4,5,6};
	  int number=10;
	  Arrays.sort(numbers);
	  KNumberSubset ki=new KNumberSubset(numbers,number);
	  ki.findSubset(0);
  }
}

- TechTycoon March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Code is good,
but i think it will fail in following scnerio's, where number will repeated
{3,2,1,3,1,5}

- Gopal March 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Gopal
Thanks for the comment,
even for you I/P {3,2,1,3,1,5} the above code will work, assuming that the subset may contains duplicate values

[1, 1, 2, 3, 3] :: 10
[1, 1, 3, 5] :: 10
[1, 1, 3, 5] :: 10
[2, 3, 5] :: 10
[2, 3, 5] :: 10

- TechTycoon November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
Thanks for posting this code. This has minor corrections and is verified: {{{ import java.util.*; public class KNumberSubset { private int number; private int sum; private LinkedList<Integer> subset; private int[] numbers; public KNumberSubset(int[] numbers, int number) { this.numbers = numbers; this.number = number; sum = 0; subset = new LinkedList<Integer>(); } public void findSubset(int startPoint, int limit) { if (sum == number) { System.out.println(subset + " :: " + sum); } else { for (int i = startPoint; i < numbers.length; i++) { sum = sum + numbers[i]; if (sum > limit) { sum = sum - numbers[i]; break; } subset.add((int) numbers[i]); findSubset(i + 1, limit); sum = sum - numbers[i]; subset.removeLast(); } } } public static void main(String args[]) { int[] numbers={1,2,3,4,5,6}; int number=15; Arrays.sort(numbers); KNumberSubset ki = new KNumberSubset(numbers, number); ki.findSubset(0, number); } } - JeremyF March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

instead break , you may need to use continue. with break, it fails with this input

int[] numbers={4,5,3};
int number=7;

- sudaredd July 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

my suggestion is to use dp, and we can do this in O(n*k) time, where k is the target sum numer.

The basic idea is to fill a Boolean dptable of size n*(k+1), and dptable[i][j] means the first i numbers form the set have a subset that sum to j, and the recursive relation is dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]).

Here is the code, and the output is a little ugly, is there any suggestion to improve the output based on the boolean table?

#include<iostream>
using namespace std;

bool ** dptable;
//n is the size of data, m is the largest number in the set
void find(int * data,int n, int target)
{
if(n<1||target<0)
return;
//initialize
dptable= new bool *[n];
for(int i=0;i<n;i++)
{
dptable[i]=new bool[target +1];
dptable[i][0]=true;
}
for(int i=1;i<target+1;i++)
{
if(data[0]==i)
{
dptable[0][i]=true;
}
else
dptable[0][i]=false;
}

//fill the table row by row
for(int i=1;i<n;i++)
{
for(int j=0;j<target+1;j++)
{
dptable[i][j]=(dptable[i-1][j])|(dptable[i-1][j-data[i]]);
}
}
}

void output(int *data, int m, int target) //m is row num, fisrt call should be n-1
{
if (!dptable[m][target])
{
cout<<"cannot find such a subset"<<endl;
return;
}
if(m==0&&target!=0&&dptable[0][target])
{
cout<< "{"<<target<<"}";
return;
}
if(m==0&&target==0)
{
return;
}
int i=m;
int j=target;
if (dptable[m-1][target]) //supose 0 is not in the set(otherwise, just add it to any satisfied subset)
{
output(data, i-1,j);
}
if(target>=data[i]&&dptable[m-1][target-data[i]])
{
cout<<"{"<<data[i];
output(data, i-1,target-data[i]);
cout<<"}";
}
}

void main()
{
int data[]={1,2,3,4,5,6};
int n=6;
find(data,n, 10);
output(data, n-1,10);
}

- luckycat March 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks. I have modified your code for prettier output. I have also added a check to the find function so that it doesn't access invalid entries.

#include <cstdio>
#include <vector>
using namespace std;

bool** dp;

void display(const vector<int>& v) {
    for (int i = 0; i < v.size(); ++i)
        printf("%d ", v[i]);
    printf("\n");
}

void output(const vector<int>& a, int i, int sum, vector<int>& p) {
    if (i == 0 && sum != 0 && dp[0][sum]) {
        p.push_back(a[i]);
        display(p);
        return;
    }
    if (i == 0 && sum == 0) {
        display(p);
        return;
    }
    if (dp[i - 1][sum]) {
        vector<int> b = p;
        output(a, i - 1, sum, b);
    }
    if (sum >= a[i] && dp[i - 1][sum - a[i]]) {
        p.push_back(a[i]);
        output(a, i - 1, sum - a[i], p);
    }
}

void find(const vector<int>& a, int sum) {
    if (a.size() == 0 || sum < 0) return;
    dp = new bool*[a.size()];
    for (int i = 0; i < a.size(); ++i) {
        dp[i] = new bool[sum + 1];
        dp[i][0] = true;
    }
    for (int i = 1; i < sum + 1; ++i)
        dp[0][i] = (a[0] == i) ? true : false;
    for (int i = 1; i < a.size(); ++i)
        for (int j = 0; j < sum + 1; ++j)
            dp[i][j] = (a[i] <= j) ? dp[i - 1][j] || dp[i - 1][j - a[i]] : dp[i - 1][j];
    if (!dp[a.size() - 1][sum]) {
        printf("There are no subsets with sum %d\n", sum);
        return;
    }
    vector<int> p;
    output(a, a.size() - 1, sum, p);
}

int main() {
    vector<int> a = {1,2,3,4,5,6};
    find(a, 10);
    return 0;
}

- Nobody November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output:
4 3 2 1
5 3 2
5 4 1
6 3 1
6 4

- Nobody November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_subsets(int arr[], size_t sz_arr, const int sum_of_subset)
{
	const unsigned int max_mask_of_subset = (int)pow((double)2, (int)sz_arr);
	const unsigned int mix_mask_of_subset = 1;
	unsigned int sum = 0;
	std::stringstream str_stream;

	for (size_t mask = mix_mask_of_subset; mask < max_mask_of_subset; ++mask)
	{
		for (size_t index = 0; index < sz_arr; ++index)
		{
			if ( (mask >> index) & 0x01 )
			{
				sum += arr[sz_arr - 1 - index];
				str_stream << arr[sz_arr - 1 - index] << " ";
			}
		}
		if (sum == sum_of_subset)
		{
			std::cout << str_stream.str() << std::endl;
		}
		str_stream.str("");//.clear();
		sum = 0;
	}
}


int main()
{
	int arr[] = {1,2,3,4,5,6,7,8,9,11,12,11};
	size_t sz_arr = sizeof(arr)/sizeof(arr[0]);
	const unsigned int sum_of_subset = 22;
	
	find_subsets(arr, sz_arr, sum_of_subset);

	return 0;
}

- Michael March 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My suggestion was the bit mask logic

- Michael March 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void _find(int a[], int used[], int v, int sum , int current)
	{
		
		if( current > a.length )
		{
			return;
		}
		sum += a[current];
		if( sum == v )
		{
			System.out.println(Arrays.toString(used));
			return;
		}else if( sum > v)
		{
			return;
		}
		for( int i = current+1; i < a.length ; i++ )
		{
			if( used[i] == 0 )
			{	used[i] = 1;_find(a,used,v,sum,i);used[i] = 0; }
		}
	}
	public void findSubset(int a[], int v)
	{
		Arrays.sort(a);
		int used[] = new int[a.length];
		System.out.println(Arrays.toString(a));
		for(int i=0;i<a.length;i++)
		{
			used[i] = 1;
			_find(a,used,v,0,i);
			used[i] = 0;
		}
	}

- Ragnarok March 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SubsetInSet
{
public static void main(String args[])
{
//int[] numbers={1,2,3,4,2,2,2,2,5,2};
//int numbers[]={1,2,3,6};
int number=10;
int numbers[]={3,2,1,3,1,5};

int sum=0,j=0;

while(j<numbers.length)
{
sum=0;
String strnum="";
for(int i=j;i<numbers.length;i++)
{
sum=sum+numbers[i];
if(sum<=10)
{
strnum+= " "+Integer.toString(numbers[i]);
if(sum==10)
{
System.out.println(strnum);
break;
}
}
if(sum>10)
{
sum=sum-numbers[i];
}
}
j++;
}
}
}


Here I am adding all those numbers from array in String whose sum equals 10 and displaying them. This is a simple code I am adding. Check this out.

- Nawaz Ahmed March 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it would be great if you test your code before you submit, its failing for 1, 2, 3, 4, 5, 6

- anonymous November 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool sumgroup(int[] input, int sum, int start, ref List<List<int>> result)
        {
            bool flag = false;
            for (int i = start; i < input.Length; i++)
            {
                if (input[i] > sum)
                    break;
                if (input[i] == sum)
                {
                    Console.Write(input[i]);
                    List<int> newmatch = new List<int>();
                    newmatch.Add(input[i]);
                    result.Add(newmatch);
                    flag = true;
                    break;
                }
                else
                {
                    int countResult = result.Count;
                    if (sumgroup(input, sum - input[i], i + 1, ref result))
                    {
                        Console.Write(input[i]);
                        int count = result.Count - countResult;
                        for (int k = 0; k < count; k++)
                        {
                            result[result.Count -1 -k].Add(input[i]);
                        }
                        flag = true;
                    }
                }
            }
            return flag;
        }

- karthik March 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sample usage

mainset=[-2,-1,2,3,4,5,6]
   n=len(mainset)
   subset_sum(0,n,[0]*n, 0, 4)

code in python (also prints the subsets lexicographically)

def subset_sum(mi,n,curset, cursum, target):
   #calculate all possible subsets sum == target
   #assumes mainset is already sorted in ascending order
   global mainset

   if cursum>target: #return constraint violated
      return

   if cursum==target: #subset found print
      print map(lambda i: mainset[i], filter(lambda x: curset[x]==1,range(n)))

   if mi==n: #return leaf reached
      return

   else: #explore more subsets
     for i in range(mi,n):
       curset[i]=1
       cursum+=mainset[i]
       subset_sum(i+1,n,curset,cursum,target)
       curset[i]=0
       cursum-=mainset[i]

- light October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use the following program to generate all the subsets of {1...n} elements. Once you have a subset, then its fairly simple to perform additional logic on that subset like checking if its sum is equal to 10 or not :

/* 
Generate all subsets of set {1..k}
*/
void Main()
{	
	Console.WriteLine("Enter value of k in set {1..k}");
	int subSetSize = Convert.ToInt32(Console.ReadLine());
	
	int[] setElements = new int[subSetSize];
	Console.WriteLine("Enter the elements of subset");
	for(int i = 0; i < subSetSize; i++)
	{
		setElements[i] = Convert.ToInt32(Console.ReadLine());
	}
	
	int[] startArray = new int[subSetSize]; //all defaults to 0
	int[] lastArray = new int[subSetSize];
	
	for(int i = 0; i < lastArray.Length ; i++)
		lastArray[i] = 1;
	
	while(!startArray.AreSequenceEqual(lastArray))
	{
		GetNextItem(ref startArray,subSetSize);
		Console.Write("{");
		for(int i = 0; i < startArray.Length; i++)
		{
			if(startArray[i] == 1)
			{
				Console.Write(setElements[i]);
				Console.Write(",");
			}
		}
		Console.WriteLine("}");
	}
}

/* - Start from rightmost element. Check if the element is smaller than the upper limit or not. If smaller then
increment it by 1, followed by setting all elements further(right) to it to 1.
*/
public void GetNextItem(ref int[] start, int subSetSize)
{
	int p = subSetSize - 1;
	while(!(start[p] != 1))
	{
		p = p - 1;
	}
	
	start[p] = 1;
	
	for(int i = p + 1; i < subSetSize; i++)
	{
		start[i] = 0;
	}
}

// Define other methods and classes here

- rk.pawan March 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

instead break , you may need to use continue. with break, it fails with this input

int[] numbers={4,5,3};
int number=7;

- sudaredd July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's how I would do this in Haskell:

subsetSum n ns = [ns | (t, ns) <- subsets ns, t == n]
    where
      subsets = foldr (\n a -> (n, [n]):map (\(t,ns) -> (t+n,n:ns)) a ++ a) []

And testing it out in GHCi:

λ> subsetSum 0 [-3, 2, 1, 5, -2, -1]
  [[-3,2,1],[-3,1,5,-2,-1],[-3,5,-2],[2,1,-2,-1],[2,-2],[1,-1]]

- Charles Strahan March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use dp

- yogeshhan March 03, 2012 | 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