2 Replies - 503 Views - Last Post: 14 January 2022 - 12:53 PM Rate Topic: -----

#1 lledo3   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 47
  • Joined: 28-February 11

Kaitenzushi (Facebook Puzzle Question) Java

Posted 10 January 2022 - 05:52 PM

Question:
There are N dishes in a row on a kaiten belt, with the ith dish being of type D_i. Some dishes may be of the same type as one another. You're very hungry, but you'd also like to keep things interesting. The N dishes will arrive in front of you, one after another in order, and for each one you'll eat it as long as it isn't the same type as any of the previous K dishes you've eaten. You eat very fast, so you can consume a dish before the next one gets to you. Any dishes you choose not to eat as they pass will be eaten by others. Determine how many dishes you'll end up eating.

Test Case 1:
N = 6
D = [1, 2, 3, 3, 2, 1]
K = 1
Expected Return Value = 5

Test Case 2:
N = 6
D = [1, 2, 3, 3, 2, 1]
K = 2
Expected Return Value = 4

Test Case 3:
N = 7
D = [1, 2, 1, 2, 1, 2, 1]
K = 2
Expected Return Value = 2

Sample Explanation
In the first case, the dishes have types of [1, 2, 3, 3, 2, 1], so you'll eat the first 3 dishes, skip the next one as it's another type-3 dish, and then eat the last 2.

In the second case, you won't eat a dish if it has the same type as either of the previous 2 dishes you've eaten. After eating the first, second, and third dishes, you'll skip the fourth and fifth dishes as they're the same type as the last 2 dishes that you've eaten. You'll then eat the last dish, consuming 4 dishes total.

In the third case, once you eat the first two dishes you won't eat any of the remaining dishes.

I have a working java solution for the test cases but I'm failing on the submitted cases. Can anyone see what I could possibly failing at?

public static int getMaximumEatenDishCount(int N, int[] D, int K){
        if(N == 0 || D.length == 0 || D.length != N)  return 0;
        int skip = 0;
        int count = 0;
        Map<Integer, Integer> eaten = new HashMap<>();
        for(int i = 0; i < D.length; i++){
            if(!eaten.containsKey(D[i])){
                eaten.put(D[i], 1);
            }else if(eaten.containsKey(D[i]) && skip < K){
                skip++;
                continue;
            }else{
                eaten.put(D[i], eaten.get(D[i]) + 1);
            }
        }
        if(eaten.size() <= 2){
            count = eaten.size();
        }else{
            count = eaten.values().stream().mapToInt(Integer::intValue).sum();
        }

        return count;
    }

This post has been edited by lledo3: 10 January 2022 - 05:54 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Kaitenzushi (Facebook Puzzle Question) Java

#2 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 872
  • View blog
  • Posts: 6,723
  • Joined: 25-December 13

Re: Kaitenzushi (Facebook Puzzle Question) Java

Posted 11 January 2022 - 04:44 AM

Can you post the console output that shows what you are talking about?

How can the code be compiled and executed for testing? Is there any input files for the program?
Was This Post Helpful? 0
  • +
  • -

#3 Piet Souris   User is offline

  • D.I.C Head

Reputation: 44
  • View blog
  • Posts: 207
  • Joined: 01-December 15

Re: Kaitenzushi (Facebook Puzzle Question) Java

Posted 14 January 2022 - 12:53 PM

Don't know if you found the problem yet, since a few days have gone.

The one problem with your code is in this line:
}else if(eaten.containsKey(D[i]) && skip < K){...

What has the variable 'skip' to do with 'K'? You should check whether the last K elements of 'eaten' contain the current meal. And a Map is not suited for that question.

For instance: if the array is {1, 2, 1} and K = 1, then when the second '1' is encountered, you execute the line I mentioned above, meaning that that '1' is skipped, resulting in a wrong output of 2.

Why not simply use a List<Integer> eaten, and add the current meal if that current meal is not contained in the last K elements of eaten (be careful here, though)?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1