Amazon Interview Question: Given an array A of n integer... | Glassdoor

Amazon

## Interview Question

Software Engineer Interview Seattle, WA

# Given an array A of n integers, in sorted order, and an

integer x. design an O(n)-time complexity algorithm to determine whether there are 2 integers in A whose sum is exactly x.

3

bool is_sum_num( int num_arr[], int size, int sum)
{

// quicksort(num_arr, size);

for (int end= size-1; end >=0; end--) {

int low = 0; high = size-1;
bool check_again = false;

while(low num_arr[low]) low++;

} wile ( low <=high);

return false;
}

liminghu on Jun 12, 2012
2

The above is not Software Engineering. It is Computer Science. Amazon got it wrong.
Software *Engineering* these days is almost always related to COTS where an engineer researches suitable components and plugs them. Custom components may be made.

A Software Engineer would therefore import some package for the above problem instead of wasting a precious time inventing from scratch.

Mark on Jun 16, 2012
0

from random import randint

# Constant bounds on the random numbers generated.
LOWER = 0
UPPER = 100

# Number of items in the array.
n = 50

# For this solution, the array doesn't have to be sorted.
array = [randint(LOWER, UPPER) for index in range(n)]

def sum_in_array(x, array):
# All of the differences are stored in a hash table; order 1 lookup.
differences = {}

for item in array:
# If the new item is in the differences hash, then we have
# a solution.
if item in differences:
print '%i + %i = %i' % (item, differences[item], x)
return True

# Store the difference and continue.
differences[x - item] = item

return False

# Test code.
for index in range(10):
# Arbitrarily generate a target x.
x = randint(LOWER, 2*UPPER)

# Check x.
sum_in_array(x, array)

Rishi Ramraj on Jun 16, 2012
1

bool sum_to_n_unsorted(int a[],int len,int sumto)
{
map diff;

for(int i=0;i<len;i++)
diff[a[i]]=1;
for(int i=0;i<len;i++)
{
int df=sumto-a[i];
if(diff.find(df) !=diff.end())
return true;
}
return false;
}

bool sum_to_n_sorted(int a[],int len,int sumto)
{
int left=0,right=len-1;
while(left<right)
{
int tmp=a[left]+a[right];
if(tmp==sumto)
return true;
if(tmp<sumto)
left++;
else
right--;
}
return false;
}
void test_sum_to_n()
{
int a[]={3,7,10,20,23};
cout << sum_to_n_unsorted(a,sizeof(a)/sizeof(int),32)<<endl;
cout << sum_to_n_sorted(a,sizeof(a)/sizeof(int),32)<<endl;
}

Sky on Jun 25, 2012
0

public static boolean canSumTo(int[] numbers, int target) {
int i=0;
int j=numbers.length-1;
int sum;
while (i < j) {
sum = numbers[i] + numbers[j];
if (sum < target) {
++i;
} else if (sum == target) {
System.out.println("soln: " + numbers[i] + " " + numbers[j]);
return true;
} else {
--j;
}
}

return false;
}

public static int[] randomIntArray(int length, int maxValue) {
Random random = new Random();
final int[] numbers = new int[length];
for (int i=0; i < length; ++i) {
numbers[i] = random.nextInt(maxValue);
}
Arrays.sort(numbers);
return numbers;
}

public static void test() {
int[] numbers = new int[] { 1, 3, 5, 7 };
System.out.println("can sum to 10:" + canSumTo(numbers, 10));

int[] numbers2 = randomIntArray(10, 50);
System.out.println("numbers: " + Arrays.toString(numbers2));
System.out.println("can sum to 50: " + canSumTo(numbers2, 50));
}

Lance on Aug 15, 2012