Epic Systems Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




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

Modified Kandane's algorithm.

class Solution{
	int[] solution(int[] n){
		if(n.length <2)
			return null;
		if(n.length == 2)
			return n;

		int maxStart = 0;
		int maxEnd = 1;
		int maxHereStart = 0;
		int maxHereEnd = 1;
		int max_ending_here = n[0] + n[1];
		int max_so_far = max_ending_here;
		for(int i = 2; i < n.length ; i ++){
			if(n[i]+n[i-1] > (max_ending_here + n[i]))
			{
				max_ending_here = n[i]+n[i-1];
				maxHereEnd = i;
				maxHereStart = i-1;
			}else
			{
				max_ending_here = max_ending_here + n[i];
				maxHereEnd = i;
			}
			if(max_ending_here > max_so_far){
				max_so_far = max_ending_here;
				maxStart = maxHereStart;
				maxEnd = maxHereEnd;
			}
		}

		int[] result = new int[maxEnd - maxStart+1];
		for(int k = 0; k<= (maxEnd-maxStart); k++){
			result[k] = n[k+maxStart];
		} 
		return result;
	}

}

- Gang.Yang2012 October 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getMaxSum(int[] arr)
	{
		int start=0;
		int end=0;
		int tempStart=0;
		int maxSum =0;
		int maxSumEnding =0;
		for(int i=0;i<arr.length;i++)
		{
			if((maxSumEnding<0 && arr[i]<0))
			{
				maxSumEnding =0;
				tempStart = i;
			}
			maxSumEnding += arr[i];
			if(maxSumEnding < arr[i])
			{
				maxSumEnding = arr[i];
				tempStart = i;
			}
				
			if(maxSumEnding > maxSum && i-tempStart >1)
			{
				maxSum = maxSumEnding;
				end = i;
				start = tempStart;
			}
		}
		System.out.println(start);
		System.out.println(end);
		return maxSum;

}

- Satya Swaroop September 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:

public static int[] maxSubsection(int[] arr){
  if(arr == null || arr.length < 2){
    return null;
  }
  int start = 0;
  int end = 1;
  int tempStart = start;
  int tempEnd = end;
  int localMax = arr[0] + arr[1];
  int max = localMax;
  int temp;
  int ptr = 2;
  while (ptr < arr.length){
    //compute shifting local max
    temp = arr[ptr-1] + arr[ptr];
    if(temp  < localMax + arr[ptr]){
      localMax += arr[ptr];
    }
    else{
      localMax = temp;
      start = ptr-1;
    }
    end = ptr;
    //compare with the overall max
    if(localMax > max){
      start = tempStart;
      end = tempEnd;
      max = localMax;
    }
    ptr++;
  }
  return new int[]{start, end};
}

- zortlord October 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

return statement should be

return Arrays.copyOfRange(arr, start, end);

- zortlord October 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] maxSubArrayEpic(int[] A) {
if (A.length <= 2 || A == null) {
return A;
}
int[] dp = new int[A.length];
dp[0] = A[0];
// use dp array to store the max sum of subarray
for (int i = 1; i < A.length; i++) {
dp[i] = Math.max(A[i], dp[i - 1] + A[i]);
}
int max = dp[0];
int index = 0;
// iterate dp array to find the max index;
for (int i = 1; i < dp.length; i++) {
if (dp[i] > max) {
index = i;
max = dp[i];
}
}
// use list to add the element of max subarray
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(A[index]);
if (index - 1 > 0) {
for (int i = index - 1; i >= 0; i--) {
if (dp[i] < 0) {
break;
}
list.add(A[i]);
}
}
int[] result = new int[list.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = list.get(i);
}
if (result.length == 1) {
result = new int[2];
int maxPair = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int i = 1; i < A.length; i++) {
if (A[i] + A[i - 1] > maxPair) {
start = i - 1;
end = i;
maxPair = A[i] + A[i - 1];
}
}
result[0] = A[start];
result[1] = A[end];
}
return result;
}

- charles901030 October 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <limits.h>

using namespace std;

void kadane(int a[], int n){
  int gstart=0;
  int gend=0;
  int lmax=0;
  int gmax=INT_MIN;

  for(int i=0;i<n;i++){
    lmax=max(lmax+a[i],a[i]);
    gmax=max(lmax,gmax);
    if(gmax==a[i]){
      gstart=i;
      gend=i;
    }
    else if(gmax==lmax){
      gend=i;
    }
  }
  if(gstart==gend){
    gmax=INT_MIN;
    for(int i=1;i<n;i++){
      gmax=max(gmax,a[i-1]+a[i]);
      if(gmax==(a[i-1]+a[i])){
        gstart=i-1;
        gend=i;
      }
    }
  }
  cout<<gstart<<" "<<gend<<" "<<gmax<<endl;
}

int main(){
  //int a[]={1,2,3,-4,5,-9};
  int a[]={-1,-2,-3,-4,-5,-9};
  int n=sizeof(a)/sizeof(a[0]);
  kadane(a,n);
  return 0;
}

