Microsoft Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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;
}
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()
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;
}
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;
}
**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()
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;
}
}
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;
}
}
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;
}
The time complexity of above solution would be O(n) and space complexity would be O(n). Is this correct?
Sum from both ends, always growing the smaller sum. When the pointers meet, return that index.
- sloreti January 03, 2016