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

Interview Answer

5 Answers

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

liminghu on Jun 12, 2012
1

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

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

Add Answers or Comments

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