- shankhs October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Follow kadane's idea, this is my code.
This one dimensional DP problem has subproblem: Given maxsub[i], to generate largest subarray sum with at least two elements, we only consider: ``maxsub[i] + A[i]``. But to continue ``maxsub`` array, we consider both ``maxsub[i]+A[i]`` and ``A[i]``.

pair<int, int> maxSubArray(int A[], int n) {
	if (n <= 1) return pair<int, int>{-1, -1};
	int ret(INT_MIN), localmax(A[0]);
	int ed = 0;
	
	for (int i = 1; i < n; ++i) {
		if (ret < localmax + A[i]) {
			ret = localmax + A[i];
			ed = i;
		}
		localmax = max(localmax + A[i], A[i]);
	}

	int sum (A[ed]), st(ed);
	do {
		sum += A[--st];
	} while (sum != ret);

	return make_pair(st, ed);
}

Playable code at

ideone.com/WMT6uZ

- XiaoPiGu December 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class Subarray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr={-1,1,10,-6,-10};
		//int[] arr={-1,-2,-5,-4,-9};
		
		int max=0,prev_max=0;
		int check_mark = arr[0]+arr[1];
		boolean  in_negate=false;
		int start_index=0,end_index=0;
		int best_score=0, arr_score=0;
		for(int p=0;p<arr.length;p++){
			best_score+=arr[p];
		}
		
		ArrayList output_arr=new ArrayList();
		ArrayList temp_arr=new ArrayList();
		
       for(int i=0;i<arr.length-1;i++){
    	   max+=arr[i];
    	   temp_arr.add(arr[i]);
    	   for(int j=i+1;j<arr.length;j++){
    		   prev_max=max;
    		   max+=arr[j];
    		   if(j!=i+1){
    			   if(max>prev_max && max>=best_score){     					
	    				if(in_negate){
	    					for(int t=start_index;t<end_index+1;t++){
	    	    				   temp_arr.add(arr[t]);
	    	    			   }
	    					if(end_index!=j){
	    					temp_arr.add(arr[j]);
	    					}
	    					start_index=0;
	    					end_index=0;
	    					in_negate=false;
	    				}
	    				else{
	    					temp_arr.add(arr[j]);
	    				}
	    		   }
    			   else{
    				   if(start_index==0 &&end_index==0){
	    					start_index=j;
	    					if(arr.length-1==j){
	    					end_index=j;
	    					}
	    					else
	    					{
	    						end_index=j+1;
	    					}
	    					in_negate=true;
	    				}
	    				else
	    				{
	    					end_index=j;
	    				}
    			   }
    			   if(max>best_score){
    					best_score=max;
    			   }
    			   else if(prev_max>best_score){
    					best_score=prev_max;
    					in_negate=false;
    			   }
    		   }
    		   else{
    		   temp_arr.add(arr[j]);
    		   if(max>best_score){
					best_score=max;
			   }
			   else if(prev_max>best_score){
					best_score=prev_max;
					
			   }
    		   }
    	   }
    	   for(int k=0;k<temp_arr.size();k++){
    		   arr_score+=(Integer)(temp_arr.get(k));
    	   }
    	  if((check_mark<=arr_score)){
    		   output_arr=(ArrayList) temp_arr.clone();
    		   check_mark=best_score;
    	   }
    	   temp_arr.clear();
    	   max=0;
    	   prev_max=0;
    	   arr_score=0;
    	   in_negate=false;
    	   start_index=0;
    	   end_index=0;
       }
       System.out.print("\n\n\n " +output_arr);
	}

}

- sam.guest947 February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Works for input {-1,-1,-10,-6,-10}
output : {-1,-1}.

Please comment if the code fails for any input.

- sam.guest947 February 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is based on Kadane's algo. Please correct me if I am wrong anywhere.

public class LengthOfMaxSumArray {
	public static int[] getMaxSumArray(int array[]) {
		int max_ending_here = 0;
		int max_so_far = 0;
		int max_start_index = 0;
		int max_end_index = 0;
		for(int i=0; i<array.length; i++) {
			max_ending_here = max_ending_here + array[i];
			if(max_ending_here < 0) {
				max_ending_here = 0;
				max_start_index = i+1;
			}
			if(max_so_far < max_ending_here) {
				max_so_far = max_ending_here;
				max_end_index = i;
			}
		}
		int res[] = new int[max_end_index - max_start_index+1];
		int j=0;
		for(int i=max_start_index; i<= max_end_index; i++) {
			res[j] = array[i];
			j++;
		}
		return res;
	}
	public static void main(String args[]) {
		int array[] = {7,4,-2,5,3,-6,8,-8};
		int res[] =getMaxSumArray(array);
		for(int i=0; i<res.length; i++) {
			System.out.println(res[i]);
		}
	}
}

- Anirudh February 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
public:
int maxSubArray(int A[], int n) {
int B[n]={0};

B[0]=A[0];//>0?A[0]:0;
int max=B[0];
for(int i=1;i<n;i++)
{
if(B[i-1]<0)
B[i]=A[i];
else
B[i]=B[i-1]+A[i];

if(B[i]>max)
max=B[i];
}
return max;

}
};

