Megasoft Interview Question
Software Engineer in TestsTeam: XBOX
Country: United States
Solution in Python. Essentially finding every combination of elements in the given list through a DFS Tree traversal ... finding sum at the leaf node and printing if sum==N
def combinationsDFS(myList, i, N, sumSoFar, ResultSoFar):
if i >= len(myList):
if (sumSoFar == N):
print [ i for i in range(len(myList)) if ResultSoFar[i]]
return
for child in [True, False]:
combinationsDFS(myList, i+1, N, sumSoFar+myList[i] if child is True else sumSoFar, \
ResultSoFar+[child])
return
## MAIN
combinationsDFS([1, 1, 2, 2, 4], 0, 4, 0, [])
## OUTPUT
[0, 1, 2]
[0, 1, 3]
[2, 3]
[4]
I'm not familiar with C# either. Following is my C code. It should be easy to understand:
#include <stdio.h>
#include <stdlib.h>
void print_sum_combinations(int dest[], int next, int arr[], int index, int remain, int* pCount)
{
if(index < 0){
if(remain == 0 && next > 1){
int i = 0;
for(; i < next; ++i) printf("%d ", dest[i]);
puts("");
++*pCount;
}
return;
}
//here to ignore zero values
if(arr[index] == 0){
print_sum_combinations(dest, next, arr, index-1, remain, pCount);
return;
}
//arr[index] != 0, we can choose arr[index]
dest[next] = index;
print_sum_combinations(dest, next+1, arr, index-1, remain-arr[index], pCount);
//we do not choose arr[index]
print_sum_combinations(dest, next, arr, index-1, remain, pCount);
}
void PrintSumCombinations(int arr[], int n, int sum)
{
int count = 0, *indexArr = (int*)malloc(n * sizeof(int));
print_sum_combinations(indexArr, 0, arr, n-1, sum, &count);
free(indexArr);
if(count == 0) puts("None");
}
int main()
{
int a[] = {0, -1, -1, 0, 0, 1, 1, 2};
PrintSumCombinations(a, sizeof(a)/sizeof(int), 0);
return 0;
}
Its in Java but I think that C# is similar.
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<Integer>(Arrays.asList(new Integer[] { 1, 1, 2, 2, 4 }));
List<Integer> result = new ArrayList<Integer>();
printSumCombinations(numbers, 4, result, 0);
}
public static void printSumCombinations(List<Integer> numbers, int sum, List<Integer> result, int currentIndex) {
if (sum == 0) {
System.out.println(result);
return;
}
if (currentIndex > numbers.size() - 1) {
return;
}
if (numbers.get(currentIndex) != 0) {
result.add(currentIndex);
printSumCombinations(numbers, sum - numbers.get(currentIndex), result, currentIndex + 1);
result.remove(result.size() - 1);
}
printSumCombinations(numbers, sum, result, currentIndex + 1);
}
Code is quite correct but you should take care of small things like
For a sample input of integers {1,1,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}
Input size is 28 integers and execution time for your code comes up to be 12.676857776 seconds which is huge!!!!!!!
Just add a statement to your code and see the difference.
Just put a check that if sum<0 then return from the call
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<Integer>(Arrays.asList(new Integer[] { 1, 1, 2, 2, 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}));
List<Integer> result = new ArrayList<Integer>();
long starttime = System.nanoTime();
printSumCombinations(numbers, 4, result, 0);
long endtime = System.nanoTime();
System.out.println("Elapsed time is " + (endtime - starttime));
}
public static void printSumCombinations(List<Integer> numbers, int sum, List<Integer> result, int currentIndex) {
if (sum == 0) {
System.out.println(result);
return;
}
if (currentIndex > numbers.size() - 1 || sum<0) {
return;
}
if (numbers.get(currentIndex) != 0) {
result.add(currentIndex);
printSumCombinations(numbers, sum - numbers.get(currentIndex), result, currentIndex + 1);
result.remove(result.size() - 1);
}
printSumCombinations(numbers, sum, result, currentIndex + 1);
}
Execution time = 0.002228474 seconds
Anyways simple solution just take care of small things
- Shch December 18, 2013