Zillow Interview Question Software Engineer / Developers
#include <iostream>
using namespace std;
int * subarray(int *a, int size)
{
int *tmp = new int[size];
int high_index = 0,low_index = 0;
for(int y=0;y<size;y++)
tmp[y]=0;
if(a[0]<0)
tmp[0] = 0;
for(int j=1;j<size;j++)
{
if((tmp[j-1]+a[j])<0)
tmp[j] = 0;
else
tmp[j] = tmp[j-1]+a[j];
}
high_index = tmp[0];
low_index = tmp[0];
for(int k=1;k<size;k++)
{
if(high_index<tmp[k])
high_index = k;
}
cout<<"High_index:"<<high_index<<"\n";
for(int k=1;k<=high_index;k++)
{
if(tmp[k] == 0)
low_index = k;
}
low_index +=1;
cout<<"low_index:"<<low_index<<"\n";
tmp = new int[high_index - low_index +1];
int *tmp2 = tmp;
for(int j=low_index;j<=high_index;j++)
*tmp++ = a[j];
*tmp='\0';
return tmp2;
}
int main()
{
int a[8]= {-7,-4,-2,5,-3,-6,-8,9};
int *tmp=subarray(a,sizeof(a)/sizeof(int));
while(*tmp != '\0')
{
cout<<"resultF:"<<*tmp<<"\n";
tmp++;
}
getchar();
return 0;
}
Here is my version..
#include<stdio.h>
void main()
{
int i, n, sum=0, prev_sum = 0, a[100], smallest_negative, start_index, end_index, prev_start_index, prev_end_index,smallest_index;
printf("Enter the number of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(i = 0;i<n;i++)
scanf("%d", &a[i]);
smallest_negative = a[0];
start_index = 0;
end_index = 0;
prev_start_index = 0;
prev_end_index = 0;
smallest_index = 0;
for(i=0;i<n;i++)
{
if(smallest_negative < a[i])
{
smallest_negative = a[i];
smallest_index = i;
}
if(sum + a[i] < sum && prev_sum < sum)
{
prev_end_index = i-1;
prev_start_index = start_index;
prev_sum = sum;
}
sum = sum + a[i];
if(sum < 0)
{
sum = 0;
start_index = i+1;
}
else
end_index = i;
}
if(sum < prev_sum)
{
start_index = prev_start_index;
end_index = prev_end_index;
}
sum = (sum > prev_sum)?sum:prev_sum;
if(!sum)
{
sum = smallest_negative;
start_index = end_index = smallest_index;
}
printf("The maximum sum in the array is %d ", sum);
printf("The elements are \n");
for(i=start_index;i<=end_index;i++)
printf("%d ", a[i]);
Isnt the greatest continuous sum for first sequence = 12 ? {4, -2, 5, 3, -6, 8}
Below is the code snippet.
public int largestSum()
{
int[] arrInt = {-7, 4, -2, 5, 3, -6, 8, -9};
int sum = 0;
int decLen1 = 0;
int decLen2 = 0;
for(int r=0;r<arrInt.length;r++)
{
decLen1 = arrInt.length;
decLen2 = arrInt.length;
for(int t=r;t<decLen1;t++)
{
for (int y=t;y<(decLen2);y++)
{
sum = sum + arrInt[y] ;
}
sSt.add(sum);
decLen2 --;
sum = 0;
}
}
System.out.println("So the greatest sum is : " + sSt.last());
}
You can use prefix sums and suffix sums. First compute both sum arrays. Then scan the prefix sum from left to right to find out the best end index. This is the position that if you go further to the right, the sum will only decrease.
From this position, scan the suffix sums backward to find the max suffix sum value you encounter.
Once you have the start and end position, calculate the sum of the slice between best start index and best end index.
public static int getMaxSequenceSum(int[] numbers) {
int n = numbers.length;
int[] prefixSum = new int[n];
int[] suffixSum = new int[n];
int bestEndIndex = 0;
int bestEndValue = prefixSum[0];
prefixSum[0] = numbers[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = numbers[i] + prefixSum[i - 1];
int endValue = prefixSum[i] - prefixSum[i - 1];
if (endValue > bestEndValue) {
bestEndValue = endValue;
bestEndIndex = i;
}
}
int bestStartIndex = bestEndIndex;
int bestStartValue = suffixSum[bestStartIndex];
suffixSum[n - 1] = numbers[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffixSum[i] = numbers[i] + suffixSum[i + 1];
int startValue = suffixSum[i];
if (startValue > bestStartValue) {
bestStartValue = startValue;
bestStartIndex = i;
}
}
int maxSum = prefixSum[bestEndIndex];
if (bestStartIndex > 0)
maxSum -= prefixSum[bestStartIndex - 1];
return maxSum;
}
}
public List<Integer> maxSum(int[] arr) {
if(arr == null || arr.length == 0) return null;
int len = arr.length, st = 0, en = 0, max = arr[0], nextMax = arr[0], nextSt = 0;
for(int i = 1; i < len; ++i) {
if(nextMax <= 0){
nextMax = arr[i];
nextSt = i;
}else{
nextMax += arr[i];
}
if(max < nextMax) {
max = nextMax;
st = nextSt;
en = i;
}
}
List<Integer> result = new ArrayList<Integer>();
for(int i = st; i < en + 1; ++i){
result.add(arr[i]);
}
return result;
}
public List<Integer> maxSum(int[] arr) {
if(arr == null || arr.length == 0) return null;
int len = arr.length, st = 0, en = 0, max = arr[0], nextMax = arr[0], nextSt = 0;
for(int i = 1; i < len; ++i) {
if(nextMax <= 0){
nextMax = arr[i];
nextSt = i;
}else{
nextMax += arr[i];
}
if(max < nextMax) {
max = nextMax;
st = nextSt;
en = i;
}
}
List<Integer> result = new ArrayList<Integer>();
for(int i = st; i < en + 1; ++i){
result.add(arr[i]);
}
return result;
}
using System;
- Veritas September 26, 2007using System.Collections.Generic;
using System.Text;
namespace SequenceSumFinder
{
class Program
{
private int[] sequence;
static void Main(string[] args)
{
Program pg = new Program();
int sum = 0;
int[] array;
string[] strLine = Console.ReadLine().Split(',', '}', '{');
array = new int[strLine.Length];
for (int i = 0; i < strLine.Length; i++)
{
array[i] = Convert.ToInt32(strLine[i]);
}
pg.FindLargestSum(array,array,ref sum);
pg.PrintResult();
}
public void PrintResult()
{
string prnt = "{";
for (int i = 0; i < sequence.Length; i++)
{
prnt += sequence[i] + ",";
}
prnt = prnt.TrimEnd(',');
prnt += "}";
Console.Write(prnt);
}
public void FindLargestSum(int[] seqArr, int[] iniArr, ref int sum)
{
int[] tmpArr = new int[seqArr.Length];
while (iniArr.Length > 0)
{
SumLeftToRight(seqArr, ref sum);
SumRightToLeft(ReverseArray(seqArr), ref sum);
if (iniArr.Length > 2)
{
iniArr = TrimArray(iniArr, 1, iniArr.Length - 1);
FindLargestSum(iniArr, iniArr, ref sum);
}
else
{
SumLeftToRight(iniArr, ref sum);
SumRightToLeft(ReverseArray(iniArr), ref sum);
iniArr = TrimArray(iniArr, 1, iniArr.Length - 1);
}
}
}
public void SumLeftToRight(int[] seqArr, ref int sum)
{
int newSum = 0;
int[] tmpArr = new int[seqArr.Length];
int start = 0;
int end = seqArr.Length;
if (seqArr.Length > 0)
{
for (int i = 0; i < end; i++)
{
newSum += seqArr[i];
}
if (newSum >= sum)
{
sequence = new int[seqArr.Length];
sequence = seqArr;
sum = newSum;
}
SumLeftToRight(TrimArray(seqArr, start, end-1), ref sum);
}
}
public void SumRightToLeft(int[] seqArr, ref int sum)
{
int newSum = 0;
int[] tmpArr = new int[seqArr.Length];
int start = 0;
int end = seqArr.Length;
if (seqArr.Length > 0)
{
for (int i = 0; i < end; i++)
{
newSum += seqArr[i];
}
if (newSum >= sum)
{
sequence = new int[seqArr.Length];
sequence = ReverseArray(seqArr);
sum = newSum;
}
SumRightToLeft(TrimArray(seqArr, start, end - 1), ref sum);
}
}
public int[] TrimArray(int[] oldArr, int start, int end)
{
int size = (end - start)>=0?(end-start):0;
int[] newArr = new int[size];
int index = 0;
for (int i = start; i < end; i++)
{
newArr[index] = oldArr[i];
index++;
}
return newArr;
}
public int[] ReverseArray(int[] oldArr)
{
int[] newArr = new int[oldArr.Length];
int index = oldArr.Length - 1;
for (int i = 0; i < oldArr.Length; i++)
{
newArr[index] = oldArr[i];
index--;
}
return newArr;
}
}
}