## Amazon Interview Question

SDE1s**Country:**India

**Interview Type:**In-Person

Very nice.

I think we need to add some constraint:

Assuming A1, A2 and A3 natural numbers.

```
A1 != A2
A1 != A3
A2 != A2
A1 + 2 != A2 + 3
A1 + 2 != A3 + 4
A2 + 3 != A3 + 4
A1 + 2 <= 6 (i.e. A1 < 5)
A2 + 3 <= 6 (i.e. A2 < 4)
A3 + 4 <= 6 (i.e. A3 < 3)
A1 + A2 + A3 = 6
```

In some way this problem reminds me of the Knapsack problem...

I think one of the following can be used:

en.wikipedia.org/wiki/Simplex_algorithm (constraints relaxation is need for this one) or, probably better: en.wikipedia.org/wiki/Branch_and_bound

Being both optimisation methodologies, they will try to maximise (optimise) the problem.

This means a solution is found if (and only if) this maximum equals the sum of the array content (as stated by Naren above).

Some of the needed constraints are stated in my previous comment.

Good thinking.

But in fact, you turn the problem above into this problem:

"Given an a equation of the form of x1+x2+...+xn=sum, while x1!=x2!=..!=xn, find a soultion from the group {1,2...2n} (i.e. 1<=x1,x2...xn<=2n))

How you can solve this problem by **not using** backtracking?

The answer is that you can't. This is a NP-complete problem and if you solve it in a polynomail time that means that you prove that P=NP and you can get your turing prize this year! :)

I believe that the problem above cannot be solve without backtracking since it can be reducted into an NP complete one...

Hi Matoy,

if the above methods work (and I think they need more attention), it is true that we have just turned the problem in an equivalent one. We did that on purpose, actually, because with the initial problem it is straightforward to use a backtracking algorithm but (at least for me) it is not easy to find a different algorithm.

Turning a problem in a equivalent one doesn't change its _complexity_, of course.

But, _complexity_ and _type_ of algorithm used are two different things. Many _algorithm_ could exist for a given problem, each with the same _complexity_.

Specifically, _if_ the simplex method can be used, we will be able to solve the problem with one of its implementation (which are not backtracking).

_If_ the branch and bound algorithm can be used, we can use alphaâ€“beta pruning which again is different from backtracking.

So no, no Turing prize this year, unfortunately! :P

C++ 11 solution:

A recursive solution.

```
void fillRec(int n, vector<int>& A, vector<vector<int>> &output) {
if( n == 0 ) {
output.push_back(A);
return;
}
for(decltype(A.size()) firstLoc = 0; firstLoc <= A.size() - n - 2; firstLoc++) {
auto secondLoc = firstLoc + n + 1;
if(A[firstLoc] == 0 && A[secondLoc] == 0) {
A[firstLoc] = n;
A[secondLoc] = n;
fillRec(n-1, A, output);
A[firstLoc] = 0;
A[secondLoc] = 0;
}
}
}
vector<vector<int>> fill(int n) {
vector<int> A(2*n, 0);
vector<vector<int>> output;
fillRec(n,A,output);
return output;
}
```

Solved using back tracking. solution not possible for all n

```
import sys
def fillArray(arr, nums):
if len(nums) == 0:
print arr
return True
for n in xrange(len(nums)):
#choose number to be filled next
p = nums[n]
nums[n] = nums[0]
tobeFilled = -1
for i in xrange(len(arr)):
if arr[i] == 0:
tobeFilled = i
break
if tobeFilled >= 0 and tobeFilled + p + 1 < len(arr) and arr[tobeFilled + p + 1] == 0:
#forward
arr[tobeFilled] = p
arr[tobeFilled + p + 1] = p
ret = fillArray(arr, nums[1:])
if ret:
return True
#backtrack
arr[tobeFilled] = 0
arr[tobeFilled + p + 1] = 0
#reset numbers
nums[n] = p
return False
if __name__ == "__main__":
if len(sys.argv) != 2 or not sys.argv[1].isdigit():
print "give exactly one argument as int"
exit(1)
n = int(float(sys.argv[1]))
arr = [0] * 2*n
nums = [x for x in xrange(n, 0, -1)]
if fillArray(arr, nums):
print "success"
else:
print "failed"
#print arr
```

We already know that a backtracking algorithm exists.

The point here is to demonstrate whether a different algorithm exists or not.

We could either write an algorithm that solve the problem (for an arbitrary N) or try to reduce this to a well-known problem for which doesn't exist (or exist) a solution that doesn't use BT.

This could help: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem

Hi. I'm new here and this is the first task I saw on this site. It bugs me now for a couple of days, so I decided to share my findings, hoping that it might give some ideas to someone else working on it.

I was trying to trace some mathematical dependencies of indexes and this is what I found:

