Microsoft Interview Question for Software Developers


Team: Azure
Country: India
Interview Type: In-Person




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

import java.util.ArrayList;
import java.util.HashMap;

public class SumCombinations {

    //First combSize, second - sum
    private static HashMap<Integer, HashMap<Integer, SumCombinations>> CACHE = new HashMap<>();

    private static int CACHE_HITS = 0;
    private static int CACHE_MISSES = 0;

    private final ArrayList<ArrayList<Integer>> combinations;

    public SumCombinations(ArrayList<ArrayList<Integer>> combinations) {
        this.combinations = combinations;
    }

    public static SumCombinations create(int sum, int combSize) {
        if (combSize <= 0) {
            throw new IllegalArgumentException();
        }
        ArrayList<ArrayList<Integer>> combinations = new ArrayList<>();
        HashMap<Integer, SumCombinations> cacheForCombSize = CACHE.get(combSize);
        if (cacheForCombSize != null) {
            SumCombinations cacheCombinations = cacheForCombSize.get(sum);
            if (cacheCombinations != null) {
                CACHE_HITS++;
                return cacheCombinations;
            }
        }
        if (combSize == 1) {
            ArrayList<Integer> combination = new ArrayList<>(1);
            combination.add(sum);
            combinations.add(combination);
        } else {
            for (int i = 0; i <= sum; i++) {
                int remainder = sum - i;
                SumCombinations remainderCombinations = create(remainder, combSize - 1);
                for (ArrayList<Integer> remainderComb : remainderCombinations.combinations) {
                    ArrayList<Integer> combination = new ArrayList<>(combSize);
                    combination.add(i);
                    combination.addAll(remainderComb);
                    combinations.add(combination);
                }
            }
        }
        if (cacheForCombSize == null) {
            cacheForCombSize = new HashMap<>();
            CACHE.put(combSize, cacheForCombSize);
        }
        SumCombinations result = new SumCombinations(combinations);
        cacheForCombSize.put(sum, result);
        CACHE_MISSES++;
        return result;
    }

    public static void main(String[] args) {
        SumCombinations sumCombinations = create(20, 9);
        ArrayList<ArrayList<Integer>> combinations = sumCombinations.combinations;
        for (ArrayList<Integer> combination : combinations) {
            System.out.println(combination);
        }
        System.out.println(CACHE_HITS);
        System.out.println(CACHE_MISSES);
    }
}

- ctash April 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void recursivePrint(int sum, int n) {
		int data[] = new int[sum];
		int len = 0;
		int originalSum = sum;
		recursivePrintImproved(sum, n, data, len, originalSum, n);
	}

	private void recursivePrintImproved(int sum, int n, int data[], int len, int originalSum, int originalN) {
		if (n == 0) {
			for (int j = 0; j < len; j++) {
				System.out.print(data[j] + " ");
			}
			System.out.println();
			return;
		}
		for (int i = 0; i <= sum; i++) {
			int sum1 = 0;
			if (len == originalN - 1) {
				for (int j = 0; j < len; j++) {
					sum1 += data[j];
				}
				i = originalSum - sum1;
			}
			data[len] = i;
			recursivePrintImproved(sum - i, n - 1, data, len + 1, originalSum, originalN);
		}
	}

- RP April 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rajendra: Can you please explain the code?

- Sibendu Dey April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We will use recursion here, as one has to print event sequence possible, which would require to access it, which means, time goes to exponential.

public static void PrintRec(List<int> data, int sum, int n)
{
	if(n == 0)
	{
		if(sum == data.Sum())
		{
			PrintList(data);
		}
		return;
	}
	if(n == 1)
	{
		var newList = new List<int>();
		newList.AddRange(data);
        PrintRec(newList.Add(sum - data.Sum()),sum,0);
        return;
	}
	for(int i = 0; i <= (sum - data.Sum()); i++)
	{
		var newList = new List<int>();
		newList.AddRange(data);
		PrintRec(newList.Add(i),sum, n-1);
	}
}

public static void PrintPermutation(int sum, int n)
{
	if(n < 0 || sum < 0)
	{
		return;
	}
	PrintRec(new List<int>(),sum,n);
}

public static void PrintList(List<int> data)
{
	foreach(var val in data)
	{
		Console.Write("{0},",val);
	}
	Console.WriteLine();
}

The complexity of this O(sum^n), although the actual number is much lower than this.
Space complexity os O(N*N)

