Adobe Interview Question Applications Developers


Country: India
Interview Type: In-Person


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

int maxsum(int arr[], int arraylength, int & startIndex, int & endIndex )
{
	int maxsum = arr[0], sum = arr[0];
	startIndex = 0,endIndex = 0;
	int tempstIndex = 0, tempendIndex = 0;

	for(int index =1 ;index < arraylength;index++)
	{
		if(sum < 0)
		{
			sum = arr[index];
			tempstIndex = tempendIndex = index;
		}else{
			sum = sum + arr[index];
			tempendIndex = index;
		}

                if(maxsum < sum)
		{
			maxsum = sum;
			startIndex = tempstIndex;
			endIndex = tempendIndex;
		}
	}
	return maxsum;
}

- naveentiptur on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < inputList.Length - 1; i++)
{
int tempSum = inputList[i] ;
for (int j = i + 1; j < inputList.Length; j++)
{
tempSum += inputList[j];
if (tempSum > maxSum)
{
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}

- harish on May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maximum Sum Subarray Problem

- ravigupta on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Kadane's algorithm...

- Cantona on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getMax(int[] arr){
        int maxsum=0;
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            if(maxsum < sum)
                   maxsum=sum;
            else if(sum<0)
                sum=0;
        }
        return maxsum;
    }

Note:It will not work if array has all negative values.

- Kamal on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Incase the maxsum is negative, find the greatest number in the array which is nothing but the maximum sum.

- VMK on May 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

incase of all negative numbers, the maxsum will be negative. At that time, find the greatest number in the array which indicates the maximum sum.

- VMK on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Source code : Time complexity = O(n), Space complexity = O(1)

void find_max_sum(int *arr, int n, int *start, int *end, int *sum)
{
	int i, temp_sum, temp_start, temp_end; 

	*end = *start = temp_start = temp_end = -1;
	*sum = temp_sum = 0;

	for(i = 0; i < n; i++)
	{
		temp_sum += arr[i];

		if(temp_sum < 0)
		{
			temp_sum = 0;
			temp_start = temp_end = -1;
		}
		else if(temp_sum > 0)
		{
			if(temp_start == -1)
				temp_start = i;
			temp_end = i;
		}

		if(temp_sum > *sum)
		{
			*start = temp_start;
			*end = temp_end;
			*sum = temp_sum;
		}
	}
}

- Srikant Aggarwal on June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

double maxSubarray(double a[], int numElements)
{
double max=0;
double here=0;
int i;

for(i = 0; i < numElements; i++)
{
here = (here + a[i] > 0) ? here + a[i] : 0;
max = (here > max) ? here : max;
}
return max;
}

- vino on June 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its just Kadane's algo...Java implementation would go like this

public static void implementAlgo(int[] pArray) {
		int max_so_far = 0;
        int max_ending_here = 0;
        int maxStart=0;
        int maxEnd=0;
        int currentStart=0;
        for(int i=0;i<pArray.length;i++){
        	max_ending_here=max_ending_here+pArray[i];
        	if(max_ending_here<0){
        		max_ending_here=0;
        		currentStart=i+1;
        	}
        	if(max_so_far<max_ending_here){
        		max_so_far=max_ending_here;
        		maxStart=currentStart;
        		maxEnd=i;
        	}
        }
        System.out.println("Max="+max_so_far);
        System.out.println("Started from:"+maxStart);
        System.out.println("Ended at :"+maxEnd);
	}

- erd on June 27, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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