Interview Question


Country: United States




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

a brutforce recursive solution

void func(int i, int[] array){

        if( sumFirstK(k, array) == target){
            Print first K elements of array
        }

        for(int j=i; j<array.length; j++){
            swap(i, j, array);
            func(i+1, array);
            swap(j, i, array);
        }
    }

- Michael O August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

brutforce recursive solution

void func(int i, int[] array){

        if( sumFirstK(k, array) == target){
            print first K elements of Array
        }

        for(int j=i; j<array.length; j++){
            swap(i, j, array);
            func(i+1, array);
            swap(j, i, array);
        }

    }

- Michael August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution i came up with during the interview was something of this sort:

function sumTwo(array, target) { ... } //O(n) using hashing to return [x,y] such that x+y=target

function sumNK(array, k, target) {
  if (k === 2 ) { 
	return sumTwo(array, target); 
  }else {
	for(var i = 0; i < array.length; ++i) {
	      var subTarget = target - array[i];
	      var subArray = array.slice().splice(i, 1); //make copy and remove currently used elem
	      var subResult = sumNK(subArray, k - 1, subTarget);
              //save possible subResult if valid and return it....
	}
   }
}

- tnutty2k8 August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public static String getAllPosibleCombinations(int[] arr, int expectedSum, int n, StringBuilder possibleCombinations) {
if (n == arr.length) {
return possibleCombinations.toString();
}
for (int i = 0; i < arr.length; i = i + 1) {
int sum = 0;
int k = i;
int firstOperandCount = 0;

while (firstOperandCount < n) {
if (k == arr.length) {
k = 0;
}
sum+= arr[k++];
firstOperandCount++;
}
int j = k >= arr.length ? 0 : k;
while (j != i) {
if (sum+arr[j++] == expectedSum) {
possibleCombinations.append("{");
firstOperandCount = 0;
int l = i;
while (firstOperandCount < n) {
if (l == arr.length) {
l = 0;
}
possibleCombinations.append(" " + arr[l++]);
firstOperandCount ++;
}
possibleCombinations.append(" " + arr[j-1] + " }");
}
if (j == arr.length) {
j = 0;
}
}
}
return getAllPosibleCombinations(arr, expectedSum, ++n, possibleCombinations);
}

public static void main(String[] args) {
System.out.println(getAllPosibleCombinations(new int[] {0,1,2,3,4},6, 1, new StringBuilder()));
}

}
}}

- Rakesh Muraly August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public static String getAllPosibleCombinations(int[] arr, int expectedSum, int n, StringBuilder possibleCombinations) {
if (n == arr.length) {
return possibleCombinations.toString();
}
for (int i = 0; i < arr.length; i = i + 1) {
int sum = 0;
int k = i;
int firstOperandCount = 0;

while (firstOperandCount < n) {
if (k == arr.length) {
k = 0;
}
sum+= arr[k++];
firstOperandCount++;
}
int j = k >= arr.length ? 0 : k;
while (j != i) {
if (sum+arr[j++] == expectedSum) {
possibleCombinations.append("{");
firstOperandCount = 0;
int l = i;
while (firstOperandCount < n) {
if (l == arr.length) {
l = 0;
}
possibleCombinations.append(" " + arr[l++]);
firstOperandCount ++;
}
possibleCombinations.append(" " + arr[j-1] + " }");
}
if (j == arr.length) {
j = 0;
}
}
}
return getAllPosibleCombinations(arr, expectedSum, ++n, possibleCombinations);
}

public static void main(String[] args) {
System.out.println(getAllPosibleCombinations(new int[] {0,1,2,3,4},6, 1, new StringBuilder()));
}

}
}}

- recursive solution August 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in python

from itertools import combinations

def compute_sum_t_with_k(seq, k, t):
	return filter(lambda x: sum(x) == t, combinations(seq, k))

Some possible optimizations that could be done are:
- Sorting the array and stop the iteration when we go over the sum.
- Keeping a counter for the sum so instead of adding the k elements we subtract one element and a new one

@tnutty2k8 cool solution but the code is counting possible subsets more than one isn't? For example, [1,2,3,4,5,7] with k 3 and t 6 would count the subset {1,2,3} three times. One for the fist call on the for loop with [2,3,4,5,7], 2, 5, another one for the second iteration [1,3,4,5,7], 2, 4 and the last one for the third iteration [1,2,4,5,7], 2, 3. Javascript is not one of my strong points and perhaps you were planning to check that elsewhere on the code sorry if that is the case this is also for me to learn :).

Edit: I read the question again and it says any so my previous comment is about counting more than once is not valid.

Cheers.

- Fernando August 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@fernando,

Youre right, I didn't implement the full details in that code, it was more meant to be a demonstration of the logic, but yea, it would still need to handle duplicates. There are few way we can enforce unique solution. One is to actually splice on the actual input array, example

array.splice(i, 1);

That way on each iteration we remove the current element which will not be present for next iteration. This also prunes some premutations.

- tnutty2k8 August 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

def printCombination(list, index, op, K, sum, sumTillNow):
    if sumTillNow == sum and len(op) == K:
       print(op);
       return;
    if index >= len(list) or len(op) > K or sumTillNow > sum :
       return;   
    op.append(list[index]);
    printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
    op.pop();
    printCombination(list, index + 1, op, K, sum, sumTillNow);

printCombination([1, 2, 3, 4, 5], 0, [], 2, 6, 0);

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

The recursive formula is good for small and constant k. Most recursion can easily be fixed for large k (n-k = constant and small). Since the binomial coefficient grows exponential if k is for example n/2 all recursive solutions are of exponential time.

To solve this, there is a naive pseudo-polynomial time algo with an upper bound O(target * n * k * k). It's much better than the recursive solutions which are exponential and it only works if the input is positive and no duplicates occur which was the problem statement.

It finds one solution if at least one exists.It works as follows:
It tracks all seen sums but at most one per number of elements and sum (because 4+2 = 6 and 5+1 = 6 both have two elements, there is no need to consider them independently in the future).

unordered_set<int> anySumOfK_poly(const vector<int>& arr, int target, int k)
{
	vector<vector<unordered_set<int>>> dp(target + 1, vector<unordered_set<int>>(k));

	for (int a : arr) {
		for (int i = 0; i + a <= target; i++) {
			for (int l = 0; l < k - 1; l++) {
				if (!dp[i][l].empty() && dp[i + a][l + 1].empty() && dp[i][l].find(a) == dp[i][l].end()) { // only one solution 					
					dp[i + a][l + 1] = dp[i][l]; // copy (at most k elements)
					dp[i + a][l + 1].insert(a); // add a
					if (l + 2 == k && i + a == target) return dp[i + a][l + 1]; // found a solution
				}
			}
		}
		dp[a][0] = unordered_set<int>{ a };
	}
	return unordered_set<int>();
}

- Chris August 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def printCombination(list, index, op, K, sum, sumTillNow):
    if sumTillNow == sum and len(op) == K:
       print(op);
       return;
    if index >= len(list) or len(op) > K or sumTillNow > sum :
       return;   
    op.append(list[index]);
    printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
    op.pop();
    printCombination(list, index + 1, op, K, sum, sumTillNow);

printCombination([1, 2, 3, 4, 5], 0, [], 4, 14, 0);

- koustav.adorable August 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

sliding window with window size of K.

- Anonymous August 18, 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