Country: India
Interview Type: In-Person

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

can be achieved with a sliding window approach. Slide the window of size 3 by 1 every iteration and calculate the max and store it in the results array. Max calculator checks the last 2 max's for adjacents.

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

results array can get updated for the last 2 entry in each iteration

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

you algorithm makes no sense and I don't see how it can work. How would it find the 5 and 6 for a max value of 11 as in the example above

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

public static void printMaxSum(int[] n){
if(n.length==0)
System.out.println("array has no data");
else if (n.length==1){
System.out.println(n[0]);
System.out.println(n[0]);
}else if (n.length==2){
System.out.println(n[0] + n[1]);
System.out.println(n[0] + " " + n[1]);
}else{
int v1 = (n[0]>n[1])?n[0]:n[1];
int v2 = (n[0]>n[1])?n[1]:n[0];
for(int i=2; i<n.length;i++){
if(n[i]>v1){
v2=v1;
v1=n[i];
}else if(n[i]<v1 && n[i]>v2){
v2=n[i];
}
}
System.out.println(v1 + v2);
System.out.println(v2 + " " + v1);
}
}

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

public static void printMaxSum(int[] n){
if(n.length==0)
System.out.println("array has no data");
else if (n.length==1){
System.out.println(n[0]);
System.out.println(n[0]);
}else if (n.length==2){
System.out.println(n[0] + n[1]);
System.out.println(n[0] + " " + n[1]);
}else{
int v1 = (n[0]>n[1])?n[0]:n[1];
int v2 = (n[0]>n[1])?n[1]:n[0];
for(int i=2; i<n.length;i++){
if(n[i]>v1){
v2=v1;
v1=n[i];
}else if(n[i]<v1 && n[i]>v2){
v2=n[i];
}
}
System.out.println(v1 + v2);
System.out.println(v2 + " " + v1);
}

}

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

procedure MaxSum(d; Profit[1...n])
L = array size n + d filled with 0. //Padded d extra element to avoid bound issues
for i 2 n::1 do
in  = Profit[i] + L[i + d]
out  = Profit[i + 1]
L[i] = max(in; out)
end for
return L[0]
end procedure

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

This is the Dynamic Programming approach if I am not mistaken. It looks like this is coming from this Back Tracking approach (int C++ since nobody like psuedo code)

The basic idea is to see what's the best you can do including the current element and compare that with what's the best you can do without including it

void MaxSum(int size,  int arr[])
{
if(size<=0)
return 0;
if(size==1)
return arr[0];
if(size==2)
return MAX(arr[0],arr[1]);

//include the first element recurse on everything after skipping adjacent
int in=arr[0]+MaxSum(size-2, &arr[2]);

//skip the first one and recurse on everything after it
int out=MaxSum(size-1, &arr[1]);
return MAX(in, out);
}

Now this is NOT the solution the interviewer is looking for but your solution follows from it. The idea is that we store the solution to recursive sub-problems in the results array and thus can look them up instead of recomputing them every time...though I do like your handy trick of padding the array to not have to deal with the base cases like in my recursive solution.

Now to get the actual indexes, just save them as a linked list in as you are calculating the subproblems.

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

import java.util.ArrayList;

public class MaxSumVal {

public static void main(String[] args) {
Integer[] noArray = {-1,4,5,-2,-6,6};
//Integer[] noArray = {1,0,5,25,-1,4,5,-2,-6,6};
//Integer[] noArray = {-1,-9,-5,0,1,10,-3,5,12,-34};
//Integer[] noArray = {-1};
//Integer[] noArray = {-1,9};
Integer noArrayLen = noArray.length;
Integer finalSum = 0;
ArrayList<Integer> sumValues = new ArrayList<Integer>();
Integer tempVal = 0;

if(noArrayLen == 1){
//If the number of the values is equal to 1 then the value itself will be the highest
finalSum = noArray[0];
}else if(noArrayLen == 2){
//If the number of the values is equal to 2 then choose the greater value
finalSum = (noArray[0] > noArray[1]) ? noArray[0] : noArray[1];
}else if(noArrayLen >= 3){
//If the number of the values is equal >= 3 then do the following
for(Integer i=0; i<noArrayLen; i=i+2  ){
//resetting tempVal at the beginning of each loop
tempVal = 0;

if(i-1 > 0 && noArray[i-1] < noArray[i]){

if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
tempVal = noArray[i];
//we need to check for adjacency only when we select value at i
//if adjacency was set then we'll replace the previously set values
//to the current value and subtract that value from te finalSum
if(sumValues.size() > 0){
finalSum -= sumValues.get(sumValues.size() - 1);
sumValues.set(sumValues.size() - 1, tempVal);
}
}else{
}
finalSum +=tempVal;
}else{
//An adjacency is always set if an i+1 values is selected
tempVal = noArray[i+1];
//we set the iPlusOneAdjacency value to i+2 as the next loop has the value = i+2
finalSum += tempVal;
}

}else{

if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
if(i-1 >0){
tempVal = noArray[i-1];
finalSum += tempVal;
}else{
}
}else{
tempVal = noArray[i];
finalSum += tempVal;
}
}else{
tempVal = noArray[i+1];
finalSum += tempVal;
}

}
}
}

