## Interview Question

• -1
of 1 vote

Country: United States

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

Assumptions:
- Each number in the array can only be used once
- X is <= length of the array

This can be solved with a costly backtracking algorithm.

``````public static ArrayList<int[]> getSumPairs(int[] arr, int x){
if(arr == null){
throw new NullPointerException();
}
if(x < 2){
throw new IllegalArgumentException();
}
Worker worker = new Worker(arr, x);
worker.execute();
return worker.getResults();
}

static class Worker{
int[] arr;
int[] vals;
int limit;
int index;
int sum;
ArrayList<int[]> results;

Worker(int[] arr, int x){
this.arr = arr;
this.limit = x;
this.vals = new int[x];
this.results = new ArrayList<int[]>();
}

void execute(){
this.executeRecur(0);
}

void executeRecur(int arrPos){
if(this.index > 2 && this.sum % this.limit == 0){
int[] pair = new int[this.index];
for(int i = 0; i < this.index; i++){
pair[i] = this.vals[i];
}
}
if(this.index == this.limit){
return;
}
if(arrPos == this.arr.length){
return;
}
int localPosition = this.index;
this.index++;
for(int i = arrPos; i < this.arr.length; i++){
this.vals[localPosition] = this.arr[i];
executeRecur(i);
}
this.index--;
}

ArrayList<int[]> getResults(){
return this.results;
}
}``````

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

First of all, the example output in the question is wrong. Here's the correct output
[4 6 8] [7 6 8] [9 4 8]
[3 4 8] [4 8] [9 7 8]
[3 7 8] [7 8] [3 9 6]
[9 6] [3 6] [3 9]
No of groups: 12

OK, let's analyze the problem. The silly part of the problem is that we have to find and report ALL
the groups. That yields to non-polynomial time complexity algorithm in worst case.
If we had to find any group with a given criteria or prove that no such group exists or solve optimization problem
(e.g. find the group of a maximum length divisible by X) then we could provide a nice polynomial (or as some people say pseudo-polynomial) time
algorithm based on dynamic programming with the complexity O(X*N).
For example, if we want to maximise the length of the group, we could use the following recursive relationship for DP:
dp[i][s] = MAX( dp[i-1][r], dp[i-1][(x+s-arr[i-1])%x] + 1)
where dp[i][s] holds the maximum length of subset formed from the first i elements of the array with a sum s modulo x.
Note, that in my solution all sums are computed using modulo X. so s is a remainder of a division of a sum to X.
dp[arr.size()] will contain the length of a largest subset with a sum divisible by x.

Ok, let's solve the original problem. We want to print all groups efficiently and try to keep running time (pseudo)polynomial
if there is a few groups to report. The algorithm below is a hybridization of a dynamic programming with a
search with pruning and backtracking. dp[i][s] relationship mentioned above is used to avoid recursing into the costly branches
which don't lead to printable results.
Space complexity O(X*N), time complexity O(X*(N+k)) where k is the # of groups which will be found and printed.
If no groups exist with the given criteria or O(k) == O(N) then algorithm terminates on O(X*N) time.
If O(k) = O(N^c) for some constant c the algorithm terminates in polynomial time O(X*N^c)

Code:

``````class FindGroupsWithSumDivisibleByX
{
int x;
const vector<int>& arr;
int count;

// dp[i][j] holds maximum length of a subsequence of a first i elements of x
// which sum to j modulo X
vector<vector<int>> dp;
public:
FindGroupsWithSumDivisibleByX(const vector<int>& arr, int x): arr(arr), x(x)
{
dp.resize(arr.size() + 1, vector<int>(x, INT_MIN));
}

void PrintAllGroups()
{
count = 0;
vector<int> output(arr.size());
Backtrack(output, 0, arr.size(), 0);
cout << "No of groups: " << count << endl;
}

int Backtrack(vector<int>& output, int pos, int i, int sumModuloX)
{
if (i == 0) {
PrintGroup(output, pos, sumModuloX);
return 0;
}
int& cache = dp[i][sumModuloX];
if (cache != INT_MIN) {
if (pos >= x || cache == 0 || (pos == 0 && cache == 1)) {
// print accumulated group (if matches the criteria)
PrintGroup(output, pos, sumModuloX);
// pruning the current recursive search branch
return cache;
}
}
output[pos] = arr[i - 1];
// case a: adding arr[i-1] to the group
int a = Backtrack(output, pos + 1, i - 1, (x + sumModuloX - (arr[i - 1] % x)) % x) + 1;
// case b: not adding arr[i-1] to the group
int b = Backtrack(output, pos, i - 1, sumModuloX);
cache = max(a, b);
return cache;
}

void PrintGroup(vector<int>& output, int pos, int sumModuloX)
{
if (sumModuloX == 0 && pos > 1 && pos <= x) {
for (int j = pos - 1; j >= 0; j--)
cout << output[j] << " ";
cout << endl;
count++;
}
}
};``````

Some notes:
1) negative numbers: the code supports negative numbers, however according to C++ standard the sign of the % result for negative param is
implementation defined.
As written above, the code will work on mainstream compilers but if you care about portability
you have to replace arr[i]%x to abs(arr[i%x])*sgn(arr[i]).
2) space complexity can be optimized further: technically the program uses only 2 bits of the values stored in dp array,
so the storage can be reduced. This can be even reduced to a single bit-matrix without changing the asymptotic complexity
but at the cost of larger constants
3) I also took an assumption that numbers in array are unique. If this assumption isn't correct we need to also take care to avoid reporting duplicated groups unless this is permitted

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.