CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Microsoft Interview Question for Software Engineers


Country: United States
Interview Type: In-Person
More Questions from This Interview



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

Sum from both ends, always growing the smaller sum. When the pointers meet, return that index.

public static int balanceArray(int[] arr){

        int left = 0;
        int right = arr.length -1;
        int leftSum = 0;
        int rightSum = 0;

        while (right > left){

            if (rightSum >= leftSum){
                leftSum += arr[left];
                left++;
            } else {
                rightSum += arr[right];
                right--;
            }
        }
        return right;
    }

- sloreti January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

nice

- mehraz January 04, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question not clear.

- aka January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Start with two iterators(low and high) and sums(lowSum and highSum) from the beginning and the end each. Iterate closer to the center of the array and add to the sum from either end depending on which sum is smaller. If the lowSum sum is less, increment low and add that value to the lowSum. Same thing for highSum. Keep going until we have touched all indices and return the difference. C++ code: {{{ int findBalance(int arr[], int size) { int low = 0; int high = arr.size()-1; int lowSum = arr[low]; int highSum = arr[high]; //while we have not reached all indices while(low+1<high) { //keep adding to lowSum as long as it is less than highSum //and we have not reached all indices while(lowSum < highSum && (low+1)<high) { low++; lowSum += arr[low]; } //now highSum is less, so keep adding as long as that is the case //and we have not reached all indices while(lowSum > highSum && low < high-1) { high--; highSum += arr[high] } } return abs(lowSum-highSum); } - thegreenfrog January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sum from both ends, always growing the smaller sum. When the pointers meet, return that index.

public static int balanceArray(int[] arr){

        int left = 0;
        int right = arr.length -1;
        int leftSum = 0;
        int rightSum = 0;

        while (right > left){

            if (rightSum >= leftSum){
                leftSum += arr[left];
                left++;
            } else {
                rightSum += arr[right];
                right--;
            }
        }
        return right;
    }

- sloreti January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int balanceArray(int[] arr){

        int left = 0;
        int right = arr.length -1;
        int leftSum = 0;
        int rightSum = 0;

        while (right > left){

            if (rightSum >= leftSum){
                leftSum += arr[left];
                left++;
            } else {
                rightSum += arr[right];
                right--;
            }
        }
        return right;
    }

- Anonymous January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create pointers at both ends and a left sum and right sum. Grow the smaller sum and increment/decrement the appropriate pointer. When the pointers meet, return that index.

public static int balanceArray(int[] arr){

        int left = 0;
        int right = arr.length -1;
        int leftSum = 0;
        int rightSum = 0;

        while (right > left){

            if (rightSum >= leftSum){
                leftSum += arr[left];
                left++;
            } else {
                rightSum += arr[right];
                right--;
            }
        }
        return right;
    }

- sloreti January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import random
def solution(A,N):
equi_index = []
minimizedDiff = []
sum_suf = 0
sum_pre = 0
for index in A:
sum_suf = sum_suf + index
for itr in range(0,N):
if itr == 0:
sum_suf = sum_suf - A[itr]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == 0:
equi_index.append(itr)
elif itr < N-1:
sum_suf = sum_suf - A[itr]
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == sum_pre:
equi_index.append(itr)
elif itr == N-1:
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_pre == 0:
equi_index.append(itr)
# else:
# return -1
if equi_index is not None:
# return equi_index
print('Equilibrium Index: ',random.choice(equi_index) if equi_index is not None else print("No equilibrium indices in the given array"))
else:
#return minimizedDiff
print('Index minimizing the difference: ',min(minimizedDiff))

def main():
A = [-1,3,-4,5,1,-6,2,1]
# equi_index=solution(A,len(A))
solution(A,len(A))

if __name__ == '__main__':
main()

- Aditya Pulekar January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The time complexity of above solution would be O(n) and space complexity would be O(n). Is this correct?

- Ved January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int equilibrium(int arr[], int n)
{
   int sum = 0;      // initialize sum of whole array
   int leftsum = 0; // initialize leftsum
   int i;
 
   /* Find sum of the whole array */
   for (i = 0; i < n; ++i)
        sum += arr[i];
 
   for( i = 0; i < n; ++i)
   {
      sum -= arr[i]; // sum is now right sum for index i
 
      if(leftsum == sum)
        return i;
 
      leftsum += arr[i];
   }
 
    /* If no equilibrium index found, then return 0 */
    return -1;
}

- Nit January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int equilibrium(int arr[], int n)
{
   int sum = 0;      // initialize sum of whole array
   int leftsum = 0; // initialize leftsum
   int i;
 
   /* Find sum of the whole array */
   for (i = 0; i < n; ++i)
        sum += arr[i];
 
   for( i = 0; i < n; ++i)
   {
      sum -= arr[i]; // sum is now right sum for index i
 
      if(leftsum == sum)
        return i;
 
      leftsum += arr[i];
   }
 
    /* If no equilibrium index found, then return 0 */
    return -1;

}

- Anonymous January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/equilibrium-index-of-an-array/

- Nit January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Equilibrium index of an array -- GEEKS

- Nit January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

**Note: The code is in python. I'm providing brace brackets "{}" instead of colon ":" just for better visibility.

import random

def solution(A,N) {
equi_index = []
minimizedDiff = []
sum_suf = 0
sum_pre = 0
for index in A {
sum_suf = sum_suf + index
}
for itr in range(0,N){
if itr == 0 {
sum_suf = sum_suf - A[itr]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == 0 {
equi_index.append(itr)
}
}
elif itr < N-1 {
sum_suf = sum_suf - A[itr]
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_suf == sum_pre {
equi_index.append(itr)
}
}
elif itr == N-1 {
sum_pre = sum_pre + A[itr-1]
minimizedDiff.append(abs(sum_suf-sum_pre))
if sum_pre == 0 {
equi_index.append(itr)
}
}
}
if equi_index is not None {
print('Equilibrium Index: ',random.choice(equi_index) if equi_index is not None else print("No equilibrium indices in the given array"))
}
else {
print('Index minimizing the difference: ',min(minimizedDiff))
}
}

def main() {
A = [-1,3,-4,5,1,-6,2,1]
solution(A,len(A))
}

if __name__ == '__main__':
main()

- Aditya P January 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BalancedArray {

public static void main(String[] args) {
// TODO Auto-generated method stub

int[] myArray = {12, 1, 4, 6, 8};
int balance = findBalance(myArray);
System.out.println("Balancing Index: " + balance);
}

private static int findBalance(int[] myArray) {
// TODO Auto-generated method stub
if(myArray.length == 1)
{
System.out.println("Array length 1");
return 0;
}

int right = myArray.length-1;
int left = 0;
int rSum = myArray[right], lSum = myArray[left];

while(right != left)
{

System.out.println("LSum: " + lSum + " RSum: " + rSum);
if(rSum <= lSum)
{
right--;
rSum += myArray[right];
}
else
{
left++;
lSum += myArray[left];
}
}
return right;
}

}

- Zesta January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BalancedArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] myArray = {12, 1, 4, 6, 8};
		int balance = findBalance(myArray);
		System.out.println("Balancing Index: " + balance);
	}

	private static int findBalance(int[] myArray) {
		// TODO Auto-generated method stub
		if(myArray.length == 1)
		{
			System.out.println("Array length 1");
			return 0;
		}
		
		int right = myArray.length-1;
		int left = 0;
		int rSum = myArray[right], lSum = myArray[left];
		
		while(right != left)
		{
			
			System.out.println("LSum: " + lSum + "  RSum: " + rSum);
			if(rSum <= lSum)
			{
				right--;
				rSum += myArray[right];
			}
			else
				{
					left++;
					lSum += myArray[left];
				}
		}
		return right;
	}

}

- Zesta January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well, everybody seems to be answering the first part.. how about the second part to the problem? Minimize the difference.. I know of a way. But the condition seems to be accessing the items just once...

- Anonymous February 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Start summing from both ends. When leftSum is smaller, add the value at left pointer to leftSum and increment left pointer. When the rightSum is smaller, add the value at right pointer to rightSum and decrement the right pointer. When the pointers meet, return that index.

public static int balanceArray(int[] arr){

        int left = 0;
        int right = arr.length -1;
        int leftSum = 0;
        int rightSum = 0;

        while (right > left){

            if (rightSum >= leftSum){
                leftSum += arr[left];
                left++;
            } else {
                rightSum += arr[right];
                right--;
            }
        }
        return right;
    }

- sloreti January 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep, this is the expected answer.

- tamashionuth January 03, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The time complexity of above solution would be O(n) and space complexity would be O(n). Is this correct?

- Ved January 05, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The time complexity of above solution would be O(n) and space complexity would be O(n). Is this correct?

- Ved January 05, 2016 | Flag


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