Microsoft Interview Question: Given a set of numbers -50 to... | Glassdoor

Interview Question

Software Development Engineer In Test (SDET) Interview(Student Candidate) Redmond, WA

Given a set of numbers -50 to 50, find all pairs that add

  up to a certain sum that is passed in. What's the O notation for what you just wrote? Can you make it faster? Can you find an O(n) solution? Implement the O(n) solution
Answer

Interview Answer

17 Answers

5

O(n^2) solution is just two double for loops.

O(n log n) solution will use a binary tree

O(n) solution will use a hash table

Interview Candidate on Mar 16, 2011
1

O(n) solution possibility (no need for a data structure)
void findpairs(int sum)
{
//given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in.

    if (sum == 0)
    {
        cout 0)
    {
        for(int i = 0; i((sum/2)-1) && i>-26; i--)
        {
            if( (i - sum+i) == sum)
            {
                cout << i << " " << sum+i << "\n";
            }
        }
    }
}

Mike on Mar 29, 2011
1

@Mike
"if( (i + sum-i) == sum)"

will always give you "sum".

Anonymous on Apr 1, 2011
2

@Mike:
if (sum == 0) does not imply 0,0.
It implies -50,50; -49,49; -48,48,...

Matthew on Apr 8, 2011
0

Has anyone found the O(n) solution??? I'm having trouble with this one...

EB on May 10, 2011
4

Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n).

Now, foreach key 'k', with value 'v':
  if k == v:
     there is a match and that is your pair.
this will take another O(n) pass

totale O(2n) ~ O(n)

gee on Jul 24, 2011
1

Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like

-50 + 50
-49 + 49
-48 + 48
etc....
etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2).

Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time.

def pairs(k, minimum, maximum):
    if k >= 0:
        x = maximum
        y = k - maximum
    else:
        x = k + maximum
        y = minimum
    while x >= k / 2 and y <= k / 2:
        print str(x) + " , " + str(y) + " = " + str(x + y)
        x = x - 1
        y = y + 1

Mitchell on Oct 22, 2011
1

here is my solution using hash table that runs in O(2n) => O(n):

 public static String findNums(int[] array, int sum){
        String nums = "test";

        Hashtable lookup = new Hashtable();

        for(int i = 0; i < array.length; i++){
            try{
            lookup.put(array[i], i);
            } catch (NullPointerException e) {
                System.out.println("Unable to input data in Hashtable: " + e.getMessage());
            }
        }

        int num2;
        int num1;

        for (int i = 0; i < array.length; i++){
            num2 = sum - array[i];
            Integer index = (Integer)lookup.get(num2);
            if ((lookup.containsKey(num2)) && (index != i)){
                num1 = array[i];
                nums = array[i] + ", and " + num2;
                return nums;
            }
        }

        //System.out.println(lookup.get(-51));

        return "No numbers exist";
     }

Sen on Jan 10, 2012
1

The number you're looking for is T.

You can just create an array of size 101.
Then you loop through the array, and drop each number i in cell of index i-50.
Now you do a second pass, and for each number, you look at the number at index T-i-50. If there's something there, you have a pair.

Annymous on Mar 4, 2012
0

typedef pair Pair;
list l; //create an empty list of tuples
pairofsum(l,10); // an example of how to call the function which adds to your list of tuples the possible pairs of the sum

void pairofsum(list& l,int sum)
{
    if(sum==0)
    {
        Pair p;
        loadPair(p,0,0);
        l.push_back(p);
        for(int i=1;i<51;i++)
        {
            loadPair(p,i, -i);
            l.push_back(p);
        }
    }
    else if (sum<0)
    {
        Pair p;
        for(int i=0;i+-sum<51;i++)
        {
            loadPair(p,i,-(i+-sum));
            l.push_back(p);
        }
        for(int i=1;i<=-sum/2;i++)
        {
                loadPair(p,-i,sum+i);
                l.push_back(p);
        }
    }
    else
    {
        Pair p;
        for(int i=1;sum+i<51;i++)
        {
            loadPair(p,-i,sum+i);
            l.push_back(p);
        }
        for(int i=0;i<=sum/2;i++)
        {
            loadPair(p,i,sum-i);
            l.push_back(p);
        }
    }
}

void loadPair(Pair& p, int f, int s)
{
    p.first=f;
    p.second=s;
}

C++ Solution O(n) on Feb 17, 2015
0

Here is my C# implementation. It runs O(N) and doesn't include duplicate pairs (e.g. including [50,-50] as well as [-50,50]).

static void FindPairs(int sum) {
    for (int i=-50; i=-50) {
            Console.WriteLine(i + " " + otherNum);
        }
    }
}

Bryan Evans on May 10, 2015
0

Solution with no duplicates:

    @Test
    public void findPairsTest() {
        // TestCases
        // Alternately you can put this test cases in dataprovdier
        findPairs(50);
        findPairs(20);
        findPairs(-20);
        findPairs(-50);
        findPairs(0);
    }

    private void findPairs(Integer sum) {
        HashMap inputPair = new HashMap();
        HashMap outputPair = new HashMap();

        for(int i=-50; i<=50; i++) {
            inputPair.put(i, sum-i);
        }

        // print pairs
        for(Integer key : inputPair.keySet()) {
            Integer potentialOtherNum = inputPair.get(key);
            if(inputPair.containsKey(potentialOtherNum) && potentialOtherNum < key) {
                outputPair.put(key, potentialOtherNum);

            }
        }

        System.out.println(outputPair.entrySet().toString());
    }

Indrani on Jun 25, 2015
0

Here is the solution in O(n) time complexity.
http://www.knowsh.com/Notes/NotesSearch/NotesDetail/140226/Program-To-Find-All-The-Pairs-In-The-Given-Set-That-Add-Up-To-A-Certain-Sum

Please let me know if there is any thing I missed.

Priyank on Aug 1, 2016
0

Use two pointers, one at the begin, one at the end, let us call the pointer begin and end, the array is named nums. If nums[begin]+nums[end]>target, end--;if end

Anonymous on Dec 17, 2016
0

Half=sum/2;
i=1;
While (half+i -51) {
             first = half-i;
             second = half+i;
             System.out.println(“” + first + “, “ + second);
}

Anonymous on Oct 30, 2018
0

half=sum/2;
i=1;
While (half+i \ -51) {
             first = half-i;
             second = half+i;
             System.out.println(“” + first + “, “ + second);
}

Anonymous on Oct 30, 2018
0

Weirdly the less than and greater than signs make the text between them invisible. The conditional statement is supposed to say
Half=sum/2;
i=1;
While (half+i LESSTHAN 51 && half-i GREATERTHAN -51)

Anonymous on Oct 30, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.