## Microsoft Interview Question for Software Engineers

• 0

Country: United States
Interview Type: In-Person

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;
}``````

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

nice

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

Question not clear.

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

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;
}``````

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;
}``````

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

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?

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;
}``````

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

}

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

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

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

Equilibrium index of an array -- GEEKS

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

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

}

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

}``````

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

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;
}``````

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

Yep, this is the expected answer.

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

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

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

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

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.