Galatea Associates Interview Question
Software DevelopersCountry: United States
Interview Type: Written Test
My solution:
private static int array[];
public int largestSubarray(int S) {
int negativeCount, positiveCount, neutralCount;
getCountValues(positiveCount, negativeCount, neutralCount);
int solution = 0;
if (positiveCount < S) {
solution = 0;
} else if (positiveCount == S) {
solution = neutralCount + positiveCount;
} else if (positiveCount - S < negativeCount){
solution = neutralCount + 2* positiveCount - S;
} else if (positiveCount - S >= negativeCount) {
solution = neutralCount + 2*negativeCount + S;
}
return solution;
}
public void getCountValues(int positiveCount, int negativeCount, int neutralCount) {
for (int element : array) {
if (element < 0) {
negativeCount++;
} else if (element > 0) {
positiveCount++;
} else {
neutralCount++;
}
}
}
int Solution::longestSum (vector<int>&a, int s) {
int n=a.size();
if (s<0)
forn(i,n) a[i]=-a[i];
s=myabs(s);
vector<int>sum(n);
forkn(i,1,n-1)
sum[i]=sum[i-1] + a[i];
int i=0, i1=-1;
int j=n-1, j1=-1;
while (i<=j) {
int tmp = sum[j]-sum[i]+a[i];
if (tmp == s) {
i1=i-1;
while (i1>=0 && a[i1] == 0 )
i1--;
i1++;
j1=j+1;
while (j1<n && a[j1] == 0)
j1++;
j1--;
break;
}
if (a[i] == 0)
i++;
if (a[j] == 0)
j--;
if (tmp > s) {
if (a[j] == 1)
j--;
else i++;
}
else {
if (a[j] == -1)
j--;
else i++;
}
}
return j1-i1+1;
}
Calculate sum and run two pointers from two ends of an array and decrease it with greedy
My solution:
Complexity O(n)
Space O(n)
- techinterviewquestion.com March 02, 2016