## Amazon Interview Question for Software Engineer / Developers

• 0

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

This could be solved with Hash table.

1. Parse through the entire Array. If the value is less than the sum, lets say , a then Has this value in to the hash table.
2. Traverse the entire array again, for element b[i], Lookup hash[a-b[i]] if it does exist then b[i] and the a-b[i] exist in the array and make the pair.

Can some one give it with O(n) run time and constant space instead of hash table?

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

"If the value is less than the sum"... what if we're allowing negative numbers (which, since we haven't said otherwise, we probably are)?

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

Sorth array using quick sort. o(nlogn) complexity.
Now for each element a[i], find N-a[i] using binary search.O(log n)

I think you can get in O(nlog n) + o(logn) complexity.

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

u have written "Now for each element a[i], find N-a[i] using binary search.O(log n)"

if there are n elements , and u r doing it for each element,how can it be O(log n), it shud be O(nlogn)

so the correct complexity in worst case is O(nlogn) + O(nlogn) and
not O(nlogn) + O(logn) as has been mentioned.

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

This one is straight from Cormen's book. The problem looks more easy if we think of finding the N-a[i] value.

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

sp, u don't need an internal ref in order to get an interview.
my friend got 2 offers at the same time without an internal reference.

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

hi someone, thanks for taking the time. was just wondering if applying thru the site helps. any inputs on that. thanks

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

applyin thru site helps...i applied and i was contacted for an interview within few weeks...so go ahead

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

By using a hash table, you can do this in linear time. Is there a solution that run in linear time without using a lot of memory?

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

Can you elaborate your hash table method? how to use a hash table in this case?

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

You can split this into 2 cases:

1. N is Even
n1,n2 are odd
n1,n2 are even.

2. N is Odd
n1 even, n2 odd
n2 odd, n2 even.

This will remove certain unnecessary comparisons.

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

Using hash table, I think it is possible to do in O(n).

Array : a[]
Sum required : value

1. Take each element, a[i], from the array. Apply hash function, h(a[i]), to it.
1.1. Now apply same hash function to h(value - a[i]). If there exists a value in that place then these two numbers are victim. Here, we need to check that index this hash functions yield is not out of array bounds.

1.2. make an entry in hash table for a[i].

Continue above steps.

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

Using a data structure should be your last option as duplicate storage is sometimes unnecessary.

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

1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution

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

1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution

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

Doesn't Radix Sort assume fixed length of the input numbers, i.e. a constant no. of digits. There is no mention of that fact in the question.

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

Doesn't Radix Sort assume fixed length of the input numbers, i.e. a constant no. of digits. There is no mention of that fact in the question.

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

Think: Dynamic Programming!

This is a good case for the Subset Sum algorithm. Where the value at c[k, u] (k is the index of the value we are using and, u, is the actual weight - the sum) is the actual capacity. This can be done with the max of {(k-1, u-value[k]) + value[k], (k-1, u)}.

If you want to limit it to only 2 values from the array then all you have to do is find the minimum of the recurrence I gave above.. and instead of adding value[k] you add a 1. If c[k, u] gives you 2, then there are 2 values in the aray that add up to u.

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

Given C, find A and B such that A + B = C.
Answer: choose A to be any number and let B = C - A.

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

this is o(n*n) soln..and this is the last one we wanna do :)

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

If we can assume that the array is sorted then,
you can have 2 variabled one for first index, other for last index(end).
if sum of values at those index is less than the value needed, increment end index
if the sum is greater than, increment front index
if they are equal, u have found the one needed.
If front equals or crosses over back then its not present in the array.

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

Did you mean

"f sum of values at those index is less than the value needed, increment end index "

thats because the end index cannot be incremented

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

"decrement end index"

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

func(int total)
{
int a=0;
int b=0;

if(total != 0)
{
a = total/2;
b = total - a;
}
// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
}

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

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
func(int total)
{
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}
}

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

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total
int total = rand(); // or whatever is passed
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}

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

