## Amazon Interview Question for SDE1s

Team: Software Developer, Infrastructure Planning, Analysis and Optimization
Country: United States
Interview Type: Phone Interview

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

O(n)

We go across the array (which is large and maybe distributed) and capture the index of all numbers below 10 (from 0 to 10). The rest are discarded.

When we find a number below 10, we look for its partner (2 to 8, 3 to 7, 0 to 10) and check whether we have a registered index, if not we append the index we have in a dictionary identified by the original number and continue examining the array.

When two partners are found we print their indexes in screen.

In a distributed system, we could send to a centralized computer or broadcast everytime we find numbers below 10, or after certain amount of time depending on P(X<10).

indexes={0:[], 1: [], 2:[] ... 10:[]}
L=[1,7,8,10,34,3....]
for i in range(len(L)):
if L[i] < 11:
if len(indexes[10-L[i]]) >0:
print indexes[10-L[i]], i
else:
indexes[L[i]].append(i)

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

Sorry I forgot to delete de elemet at dictionary indexes after printing

indexes={0:[], 1: [], 2:[] ... 10:[]}
L=[1,7,8,10,34,3....]
for i in range(len(L)):
if L[i] < 11:
if len(indexes[10-L[i]]) >0:
print indexes[10-L[i]], i
del(indexes[10-L[i]][0])
else:
indexes[L[i]].append(i)

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

``````void FindIntsWithSum(unsigned int[] array, unsigned int sum)
{
if(0 == array.length)
return;

Dictionary<unsigned int, unsigned int> myDict = new Dict();

for(int index = 0; index < array.length; ++index)
{
if(myDict.contains(sum - array[index]))
{
Console.WriteLine("{0} & (1}", array[index], myDict.key(sum - array[index]));
return;
}
else
{
}
}

Console.WriteLine("This array does not contain values that sum upto: {0}", sum);
return;
}``````

// Test cases
// Empty array
Single element array
Large array -- Blow the memory
Small array
Arrays with lot of duplicates
Array without sum of the integer ...
Array with multiple combination...
Performance, Memory: (Large and small array)
Simple tests: Small arrays with sum present : Basic P1
Check for buffer overflow

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

I've checked and slightly corrected your code. Now it works fine.

``````static void FindIntsWithSum( int[] array, int sum)
{
if(0 == array.Length)
return;

Dictionary<int, int> myDict = new Dictionary<int, int>();

for(int index = 0; index < array.Length; ++index)
{
if(myDict.ContainsValue(sum - array[index]))
{
Console.WriteLine("{0} & {1}", array[index], myDict.FirstOrDefault(x => x.Value == sum - array[index]).Value);
return;
}
else
{
}
}

Console.WriteLine("This array does not contain values that sum upto: {0}", sum);
return;
}``````

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

It looks like a good solution. But the information about the ints being unsigned is NOT leveraged. For example, it the number I am examining is greater than 10, then why bother putting it in the dictionary?

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

The above solutions will work better if we put discard all numbers > sum value

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

@Pradeep. Code was not working completely I added a line in that code.
int a[]={12,3,5,4,8,7,2,6,5,89,78,4,5,68,58,4,8,8,5};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int diff;
for(int i=0;i<a.length;i++)
{
if(a[i]<=10)
{
diff=10-a[i];
if(map.containsKey(diff))
{
System.out.println(a[i]+" "+diff+"= 10");
if(!map.containsKey(a[i])){
map.put(a[i],i);
}
}
else
{
map.put(a[i], i);
}
}
}

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

Here are a couple of ways I would do it:

``````class SumOfTwoNumbers {
public static void main(String... args) {
int[] largearr = {5,9,1,100,5000,0};

for (int i : largearr) {
for (int j : largearr) {
if ((i+j) == 10) {
System.out.println(i + " " + j);
}
}
}
}
}``````

and

``````class SumOfTwoNumbers2 {
public static void main(String... args) {
int[] largearr = {5,9,1,100,5000,0};
Set<Integer> allInts = new HashSet<Integer>();
for (int i : largearr) {
}

for (int i : largearr) {
int diff = 10-i;
if (allInts.contains(diff)) {
System.out.println(i + " " + diff);
}
}
}
}``````

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

import java.util.HashMap;
import java.util.Map;

public class QuicklyFindingSumOFTwoNumber {

public static void main(String[] args) {
Map<Integer ,Integer> valueMap = new HashMap<Integer ,Integer>();
int a[] = { 0,10,2,3,4,5,6,7,8,9,0,123,34};
for(int i=0;i<a.length;i++){
if(a[i]<=10){
int temp = 10-a[i];
if(valueMap.containsKey(temp)){
System.out.println("positions :("+valueMap.get(temp) +" " + i +")" + temp +" " + a[i]);
System.exit(0);
}
valueMap.put(a[i], i);
}
}
}

}

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

I think for the shared resource problem. I guess if we are having a hashset for all the integers less than 10, for any new entry we will push it into the hashset also(if it is less than or equal to 10).

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

C++ implementation with O(n) time complexity and O(1) space complexity.

``````# include <iostream>

void findSum (unsigned int *arr, int len) {
int index[] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
for (int i = 0; i < len; ++i) {
if (arr[i] <= 10) {
if (index[10 - arr[i]] == -1) {
index[arr[i]] = i;
}
else {
std::cout << "Indexs are " << index[10 - arr[i]] << " " << i << "\n";
return;
}
}
}
std::cout << "No two numbers with sum 10\n";
}