- Anonymous March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int check_all_positive(int input[],int size){
	for(int i=0; i<size;i++){
		if (input[i]<0)
			return 0;
	}	
	return 1;
}
int check_all_negative(int input[],int size){
	for(int i=0;i<size;i++){
		if(input[i]>0)
			return 0;
	}
	return 1;
}
int sum_array_positive(int input[],int size){
	int sum=0;
	for(int i=0; i<size; i++){
		sum=sum+input[i];
	}
	return sum;
}
int sum_array_negative(int input[],int size){
	int sum=input[0];
	for(int i=1;i<size;i++){
		if(input[i]>sum)
			sum=input[i];
	}

	return sum;
}
int Find_max_sum(int input[],int size){
	int length=2,maximum=0,start_pos=0,temp_sum=0;
	while(length<=size){
		start_pos=0;
		while(start_pos<=(size-length)){
			temp_sum=0;
			for(int i=start_pos;i<(start_pos+length);i++){
				temp_sum=temp_sum+input[i];
			}
			if(temp_sum>maximum)
				maximum=temp_sum;
			start_pos=start_pos+1;
		}		
		length=length+1;
	}
	return maximum;
}
int main(){
	int input[]={-2,-3,-7,-2,-7,-4,-1,11,-1,13};
	int size=sizeof(input)/sizeof(input[1]);
	if(check_all_positive(input,size)){
		printf("%d",sum_array_positive(input,size));
		return 0;
	}	
	if(check_all_negative(input,size)){
		printf("%d",sum_array_negative(input,size));
		return 0;
	}

	printf("%d",Find_max_sum(input,size));
}

- jha jha June 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Kandane's algo.

public class MaximumSubsequence {
	public static void main(String[] args) {
		maximum(new int[] { -2, -3, 4, -1, -2, 1, 5, -3 });
	}

	static void maximum(int a[]) {
		int max_ending_here = 0;
		int max_so_far = 0;
		int start = 0, end = 0;

		for (int i = 0; i < a.length; i++) {
			max_ending_here += a[i];
			if (max_ending_here < 0) {
				max_ending_here = 0;
				start = i + 1;
			}
			if (max_so_far < max_ending_here) {
				max_so_far = max_ending_here;
				end = i;
			}
		}
		if (end - start >= 2) {
			print(a, start, end);
		}
	}

	private static void print(int[] a, int start, int end) {
		while (start <= end) {
			System.out.print(a[start] + " ");
			start++;
		}
	}
}

- Solution September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are given {1,2,3,-7,1,1,2}, your code will end up with start=4, end=2.

- Belmen September 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not work for this case : {-1,-1,-10,6,-10}
the solution should be {-1, -1}

- Anonymous October 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public class MaxSubSequence {
	public static void main(String[] args) {
		//maximum(new int[] { -2, -3, 4, -1, -2, 1, 5, -3 });
		
		maximum(new int[] { 1,2,3,-7,1,1,2 });
	}

	static void maximum(int a[]) {
		int max_ending_here = 0;
		int max_so_far = 0;
		int start = 0, end = 0;
		int start_L =0;

		for (int i = 0; i < a.length; i++) {
			max_ending_here += a[i];
			if (max_ending_here < 0) {
				max_ending_here = 0;
				start = i + 1;
			}
			if (max_so_far < max_ending_here) {
				max_so_far = max_ending_here;
				start_L =start;
				end = i;
			}
		}
		if (end - start_L >= 2) {
			print(a, start_L, end);
		}
		else 
			System.out.println("sub array less than 2");
	}

	private static void print(int[] a, int start, int end) {
		while (start <= end) {
			System.out.print(a[start] + " ");
			start++;
		}
	}
}

- Anonymous November 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class LargestSumSubArray {

	public static void main(String[] args) {


		int [] a={1,2,-5,8,-7,2,11,-4};
		int max=a[0],maxt=max;
		int start=0,end=0;
		int maxtemp= a[0];
		for(int i=1; i< a.length; i++){
			maxt=max;
			maxtemp=Math.max(a[i],maxtemp+a[i]);
			max=Math.max(maxtemp, max);
			if(maxtemp<=a[i]){
				start=i;
			}
			if(max>maxt)
				end=i;
		}
		
		for(int j=start;j<=end;j++)
			System.out.print(a[j]+" ");
		System.out.println();
		System.out.println(max);

	}

}

- manoj October 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>

using namespace std;
int largest_sum_array(int* arr,int len)
{
	int i,max_so_far=arr[0],current_sum=arr[0];
	for(i=1;i<len;i++)
	{
		current_sum=max(current_sum+arr[i],arr[i]);
		max_so_far=max(current_sum,max_so_far);

	}
	return max_so_far;
}
int main()
{
	int a[]={-1,-2,4,5};
	cout<<largest_sum_array(a,4);

}

- Anonymous October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not vanilla kadane. Check case: {-1,-2,1000,-1}. Your algorithm returns 1000. But the questions states that the min number of elements in the resulting subarray must be at least 2. In this case, you should return 1000 + (-1) = 999.

- XiaoPiGu December 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use Kandane's algorithm with another extra check of length of the sub Array

- Mahmud September 20, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More