CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person



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

It can be solved with backtracking algorithm...Try to place values 1 after another in the array after checking that the condition is being satisfied and the array positions are available for this value to be placed. If a value could not be placed anywhere in the array try to backtrack and replace the position of the previous value.

In my simple test it did not work for n=5 and 6 etc...that means such an array could not be constructed for that value of n. Here is my java code

public class SpecialArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		createSpecialArray(7);
	}

	
	public static void createSpecialArray(int n){
		int [] outArr = new int[2*n];
		//place 1
		boolean ret = placeVal(1, outArr, n);
		if(!ret) {
			System.out.println("could not implement the solution.");
		} else{
			System.out.println("Array content is : ");
			for(int val :outArr) {
				System.out.print("  "+val);
			}
		}
	}
	
	public static boolean placeVal(int val, int [] outArr, int highest ){		
		boolean ret = false;
		if(val > highest) {
			return true;
		}
		int i;
		boolean isValid = false;

		for(i= 0; i < outArr.length; i++){
			isValid = i+val+1>=outArr.length?false:(outArr[i]==0 && outArr[i+val+1]==0)?true:false;
			if(isValid) {
				outArr[i] = val;
				outArr[i+val+1] = val;
				ret= placeVal(val+1, outArr,highest);
				if(!ret){
					outArr[i] = 0;
					outArr[i+val+1] = 0;
				}else{
					return true;
				}
			}		
		}
			
		return false;		
	}
}

Output: for N= 7
Array content is :
1 7 1 2 5 6 2 3 4 7 5 3 6 4

- Anonymous April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 votes

There could be more than one array matching the requirement and we only need to find one. So we can make a great optimization to backtracing by placing the large value first, which has less possibilities:
(1)as soon as we can not place the large value, we stop the search process.
(2)by placing large value first we also cut off many search branches for smaller ones.
As an example, when length = 16, following code is much faster than the above one.

public class OrderMaker {
	private static boolean place(int n, int[] arr){
		if(n == 0) return true;
		for(int i = 0; i + n + 1 < arr.length; ++i){
			if(arr[i] == 0 && arr[i + n + 1] == 0){
				arr[i] = arr[i + n + 1] = n;
				if(place(n - 1, arr)) return true;
				arr[i] = arr[i + n + 1] = 0;
			}
		}
		return false;
	}
	public static int[] makeNumberDistanceEqualsToNumber(int length){
		int[] arr = new int[length];
		Arrays.fill(arr, 0);
		if(place(length >> 1, arr)) return arr;
		return null;
	}
	
	public static void main(String args[]){
		int[] arr = makeNumberDistanceEqualsToNumber(16);
		if(arr != null) System.out.println(Arrays.toString(arr));
		else System.out.println("Can not make such array");
	}

- uuuouou May 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For one who would like to use C++.

bool idistant_internal(std::vector<int>& arr, int curr) {
    if (curr == 0) return true;
    for (int pos = 0; pos < (int)arr.size() - curr - 1; ++pos) {
        if (arr[pos] == 0 && arr[pos + curr + 1] == 0) {
            arr[pos] = arr[pos + curr + 1] = curr;
            if (idistant_internal(arr, curr - 1)) return true;
            arr[pos] = arr[pos + curr + 1] = 0;
        }
    }
    return false;
}

std::vector<int> idistant(int n) {
    std::vector<int> res(2*n);
    if (idistant_internal(res, n)) return res;
    return {};
}

- Yola July 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] GetNewOrder(int n)
        {
            int[] res = new int[n * 2];
            bool[] valid = new bool[n * 2];
            SetValid(valid);
            if(GetOrder(res, valid, n))
            {
                return res;
            }
            return null;
        }

        private bool GetOrder(int[] res, bool[] valid, int num)
        {
            if(num <= 0)
            {
                return true;
            }
            int start = 0;
            int[] validPositions = GetFirstValidPosition(start, num, valid);
            while(validPositions != null)
            {
                start = validPositions[0] + 1;
                valid[validPositions[0]] = false;
                valid[validPositions[1]] = false;
                if(GetOrder(res, valid, num-1))
                {
                    res[validPositions[0]] = num;
                    res[validPositions[1]] = num;
                    return true;
                }
                valid[validPositions[0]] = true;
                valid[validPositions[1]] = true;
                validPositions = GetFirstValidPosition(start, num, valid);
            }
            return false;
        }

        private void SetValid(bool[] valid)
        {
            for(int i=0; i < valid.Length; i++)
            {
                valid[i] = true;
            }
        }

        private int[] GetFirstValidPosition(int pos, int num, bool[] valid)
        {
            for(int i=pos; i < valid.Length; i++)
            {
                int shiftedPos = i + num + 1;
                if(shiftedPos >= valid.Length)
                    break;
                if(valid[i] && valid[i + num + 1])
                {
                    return new int[] { i, i + num + 1 };
                }
            }
            return null;
        }

- Sehs April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the algo?

- Anonymous April 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How did you come up with this?! I tried your solution and it only works for certain numbers: 3, 4, 7, 8, 11, 12. 13 and beyond takes too long for me to wait

