## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

Similar to Merge Sort and Reverse Pairs. NlogN

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

Cool

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

patpat, you are right.
And this is my code.
Using Merge way, based on your idea:

public class Sum_Smaller_Then_Current {

public static int getSumofLessSum(int[] test,int begin,int end){
if(begin==end){
return 0;
}
if(begin==end-1){
if(test[begin]<=test[end]){
return test[begin];
}
else{
swap(test,begin,end);
return 0;
}
}
int mid=(begin+end)/2;
int leftPart=getSumofLessSum(test,begin,mid);
int rightPart=getSumofLessSum(test,mid+1,end);
int mergeSum=mergeTwoPartGetSum(test,begin,mid,end);
return leftPart+rightPart+mergeSum;

}
public static int mergeTwoPartGetSum(int[] test,int begin,int mid,int end){
int[] helpArray=new int[end-begin+1];
int begin1=begin;
int end1=mid;
int begin2=mid+1;
int end2=end;
int result=0;
int helpArrayIndex=0;

while(begin1<=end1&&begin2<=end2){
if(test[begin1]<=test[begin2]){
result+=test[begin1]*(end2-begin2+1);
helpArray[helpArrayIndex++]=test[begin1++];
}
else{
helpArray[helpArrayIndex++]=test[begin2++];
}
}

if(begin1>end1){
for(;begin2!=end2+1;){
helpArray[helpArrayIndex++]=test[begin2++];
}
}
else{
for(;begin1!=end1+1;){
helpArray[helpArrayIndex++]=test[begin1++];
}
}

for(int i=0;i!=helpArray.length;i++){
test[begin++]=helpArray[i];
}

return result;
}
public static void swap(int[] test,int begin,int end){
int tmp=test[begin];
test[begin]=test[end];
test[end]=tmp;
}
public static void main(String[] args) {
int[] test={3,1,2,4,6,2,7,8};
System.out.println(getSumofLessSum(test,0,test.length-1));

}

}

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

This solution is O(n*logn)

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

@ Chengyun Zuo Can u please xplain the logic.

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

Can you guys explain in English what your idea is and why is it nlogn?

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

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

Chengyun Zuo is right. I have removed some unnecessary code

``````public class sumSmallerThanCurr{
public static int getSumofLessSum(int[] test,int begin,int end){
if(begin==end) return 0;//base case
int mid=(begin+end)/2;
int leftPart=getSumofLessSum(test,begin,mid);
int rightPart=getSumofLessSum(test,mid+1,end);
int mergeSum=mergeTwoPartGetSum(test,begin,mid,end);
return leftPart+rightPart+mergeSum;
}
public static int mergeTwoPartGetSum(int[] test,int begin,int mid,int end){
//both subarrays are sorted due to merge in previus step
int[] helpArray=new int[end-begin+1];
int begin1=begin;
int end1=mid;
int begin2=mid+1;
int end2=end;
int result=0;
int helpArrayIndex=0;

while(begin1<=end1&&begin2<=end2){
if(test[begin1]<=test[begin2]){
result+=test[begin1]*(end2-begin2+1);
helpArray[helpArrayIndex++]=test[begin1++];
}
else helpArray[helpArrayIndex++]=test[begin2++];
}

if(begin1>end1)
for(;begin2!=end2+1;) helpArray[helpArrayIndex++]=test[begin2++];
else
for(;begin1!=end1+1;) helpArray[helpArrayIndex++]=test[begin1++];
for(int i=0;i!=helpArray.length;i++) test[begin++]=helpArray[i];
return result;
}
public static void main(String[] args) {
//int[] test={1,5,3,6,4};
int[] test={3,1,2,4,6,2,7,8};
}
}``````

Now the logic... we require sum of all elements which are current than current element and we have to find sum of such sum.... In other words each element will contribute M times where M is the number of elements larger than current element at indices higher than current index.

So the algo is exactly the merge sort with one additional line
result+=test[begin1]*(end2-begin2+1);

and this gives us the sum of sum

So for each sorted subarrays while merging if item in left subarray is smaller than item at right subarray then that element in left subarray will contribute K times (end2-begin2+1 i.e. elements still left in right subarray to merge)

So this is almost merge sort and we calculate sum at logN levels for N elements while merging subarrays so complexity becomes O(NlogN)

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

How it is like merge sort? In merge sort , you merge two sorted arrays. How this is like merge sort?

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

@vik
OMG, this is so complicated. Could you explain more about it? Thank you.

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

simple solution is that we caniterate over the previous existing list . a second is to keep tree hash map

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

algo should be better than O(n^2) . Values are in the range of 1 to 10^6 and can be repeated also.

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

I know how to do this in O(N * ln N) - Python code below. Linear solution seems to be possible given the fact the numbers are ranged - so we should be able to map the numbers to the sorted order in linear time, but then we need to iterate over them in linear time and that will take 10^6 steps. Whether it's better or worse than O(N * ln N) will depend on how many numbers we have.

