Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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);
}
}
@All can you please explain in plain english commenting your garbage code. Unless you explain your logic, keep your garbage to yourself.
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)
How it is like merge sort? In merge sort , you merge two sorted arrays. How this is like merge sort?
simple solution is that we caniterate over the previous existing list . a second is to keep tree hash map
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))))])
@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 ??
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.
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.
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.
//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;
}
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);
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
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);
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)
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)
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);
}
}
Similar to Merge Sort and Reverse Pairs. NlogN
- patpat October 07, 2012