- foo April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

also works (returns an answer quickly) for 15, 16, 19, 20, 23, 24, 27, 28, 31, 32, 35, 40, 43, 44. This is very weird. What is the meaning behind this sequence of numbers?

- foo April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's a backtracking algorithm and sure it's not the most optimal one. Starting with placing the most restricted number (n) into a place and checking if the placing will work for the rest of numbers (n-1, n-2, etc..).

At any step, if the placement of next numbers failed in all possible positions, change the placement of the current number to the next available placement

- Sehs April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ // brute force approach O(N2) public void approach1(byte[] arr,byte[] brr) { for(int i=0;i<arr.length;i++) for(int j=0;j<brr.length;j++) if(arr[i]==brr[j]) } public void approach2(byte[] arr, byte[]brr) { Arrays.sort(arr); Arrays.sort(brr); for(int i=0,j=0;j<brr.length;j++,i++) { if(arr[i]==brr[j]) System.out.print(brr[j]+ " "); } } public void approach3(byte[] arr, byte[] brr) { Map<Byte,Boolean> map=new HashMap<Byte,Boolean>(); Map<Byte,Boolean> mapB=new HashMap<Byte,Boolean>(); for(byte a: brr) map.put(a,true); for(byte b: arr) if(map.get(b)!=null) mapB.put(b, true); System.out.println(mapB); } - lal April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The logic is to do it in one pass. while i will the position to store the no arr[i] + i +1 will be the position where the no will reappear next. Keep incrementing the seed value and divide by input bound when it exceed to circle back.

/**
 * Created by virajnagar on 5/2/14.
 */

public class WhateverArray {

    public static void main(String[] args){

       int input = 5;
       //int size = 2*input;
       createAndDisplayArray(input);

    }

    private static void createAndDisplayArray(int input) {

        int size = 2*input;
        int arr[] = new int[size];
        
	//This will be the first element to be entered. You can use a bounded random no generator to get this.
	int seed = 2; 	
        
	for(int i =0;i<size; i++){
            if(arr[i] <= 0){
                if(seed > input){
                    seed = seed/input;
                }
                arr[i] = seed;
                int seedPosition = arr[i] + i + 1;
                if(seedPosition < size && arr[seedPosition] <= 0){
                   arr[seedPosition] = seed;
                }
            ++seed;
            }

        }
    for(int i = 0 ; i < size;i++){
        System.out.print(" " + arr[i]);
    }
    }

}

- Viraj Nagar May 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test.arr;

import java.util.Arrays;

public class Test1 {

public static boolean returnF= false;

public static void main(String[] args) {
int n =40 ;
int a[] = new int[2*n];

for(int i=n; i<=1;i-- ){
a[n] =0;
}

fillNum(a,n);

System.out.println(Arrays.toString(a));
}

public static void fillNum(int[]a, int i) {

String iPos [] = calcPos(i, a.length);
for (String pos : iPos) {
if(returnF) return;
clearI(a, i);
String poss[]=pos.split(",");
if(a[Integer.parseInt(poss[0])] ==0 && a[Integer.parseInt(poss[1])] ==0){
a[Integer.parseInt(poss[0])] = i;
a[Integer.parseInt(poss[1])] =i;
if(i==1) returnF = true;
// System.out.println(Arrays.toString(a));
fillNum(a, i-1);
}


}

}

public static void clearI(int a[], int i) {
for(int j=0;j<a.length ; j++){
if(a[j]<=i) {
a[j]=0;
}
}
}

public static boolean findI(int a[], int i) {
for(int j=0;j<a.length ; j++){
if(a[j]==i) {
return true;
}
}
return false;
}

public static String[] calcPos(int num,int len) {
String[] posArr = new String[len-(num+1)];

for(int i =0 ; i<posArr.length;i++){
posArr[i] = i + "," + (i+num+1) ;
}
return posArr;
}

}

- siddhartha May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test.arr;

import java.util.Arrays;

public class Test1 {
	
	public static boolean returnF= false;
	
	public static void main(String[] args) {
		 int n =40 ;
		 int a[] = new int[2*n];
		
		 for(int i=n; i<=1;i-- ){
			 a[n] =0;
		 }
		 
		fillNum(a,n);
		
		System.out.println(Arrays.toString(a));
	}
	
	public static void fillNum(int[]a, int i) {
	
		String iPos [] = calcPos(i, a.length);
			for (String pos : iPos) {
				if(returnF) return;
				clearI(a, i);
					String poss[]=pos.split(",");
					 if(a[Integer.parseInt(poss[0])] ==0 && a[Integer.parseInt(poss[1])] ==0){
						 a[Integer.parseInt(poss[0])] = i; 
						 a[Integer.parseInt(poss[1])] =i;
						 if(i==1) returnF = true;
					//	 System.out.println(Arrays.toString(a));
						 fillNum(a, i-1);
					 }	
				
				 
			}
		
	}
	