System.out.println(finalSum);
System.out.println(sumValues);
}

}

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

I dont know where the semicolon came from in if(i-1 >;0){}, its not in my actual code but still comes up

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

I noticed that you included negative numbers in your sum. You don't want to do that. Also, I was trying to follow along your code with the below test case and got { 8 11 } = 19 when the max sum = { 4 7 11 } = 22.

{ -1, 4, 8, 7, 1, 3, 11, -1, -1, -1 }

In general I don't think that anyone's greedy algorithm will work because finding the best path requires forward probing an arbitrary distance down the array. I don't think going backwards works for the same reason. I've been foiling myself with test cases like this one that require looking ahead several steps to avoid getting trapped.

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

I wrote the approach below : it works well with this case as well

{ -1, 4, 8, 7, 1, 3, 11, -1, -1, -1 }
|	{0}
|		{0}
|			{0}
|				{11 + 0}
|				{3 + 0}
|					{1 + 11 + 0}
|					{7 + 11 + 0}
|						{8 + 1 + 11 + 0}
|						{4 + 7 + 11 + 0}
|							{greater of next two postive number, if second is negative take only of the first}
= {4 + 7 + 11 + 0} = 22

Let me know if there is any issue.

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

@John42, just making things clear, what if all the numbers are negative, just choose the one closest to zero?

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

@jack - yes, if all negative, closest to zero.
@Bharat - I'll take a closer look at your solution; I think I followed it incorrectly the first time.
@Everyone - Sorry, I should never say "can't be done" -- especially in an interview!

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

Think of this as a graph problem.
example: -1, 5, -2, 0

1. Make a graph with nodes equal to number of elements in the array.
2. Connect the edges in this way: -1 can connect to -2 and 0 so there will be a outgoing two outgoing edges to -2 and 0.
Same goes with other nodes i.e. 5 node will be connected to 0 using only one outgoing edge.
3. Once you have the graph ready then nodes values will be equal edge weights.
4. for_each_node {
target = 0 (end of array element)
start = current_node
longest_path = max(longest_path, find_longest_path(graph))
}
return longest_path

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

This idea is perfect.

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

here is a c++ code
but i don't know if it can be done in a simpler way

#include <iostream>

using namespace std;

int main()
{
int i,n,*a,sum=0,pospre=0,j,k,sum1,sum2,s=0;
cin>>n;
a=new int[n];
for(i=0;i<n;i++)
cin>>a[i];
i=0;
while(i<n)
{
if(a[i]>0)//is this a positive integer?
{
if(pospre==0)//found the first positive number
pospre=1;
j=i;//trying to find a continuous subarray with no negative ints
while(j<n&&a[j]>0)//is the end due to array end or due to occurrence of -ve num
{
j++;
}
j--;
if(i==j)
{
a[s]=a[i];
s++;
sum=sum+a[i];
}
else{
k=i;
sum1=0;
sum2=0;
while(k<=j)
{
sum1+=a[k];
k++;
if(k<=j)
{
sum2+=a[k];
k++;
}
}
if(sum1>=sum2)//see which sum is greater add that sum and print the numbers contributing
{
sum+=sum1;
for(k=i;k<=j;k+=2)
{
a[s++]=a[k];
}
}
else
{
sum+=sum2;
for(k=(i+1);k<=j;k+=2)
{
a[s++]=a[k];
}
}
}
i=j;
}
i++;
}
if(pospre==1)
{
cout<<sum<<endl;
for(i=0;i<s;i++)
{
cout<<a[i]<<" ";
}
}
else{
k=a[0];
for(i=0;i<n;i++)
{
if(a[i]>k)
k=a[i];
}
cout<<k<<endl;
}

return 0;
}

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