- sonesh April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Sibendu Dey, Its like there are n nested loops iterating until sum. but for each iteration we are interested only in printing the sum in n values. so are waiting for two values to calculate from the loops and as the length turns to n-1 calculating the third/index value.
However we don't need to recurse just to print so removing that as well. Here it is.

public static void recursivePrint(int sum, int n) {
		int data[] = new int[sum];
		int len = 0;
		int originalSum = sum;
		recursivePrintImproved(sum, n, data, len, originalSum, n);
	}
	private static void recursivePrintImproved(int sum, int n, int data[],
			int len, int originalSum, int originalN) {
//		System.out.println("len: " + len + " sum: " + sum + " i: "
//				+ (originalSum - sum) + " n:" + n);
		for (int i = 0; i <= sum; i++) {
			int sum1 = 0;
			if (len == originalN - 1) {
				for (int j = 0; j < len; j++) {
					sum1 += data[j];
					System.out.print(data[j] + " ");
				}
				data[len] = originalSum - sum1;
				System.out.print(data[len] + " ");
				System.out.println();
				break;
			} else {
				data[len] = i;
				recursivePrintImproved(sum - i, n - 1, data, len + 1,
						originalSum, originalN);
			}
		}
	}

- RP April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my version, I just check all possible combinations and see if the indices sum up to "sum". I reset start index to zero each time so we get all permutations of sum.

public static void main(String[] args)
  {
    int n = 16;
    int k = 2;
    combSum(n, k, new ArrayList<Integer>(), 0);
  }
  
  public static void combSum(int n, int k, ArrayList<Integer> list, int start) {
    if (list.size() == k && n != 0) return;
    if (list.size() == k && n == 0) {
      System.out.println(list);
      return;
    }
    for (int i = start; i <= n; i++) {
      list.add(i);
      combSum(n - i, k, list, 0);
      list.remove(list.size() - 1);
    }
  }

- Anonymous April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically, every recursion step you narrow your task to n-1 case, eventually you'll end up to solving the task, with n = 1. Here is recursive solution on Golang:

func generate(k, curSum, target int, output []int) {
	if k == 0 {
		output = append(output, target-curSum)
		fmt.Println(output)
		return
	}

	for i := 0; i <= target-curSum; i++ {
		output = append(output, i)
		generate(k-1, curSum+i, target, output)
		output = output[:len(output)-1]
	}
}

func main() {
	n, target := 4, 6
	array := make([]int, 0, n-1)
	generate(n-1, 0, target, array)
}

- Marcello Ghali April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Too much code. I don't like to code at all. Be lazy.

/* 
For a given Sum and N print all the combinations .
This is integer partition problem.
Constrained to number of partitions := N 
Given an integer is n, imagine 
1 1 1 1 ... 1 ( n 1's)
Now, there can be n-1 cut positions.
Choosing or not choosing a cut position 
will create a partition.
Thus, create a binary string with n-1 digits.
When 1, we choose the cut, when 0, we do not.
This will produce all the cuts and thus, all partitions.
The problem is constrained by number of cuts := N-1
*/
def partition_int( n , N ){
  n_splits = n - 1
  max = 2 ** n_splits 
  partitions = set()
  for ( x : [1:max] ) {
    bs = str(x,2)
    // do 0 padding on left
    bs = '0' ** ( n_splits - size(bs) ) + bs 
    nums = list()
    c = 1
    for ( b : bs.value ){
      if ( b == _'1' ){
        nums += c
        c = 1
      } else {
        c += 1
      }
    } 
    nums += c
    continue ( size(nums) != N )
    // to make the partitions unique 
    sorta(nums)
    ps = str(nums,',')
    continue ( ps @ partitions )
    // only when does not exist 
    partitions += ps 
    // now print 
    printf('%s -> %s \n', bs, ps )
  }
}
partition_int( @ARGS = list( @ARGS ) -> { int($.o) } )

The result if you run it :

zmb tmp.zm 16 2
000000000000001 -> 1,15 
000000000000010 -> 2,14 
000000000000100 -> 3,13 
000000000001000 -> 4,12 
000000000010000 -> 5,11 
000000000100000 -> 6,10 
000000001000000 -> 7,9 
000000010000000 -> 8,8

Let's try another one:

