Marketshare Inc. Interview Question
Java DevelopersCountry: United States
Interview Type: In-Person
This is my interpretation of the problem. Suppose pizza has 1 2 3 4 5 6 where n=2. If you eat piece 6, then you have to immediately discard its 2 neighbors and so the pizza now becomes 2 3 4, so you would pick piece 4 in the 2nd iteration, resulting in 10 total. But if you were to eat piece 5 originally, you would end up with 1 2 3, at which point you would pick 3, resulting in 8 total.
I re-read the problem statement again. It says "every time we eat and discard there are new neighbors being formed per piece. "So I am no sure if my interpretation in previous comment is correct, because not all pieces will have new neighbors each time we eat according to my understanding.
I could only come up with the straightforward approach. Basically try eating each slice, marking itself and its two neighbors unavailable, and then compute its volume plus the maximum volume you get from making the recursive call.
class EatPizza {
static int maxVolume(int[] arr) {
boolean[] available = new boolean[arr.length];
for(int i=0; i<available.length; i++)
available[i] = true;
return maxVolumeHelper(arr, available, 0);
}
static int maxVolumeHelper(int[] vol, boolean[] available, int n) {
int len = vol.length;
if(n == len/3)
return 0;
int max = 0;
for(int i=0; i<len; i++) {
if(available[i]) {
int right = i+1;
while(!available[right%len]) {
right++;
}
int left = i-1;
while(!available[(left+len)%len]) {
left--;
}
available[i] = false;
available[(left+len)%len] = false;
available[right%len] = false;
int volume = vol[i] + maxVolumeHelper(vol, available, n+1);
max = Math.max(max, volume);
available[i] = true;
available[(left+len)%len] = true;
available[right%len] = true;
}
}
return max;
}
public static void main(String[] args) {
int[] arr = new int[args.length];
for(int i=0; i<args.length; i++)
arr[i] = Integer.parseInt(args[i]);
System.out.println(maxVolume(arr));
}
}
In this case, the time complexity is almost (n!) which is too large. For example, when n is greater than 12, your solution cannot give the answer within a few seconds. If n is 100, we can never get the result. I hope someone can come up with a better solution.
@Eugene.Yarovoi
Please ask me where you are not clear. I am also taking a stab at it using DP.
It seems that greedy algorithm can solve this problem, at least the three examples. Can anyone give me an example where greedy algorithm doesn't work?
The example 9 10 9 7 1 1 is not solvable by a greedy algorithm.
Greedy algorithm will choose 10, then 7, then 1, which adds up to 18. However, a better choice is to choose 9, 9, and 1, which adds up to 19.
The example is good but if my interpretation of this "3n pieces" problem is correct, then with the greedy approach you would first pick 10, which makes the 2 adjacent 9s disappear. The array is now 7 11, so you would pick 7 and now the array is empty. So total is 17.
If you first pick the 9 in front, the array will now be 9 7 1, so you would again pick 9, so the total in this case is 18.
Here is my killer solution that uses a greedy strategy. Several iterations are used, where a greedy strategy is applied in each iteration to find local maximum and then a global maximum is computed among the local iterations.
package com.marketshare.interviews;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
* @author Murali Mohan
*
*/
class PizzaPiece {
int size, index;
PizzaPiece(int size, int index) {
this.size = size;
this.index = index;
}
}
public class PizzaPieces {
public static void main(String[] args) {
List<PizzaPiece> pieces = new ArrayList<PizzaPiece>();
List<PizzaPiece> selectedPieces = new ArrayList<PizzaPiece>();
int localMax = 0, globalMax = 0;
System.out.println("Input 3n pizza sizes separated by space. Enter twice to start execution");
Scanner scanner = new Scanner(System.in);
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
int piecesNumber = 0;
while (scanner.hasNextInt()) {
PizzaPiece piece = new PizzaPiece(scanner.nextInt(), piecesNumber++);
pieces.add(piece);
} ;
if (piecesNumber % 3 != 0) {
throw new RuntimeException("# of pizza pieces is not a multiple of 3");
}
// Sort the arrayList
Collections.sort(pieces, new Comparator<PizzaPiece>() {
public int compare(PizzaPiece piece1, PizzaPiece piece2) {
return piece2.size - piece1.size;
}
});
for (int i = 0; i < piecesNumber / 3; i++) {
PizzaPiece firstPiece = pieces.get(i);
List<PizzaPiece> chosenPieces = new ArrayList<PizzaPiece>();
chosenPieces.add(firstPiece);
localMax = firstPiece.size;
int chosenPiecesount = 1;
for (int j = i + 1; j < piecesNumber; j++) {
PizzaPiece currPiece = pieces.get(j);
boolean canBeAdded = true;
// This for-loop should be a binary search tree to make the
// search and hence the solution more efficient
for (int k = 0; k < chosenPieces.size(); k++) {
PizzaPiece chosenPiece = chosenPieces.get(k);
if (((currPiece.index + 1) % piecesNumber == chosenPiece.index)
|| ((currPiece.index - 1 + piecesNumber) % piecesNumber == chosenPiece.index)) {
canBeAdded = false;
break;
}
}
if (canBeAdded) {
chosenPieces.add(currPiece);
localMax += currPiece.size;
chosenPiecesount++;
if (chosenPiecesount == piecesNumber/3) {
break;
}
}
}
if (localMax > globalMax) {
globalMax = localMax;
selectedPieces.clear();
selectedPieces.addAll(chosenPieces);
}
}
System.out.println("The maximum size that can be chosen is: " + globalMax);
System.out.println("Pieces' (size, position) are:");
for (PizzaPiece piece: selectedPieces) {
System.out.print("(" + piece.size + "," + (piece.index + 1) + ") ");
}
}
}
Here's a counter-example:
0 9 8 0 0 5 7 6 0 0 4 0
The greedy approach will pick 9 7 4 0 = 20 whereas the optimal answer should be 9 6 5 4 = 24
@Sunny.
Good one.Killer solution is not working lol. DP is the way to go. Thanks for the counter example.
I wonder if DP can get the job done. I tried a recursive brute-force with memoization of subproblems. The numbers of subproblems are varying at each level...not sure how that can be captured using DP. The total number of subproblems that need be searched for an input of size 3n using brute-force is n!*3^n .However using memoization, that number can be reduced as the following examples illustrate.
Input(Size 36):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0
Output:
Time taken in secs=284
Maxsize = 72
No. of subproblems of size(3): 936
No. of subproblems of size(6): 18018
No. of subproblems of size(9): 97240
No. of subproblems of size(12): 226746
No. of subproblems of size(15): 279072
No. of subproblems of size(18): 201894
No. of subproblems of size(21): 91080
No. of subproblems of size(24): 26325
No. of subproblems of size(27): 4872
No. of subproblems of size(30): 558
No. of subproblems of size(33): 36
No. of subproblems of size(36): 1
Input(Size 39):
0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8 0 0 5 7 6 0 0 4 0 0 9 8
Output:
Time taken in secs=1149
Maxsize = 81
No. of subproblems of size(3): 1183
No. of subproblems of size(6): 28392
No. of subproblems of size(9): 189618
No. of subproblems of size(12): 545870
No. of subproblems of size(15): 831402
No. of subproblems of size(18): 749892
No. of subproblems of size(21): 427570
No. of subproblems of size(24): 159705
No. of subproblems of size(27): 39585
No. of subproblems of size(30): 6448
No. of subproblems of size(33): 663
No. of subproblems of size(36): 39
No. of subproblems of size(39): 1
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.regex.Pattern;
/**
* @author Murali Mohan
*
*/
class PizzaPiece {
int size, index, leftNeighbor, rightNeighbor;
boolean isTaken = false;
PizzaPiece(int size, int index) {
this.size = size;
this.index = index;
}
}
public class PizzaPiecesDP {
static List<PizzaPiece> pieces = new ArrayList<PizzaPiece>();
static List<PizzaPiece> selectedPieces = new ArrayList<PizzaPiece>();
static Map<String, Integer>[] pieceSubsets;
public static String getKey(int chosenPizzaIndex, List<PizzaPiece> pizzaPieces) {
Collections.sort(pizzaPieces, new Comparator<PizzaPiece>() {
public int compare(PizzaPiece piece1, PizzaPiece piece2) {
return piece1.index - piece2.index;
}
});
StringBuffer key = new StringBuffer();
for (int i = 0; i < pizzaPieces.size(); i++) {
if (!pizzaPieces.get(i).isTaken) {
key.append(":" + pizzaPieces.get(i).index);
}
}
return key.toString();
}
public static int computeMaxSubset(List<PizzaPiece> pizzaPieces, int startIndex, int remSize) {
//System.out.println("Begin: startIndex=" + startIndex + " remSize=" + remSize);
int max = 0, maxIndex = -1;
String key = "";
Integer remOptSize;
if (remSize == 3) {
key = getKey(startIndex, pizzaPieces);
remOptSize = pieceSubsets[0].get(key);
if (remOptSize == null) {
if (!pizzaPieces.get(startIndex).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).isTaken && !pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).isTaken) {
max = Math.max(pizzaPieces.get(startIndex).size, Math.max(pizzaPieces.get(pizzaPieces.get(startIndex).leftNeighbor).size, pizzaPieces.get(pizzaPieces.get(startIndex).rightNeighbor).size));
pieceSubsets[0].put(key, max);
} else {
System.out.println("WARN: Something's wrong!");
}
} else {
max = remOptSize;
}
} else {
int i = startIndex;
for (int j = 0; j < remSize; j++) {
key = getKey(i, pizzaPieces);
remOptSize = pieceSubsets[((remSize - 3) / 3)].get(key);
if (remOptSize != null) {
max = remOptSize;
} else {
int previous = pizzaPieces.get(i).leftNeighbor;
int next = pizzaPieces.get(i).rightNeighbor;
pizzaPieces.get(previous).isTaken = true;
pizzaPieces.get(i).isTaken = true;
pizzaPieces.get(next).isTaken = true;
PizzaPiece secondLeft = pizzaPieces.get(pizzaPieces.get(previous).leftNeighbor);
PizzaPiece secondRight = pizzaPieces.get(pizzaPieces.get(next).rightNeighbor);
secondLeft.rightNeighbor = secondRight.index;
secondRight.leftNeighbor = secondLeft.index;
remOptSize = computeMaxSubset(pizzaPieces, secondRight.index, remSize - 3);
if (max < remOptSize + pizzaPieces.get(i).size) {
max = remOptSize + pizzaPieces.get(i).size;
maxIndex = i;
}
pizzaPieces.get(previous).isTaken = false;
pizzaPieces.get(i).isTaken = false;
pizzaPieces.get(next).isTaken = false;
secondLeft.rightNeighbor = previous;
secondRight.leftNeighbor = next;
}
i = pizzaPieces.get(i).rightNeighbor;
}
pieceSubsets[((remSize - 3) / 3)].put(key, max);
}
//System.out.println("End: startIndex=" + startIndex + " remSize=" + remSize + " max=" + max + " maxIndex = " + maxIndex + " size = " + ((maxIndex == -1) ? 3 : pizzaPieces.get(maxIndex).size) + " key = " + key + " keysize = " + key.split(":").length);
return max;
}
public static void main(String[] args) {
System.out.println("Input 3n pizza sizes separated by space. Enter twice to start execution");
Scanner scanner = new Scanner(System.in);
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
int piecesNumber = 0;
while (scanner.hasNextInt()) {
PizzaPiece piece = new PizzaPiece(scanner.nextInt(), piecesNumber++);
piece.rightNeighbor = 0;
if (piecesNumber > 1) {
piece.leftNeighbor = (piecesNumber - 2);
pieces.get(piecesNumber - 2).rightNeighbor = piecesNumber - 1;
}
pieces.add(piece);
} ;
pieces.get(0).leftNeighbor = pieces.size() - 1;
if (piecesNumber % 3 != 0) {
throw new RuntimeException("# of pizza pieces is not a multiple of 3");
}
pieceSubsets = new HashMap[piecesNumber / 3];
for (int i = 0; i < piecesNumber / 3; i++) {
pieceSubsets[i] = new HashMap<String, Integer>();
}
long startTime = System.currentTimeMillis();
int maxSize = computeMaxSubset(pieces, 0, pieces.size());
long elapsedTime = (System.currentTimeMillis() - startTime)/1000;
System.out.println("Time taken in secs=" + elapsedTime);
System.out.println("Maxsize = " + maxSize);
for (int i = 0; i < pieceSubsets.length; i++) {
System.out.println("No. of subproblems of size(" + ((i+1) * 3 ) + "): " + pieceSubsets[i].size() /*+ ", "+ pieceSubsets[i].toString() */);
}
}
}
Here is a simple solution using DP . Please comment if you are able to find any issue :)
package basic.carrerCup;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader.Array;
public class VolumePizzaSkipTwoAdjacentPiece {
public static void main(String args[]) {
int[] arr = { 0,9,8,0,0,5,7,6,0,0,4,0,0,9,8,0,0,5,7,6,0,0,4,0,0,9,,0,0,5,7,6,0,0,4,0};
int[] arr2 ={0,9,8,0,0,5,7,6,0,0,4,0,0,9,8,0,0,5,7,6,0,0,4,0,0,9,8,0,0,5,7,6,0,0,4,0,0,9,8};
int[] arr3 = { 0, 9, 8, 0, 0, 5, 7, 6, 0, 0, 4, 0 };
getMaxVolumeAndPath(arr2);
}
public static void getMaxVolumeAndPath(int[] arr) {
int[] sum = new int[arr.length];
int maxV = 0;
sum[0] = arr[0];
sum[1] = arr[1];
if (sum[1] > maxV)
maxV = sum[1];
for (int i = 2; i < arr.length; i++) {
sum[i] = (sum[i - 2] + arr[i]) > maxV ? (sum[i - 2] + arr[i]) : maxV;
maxV = sum[i];
}
System.out.println("Max volume is " + maxV);
//Back Traversal to find elements
ArrayList<Integer> nos = new ArrayList<Integer>();
int j= sum.length-1;
int temp = sum[j];
while(j>1)
{
while(sum[j] > temp || sum[j] == sum[j-1])
j--;
if(sum[j] == arr[j])
{
nos.add(arr[j--]);
}
else if(sum[j] == arr[j] + sum[j-2])
{
temp = sum[j-2];
nos.add(arr[j--]);
}
else
j--;
}
Collections.reverse(nos);
System.out.println("Array used is " + nos.toString());
}
}
Could you please explain the problem a little more, perhaps by giving the best strategy for the example given ?
- uuuouou May 31, 2014