3 5 3 6 3 2 5 6
|		{6}
|		{5}
|			{2 + 6}
|			{3 + 6}
|				{6 + 2 + 6}
|				{3 + 3 + 6}
|					{5 + 6 + 2 + 6} = 19
|					{3 + 6 + 2 + 6} = 17

* This starts from last to first
* For an element at i check only sum with i + 2, i + 3 (which ever is bigger)
* For a negative number remember the index of last biggest sum, and redirect to that element if queried
* If first number is non-positive it will have biggest sum (index to refer)
* If first number is positive and second is non-positive than first number has biggest sum
* If first and second both are positive biggest sum = max { first sequence sum, second sequence sum}
* Also keep a variable for lowest non-positive number found if first number is non-positive and has biggest sum still 0 or set nothing then print this lowest non-positive number

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

num =[2,3, -4, 1, 2, 5, 4, -3, 3, 5, 6, 2, 8, 8, 9, 9, -2, 5, 7, 7, 4,];

#This is a graph problem.
# sort the indices of the numbers and take only the ones  > 0.
# pick each item for the summation for adding to the 'sumbag'. If the there is conflict
# due to prexisting adjacent recursively call sum with and wthout the conflicting item in the
# sumbag.  In the end compare the sums and pick the sumbag with the largest sum.

def sum(num , sortidx, sumbag, skipbag, start,  l):
tot1 = 0;
ary1 = [];
tot2 = 0;
ary2 = [];
for x in range(start, l):
if sortidx[x]-1 in sumbag  and  not sortidx[x]-1 in skipbag and not x-1 < 0:
ary1 = sumbag[:];
skp1 = skipbag[:];
ary1.remove(sortidx[x]-1);
skp1.append(sortidx[x]-1)
tot1, ary1 =  sum(num, sortidx, ary1, skp1, x, l);
elif sortidx[x]+1 in sumbag and  not sortidx[x]+1 in skipbag and not x+1 >= l:
ary2 = sumbag[:];
skp2 = skipbag[:];
ary2.remove(sortidx[x]+1);
skp2.append(sortidx[x]+1)
tot2, ary2 =  sum(num, sortidx, ary2, skp2, x, l);
elif not sortidx[x] in skipbag:
sumbag.append(sortidx[x])

tot = 0;
for x in sumbag:
tot = tot + num[x];

if tot < tot1 :
tot = tot1;
sumbag = ary1;

if tot < tot2 :
tot = tot2;
sumbag = ary2;

#---------------------------------------------------------------------------

#sort the indices of the numbers and get only the ones greter than 0
sortedindex = [i[0] for i in reversed(sorted(enumerate(num), key=lambda x:x[1]))  if num[i[0]] > 0];
sumb = [];
skipb = [];
l = len(sortedindex);
total , sumb =  sum(num , sortedindex, sumb, skipb, 0, l);

print total ;
print sumb;

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

Here is the idea,
1. only interested on positive number,so negative numbers splits the whole array to multiple sub arrays which contains only positive number,
2. for each sub array, i.e. a(0), ..,a(n-1), use slide window (size=3) to get best pick. For current item, sum(j) = max( sum(j-2)+a(j), sum(j-3)+a(j)),
at the end, the result is max( sum(n-1), sum(n-2));
3. Now how to get contributed number? Reconsider the method in step 2, we should scan it in reverse order, i.e. n-1 to 0, then the result is either sum(0) or sum(1), say, R,
i=0;
while (R!=0) {
if (R==sum(i)) { print a(i); R = R-a(i); i--; }
i++;
}

space: O(N) to store sum for each positive number
time: O(N)

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

For last part, it should be

i=0;
while (R!=0) {
if (R==sum(i)) { print a(i); R = R-a(i); i++/*skip next one*/; }
i++;
}

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

This is a DP solution to the problem

public class MaxSumMain {

public static int maxSum(int array[]) {
int sumArray[] = new int[array.length];
sumArray[0] = array[0];
sumArray[1] = array[1];
for(int i=2;i<array.length;i++) {
int tempArray[] = {sumArray[i-2],sumArray[i-1],array[i],sumArray[i-2]+array[i]};
sumArray[i] = max(tempArray);
}
return sumArray[sumArray.length-1];
}
/**
* @param tempArray
* @return
*/
private static int max(int[] tempArray) {
int maxElement = tempArray[0];
for(int i=1;i<tempArray.length ;i++){
if(tempArray[i] > maxElement)
maxElement = tempArray[i];
}
return maxElement;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = {-1,4,5,-2,-6,6};
//int array[] = {-1,-4,-5,-2,-6,-6};
System.out.println(maxSum(array));
}

}

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