zmb tmp.zm 10 4
000000111 -> 1,1,1,7 
000001011 -> 1,1,2,6 
000010011 -> 1,1,3,5 
000010101 -> 1,2,2,5 
000100011 -> 1,1,4,4 
000100101 -> 1,2,3,4 
000101010 -> 2,2,2,4 
001001001 -> 1,3,3,3 
001001010 -> 2,2,3,3

Hope this should do fine.

- NoOne April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
I'm not sure but the recursive implementation is given and 
according to the comment in the question "need a better solution
so that we can store results by using hashmaps" there is some kind
of optimization looked for using memoization.
This is might be interesting if N is big, because prefixes with the
same sum and length have suffixes that can be re-used (are the same).
But then, if the prefixes produce the same sum with the same length, the
same results can be reused. So, a divide and conquer strategy with
memoization might be good.

Let's assume we divide N to reach S (the Sum), there are S ways to do so,
Left + Right = S: If we solved Left, we can reuse the solution for the Right
etc. Sum(S, N) returns a List where each element contains a List of integers
that sum up to S (actually comma separated strings in the implementation)

Sum(S, N) = Sum(s, N/2) ** Sum(S-s, N/2), if N > 1 AND for each 0 <= s <= S,
                                          whereas the "**" indicates all permutations
                                          of the two lists returned from Sum(...)

Below in Java8 with "Sum" being "recursiveSolve" and some inspection 
counters to actually show the improvements over the just recursive 
solution.
*/

package com.stackoverflow;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;

public class Main {
    public static class SumCreator {
        private int mDigits, mSum;
        private Hashtable<Long, List<String>> mMemo = new Hashtable<>();
        private int mHitCounter = 0;

        SumCreator(int digits, int sum) {
            assert (digits > 0 && sum > 0);
            mDigits = digits;
            mSum = sum;
        }

        public void printAll() {
            System.out.println("Solve it for Digits: " + mDigits + ", Sum: " + mSum);
            List<String> results = recursiveSolve(mDigits, mSum);
            for(String res : results) {
                System.out.println(res.substring(0, res.length() - 2)); // remove last ", "
            }
            System.out.println("Memo HT size: " + mMemo.size() +
                    ", Memo hit count: " + mHitCounter +
                    ", #results: " + results.size() +
                    "\n\n\n");
        }

        List<String> recursiveSolve(int digits, int sum) {
            List<String> result = mMemo.get(createKey(digits, sum));
            if(result == null) {
                result = new ArrayList<>();
                if(digits == 1) {
                    result.add(sum + ", ");
                } else {
                    for (int s = 0; s <= sum; s++) {
                        List<String> left = recursiveSolve(digits / 2, s);
                        List<String> right = recursiveSolve(digits - (digits / 2), sum - s);
                        for (String l : left) {
                            for (String r : right) {
                                result.add(l + r);
                            }
                        }
                    }
                }
                mMemo.put(createKey(digits, sum), result);
            } else {
                mHitCounter++;
            }
            return result;
        }

        static long createKey(int digits, int sum) {
            return (long)digits * (long)Integer.MAX_VALUE + (long)sum;
        }
    }

    public static void main(String[] args) {
        new SumCreator(1, 16).printAll(); // Memo HT size: 1, Memo hit count: 0, #results: 1
        new SumCreator(2, 16).printAll(); // Memo HT size: 18, Memo hit count: 17, #results: 17
        new SumCreator(3, 16).printAll(); // Memo HT size: 35, Memo hit count: 306, #results: 153
        new SumCreator(4, 16).printAll(); // Memo HT size: 35, Memo hit count: 306, #results: 969
        new SumCreator(5, 16).printAll(); // Memo HT size: 52, Memo hit count: 595, #results: 4845
        new SumCreator(6, 16).printAll(); // Memo HT size: 52, Memo hit count: 595, #results: 20349
    }
}

- Chris April 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def printPerm(Sum,N,items):
     if N == 0 and Sum == 0:
        print items 
        return; 
     if Sum < 0 or N < 0 :
         return; 
     for i in range(Sum+1):
      items.append(i);   
      printPerm(Sum-i,N-1,items);
      items.remove(i);

- koustav.adorable May 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

int recursive (int n, int sum, int origN, int level, int *values)
{
int i, j;
int total;

if (n == 1) {
for (j = origN - 1; j > 0; j--) {
printf ("%d ", values [j]);
}
printf ("%d\n", sum);
return 0;
}

for (i = 0; i <= sum; i++) {
total = sum - i;

values[n - 1] = i;
level++;

recursive (n - 1, total, origN, level, values);
}

return 0;
}