// a and b are two numbers that add up to total.
// works for any zero, negative or positive values of total

int total = rand(); // or whatever is passed
int a=0;
int b=0;

if(total > 0)
{
a = rand() % total;
b = total - a;
}
else if(total < 0)
{
a = -1 * (rand() % (total * -1));
b = total - a;
}

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

Kiran, Your algo assumes that the original input is sorted. This is a point which might be true. Khoa, the hash method is definitely good but yeah it requires extra memory but the only one i can think of in O(n).

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

how write the algorithem that prints the sum of the first n positeve integer??

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

The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}

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

The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=&arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}

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

For unsorted array this code should work:

int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
for (int i=0;i<len-1;i++)
for (int j=i+1;j<len;j++)
{
if (arr[i]+arr[j]==sum)
{
*num1=arr[i];*num2=arr[j];return 0;//success
}
}

return -1; //Such numbers are not present in the array

}

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

good solution thax

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

n*(n+1)/2

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

Store the array in binary tree, instead of hash table. Here we will require less memory but time will be O(nlogn) and then searching for number will be O(logn) so overall all nlogn + logn

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

Can someone build the hash table for this problem??

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

Use inplace sort that will take O(nlogn) time. And have two pointers at:

startindex = 0 and lastindex = last

find the sum if this sum > resultsum
lastindex = lastindex - 1
else if sum < resultsum
startindex = startindex + 1
else // the numbers found.
print element at startindex and lastindex.

do this for until we find the elements.

This will be done in O(n) so, O(nlogn) is the max time with minimal memory.

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

I doubt is it correct? Can you write the sudo code?

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

Can someone explain the hash function please?
Pratik: How will you make sure that arr[i] and (sum - arr[i) will hash to the same location??

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

I dont think thats a good solution. It is taking O(n**2) time. sorting solutions looks fine to me. O(n/2) + O(n log n) = O(n log n)

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

#define sum 100
#define HASHSIZE 256
int hash[256];
int main()
{
int a[] = {30,70,40,60,50,50};
int index = 0;
for(index=0;index<HASHSIZE;index++)
hash[index]=0;
index =0;
while(index<sizeof(a)/4){
hash[a[index]]=1;
index++;
}
index = 0;
while(index <sizeof(a)/4){
if(hash[(sum-a[index])]==1)
printf("%d and %d\n",a[index],sum-a[index]);
index++;
}
return(0);
}

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

@sgfault...
Any specific reason of iteration till sizeof(a)/4.If this is the case ,then it skips few prospective elements.

Do you accept it ?

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

Time Complexity is O(n) using the above approach.

Assumption:
1) Unordered.
2) Unique

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

Just a simple logic, for simplicity not including checks like if element is < sum or not, or if number is -ve etc etc.

1.) Use a bit vector of length = (given_sum)
2.) Scan the array, for each element read, mark the corresponding bit in the bit vector, for example number 5 will set 5th bit to 1 in the bit vector.
3.) Scan the array again, for each element say i check if (sum-i)th bit in the bit vector is SET (or 1. If yes this is the pair. In this way you can find all the pairs.

We can avoid 2nd iteration through the array as well, while scanning the array for the first time, include the checks to find the other paired number as well (whether or not it is set to 1)

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

assume length of array is N;
foreach number in the array
check hash(sum - number),
if exist, return
else hash(number): slot = number % N; insert number to hash table

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

1) iterate through the array -- put each value into a hashtable (the key is input[i], the value is the number of times that value has occurred)
2) iterate through the array again -- int myValue = sum-input[i]
3) if myValue == input[i], then make sure myValue occurs in the array more than just once. if it does, then that's a pair
4) if myValue != input[i], then if myValue occurs in the array 1 or more times, then that is a pair.

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

Using sorting,

Time complexity : o(nlogn)

