## Microsoft Interview Question for SDE-3s

• 0

Country: United States
Interview Type: In-Person

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

``````public static boolean permute(ArrayList<Integer> prefix, ArrayList<Integer> input){
int sum1 = sum(prefix);
int sum2 = sum(input);
if(sum1 == sum2){
System.out.println("Sum: "+sum1);
return true;
}
else{
for(int i=0;i<input.size();i++){
//remove the element from input to prefix

boolean value = permute(prefix,input);

//add back the value from prefix to input

if(value) return true;
}
}
return false;
}

private static int sum(List<Integer> arr) {
int sum =0;
for(Integer val : arr){
sum+=val;
}
return sum;
}``````

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

This is called as a partition problem.
It can be solved using dynamic programming.
Also the time complexity is polynomial in n and not 2^n if we have liberty of space. Otherwise we will have to use recursive solution which has time complexity of 2^n.

``````public class Main {

public static void main(String[] args) {
int[] array = {1, 5, 11, 5, 2};
if(canBePartitioned(array)){
System.out.println("the given array can be partitioned.");
}else{
System.out.println("the given array cannot be partitioned.");
}

}

public static boolean canBePartitioned(int[] array){
int sum = 0;
for(int i=0; i<array.length; i++){
sum += array[i];
}
if(sum%1 == 1){
return false;
}
boolean[][] partition = new boolean[sum/2+1][array.length+1];
for(int i=0;i<array.length+1;i++){
partition[0][i] = true;
}
for(int i=1;i<sum/2+1; i++){
partition[i][0] = false;
}
for(int i=1; i<sum/2+1; i++){
for(int j=1; j<array.length+1; j++){
partition[i][j] = partition[i][j-1];
if(i >= array[j-1])partition[i][j] = partition[i-array[j-1]][j-1] || partition[i][j];
}
}
return partition[sum/2][array.length];
}
}``````

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

``````// ZoomBA
l = [ 4, 2, 2, 0, -1, 1 ]
possible = exists ( [1: #|l|] ) :: {
inx = \$.o
sum( l[0:inx-1] ) == sum ( l[inx:-1] )
}
println( possible )``````

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

Could you provide some clarification because I am not sure that I understand the problem well. If complexity should be 2^n, than we are talking about splitting the list in 2 subsets which have equal sum. I mean we have 1,2,5,4 and we split on {1,5} and {2,4} .Otherwise complexity is linear.
One offtopic question - is it true that you know the status of your interveiw at the end of the day (on site) I mean you are in or out, or this is a myth.

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

To answer you last question: It depends on the company. Amazon, Google, Facebook will respond in ~1 week. Microsoft can get back to you on the same day.
As for the first question:
The list does not need to be EVENLY split. So basically you can have a list
{1, 10, 2, 3, 4} that can be split into {10}, {1,2,3,4}
So you're basically looking at a permutation problem where you have to find lists of length 1-n such that Sum(subList) == Sum(List)/2
Also, another hint:
If sum(list) is odd then no such solution exists.

Also, it was the interviewer that said it cannot be resolved in polynomial time, so if you can disprove her, then good for you. I didn't get the answer because it was my 5th interview and I was completely burned out.

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

``````private bool CheckSumHelp(int[] input, int length)
{

int[] help = new int[length];
int p;
int n = (int)Math.Pow(2, length);

for (int index = 0; index < n; index++)
{

p = 0;
help[p] = help[p] + 1;
while (help[p] == 2)
{

help[p] = 0;
help[p + 1] = help[p + 1] + 1;
p++;
}

List<int> left = new List<int>();
List<int> right = new List<int>();

for (int i = 0; i < length; i++)
{

if (help[i] == 1)
{
}
else
{
}
}

if (left.Sum() == right.Sum())
{
Console.WriteLine("True");
return true;
}
}
Console.WriteLine("False");
return false;
}``````

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

Basically, the solution is polynomial as mentioned by the interviewer
Solution: Create subsets of the array (2^n subsets).
For each subset, check the sum of the subset is equal to sum of the other subset (superset - this subset). if yes return true, otherwise false.

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

``````int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) {
cin>>a[i];
}
bool ok=false;
int left=0,right=0;
for(int i=0;i<n;i++) {
// i  bit is set consider it as left pile
left+=a[i];
} else {
// i bit is not set consider as right pile
right+=a[i];
}
}
if(left==right) {
ok=true;
break;
}
}
if(ok) {
cout<<"Yes\n";
} else {
cout<<"No\n";
}``````

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

it is a dynamic programming problem.
let B[i][j] be the true/false value if value i can be represented by elements from an array A[1] to A[j]
then B[i][j] = B[i][j-1] or B[i-A[j]][j-1]
B[s/2][n] contain the final result.

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

Why not try the following:
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n-1] - a[i] = a[i]

e.g.
-1 1 1 2 2 5
Sums:
-1 0 1 3 5 10

10-5 = 5. we have a winner

e.x2:

-1 -1 1 2 2 2 3 5 6 7
Sums:
-1 -2 -1 1 3 5 13 19 26

26-13 = 13, we have a winner

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

Why not try the following (nlogn):
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n-1] - a[i] = a[i]

e.g.
-1 1 1 2 2 5
Sums:
-1 0 1 3 5 10

10-5 = 5. we have a winner

e.x2:

