## A9 Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Hi this a tested code i used using backtacking.

public class combinations {

int arr[];

int sumuptoAi(int m,int n)
{
int sum=0;
for(int i=m;i<=n;i++)
sum=sum*10+arr[i];

return sum;
}

public boolean Combinations(int start,int sum)
{

if(sum==0&&start==arr.length)
return true;

for(int i=start;i<arr.length;i++)
{

if(Combinations(i+1, sum-sumuptoAi(start, i)))
return true;

}
return false;
}

public static void main(String args[])
{

int arr[]= {2,3,7,2};
combinations obj=new combinations();
obj.arr=arr;

System.out.println(obj.Combinations(0, 239));

}

}

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

what is the time complexity for this

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

Brute force approach is something in these lines (basically start from individual numbers and then increase the size by 1 and repeat for the subarray) with X to be our target. However I'd be much more interested in dynamic programming solution, which appears could exist for this problem:

return foo(A, 0)

bool foo(A, startIndex) {
for size in (1...Length-startIndex) {
n = getNumberOfSize(startIndex, size)
if (n + foo(A, startIndex + size) == X {
return true;
}
}
return false;
}

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

Using a simple example of elements [1,2,3], build a tree of prefixes of the array as below:

123
/
-12 -- 3
\
1 --23
\
2 -- 3

Traverse the tree in a DFS fashion starting from the root, each time adding up the node values and checking against the target value.

The above tree can be created using prefix arrays of the suffix array of the given array.

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

That's a good observation -- prefix tree edges will give you all possible combinations of digits. What are your estimates on running time?

Building a tree (or trie) in performant way (linear or close to it) is difficult though so I wonder what would interviewer expectations would be in such case.

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

Wouldn't the tree, as you've described it, be exponential in size with the size of the input? I might misunderstand your approach, but isn't this tree approach doing the same thing as regular backtracking, with the exception that you first enumerate all the possibilities, store them, and then evaluate them (whereas backtracking evaluates possibilities as they are enumerated)?

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

Build a Prefix tree and while building a tree also ignore the prefixes which are greater than the target. Like in this example {5,2,1,4,3,6,7,8} all those prefix which are greater than 333 will be ignored. 521, 5214, 52143, 521436, 5214367, 52143678 will be ignored . Only valid prefixes are 52 and 5. Similarly for for selecting prefix for child elements ignored alll the prefixes which are greater than the target. Then on that tree Perform DFS (Pre order) and check for sum on each setup.
.

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

You can use DP, memoization would look like this (I made the code here, so there can be some mistakes, but I think it's enough to get the idea. It could be improved so that it's not necessary to use "get_val"):

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

int a[10005], target;
map <pii, bool> mp;

int get_val(int b, int e){
int r = 0;
for(int i = b; i <= e; i ++)
r *= 10, r += a[i];
return r;
}

bool memo(int sum, int px){
if(sum > target) return false;
if(px == n) return (sum == target);
if(mp.find(pii(sum, px)) != mp.end()) return mp[pii(sum, px)];
bool ok = false;
for(int i = px; i < n; i ++)
ok |= memo(sum + get_val(px, i), i + 1);
return (mp[(pii(sum, px)] = ok);
}

int main(){

scanf("%d %d", &n, &target);

for(int i = 0; i < n; i ++)
scanf("%d", &a[i]);

if(memo(0, 0)) printf("True\n");
else printf("False\n");

return 0;
}

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

I assume all numbers in the given array are nonnegtive. Following is a solution in C. Please notice that the combinations like 34352 with 56789 can result into an arithmetic overflow.

#include <stdio.h>

const int tenPower[10] = {
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};

//count how many digits the positive number has
int countDigits(int n)
{
int digits = 0;
for(; n != 0; n /= 10) ++digits;
return digits;
}

//check if the integer array can combine into the target number
int combine(int a[], int i, int n, int target)
{
if(i >= n) return target == 0;
return combine(a, i+1, n, target);
}

int sum = 0;
for(; i < n; ++i){
//combine a number in this level
sum = sum * tenPower[countDigits(a[i])] + a[i];
//if already larger than target, then no need to search deeper
if(sum > target) break;
//search next level
if(combine(a, i+1, n, target - sum)) return 1;
}
return 0;
}

int main()
{
int a[] = {5,2,1,4,3,6,7,8}, target = 333;

if(combine(a, 0, sizeof(a)/sizeof(a[0]), target)) puts("YES");
else puts("NO");

return 0;
}

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

I end up giving the following answer to the interviewer..

1) Create all the combination of the given input i.e for {1,2,3} = {1,2,3,12,23,123}
2) Take the numbers add it if the number is <= target value.. The numbers should be selected in such a way that it's not repeated. E.g. If I select '12' then I cannot select '1','2','23' and '123'

Please let me know if this make sense. Complexity i worst though :( but in 20 minutes this is the approach that I was able to get too..

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

If u want to code simple, then just create a bool set B.
B[i]=true means there will be a '+' between A[i] and A[i+]
false means there will be nothing between the two.
Time complexity is 0(2^n）

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

This is a good solution. Whoever downvoted it, please explain.

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

sdfsdf

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.

### 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.