``````import java.io.*;
import java.util.*;
public class Sum2
{
// Global variables
static int len=0,sum=0;
private static int array[] =new int[len]; // initialization of array length as 0

public static void main(String args[]) throws NumberFormatException, IOException
{
System.out.println("Enter length of array");
len =Integer.parseInt(br.readLine()); // take length of array from user

setArray(Arrays.copyOf(getArray(), getArray().length + len));  // reinitialize array to given length

System.out.println("Enter elements:"); // takes input
for(int i=0;i<len;i++)

System.out.println("Enter sum:");

Sum2 s = new Sum2();
Quicksort q = new Quicksort();

q.sort(0,getArray().length-1); // perform sorting
s.find2sum(); // to find pair in A[] with sum as x
}

/***************************************************************************
*  Method for finding pair in A[] with sum as x
***************************************************************************/
void  find2sum()
{
System.out.println("Output pairs:");
int lo = 0;
int hi = array.length-1;
while (lo < hi)
{
if((array[lo] + array[hi]) == sum)
System.out.println("Pair with given sum "+sum+" is (" + array[lo]+", "+array[hi]+")");
if((array[lo] + array[hi]) < sum)
lo++;
else
hi--;
}
}

/***************************************************************************
* functions to access array
***************************************************************************/
public static int[] getArray() {
return array;
}

public static void setArray(int array[]) {
Sum2.array = array;
}
}
/***************************************************************************
*  QuickSort Algorithm
***************************************************************************/
class Quicksort
{
static Quicksort q1= new Quicksort();

void sort(int low,int high) // Check whether an array is empty
{
if(high<=low)
return ;
int j=partition(low,high);
// recursive call to quickSort() method
sort(low,j-1);
sort(j+1,high);
}

int partition(int low,int high)
{
int i=low;
//System.out.println(s1.getArray()[low]);
int j=high+1;
int pivot=Sum2.getArray()[low];
while(true)
{
while(Sum2.getArray()[++i]<pivot) // find item on low to swap
if (i == high) break; // Boundary case

while(Sum2.getArray()[--j]>pivot)  // find item on high to swap
if (j == low) break;   // Boundary case
// check if pointers cross
if (i >= j) break;
q1.exchange(i,j);

}
exchange(low, j);
return j;
}

void exchange(int i,int j)
{
int temp=Sum2.getArray()[i];
Sum2.getArray()[i]=Sum2.getArray()[j];
Sum2.getArray()[j]=temp;
}

}

/***************************************************************************
OUTPUT:

Enter length of array
8
Enter elements:
55
181
45
69
-81
3145
31
801
Enter sum:
100
Output pairs:
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
Pair with given sum 100 is (45, 55)
***************************************************************************/``````

using hashing,

Time complexity : o(n)

``````import java.io.*;
import java.util.*;

public class Sum2Hash
{
public static void main(String args[]) throws NumberFormatException, IOException
{
Sum2Hash s=new Sum2Hash();
System.out.println("Enter array length");

int array[]=new int[len];
System.out.println("Enter Element");
for(int i=0;i<array.length;i++)

System.out.println("Enter sum:");

s.findpairs(array, sum);
}

void findpairs(int array[],int sum)
{
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

for (int i=0; i<array.length; i++)
{
if(pairs.containsKey(array[i]))
System.out.println("Pair with given sum "+sum+" is ("+array[i] +", "+ pairs.get(array[i])+")");
else
pairs.put(sum-array[i], array[i]);
}
}
}

/***************************************************************************
OUTPUT:

Enter array length
8
Enter Element
55
181
45
69
-81
3145
31
801
Enter sum:
100
Pair with given sum 100 is (45, 55)
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
***************************************************************************/``````

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

1. sort the array
2. kep one pointer at smallest and one at largest,
3. Use binary search to bring the largest pointer to either the x-a[0] or if that is not there just smaller one.
3. now increase left if smaller or decrease right if bigger(perhaps here too we should use binary search to increase or decrease)

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

hmmm theres no o(n) best case. avg case for the hash table is o(n) and thats the best.

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

This is abt the amazon application. Is it necessary to have an internal ref to get an interview i.e., does applying thru the site help? thanks

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.