GE (General Electric) Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
Just had a quick go at this using a sliding window approach in C assuming an array of integers:
#include <stdio.h>
// Uses a sliding window
int MaxSumOfSubArray(int *intArray, int len, int subLen)
{
if ( ( ! intArray ) || (subLen > len) )
{
return 0;
}
int blockSum = 0; // To store each possible sum
// Calculate the initial sum
int frontIdx = 0;
while (frontIdx < subLen)
{
blockSum += intArray[frontIdx];
frontIdx++;
}
int maxSum = blockSum; // Initial Result
// Slide the window through the array
int backIdx = 0;
while (frontIdx < len)
{
blockSum -= intArray[backIdx];
blockSum += intArray[frontIdx];
if (blockSum > maxSum)
{
maxSum = blockSum;
}
backIdx++;
frontIdx++;
}
return maxSum;
}
#define TEST_ARRAY_LEN 4
#define TEST_LENGTHS_LEN 6
void main(int argc, char * argv[])
{
int testArray[TEST_ARRAY_LEN] = { 1, 3, 5, 4 };
int testLengths[TEST_LENGTHS_LEN] = { 0, 1, 2, 3, 4, 5 };
printf("For testing array: { ");
for (int i = 0; i < TEST_ARRAY_LEN; i++)
{
printf("%d ", testArray[i]);
}
printf("}\n");
for (int i = 0; i < TEST_LENGTHS_LEN; i++)
{
printf("Max sum for subarray of length %d: %d\n", testLengths[i], MaxSumOfSubArray(testArray, TEST_ARRAY_LEN, testLengths[i]));
}
}
Seems to work pretty quickly but doesn't really employ any shortcuts.
We could use divide and conquer approach in this case.
public class MaxSumOfSubArray {
public static int findMaxSumOfSubArray(int[] elements) {
return findMaxSumOfSubArray(elements, 0, elements.length - 1);
}
private static int findMaxSumOfSubArray(int[] elements, int start, int end) {
if(start == end) {
return elements[start];
}
int sum = 0;
int mid = (start + end)/2;
int left = findMaxSumOfSubArray(elements, start, mid);
int right = findMaxSumOfSubArray(elements, mid+1, end);
int maxSum = 0;
int leftSum = Integer.MIN_VALUE;
int rightSum = Integer.MIN_VALUE;
for(int i = mid + 1; i <= end; i++) {
sum += elements[i];
leftSum = Math.max(sum, leftSum);
}
sum = 0;
for(int i = mid; i >= 0; i--) {
sum += elements[i];
rightSum = Math.max(rightSum, sum);
}
maxSum = Math.max(left, right);
int leftRightSum = leftSum + rightSum;
return Math.max(maxSum, leftRightSum);
}
public static void main(String[] args) {
int arr[] = {2, 3, -4, -5, -7};
int max = MaxSumOfSubArray.findMaxSumOfSubArray(arr);
System.out.println("Max: " + max);
}
}
@Stephen, since the question does not give a length for the subarray, applying Kadane's algorithm for Maximum subarray problem would be more optimal.
- raitGroup1007 July 25, 2017