Microsoft Interview Question
Software DevelopersTeam: Azure
Country: India
Interview Type: In-Person
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);
}
}
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)
@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);
}
}
}
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);
}
}
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)
}
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.
/*
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
}
}
#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);
}
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);
}
}
}
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);
}
}
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);
}
}
}
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
- ctash April 23, 2017