## Interview Question

## Interview Answer

5 Answers

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.

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)

bool sum_to_n_unsorted(int a[],int len,int sumto)

{

map<int,int> 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;

}

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));

}

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

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<high)

{

if (sum = num_arr[low]+num_arr[high]) return true;

if ( sum -num_arr[low]<num_arr[high] high--;

if (sum-num_arr[high] > num_arr[low]) low++;

} wile ( low <=high);

return false;

}

liminghuonJun 12, 2012