int main () {
unsigned int arr1[] = {0, 2, 5, 4, 3, 8};
unsigned int arr2[] = {1, 2, 1, 9, 8, 2};
unsigned int arr3[] = {3, 0, 13, 10, 3, 1};
unsigned int arr4[] = {3, 4, 5, 0, 5, 1};

unsigned int arr5[] = {9, 4, 3, 3, 4, 3};
unsigned int arr6[] = {11, 32, 45, 12, 24, 93};
unsigned int arr7[] = {3, 2, 13, 10, 3, 1};

findSum (arr1, 6);
findSum (arr2, 6);
findSum (arr3, 6);
findSum (arr4, 6);
findSum (arr5, 6);
findSum (arr6, 6);
findSum (arr7, 7);
return 0;
}``````

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

you still have to loads the array to memory so memory complexity is O(n)

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

/**
*
*/
package h;

import java.io.IOException;

/**
* @author vaio
*
*/
public class twoNoWhosSumis10 {

/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
int n,i,j,sum,k,l,r,s;
System.out.println("how large you want to make the array of unsigned int");
int arr[]=new int [n];
int dupli[]=new int [n];
for(i=0;i<n;i++)
{
System.out.println("Enter your value into the postion no "+(i+1)+" in the array");
if(j<0){

System.out.println("Did you forget that we are dealing with array of unsigned int!!! Re-enter ");
j=0;
i--;
}else{
arr[i]=j;

}

}
k=-1;l=-1;
r=0;s=1;
int flag1=0;int flag2=0,q;
dupli[0]=-1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
if(i!=j){
sum=arr[i]+arr[j];

if(sum==10 && k!=arr[i] && l!=arr[j] && k!=arr[j] && l!=arr[i]){
k=arr[i]; l=arr[j];
for(q=0;q<s;q++){
if(dupli[q]==k){
flag1=1;
break;}
else
flag1=0;
}
for(q=0;q<s;q++){
if(dupli[q]==l){
flag2=1;
break;}
else
flag2=0;
}
if(flag1==0 && flag2==0){
dupli[r]=k;
dupli[s]=l;
r+=2; s+=2;
System.out.println("The two number whose sum is 10 are "+k+" and "+l);
}
}
else{
continue;
}
}
}

}

}

}

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

If required sum is less than number of bits in long,we can use bit operations to provide the solution.(given numbers are unsigned int's)
c++ code:
#include<iostream>
using namespace std;
int main()
{
long check=0;
int A[100],n;
cout<<"enter number of elements in array\n";
cin>>n;
cout<<"enter elements\n";
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<n;i++)
{
int num=10-A[i];
int check_tmp=1;
if(num>=0)
{
// checking 10-current_num already exists in list or not
check_tmp=check_tmp<<num;
if((check & check_tmp) >0)
{ cout<<"first pair is"<<num<<"\t"<<A[i]<<endl;
return 0;
}
//if 10-current_num doesn't exist then we'll make the bit in current num's position to 1
check_tmp=1;
check_tmp=check_tmp<<A[i];
check=(check | check_tmp);
}

}
return 0;
}

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

small correction on comment in code
// If (10-current_num) doesn't exist in already parsed array elements, then we'll make the bit in (current num+1) position to 1.
Note:we are using (current num+1)position instead of current num position because if current num is 0 then we are making check's right most bit as 1 to handle (0,10) case.

Pros:
time complexity -worst case O(n)
space complexicity: O(1) (we are using only 2 variables)
bit operations are faster

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

public class Check {

public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = { 3, 10, 12, 5, 8, 2, 0, 7 };
boolean flag = false;
if (a.length == 0) {
System.out.println("Empty array");
} else {
int i = 0, j = 0;
while (i < a.length) {
while (j < a.length) {
int x = a[i] + a[j];
if (x == 10) {
System.out.println(a[i] + " " + a[j]);
flag = true;
break;
} else {
j++;
}
}
i++;
j = i;
}
if (flag == false)
System.out.println("No combo");
}

}

}

is above program fine in interview w.r.t time complexity

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

``````class FindTwoWithGivenSum{
public static void main(String... a){
int[] arr = {5,4,6,1,11,8};
int number = 10;

// Sorted !!
for(int i=arr.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(int i: arr){
System.out.print(i);
}

// Find closest smallest element for a given no.
int indexClosest = 0;
for(;indexClosest<arr.length;indexClosest++){
if(number<arr[indexClosest]){
indexClosest--;
break;
}
}
if(indexClosest == arr.length){
indexClosest--;
}

System.out.println("\n closest Index:"+indexClosest);

boolean solutionFound = false;
if(indexClosest>=0){
int startIndex = 0;
int endIndex = indexClosest;
while(startIndex<endIndex && !solutionFound){
if(arr[startIndex]+arr[endIndex] ==number){
System.out.println(arr[startIndex]+","+arr[endIndex]);
solutionFound=true;
}
else if(arr[startIndex]+arr[endIndex] > number){
endIndex--;
}
else{
startIndex++;
}
}
}

if(!solutionFound){
System.out.println("No such combination of numbers found in given array!!");
}

}
}``````

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

1) sort the given array in ascending order till the max value of 10.it means now the array contains only elements from 0 -10
2) then loop thru the array from beginning till middle of the array(outer loop)
fetch the first element
then subtract from 10 get the reminder
3) loop thru the array from end till middle(inner loop)
search for the reminder from the end of the array till middle.
if found break else conitinue step 3
repeat step 2

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

Done in O(n) complexity with O(n) memory:

``````public static int[] getSum(int[] arr, in sumTo){
if(arr == null || sumTo < 1){
return null;
}
HashSet<Integer> cache = new HashSet<Integer>();
for(int i : arr){
int otherSum = sumTo - i;
if(cache.contains(otherSum)){
return new int[]{i, otherSum};
}
}
return null;
}``````

(edit: fixed logical bug)

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.