1. Task can be resolved only for 3*i+1 and 3*i+2 for i > 1. For example there is no solution (or at least I couldn't find it) for 5,6,9,10 etc. Solutions for 3,4,7,8,11,12 etc are easy calculated by the backtrack algorithm

2. For each valid n there are 2 solutions: one having n on position 0 and second is mirrored. I.e. for 4: it's 4 1 3 1 2 4 3 2 and 2 3 4 2 1 3 1 4

3. In all the cases I observed the first index of n is 0 (obvious), n - 1 is at 2, n-2 is at 1.

Here are some solutions, to observe:

3: 3 1 2 1 3 2

4: 4 1 3 1 2 4 3 2

7: 7 3 6 2 5 3 2 4 7 6 5 1 4 1

8: 8 3 7 2 6 3 2 4 5 8 7 6 4 1 5 1

11: 11 6 10 2 9 3 2 8 6 3 7 5 11 10 9 4 8 5 7 1 4 1

12: 12 10 11 6 4 5 9 7 8 4 6 5 10 12 11 7 9 8 3 1 2 1 3 2

15: 15 13 14 8 5 12 7 11 4 10 5 9 8 4 7 13 15 14 12 11 10 9 6 3 1 2 1 3 2 6

16: 16 14 15 9 7 13 3 12 6 11 3 10 7 9 8 6 14 16 15 13 12 11 10 8 5 2 4 1 2 1 5 4

hi denis, thanks for sharing your thought.

I have a different opinion for your 2 & 3 rd points.

For the number 7, i have one more possible values & that's not fit for the 3rd point.

Is there any way to identify the given number is valid.

5 1 7 1 6 2 5 4 2 3 7 6 4 3

Thanks for your input. I did not check if there are other possible solutions for 7, mainly because my backtrack algorithm starts by putting n at 0 and usually it either find the solution having n at 0 index, or does not find it at all. For n=3 and n=4 I could not find any more solutions. So,

2. For each valid n there are at least 2 solutions. One of which having n on position 0. All solutions are mirrored I.e. for 4: it's 4 1 3 1 2 4 3 2 and 2 3 4 2 1 3 1 4

3. For the solution, where n goes at 0, n-1 is at 2, for all observed n > 3 < 16.

Were there any clarification on what happens if there are any collisions, and out of range?

let's say we have: (4, 2, 5, 1, 7) -> (4, 2, 5, 1, 4|2, 1, 7, 5, E, E), ..., 7

It is clear that 4 and 2 will compete for the same position.

7 will be moved away, also 7 is the last number in the range so when trying to put into a

position within 2N range, will fall out or range.

Am I to lost on this?

Here is a Java solution to this problem.

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FillArrayBackTracking {
public static void main(String[] args) {
List list= Arrays.asList(1,2,3,4,5,6,7);
ArrayList<Integer> listArr=new ArrayList<Integer>(list);
int[] solution=new FillArrayBackTracking().solve(listArr);
System.out.println(Arrays.toString(solution));
}
public int[] solve(ArrayList<Integer> list){
if (list==null || list.size()==0)
return null;
return solveRec(list, new int[list.size()*2],0);
}
private int[] solveRec(ArrayList<Integer> list, int[] arr, int startPos) {
if (startPos>=arr.length || list.size()==0)
return arr;
for (int i=0;i<list.size();i++){
int v=list.get(i);
if (arr.length>v+startPos+1
&& arr[v+startPos+1]==0){ // if it's within the range!
arr[startPos]=v;
arr[startPos+v+1]=v;
ArrayList<Integer> nlist=(ArrayList<Integer>) list.clone();
nlist.remove(i);
int nStartPos=startPos;
do{
nStartPos++;
}while(nStartPos<arr.length && arr[nStartPos]>0);
int[] nArr=Arrays.copyOf(arr,arr.length);
int[] sol=solveRec(nlist, nArr, nStartPos);
if (sol!=null){
//It works ... let's return the result and be happy....
return sol;
}else{
//reset the array and try with another value!
arr[startPos]=0;
arr[startPos+v+1]=0;
}
}
}
return null;
}
}
```

Ok I got the partial solution by not using backtracking.

- naren November 16, 2014Let A1,A2,A3 be the positions of 3 numbers(i.e. A1 for 1,A2 for 2 and A3 for 3) in the 6 slots.

Sum of 6 slots indexes(starting with 1) = 6*7/2=21 (geometric series sum problem)

Based on the position of slots of the numbers, the sum should be

A1+(A1+2)+A2+(A2+3)+A3+A3+4 = 21 There is A1+2 because the second '1' will be 2 indexes after the first '1'. similarly for 2 and 3

2(A1+A2+A3) = 21 -9 i.e. A1+A2+A3 = 6

Had the sum of the numbers been contains decimals, there is no possible solution. i.e. try for 5.

If we choose the highest number in the first slot, then

equation will be A1+A2 = 5. 5 is possible with 2 numbers (remaining) with the following either (4,1) (1 is already taken) and so the other (2,3) is the only place where we can put either 2 or 1. Trying these two cases, will yield A2 = 3 and A1=2

I think this can be further improved. Feel free to jump in with your improvements...