Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Since we know we are looking for pairs where x+y = A[x] + A[y], by simple algebra, you can also look for x-A[x] = A[y]-y

public static ArrayList<ArrayList<Integer>> findSums(int[] A) {
		// Look for pairs where  x - A[x] == A[y] - y
		ArrayList<ArrayList<Integer>> soln = new ArrayList<ArrayList<Integer>>();
		HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();
		
		for (int x = 0; x < A.length; x++) {
			h.put(x-A[x],x);
		}
		
		for (int y = 0; y < A.length; y++) {
			if (h.containsKey(A[y]-y)) {
				int x = h.get(A[y]-y);
				if (y != x) {
					ArrayList<Integer> pair= new ArrayList<Integer>();
					pair.add(x);
					pair.add(y);
					soln.add(pair);
				}
			}
		}
		
		return soln;
	}

- andrew January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 6 votes

Looks like an excellent solution driven by mathematics !!!

- Anil Singh January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need additional arraylist while you can do the same thing, just using the hashmap?

- <--> January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

shouldn't the answer be a boolean?
btw, what is the example of the input (other then {0,1,2,..}) which meets requirements?

- Anonymous January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
if given array is {10,12,0,13,14,7} then this might fail. The hash map will have {{{(-10,0),(-11,1),(-2,2),(-10,3),(-10,4),(-2,5)). - Vijay January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should the value of the hashmap be an ArrayList<Integer> as many entries might have the same difference?

HashMap<Integer,ArrayList<Integer>> h = new HashMap<Integer,ArrayList<Integer>>();

- hanhan January 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

walk the input array (say A) and create another array of structures (B). such that
b[i].index = i
b[i].diff = a[i] - i;

Now our problem is reduced to finding two elements in B such that the sum of diff is zero! To do that sort the new array on the key = abs(b[i].diff)

now walk the array b, and see if any adjusant elements sum is zero. If yes, then we got our target, if not we didnt!

This will be O(n + nlogn + n) == O(n log(n)) solution.

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

for A = {12, -3, 12, 12, 8}
the B = { {0,12}, {1,-4}, {2, 10}, {3, 9}, {4,4}}
when you sort B by abs(diff) you get
B = { {1,-4}, {4,4}, {3, 9}, {2, 10}, {0,12}}

Now since b[0].diff + b[1].diff == 0

you return the answer a i = 1, j = 4

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To explain more on why method works:

we are looking for i and j so that
i + j = a[i] + a[j]
i.e
a[i] - i = - 1 * (a[j] - j)

we store the diff of a[i] - i in B[i].diff
and by looking at two elements in b where B[i].diff - B[j].diff == 0 we find our answer.

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// FindIJ.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

int partition(int a[], int l, int r) {
    int pivot, i, j, t;
    pivot = a[l];
    i = l; j = r + 1;

    while (1)
    {
        do ++i; while (a[i] <= pivot && i <= r);
        do --j; while (a[j] > pivot);
        if (i >= j) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
    }
    t = a[l]; a[l] = a[j]; a[j] = t;
    return j;
}

void quickSort(int a[], int l, int r)
{
    int j;

    if (l < r)
    {
        // divide and conquer
        j = partition(a, l, r);
        quickSort(a, l, j - 1);
        quickSort(a, j + 1, r);
    }
}


// returns true if two elements exist in a, such that a[i] + a[j] = i + j
bool DoesExist(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        a[i] = i - a[i];
    }

    // sort the array
    quickSort(a, 0, n - 1);

    for (int i = 0; i < n-1; i++)
    {
        if (a[i] + a[i+1] == 0) return true;
    }
    return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[] = { 12, -3, 12, 12, 8 };
    printf("DoesExist(\"{ 12, -3, 12, 12, 8 }\"):");  DoesExist(a, sizeof(a) / sizeof(a[0])) ? printf("yes\n") : printf("no\n");
    

    int b[] = { 12, -2, 12, 12, 8 };
    printf("DoesExist(\"{ 12, -2, 12, 12, 8 }\"):"), DoesExist(b, sizeof(b) / sizeof(b[0])) ? printf("yes\n") : printf("no\n");

}

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

O(n) solution,

Basically keep a track of (Value - Index) of all the element you walked thru, if you happen to see one that the result of (index - value) is logged previously you got the pair .

private static bool ContainElementsWithValueSumEqualsToIndexSum(int[] array)
        {
            var hash = new HashSet<int>();
            int idx; 
            for(idx = 0; idx < array.Length; idx++)
            {
                if(hash.Contains(- (array[idx] - idx)))
                return true;
                else
                hash.Add(array[idx] - idx);
            }

            return false;

        }

- i059069 January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would be O(n):O(n) in time:space.
I did a bit of research on this problem actually, and found out that you can
either be satisfied with the above, or go for O(nlogn):O(1) in time:space. In either
case, it is a trade-off based on your computing system :)

