Kaitenzushi

Or check directly the Meta career page (an account is requiered)

Description from Meta

There are 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.

Solution 1

The idea is to use a dict that will keep the dishes already eaten and the round they were last eaten. If difference of rounds between the last round a dishe was a eaten and the current round is greater than K then we eat the dish again and update its value in the dict. Otherwise we just do nothing. And if the dish is not in the dict we can eat it and add to the dict.

from typing import List

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
    window = {}
    eaten_counter = 0

    for i in range(N):
        if not D[i] in window or (eaten_counter - window[D[i]]) > K:
            window[D[i]] = eaten_counter
            eaten_counter += 1
    return eaten_counter

Solution 2

The idea is to keep a queue of length K with the K last dishes eaten. To improve search time in the queue (O(K)) we use a set that allows to search in O(1). Hence:

• The queue is used to keep the order of the last eaten dishes (popleft() will remove oldest element in O(1))
• The set is used to search in O(1) (and the output of popleft() will be remove from the set in O(1))

from typing import List
from collections import deque

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
    queue_dishes, set_dishes, eaten_counter = deque(), set(), 0
    
    for dish in D:
        if dish not in set_dishes:
            if len(queue_dishes) >= K:
                set_dishes.remove(queue_dishes.popleft())
            queue_dishes.append(dish)
            set_dishes.add(dish)
        eaten_counter += 1
        
    return(eaten_counter)