Microsoft Interview Question for SDE-2s


Team: Cloud & Enterprise team
Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array.
One variable points to the first element.
Another variable points to the last element.
Add the numbers in those indexes and move them as needed.

A few other testcase
Smallest and the biggest number should not add more than Integer.Max.
Array length must not be more than Integer.Max
Method parameters must not allow long.

- s100banerjee May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I implemented the sort technique in C. I dont think we need to return true or false. The question says, find all pairs which add to the number given. Hence must print out the pairs:

void find_pairs( int a[],int size) {
    sort(a);
    int first,last,i,j;
    first = a[0];
    last = a[size-1];
    i=0;
    j=size-1;
    while(j>i) {
	if(first+last == num) {
		printf("%d,%d\n",first,last);
		first=a[++i];
		last=a[--j];
	}
	if(first>num) first= a[++i];
	if(last>num) last =a[--j];
    }
}

I am not very good at calculating complexity. But this is an O(n) algorithm I guess?

- sowmya.kp May 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another O(n) approach in C:

void find_pairs(int a[], int size) {
static int arr[100],i;
for(i=0;i<size;i++) 
    arr[a[i]]=1;
for(i=0;i<size;i++) {
    if((num >= a[i]) {
        if(arr[num-a[i]]==1) {
		arr[a[i]]=0;
		printf("%d,%d\n",a[i],num-a[i]);
         }
   }
}

- sowmya.kp May 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity of your program is not O(n) , it depends on sorting algorithm.

- ansari May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity of your program is not O(n) , it depends on sorting algorithm.

- ansari May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be considered as well: all values in array should not be greater than the given number

- azharrahi May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain HashSet or HashMap of numbers found.
For each number n
- Search for sum-n in hash. If it exists, then n + sum-n is a pair that sums to sum.
- Place n into hash.
O(n)

For one thing, the question says to find all pairs that sum to a given number. This means testing return of true or false isn't quite valid. You would want to test for different sets of results.

- JW May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think having negative numbers is valid. -4+ -1 = -5. Nothing wrong in this.

- sowmya.kp May 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] getSums(int[] a, int n)
		{
			Array.Sort<int>(a);
			Array.Reverse(a);
			int sum = 0;
			int[] result = new int[a.Length];

			int k = 0;
			for (int i = 0; i < a.Length; i++)
			{
				if (a[i] + sum <= n)
				{
					sum += a[i];
					result[k++] = a[i];
				}
			}

			if (sum == n)
			{
				Array.Resize(ref result, k);
				return result;
			}

			return new int[0];
		}

- tus124 May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some more test cases are as follows:
1) If the given number is zero, then the integer array must have at least one negative number and one positive number having the same absolute value. Otherwise the we don't have valid pairs. for e.g. {1,-1} or {-2,2} etc.

2) If the given number is negative then at least one negative number exist in the integer array. Otherwise the we don't have valid pairs.

3) If the given number is positive, then at least one positive number exists in the integer array. Otherwise the we don't have valid pairs.

4) If the number is even, then the resultant pair must be combination of even numbers only or odd numbers only. The resultant pair cannot have one even and one odd because sum of even and odd cannot be even. So the valid pairs can be {even, even} or {odd, odd}.

5) Similarly, if the given number is odd, the valid pair should be combination of one even number and one odd number. for e.g. {even, odd} or {odd, even}.

Hope this helps.
Thanks,

- Piyush May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some more test cases are as follows:

1) If the given number is zero, then the integer array must have at least one negative number and one positive number having the same absolute value.
Otherwise we don't have valid pairs.

2) If the given number is negative, then the integer array must have at least one negative number. Otherwise we don't have valid pairs.

3) If the given number is positive, then the integer array must have at least one positive number. Otherwise we don't have valid pairs.

4) If the number is even, then the resultant pair must be combination of even numbers only or odd numbers only. The resultant pair cannot have one even and one odd because sum of even and odd cannot be even. So the valid pairs can be {even, even} or {odd, odd}.

5) Similarly, if the number is odd, then the resultant pair must be combination of even number and odd number only. So the valid pairs can be {even, odd} or {odd, even}.

Hope this helps.

Thanks,

- Piyush May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hmm, your test cases dont sound like test cases. They sound more like requirements for the function.