	public static void clearI(int a[], int i) {
		for(int j=0;j<a.length ; j++){
			if(a[j]<=i) {
				a[j]=0;
			}
		}
	}
	
	public static boolean findI(int a[], int i) {
		for(int j=0;j<a.length ; j++){
			if(a[j]==i) {
				return true;
			}
		}
		return false;
	}
	
	public static String[] calcPos(int num,int len) {
		String[] posArr = new String[len-(num+1)];
		
		for(int i =0 ; i<posArr.length;i++){
			posArr[i] = i + "," + (i+num+1) ;
		}
		return posArr;
	}

}

- Anonymous May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've noticed there are cases where more than one solution exists. This is a C++ approach that takes care of such cases:

{

using namespace std;

void print(int * arr, int length)
{
	cout << "Solution found" << endl;
	for(int i = 0; i < length; i++)
		cout << arr[i] << " ";
	cout << endl;
}

void makeArrayUtil(int val, int * arr, int length, int max)
{
	if(val > max)
	{
		print(arr, length);
		return;
	}
	
	for(int i = 0 ; i < length; i++)
	{
		if(arr[i] == 0 && arr[i + val + 1] == 0 && (i + val + 1) < length)
		{
			arr[i] = val;
			arr[i + val + 1] = val;
			makeArrayUtil(val + 1, arr, length, max);
			arr[i] = 0;
			arr[i + val + 1] = 0;
		}
	}
}

void makeArray(int input)
{
	int * output = new int[2 * input];
	int length = 2 * input;
	
	makeArrayUtil(1, output, length, input);
}

int main(int argc, const char * argv[])
{
	makeArray(7);
	return 0;
}

}

- NL May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this the interview question in reality? Because one SIMPLE solution can be just enumerate the numbers from 1 to n while keeping the distance between two duplicates to be zero. Eg: for N= 7 , I can give an array that contains 11223344556677. The distance between same values = 0.

- huh June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

public static void main(String arg[]) {
for (int n = 2; n < 1000; n++) {
double[] r = new double[2 * n];
if (populate(n, r)) {
System.out.println(n+" -> "+Arrays.toString(r));
}
}
}

public static boolean populate(int N, double r[]) {
if (N == 0) {
return true;
}

for (int i = 0; i < r.length - N - 1; i++) {
if (r[i] == 0 && r[i + N + 1] == 0) {
r[i] = N;
r[i + N + 1] = N;
if (populate(N - 1, r)) {
return true;
} else {
r[i] = 0;
r[i + N + 1] = 0;
}
}
}

return false;
}

"C:\Program Files\Java\jdk1.8.0_20\bin\java" -Didea.launcher.port=7539 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.1\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_20\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\rt.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_20\jre\lib\ext\zipfs.jar;C:\xfiles\out\production\xfiles;C:\work\simplejms\lib\log4j-1.2.16.jar;C:\Jama-1.0.3.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.1\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain quiz.MagicArray
3 -> [3.0, 1.0, 2.0, 1.0, 3.0, 2.0]
4 -> [4.0, 1.0, 3.0, 1.0, 2.0, 4.0, 3.0, 2.0]
7 -> [7.0, 3.0, 6.0, 2.0, 5.0, 3.0, 2.0, 4.0, 7.0, 6.0, 5.0, 1.0, 4.0, 1.0]
8 -> [8.0, 3.0, 7.0, 2.0, 6.0, 3.0, 2.0, 4.0, 5.0, 8.0, 7.0, 6.0, 4.0, 1.0, 5.0, 1.0]
11 -> [11.0, 6.0, 10.0, 2.0, 9.0, 3.0, 2.0, 8.0, 6.0, 3.0, 7.0, 5.0, 11.0, 10.0, 9.0, 4.0, 8.0, 5.0, 7.0, 1.0, 4.0, 1.0]
12 -> [12.0, 10.0, 11.0, 6.0, 4.0, 5.0, 9.0, 7.0, 8.0, 4.0, 6.0, 5.0, 10.0, 12.0, 11.0, 7.0, 9.0, 8.0, 3.0, 1.0, 2.0, 1.0, 3.0, 2.0]

- Anonymous April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No algo, no explanation = -1.

- Anonymous April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int isvalid(int a[],int ind,int data)
{
    int i=ind-1;
    while(i>=0 && a[i]!=data)
       i--;
    if(i<0 || ind-i-1==data)
       return 1;
    return 0;
}

void getarray(int a[],int ind,int n,int val[])
{
     if(ind==2*n)
     {
        
        int i=0;
        for(i=1;i<=n;i++)
        {
           if(val[i]==0)
              return;
        }
        for(i=0;i<2*n;i++)
           printf("%d\t",a[i]);
        printf("\n");
        return;
     }
     int i=0;
     for(i=1;i<=n;i++)
     {
        if(isvalid(a,ind,i))
        {
           a[ind]=i;
           val[i]++;
           getarray(a,ind+1,n,val);
           val[i]--;
        }
     }
}

- Nitin April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No algo, no explanation = -1.

- Anonymous April 30, 2014 | Flag


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