``````s = [1, 1, 5, 3, 6, 4]
print sum([i * min(i, i) for i in zip(
sorted(zip(s, reversed(range(len(s))))),
reversed(range(len(s))))])``````

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

Should the array remain un-sorted at the end? What about using extra space?

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

@Barney ...just to be more clear..
For sum[i] , you need to grab the elements which are less than a[i] and in range 0 to i-1 ??

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

Yes

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

Crazy Idea very likely to be shot down instantly
O(nlogn)
Have a BST where each node is of this form

``````{
class Node
{
public int Data;
public Node Parent;
public Node Left;
public Node Right;
public int SumOfLeftSubTree;
public int SumofAllValuesLessThanCurrent;
}``````

}

Modify insert such that
1) In tree with root n, if you are trying to insert new element x into n's Left subtree then do this
n.SumOfLeftSubTree += x
2) To calculate SumofAllValuesLessThanCurrent, traverse tree upwards till root node. Every time temp node t Right child of parent p, do n.SumofAllValuesLessThanCurrent+=p.Data+p.SumOfLeftSubTree

Hope the solution makes sense.
I think its correct.

But its quite complicated and may not be optimal.

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

I thought the same thing. But it's going to be difficult if it forms a skew BST. Using AVL is not helping either. I mean updating the value of sum is quite tough to code during rotation.

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

Good, this is standard stuff, and rotation algorithms (for balanced trees) can deal with updating the sums.

Read CLR for a discussion using red-black trees.

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

parent node and sumallvalueslessthancurrent are not required, without these also we can do solve it...!!!

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

``````//keep adding the node in a BST and every node maintains a sum of its left subtree
//InsertAndSum returns the desired SumOfSums after the last node added.

struct NODE
{
int val;
NODE* left;
NODE* right;
int sum_ltree;

NODE(int v) : val(v), left(NULL), right(NULL), sum_ltree(0) {}
};

int InsertAndSum(NODE* root, int val)
{
int sum = 0;
if(root->val > val)
{
//insert on left
root->sum_ltree += val;
if(root->left)
{
sum = InsertAndSum(root->left, val);
}
else
{
NODE* p = new NODE(val);
root->left = p;
}
}
else
{
//insert on right
if(root->right)
{
sum = InsertAndSum(root->right, val);
}
else
{
NODE* p = new NODE(val);
root->right = p;
}

sum += root->val + root->sum_ltree;
}

return sum;
}``````

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

Simple Solution:

int a[ ] ,sum = 0 , n;

printf("Enter Size of array");
scanf("%d" , n);

/* Sum for a will always be 0. */

for(int i =1 ; i< n -1 ; i++)
{
for(int j = 0 ; j< i ;j++)
if(a[i] > a[j])
sum = sum + a[j];
}

Printf ("Sum is",sum);

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

this is O(n^2) solution.

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

This is a dynamic programming question. All one needs to do is start with the first element and add all items before it (it will be zero) and store that sum in some table labled first element. For all other elements just look only at the previous element and if it is less, store that element's stored value plus that element in this element's entry in the table. If not only store the element's stored value. The answer is what ever is stored last

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

@xx, this solution is wrong.

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

sort it first.

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

Try this simple solution
int a[] = new int[]{1,5,3,6,4,2,3};
int s=0;
for (int i=1;i<a.length;i++)
{
for(int j=i-1;j>=0;j--)
{
if (a[i]>a[j])
{
s = s+a[j];
}
}
}
System.out.println("Total Sum is ="+s);

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

Algorithm :
for each number in array find the occurrence of the number in total sum

e.g
a = 1 is less than every number following it (5, 3, 6, 4)
so it will come 4 times in the total (1 * 4)

Code :

int totalCnt = 0;
int n = a.Length;
for( int i= 0; i<n; i++)
{
int occurrence =0;
for(int j = i+1; j< n; j++){
if(a[i] < a[j]) { occurrence++; }
}

totalSum += a[i] * occurrence;
}

Console.WriteLine("TotalSum : {0}", totalSum);

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

@optimumsPrime

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

first, use a subsidy array to record the index of the elements, sort the array together with the index. In this example, we get
Sorted array A: 1,3,4,5,6
Index array B: 0,2,4,1,3
Sum = (A.length-1)*A + (A.length-2)*A +...+A[A.length-2]
scan array B, if B[i]>i, sum=sum - (B[i]-i)*A[i]
After the scanning, we get the sum.
This works for array with no repeating number. Time complexity is O(nlogN)

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

It wont work for the below input
1 6 5 3 4
0 1 2 3 4
Answer should be 4*1 + 3*1
New index according to algo
0 3 4 2 1

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

May be the above algo will work if we do the same processing freshly for left shifted elements also.

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

public class Sum {

public static void main(String[] args)
{
Generator arith = new Arithmetic(71, 21, 27);

int n = 100;

int[] input = arith.GenerateRandom(n);

int sum = 0;

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

for (int j = 0; j < i; j++) {
if (input[i] > input[j]) {
sum += input[j];
}
}
}

System.out.println(Arrays.toString(input));

System.out.println(sum);
}
}

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.