Think of testcases as inputs to the program.

1. give input > number
2. give negative input
3. give all numbers are the same < number
etc etc.
4. give all numbers > 0 in array, number = 0
etc etc

think of all possible variations of inputs that may exists and come up with a reasonable sampling of those.

that makes a good test case.

- TestingTesting May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an O(m+n) solution with lots of places where u can check for various boundary conditions and other test inputs. Build it on that. You have actually sort of specified test cases like requirements!!

import java.util.*;
class pairs
{
public static void main(String args[])
{
 int[] arr = new int[]{5,2,8,6,9,1,4,3};
 int sum = 9;
 Hashtable vals = new Hashtable();
 
 for(int i=0; i<arr.length;i++)
  vals.put(arr[i],arr[i]);

for(int i=0; i<arr.length;i++)
{ 
 if(vals.contains(sum-arr[i]))
 {
  
  System.out.println(arr[i]+" "+(sum-arr[i]));
  vals.remove(arr[i]);
  }
}
}
}

- liju.leelives June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry may not be O(m+n)..can be O(n+n) => O(2n) => O(n)?? i guess!! :/

- liju.leelives June 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;

void findAllPairs(int a[], 
                        int n, 
                        int num, 
                        std::vector<std::pair<int,int> >& pairs);
int partition(int a[], int start, int end, int pivot);
void quicksort(int a[], int n);
void qsort(int a[], int start, int end);

void printArr(int a[], int n)
{
    cout<<endl;
    for(int i=0;i<n;++i)
    {
        cout<<a[i]<<",";
    }
    cout<<endl;
}

int main()
{
	std::vector<std::pair<int,int> > pairs;
    int a[] = {3,5,9,10,2,1,-2,-3};
    int n = 6;
    findAllPairs(a,sizeof(a)/sizeof(int), n, pairs);
    for(int i=0;i<pairs.size();++i)
    {
        cout<<"pair["<<i<<"] = "<<pairs.at(i).first<<","<<pairs.at(i).second<<endl;
    }	
	return 0;
}

void findAllPairs(int a[], int n, int num, std::vector<std::pair<int,int> >& pairs)
{
	if (n <= 1)
	{
		return; //no pair.
	}
    cout<<"Array before sorting."<<endl;
    printArr(a,n);
	quicksort(a,n);
    cout<<"Array after sorting."<<endl;
    printArr(a,n);
	int start = 0;
	int end = n-1;
	while(start < end)
	{
		if (a[start] + a[end] == num)
		{
			pairs.push_back(std::make_pair(a[start], a[end]));
            ++start;
            --end;

		}
		else if (a[start] + a[end] < num) 
		{
			++start;
		}
		else 
		{
			--end;
		}
	}
}

void quicksort(int a[], int n)
{
    if (n <= 0)
        return;
    int start = 0;
    int end = n-1;
    qsort(a, start, end);
}

void qsort(int a[], int start, int end)
{
    if (start < end)
    {
        int pivot = start;
        int j = partition(a, start, end, pivot);
        int temp = a[pivot];
        a[pivot] = a[j];
        a[j] = temp;
        qsort(a, start, j-1);
        qsort(a, j+1, end);
    }
}

int partition(int a[], int start, int end, int pivot)
{
    while(start < end)
    {
        while(a[start] <= a[pivot] && start < end)
            ++start;
        while(a[end] > a[pivot])
            --end;
        if (start < end)
        {
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
        }
    }
    return end;
}

- jeetscoder August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Questions to ask:
Does an array contains duplicate?
Does an array contain negative?
Can we afford O(n) auxiliary space to boost performance?

Approaches:

Use hashtable - Time O(n) and Space O(n)

static void PrintSumNPairs(int[] input, int sum)
        {
            Dictionary<int, int> map = new Dictionary<int, int>();
            foreach (int i in input)
                map.Add(i, 1);

            foreach (int j in input)
            {
                if (j != sum -j && map.ContainsKey(sum - j))
                {
                    Console.WriteLine("Pair found - " + j + ", " + (sum - j));
                    map.Remove(j);
                    map.Remove(sum - j);
                }
            }
        }

Approach 2:

Sort O(nlogn)
Traverse from front and back in - O(n2)

total time O(n2) space O(1)

- codealtecdown September 11, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More