-1 -1 1 2 2 2 3 5 6 7
Sums:
-1 -2 -1 1 3 5 13 19 26

26-13 = 13, we have a winner

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

It is a DP problem. Sum the entire array and divide by 2. If the sum is even than use the subset sum problem to search for sum/2. If the sum is odd no solution exists.

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

This can be done in O(n) time complexity.
1. Sum the whole array as right_sum;
2. Left_sum = 0;
3. At any index compare if left _sum is equal to right_sum and return true if they are equal.
4. At every index right_sum =--a[i] and left_sum+=a[i].
5. After i exhaust return false

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

hjj

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

hihi

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

This is a O(N) solution.
1. get a sum array, where sumArray[i] = sumArray[i-1] + array[i] for all i in array.
2. find the index of sumArray[N] / 2 , say iSplit.
3. Split at iSplit

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

Hi,
I tried to solve it without permutation. First sort the given array and then divide the array in two sorted vectors. Hence, the resultant sorted vectors will have minimum difference in their total sums.Then recursively I swap the elements till we get the equal sum on both the sides. I keep the vectors sorted so that it becomes easy in swapping the elements.

You can directly copy paste the following code are compile are run it. Please let me know if find any issue.

Time complexity of the following algo in average case should much less than 2^n.

``````// TwolistEqualSum.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}

void SwapItems(vector<int> *v1, int * arry1Total, vector<int> *v2, int * array2Total, int mean)
{

if ((v1->size() == 0) || (v2->size()==0))
{
return;
}

if (*arry1Total == *array2Total)
{
return;
}

if (*arry1Total > mean)
{
int diff =  *arry1Total - mean;
int i = 0;
int temp;

do
{

temp = (*v1)[i];

*arry1Total = *arry1Total - temp;

v2->push_back(temp);

v1->erase(v1->begin() + i);

*array2Total = *array2Total + temp;

if (*array2Total == *arry1Total)
{
break;
}

diff = diff - temp;

}while (v1->size() > 0 && diff > 0);

qsort(&(*v2)[0], v2->size(), sizeof(int), compare);

}
else
{
int diff = *array2Total - mean;

int i = 0;
int temp;
do
{
temp = (*v2)[i];

*array2Total = *array2Total - temp;

v1->push_back(temp);

v2->erase(v2->begin() + i);

*arry1Total = *arry1Total + temp;

if (*array2Total == *arry1Total)
{
break;
}

diff = diff - temp;

}while (v2->size() > 0 && diff > 0);

qsort(&(*v1)[0], v1->size(), sizeof(int), compare);

}

static int iteration = 0;

iteration++;

if (iteration < ((v1->size() + (v2->size()) / 2)))
{
SwapItems(v1, arry1Total, v2 , array2Total, mean);
}

return;

}

int _tmain(int argc, _TCHAR* argv[])
{

const int inputSize = 22;
int input[inputSize] = {4,2,2,0,-1,1,10,3,7,15,23,20,3,9,6,199,50,50,50,49,12,2}; // assume the input and its size is known. For testing purpose just change inputSize and input array

/* Sampe input2
const int inputSize = 19;
int input[inputSize] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,1,10}; // assume the input and its size is known. For testing purpose just change inputSize and input array

*/

vector<int> v1, v2;

int total = 0;

cout << " Input list : ";

for (int i =0 ; i < inputSize; i++)
{
total = total + input[i];
cout << input[i] << " ";
}

cout << endl;

if (total % 2)
{
cout << " Not possible to divide the input list";
}
else
{
qsort(input, inputSize, sizeof(int), compare);

int arry1Total = 0;
int array2Total = 0;
int mean = 0;

for (int i =0 ; i < inputSize; i++)
{
if (!(i % 2))
{
v1.push_back(input[i]);
arry1Total = arry1Total + input[i];
}
else
{

v2.push_back(input[i]);

array2Total = array2Total + input[i];
}
}

mean = (arry1Total + array2Total) / 2;

SwapItems(&v1, &arry1Total, &v2, &array2Total,  mean);

if (arry1Total == array2Total)
{

cout << " List 1: ";

for ( int k = 0; k < v1.size(); k++)
{
cout << v1[k] << "  ";
}

cout << " : Total:" << arry1Total;
cout << endl;

cout << " List 2: ";
for ( int k = 0; k < v2.size(); k++)
{
cout << v2[k] << "  ";
}

cout << " : Total:" << array2Total;
cout << endl;
}
else
{
cout << " Not possible to divide the input list";
}
}

int j;

cin >> j;

return 0;
}``````

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

You don't need 0(n2) algorithm for this because it is a partition between prefix and postfix strictly.. what u do is find the get the sum of all the elements in the array (lets call it total_sum). Now start with element 0, and start cumulative sum.. at any time if 2*cumulative sum = total sum, we have the partition.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Thank you for the answers William.
Here is my solution - dynamically programming - partition problem

``````boolean canSplitEqually(int[] nums) {

int sum = 0;
for ( int item : nums) {
sum += item;
}
if (sum%2 != 0) {
return false;
}
boolean can[] = new boolean[sum+1];
can[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int s = sum; s + 1 >  0; s--) {
if (can[s]) {
if(s+nums[i] <= sum)
can[s+nums[i]] = true;
}
}
}
return can[sum/2];
}``````

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

2, 2, 4, 8, 0, 1, -1, 6, 7, 8, 9

out of range

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.

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