## Ebay Interview Question for Software Engineer / Developers

Team: Traffic
Country: United States
Interview Type: In-Person

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

github.com/techpanja/interviewproblems/tree/master/src/arrays/maxsubarray

``````/**
* the task of finding the contiguous subarray which has the largest sum.
*
* Algo:----
*
* 1. Maintain two variables: maxSoFar and maxEndingAtCurrentPosition in Array.
* 2. Update maxEndingAtCurrentPosition if (maxEndingAtCurrentPosition + current[i]) > than 0.
* 3. Keep on updating maxSoFar whenever maxEndingAtCurrentPosition is greater than maxSoFar.
*
* Date: 11/4/13
* Time: 3:23 PM
*/
public class FindMaxSubArray {

private FindMaxSubArray() {

}

public static int findMaxOfSubArrayUsingMathMax(int[] inputArray) {
int maxSoFar = 0;
int maxEndingHere = 0;
for (int i : inputArray) {
maxEndingHere = Math.max(0, maxEndingHere + i);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}

public static String findMaxSubArrayUsingFor(int[] inputArray) {
int maxSoFar = 0;
int maxEndingHere = 0;
int maxStartIndex = 0;
int maxEndIndex = 0;
for (int i = 0; i < inputArray.length; i++) {
System.out.println("ending here " + maxEndingHere);
System.out.println("so far " + maxSoFar);
if (maxEndingHere + inputArray[i] > 0) {
maxEndingHere = maxEndingHere + inputArray[i];
} else {
maxEndingHere = 0;
maxStartIndex = i + 1;
}
if (maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
maxEndIndex = i;
}
}
int[] maxArray = new int[0];
if (maxStartIndex <= maxEndIndex) {
maxArray = Arrays.copyOfRange(inputArray, maxStartIndex, maxEndIndex + 1);
}
return String.valueOf("\nInput-Array:" + Arrays.toString(inputArray)
+ "\nMax: " + maxSoFar
+ "\nSub-Array:" + Arrays.toString(maxArray));
}
}``````

Comment hidden because of low score. Click to expand.
-2

I'm not sure if this answer is correct. The question is about subsequence not subarray. In case of the input: {1, -10, 2, -10, 3} the output should be 6 not 3.

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

I assumed that its about max sub array which sometimes is also called as maxsubsequence. An e.g. with the question would have been better.

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

I think the answer is the set of positive numbers

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

yeah, brute force would be the way to go unless there are some time/space requirements.

Finding a 1 million sequence subset within a 1 billion item array, this would not work very well, but author didn't really specify

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

public int maxSubArray(int[] A) {

if(A.length == 0) return 0;
if(A.length == 1) return A[0];
int[] sums = new int[A.length];
sums[0] = A[0];

for(int i=1; i < A.length; i++){
sums[i] = sums[i-1]>0?sums[i-1] + A[i]:A[i];
}

int max = A[0];
for(int i=0; i < sums.length; i++){
if(max < sums[i]) max = sums[i];
}

return max;

}

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

package ms.ArraysStrings;

public class MaxSubArraySum {

public int findMaxSum(int[] inputArray) {
int currentMax = 0, maxSum = 0;
int curStart = 0, curEnd = 0;
int start=0, end=0;
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i] > currentMax + inputArray[i]) {
currentMax = inputArray[i];
curStart = i;
curStart = i;
} else {
currentMax = currentMax + inputArray[i];
curEnd = i;
}
if (currentMax > maxSum) {
maxSum = currentMax;
start = curStart;
end = curEnd;
}
}
System.out.println("Start of Max "+start+ " "+"End of Max "+end);
return maxSum;
}

public static void main(String[] args) {
int[] inputArray = { -2, -3, 4, -1, -2, 1, 5, -3 };
MaxSubArraySum mSum = new MaxSubArraySum();
int output = mSum.findMaxSum(inputArray);
System.out.println("Maximum sub array sum " + output);
}

}

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.