- Nishant Kelkar January 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Assume int i and j are index positions.
2 Possible Cases:
1) arr[i] = i, arr[j] = j
thus, arr[i] + arr[j] = i + j
2) arr[i] = j, arr[j] = i;
thus, j + i = i + j
*/

public static boolean isSumEqualToIndices(int[] arr)
{
    if (arr == null || arr.length < 2)
        return false;
    
    HashMap<Integer, Integer> ht = new HashMap<>();
    
    for (int i = 0; i < arr.length; i++)
    {
        if (arr[i] == i)
        {
            if (ht.containsKey(null) == false)
                ht.put(null, i);
            else
                return true;
        }
        
        if (arr[i] != i)
        {
            if (ht.containsKey(arr[i])
            {
                if (ht.get(arr[i]) == i)
                    return true;
            }
        }
        
        ht.put(i, arr[i]);
    }
    
    return false;
}

- Omar January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n).
1) Create a temp array such that temp[i] = i-arr[i]
2) Find any two indexes i, j in temp arrray such that their sum is 0. This can be done in O(n) using hashing. ( Same approach as to find a target sum using any two elements of array )

- Delta January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<n;i++)
if( a[i] == a[ a[i] ] ) return true;
return false

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

Let's say i'th and j'th element in the array are p and q, respectively . What we want is

i + j = p + q    
or 
i - p = - (j - q)

O(n) algorithm:
1. walk over the array and do

a[i] = a[i] - i

2. Again walk over the array

h = hashMap
      for every A[i]:
            if -A[i] in h :
                return true;
            else
               insert A[i] -> h

- n.j.joshi January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is ambigous and can be understood in two different ways:

1. return true if at least a pair of numbers satisfies the requirement.

2. return true if all pairs of numbers satisfy the requirement.

Both are O(n)

- jiangok2006 January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is ambigous and can be understood in two different ways:

1. return true if at least a pair of numbers satisfies the requirement.

2. return true if all pairs of numbers satisfy the requirement.

Both are O(n)

- jiangok2006 January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sum {


    //a[i]+a[j]=i+j
    //a[i]-i =j-a[j]

    public static void main(String[] args) {
        int[] array = {6, 1, 3, 2, 10, 14, 50};
        Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

        for (int i = 0; i < array.length; i++) {


            hashmap.put(array[i] - i, i);
        }

        for (int i = 0; i < array.length; i++) {

            if (hashmap.containsKey(i-array[i]) && hashmap.get(i-array[i])!=i)
            {

               System.out.print("the condition is true   " +"index1: "+ i +", value1: "+array[i]+", index2: "+hashmap.get(i-array[i])+", value2: "+array[hashmap.get(i-array[i])]);
                break;

            }

        }
    }
}

- geekgirl January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check if it is {0,1,2,3..} (Ai==i), if yes, return true, otherwise false.

- Anonymous January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ public boolean hasSuchPair(int[] arr) { HashSet<Integer> set = new HashSet<>(); for (int i = 0, temp = 0; i < arr.length; ++i) { temp = arr[i] - i; if (set.contains(temp)) { return true; } } return false; } } - Anonymous January 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean hasSuchPair(int[] arr) { 
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0, temp = 0; i < arr.length; ++i) {
        temp = arr[i] - i;
        if (set.contains(temp)) {
            return true;
        }
    }
    return false; 
}

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

actually I found the array is just 0, 1, 2, 3, 4.....
proof:

consider the first three elements, namely x, y, z so x has index 0, y->1, z->2
we have the following equations:
x+y = 0+1=1
y+z = 1+2 = 3
x+z = 0+2 =2
so we get x = 0, y = 1, z =3 it is a fixed solution
now we prove that the array is 0, 1, 2, 3..... as follows:

suppose we have any two distinct elements a1, a2(suppose a2 is not the last element) in that array, and a3 is the element right next to a2, so the index[a3]=index[a2]+1
we have a1+a3 = index[a1]+index[a3] = index[a1]+index[a2]+1=a1+a2+1
so we have a3 = a2+1
which means we have an unique array 0, 1, 2, 3, 4,......
END

- tango January 17, 2014 | 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