//
// Code is written in C language and executed successfully using GCC compiler and it
// works fine.
//
int main() {
int data[4]; // plug-in your N here in data[N]
int sum = 16; // plug-in your sum value here
return recursive (4, sum, 4, 0, data);

}

- Cowboys June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void AllCombinations(int Sum, int n)
{
    AllCombinations(Sum, n, "");
}
private static void AllCombinations(int sum, int n, string output)
{
    if (n == 1)
    {   
        Console.WriteLine(output+sum);
    }
    else
    {
        for(int i=sum; i>=0; i--)
        {
            string new_output = output + i + ",";
            AllCombinations(sum - i, n - 1, new_output);
        }
    }
}

- yasharonline June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;
import java.util.*;

public class Aish
{
//public static int count;
public static void generatesum(ArrayList<Integer>x,int total,int n)
{
int sum=0;
if(x.size()==n)
{
for(Integer y:x)
{
sum+=y;
}
if(sum==total)
System.out.println(x);
return;
}
for(int i=0;i<=total;i++)
{
x.add(i);
generatesum(x,total,n);
x.remove(x.size()-1);
}

}
public static void main(String[] args)
{
int total=15;
int n=3;
ArrayList<Integer> x=new ArrayList<Integer>();
generatesum(x,total,n);
}
}

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

import java.util.*;

class GetCombs {
	public static void main (String[] args) {
		int sum = 16, n = 2;
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		getCombs(res, new ArrayList<Integer>(), sum, n);
		for (List<Integer> al : res)	System.out.println(al);
	}
	
	private static void getCombs(List<List<Integer>> res, List<Integer> al, int sum, int n) {
		if (n == 0) {
			if (sum > 0)	return;
			res.add(new ArrayList<Integer>(al));
			return;
		}
		
		for (int a = 0; a <= sum; a++) {
			al.add(a);
			getCombs(res, al, sum - a, n - 1);
			al.remove(al.size() - 1);
		}
	}
}

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

My Output for N =3 and Sum = 16

0 0 16
0 1 15
0 2 14
0 3 13
0 4 12
0 5 11
0 6 10
0 7 9
0 8 8
0 9 7
0 10 6
0 11 5
0 12 4
0 13 3
0 14 2
0 15 1
0 16 0
1 0 15
1 1 14
1 2 13
1 3 12
1 4 11
1 5 10
1 6 9
1 7 8
1 8 7
1 9 6
1 10 5
1 11 4
1 12 3
1 13 2
1 14 1
1 15 0
2 0 14
2 1 13
2 2 12
2 3 11
2 4 10
2 5 9
2 6 8
2 7 7
2 8 6
2 9 5
2 10 4
2 11 3
2 12 2
2 13 1
2 14 0
3 0 13
3 1 12
3 2 11
3 3 10
3 4 9
3 5 8
3 6 7
3 7 6
3 8 5
3 9 4
3 10 3
3 11 2
3 12 1
3 13 0
4 0 12
4 1 11
4 2 10
4 3 9
4 4 8
4 5 7
4 6 6
4 7 5
4 8 4
4 9 3
4 10 2
4 11 1
4 12 0
5 0 11
5 1 10
5 2 9
5 3 8
5 4 7
5 5 6
5 6 5
5 7 4
5 8 3
5 9 2
5 10 1
5 11 0
6 0 10
6 1 9
6 2 8
6 3 7
6 4 6
6 5 5
6 6 4
6 7 3
6 8 2
6 9 1
6 10 0
7 0 9
7 1 8
7 2 7
7 3 6
7 4 5
7 5 4
7 6 3
7 7 2
7 8 1
7 9 0
8 0 8
8 1 7
8 2 6
8 3 5
8 4 4
8 5 3
8 6 2
8 7 1
8 8 0
9 0 7
9 1 6
9 2 5
9 3 4
9 4 3
9 5 2
9 6 1
9 7 0
10 0 6
10 1 5
10 2 4
10 3 3
10 4 2
10 5 1
10 6 0
11 0 5
11 1 4
11 2 3
11 3 2
11 4 1
11 5 0
12 0 4
12 1 3
12 2 2
12 3 1
12 4 0
13 0 3
13 1 2
13 2 1
13 3 0
14 0 2
14 1 1
14 2 0
15 0 1
15 1 0
16 0 0

- NoMind April 23, 2017 | 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