Monday, April 22, 2013

Microsoft SDET phone interview: Two Sum for Sorted Array in C++

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are zero-based.
Suppose the array is already sorted.
vector<int> twoSum(vector<int> &numbers, int target) {
        int start =0;
        int end = numbers.size()-1;
        vector<int> result(2,0);
        while(start<end)
        {
            if(numbers[start]+numbers[end]>target)
            {
                end--;
            }
            else if(numbers[start]+numbers[end]<target)
                start++;
            else
                break;
        }
        if(start!=end)
        {
            result[0] = start;
            result[1] = end;
        }
        return result;
    }

No comments:

Post a Comment