This is basically finding two max numbers from Array.

int a[ARR_SIZE];
int max1=-1,max2=-1;
for(int i=0;i<ARR_SIZE;i++)
{
if(a[i]>max1 || a[i]>max2)
{

max1=a[i];
if(a[i]> max2)
{
max1=max2;
max2=a[i];
}

}

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

Why don't e just split the Array wherever we find a -ve number and just use backtracking on the splited arrays to get their respective highest sum then combine the result.
Reason :1. we don't have to take -ve numbers in our ans anyways (omitting -ve number)

2. -ve numbers will give you freedom to chose any pattern in the next array since present array and next one will have always one element in between (-ve number we omitted) .

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

Why don't e just split the Array wherever we find a -ve number and just use backtracking on the splited arrays to get their respective highest sum then combine the result.
Reason :1. we don't have to take -ve numbers in our ans anyways (omitting -ve number)

2. -ve numbers will give you freedom to chose any pattern in the next array since present array and next one will have always one element in between (-ve number we omitted) .

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

public class CalcilateMaxSum {

public static void main(String[] args) {

int[] a= {-1,9,-5,-6};
System.out.println("Sum is::"+maxsum(a,0,0,0,Integer.MIN_VALUE));

}

public static int maxsum(int[] a,int sum,int k,int count,int min)
{
int sum1 =Integer.MIN_VALUE;
int sum2=0;
if(k>=a.length)
{
if(count==a.length)
return min;
return sum;
}

if(a[k]>0&&(k+1<a.length)&&a[k]<a[k+1])
{
sum1= maxsum(a,a[k+1],k+2,count,min);
System.out.print(k+1);
}
else if(a[k]>0)
{
sum1= maxsum(a, sum+a[k] , k+2,count,min) ;
System.out.print(k);
}
else
{
count = count+1;
if(min<a[k])
{min = a[k];}
sum2= maxsum(a,sum,k+1,count,min);

}
return Math.max(sum1, sum2);
}

}

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

public class CalcilateMaxSum {
public static void main(String[] args) {
int[] a= {-1,9,-5,-6};
System.out.println("Sum is::"+maxsum(a,0,0,0,Integer.MIN_VALUE));
}
public static int maxsum(int[] a,int sum,int k,int count,int min)
{
int sum1 =Integer.MIN_VALUE;
int sum2=0;
if(k>=a.length)
{
if(count==a.length)
return min;
return sum;
}

if(a[k]>0&&(k+1<a.length)&&a[k]<a[k+1])
{
sum1= maxsum(a,a[k+1],k+2,count,min);
System.out.print(k+1);
}
else if(a[k]>0)
{
sum1= maxsum(a, sum+a[k] , k+2,count,min) ;
System.out.print(k);
}
else
{
count = count+1;
if(min<a[k])
{min = a[k];}
sum2= maxsum(a,sum,k+1,count,min);
}
return Math.max(sum1, sum2);
}}

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

public static int MAX = -10;
// choose a reasonable value, should be lower than the min value in the given array

public static void main(String args[])
{
int[] arr = {-1, 4, 5, -2, -6, 6};

System.out.println(findMaxSum(arr, 0, arrLst));
for(Integer i: arrLst)
System.out.print(i+" ");

}

public static int findMaxSum(int[] arr, int index, LinkedList<Integer> arrLst)
{
if(index >=arr.length)
return MAX;
if(index == arr.length-1 || index == arr.length-2)
{
return arr[index];

}

int a = findMaxSum(arr, index+2, arrLst2);
int b = findMaxSum(arr, index+3, arrLst3);

int max =arr[index];

if(a > max)
{
modifyList(arrLst, arrLst2);
max = a;
}
if(b > max)
{
modifyList(arrLst, arrLst3);
//arrLst=(arrLst3);
max = b;
}
if(arr[index]+a > max)
{
modifyList(arrLst, arrLst2);

max = arr[index]+a;
}
if(arr[index]+b > max)
{
modifyList(arrLst, arrLst3);
max = arr[index]+b;
}

return max;
}

{
orig.clear();

for(Integer i : newll)
}

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.