Walmart Labs Interview Question
Java DevelopersCountry: 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)}