## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

Time complexity is O[n]

Go through from head and tail to middle. Sum array[head index] and array [tail index] to tell which it meet requirement. If small, move head index with +1. If big, move tail index with -1

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

@Greatnose-But i don't get how the complexity comes out to be O(0) ? I mean in the worst case you end up travelling the whole array right ? this implies that complexity is O(n)

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

sorry, it is one typo. It shall be o[n]

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

Here's a C# implementation of your algo, any feedback will help. Thanks =>O

``````/// <summary>
/// Method that returns combinations of elements that add upto a sum from a sorted int Array.
/// Assume that both -ve and +ve integers are elements and there no duplicates.
/// </summary>
protected internal static void GetSumElements(int[] A, int sum)
{
int iLength = A.Length;
int iLow = A[0];
int iHigh = A[iLength - 1];
do
{
if ((iLow + iHigh) == sum)
{
Console.WriteLine("Valid sum pair: " + iLow + "," + iHigh);
iLow++;
}
else if ((iLow + iHigh) < sum) iLow++;
else if ((iLow + iHigh) > sum) iHigh--;
} while (iLow <= iHigh);
}``````

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

Worst case would be O(n)
But average case would be O(logn) right?

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

@shahkosha.161189 ... the avg case also will be O(n) because we are never reducing the search space by factor of 2 or any other factor so it cant be O(logn)

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

What if the question was asking about 3 numbers that sum to a given number?

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

you can subtract arr[i] from value and search for difference in rest of array using binary search. This will have complexity of O(nlog(n).

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

``````//arr = 0,1,2,3,4,5,7,8,9
//sum = 10
//sub = 10,9,8,7,6,3,2,1
//-------------------------------
arr[]={0,1,2,3,4,5,7,8,9};
val = 10;
int n = arr.length;
if(arr[0] == 0)
{
if(val != 0)
{
int i = bsearch(arr, val, 0, n-1);
if(i!= -1)
{
print i,val ;
return;
}
}
else
{
print arr[0],val;
return;
}
} else
{
array sub = nrw array[n-1];
for(int ctr=0; ctr < (n-1); ctr++)
{
var temp = arr[ctr];
sub[ctr] = val - temp;
int num = bsearch(arr, sub[ctr], 0, n-1);
print num, temp;
return;
}

}``````

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

``````//arr = 0,1,2,3,4,5,7,8,9
//sum = 10
//sub = 10,9,8,7,6,3,2,1
//-------------------------------
arr[]={0,1,2,3,4,5,7,8,9};
val = 10;
int n = arr.length;
if(arr[0] == 0)
{
if(val != 0)
{
int i = bsearch(arr, val, 0, n-1);
if(i!= -1)
{
print arr[i],val ;
return;
}
}
else
{
print arr[0],val;
return;
}
} else
{
array sub = new array[n-1];
for(int ctr=0; ctr < (n-1); ctr++)
{
var temp = arr[ctr];
sub[ctr] = val - temp;
int num = bsearch(arr, sub[ctr], 0, n-1);
print arr[num], temp;
return;
}

}``````

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

iterate in the array with low starting from 0 and high from aray.length -1
in each iteration
-->if we find the sum return both the elements, array[low] and array[high]
->if the sum of array[low] and array[high] is less than sum increment low, low++
-->else decrement high, high --

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

``````private static void findTwoElementsSumUpToN_inGivenSortedArray(final int[] a, final int n) {
int i = 0, j = a.length - 1, sum = 0;
while (i < j) {
sum = a[i] + a[j];
if (sum > n) {
j--;
} else if (sum < n) {
i++;
} else {
System.out.println(a[i] + "," + a[j]);
break;
}
}``````

}

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

``````* Given a sorted array find two num that sum to given number */
void findelementsthatsum(int *array, int length, int sum)
{
int tail = length - 1;
int temp = 0;

{
if (sum < temp) tail--;
if (sum == temp) printf("\nTHe needed pair is :%d, %d", array[head++], array[tail]);
}
}``````

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

``````int N = 2 +4;
static const int ar[] = {1,2, 4, 6, 7, 11, 3343, 22331};
int size = sizeof(ar)/sizeof(ar[0]);
const int* oldlow = ar + size;
for(int i = 0; i < size; ++i)
{
int a = ar[i];
const int* low = std::lower_bound(ar, oldlow, N - a);
if((low == oldlow) || (*low + a) != N)
continue;
else
{
if(a > *low)
break;
std::cout << a << " " << *low << std::endl;
}
oldlow = low;
}``````

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

int[] in = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i ,j,n;
n = 10;

for (i = 0, j = in.length - 1; j > i; i++, j--) {
if (in[i] + in[j] > n)
j--;
else if (in[i] + in[j] < n)
i++;
else
System.out.println("Pair(i+j=n) = ("+(i+","+j)+"="+n+")");
}

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

Simple Binary Search Logic will work.. since it is a sorted array. Complexity is O(log n).

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

How to simply? It is O(n)

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

Input: sum and a sorted array.
Idea: you select the larger of the two numbers and find a smaller matching number.

Approach:
1.) Find the largest number in the array that is smaller than sum. You wouldn't require to go beyond this index to search for the sum. Save the index as 'maxInd'.
2.) Now go backwards from 'maxInd' till index 1 OR 'sum' - '[current value in array]' is less than the '[current value in array]'. There is no point in selecting larger number which cannot add up to sum with a smaller number.
[You can store the index of the previous 'smaller' number which you had found. You need not reconsider this number again. Since, you would have already found a pair that contains the value at that index.]
2.1) Now starting from 'prev index'+1 till 'maxInd'-1,
2.1.1) if current value in array equals 'sum' - '[current value in array]' store the current index as 'prev index' print out the larger and the current number.
2.1.2) break; and continue with loop in step 2.)

eventually you would have found all the pairs that sum up to the given sum.
Space complexity O(1). Time complexity, O(n).

Above approach could be easily modified to be a reccursive version with space complexity as O(m[m is the number of integers to find]) and time complexity as O(nxm).

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.

### 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.

### 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.