## Walmart Labs Interview Question

Java Developers**Country:**India

**Interview Type:**Written Test

```
public class DiamondCollectionPuzzle {
private static int[] input= {1, 2, 3, 4, 5, 6, 7};
public static void main(String[] args) {
PosssibleDiamondCount possibleDiamonds = collectDiamonds(0);
System.out.println(Math.max(possibleDiamonds.maxExcludingCurrent, possibleDiamonds.maxIncludingCurrent));
}
private static PosssibleDiamondCount collectDiamonds(int startIndex) {
if(startIndex == input.length-1){
PosssibleDiamondCount possibleDiamondCount = new PosssibleDiamondCount();
possibleDiamondCount.maxIncludingCurrent = input[startIndex];
possibleDiamondCount.maxExcludingCurrent = 0;
return possibleDiamondCount;
}else{
PosssibleDiamondCount nextPossibleDiamondCount = collectDiamonds(startIndex + 1);
PosssibleDiamondCount currPossibleDiamondCount = new PosssibleDiamondCount();
currPossibleDiamondCount.maxIncludingCurrent = input[startIndex] + nextPossibleDiamondCount.maxExcludingCurrent;
currPossibleDiamondCount.maxExcludingCurrent = nextPossibleDiamondCount.maxIncludingCurrent;
return currPossibleDiamondCount;
}
}
/**
* Data structure to hold possible diamonds including current and excluding current
*/
private static class PosssibleDiamondCount{
int maxIncludingCurrent;
int maxExcludingCurrent;
}
}
```

```
public class DiamondCollectionPuzzle {
private static int[] input= {1, 2, 3, 4, 5, 6, 7};
public static void main(String[] args) {
PosssibleDiamondCount possibleDiamonds = collectDiamonds(0);
System.out.println(Math.max(possibleDiamonds.maxExcludingCurrent, possibleDiamonds.maxIncludingCurrent));
}
private static PosssibleDiamondCount collectDiamonds(int startIndex) {
if(startIndex == input.length-1){
PosssibleDiamondCount possibleDiamondCount = new PosssibleDiamondCount();
possibleDiamondCount.maxIncludingCurrent = input[startIndex];
possibleDiamondCount.maxExcludingCurrent = 0;
return possibleDiamondCount;
}else{
PosssibleDiamondCount nextPossibleDiamondCount = collectDiamonds(startIndex + 1);
PosssibleDiamondCount currPossibleDiamondCount = new PosssibleDiamondCount();
currPossibleDiamondCount.maxIncludingCurrent = input[startIndex] + nextPossibleDiamondCount.maxExcludingCurrent;
currPossibleDiamondCount.maxExcludingCurrent = nextPossibleDiamondCount.maxIncludingCurrent;
return currPossibleDiamondCount;
}
}
/**
* Data structure to hold possible diamonds including current and excluding current
*/
private static class PosssibleDiamondCount{
int maxIncludingCurrent;
int maxExcludingCurrent;
}
}
```

import java.util.Scanner;

class MaxProblem

{

public static void main(String[] args)

{

Scanner scn=new Scanner(System.in);

int n=scn.nextInt();

int arr[] =new int[n];

for(int i=0;i<n;i++)

arr[i]=scn.nextInt();

System.out.println( FindMaxSum(arr, n));

}

public static int FindMaxSum(int arr[], int n)

{

int incl = arr[0];

int excl = 0;

int excl_new;

for (int i = 1; i < n; i++)

{

excl_new = (incl > excl)? incl: excl;

incl = excl + arr[i];

excl = excl_new;

}

return ((incl > excl)? incl : excl);

}

}

import java.util.Scanner;

class MaxProblem

{

public static void main(String[] args)

{

Scanner scn=new Scanner(System.in);

int n=scn.nextInt();

int arr[] =new int[n];

for(int i=0;i<n;i++)

arr[i]=scn.nextInt();

System.out.println( FindMaxSum(arr, n));

}

public static int FindMaxSum(int arr[], int n)

{

int incl = arr[0];

int excl = 0;

int excl_new;

for (int i = 1; i < n; i++)

{

excl_new = (incl > excl)? incl: excl;

incl = excl + arr[i];

excl = excl_new;

}

return ((incl > excl)? incl : excl);

}

}

```
public class MyClass {
public static void main(String args[]) {
int n[]=new int[]{5, 5, 10, 100, 10, 5};
System.out.println(helper(n));
}
public static int helper(int[]n)
{
int dp[]=new int[n.length];
if(n.length==1)
{
return n[n.length-1];
}
if(n.length==2)
{
return n[n.length-2];
}
if(n.length==3)
{
return Math.max(n[n.length-3]+n[n.length-1],n[n.length-2]);
}
dp[n.length-1]=n[n.length-1];
dp[n.length-2]=n[n.length-2];
dp[n.length-3]=n[n.length-3]+n[n.length-1];
for(int i=n.length-4;i>=0;i--)
{
dp[i]=n[i]+Math.max(dp[i+2],dp[i+3]);
}
int result=0;
for(int i=0;i<dp.length;i++)
{
result=Math.max(dp[i],result);
}
return result;
}
}
```

Typical DP problem, developing a mathematical equation should solve

- Anonymous July 28, 2016Assume all the diamonds are in array, arr[] whose size is N

Maximum he can collect with N dragons is

MaxDiam(N)= Math.max{ arr[N-1] + MaxDiam(N-2), MaxDiam(N-1)}