Microsoft Interview Question for Software Engineer / Developers


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

- patpat October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cool

- Chengyun Zuo October 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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));

int answer=(1)+(3+1+2)+(3+1+2+4)+(1+2)+(3+1+2+4+6+2)+(3+1+2+4+6+2+7);
System.out.println(answer);
}

}

- Chengyun Zuo October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is O(n*logn)

- Chengyun Zuo October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Chengyun Zuo Can u please xplain the logic.

- rahul October 08, 2012 | Flag
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?

- fizzybuzzer October 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@All can you please explain in plain english commenting your garbage code. Unless you explain your logic, keep your garbage to yourself.

- Nobody October 21, 2012 | Flag
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)

- vik January 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- musfiqur February 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kevin March 05, 2013 | Flag
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

- sandesh October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Shobhit October 07, 2012 | Flag
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[0][0] * min(i[0][1], i[1]) for i in zip(
                           sorted(zip(s, reversed(range(len(s))))),
                           reversed(range(len(s))))])

- Nightingale October 07, 2012 | Flag Reply
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?

- Anonymous October 07, 2012 | Flag Reply
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 ??

- Dharam October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes

- Barney October 07, 2012 | Flag
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.

- DarkKnight October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Shobhit October 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sonesh November 22, 2012 | Flag
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;
}

- Raghav October 10, 2012 | Flag Reply
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[0] 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);

- REAMS.AL October 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is O(n^2) solution.

- Anonymous October 15, 2012 | Flag
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

- xx October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@xx, this solution is wrong.

- moron October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort it first.

- sophia October 16, 2012 | Flag Reply
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);

- Ankit October 21, 2012 | Flag Reply
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[0] = 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);

- OptimumsPrime October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@optimumsPrime
Your solution is still O(n^2)

- Kevin March 05, 2013 | Flag
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[0] + (A.length-2)*A[1] +...+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)

- offerofferoffer October 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
Your answer (4*1 +3*3 +2*4+1*5)-(2*3+2*4)

- Ankur November 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankur November 11, 2012 | Flag
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);
}
}

- In O(n2) September 10, 2013 | 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