---
title: "Meta - Kaitenzushi"
url: "https://laigary.com/interview/coding/meta-kaitenzushi"
type: "note"
section: "coding"
date: "2024-07-07"
updated: "2024-07-07"
tags: ["Heap", "Meta", "Array"]
---

# Meta - Kaitenzushi

```python
from typing import List
# Write any import statements here
import heapq

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  # Write your code here
  
  heap = []
  eaten = set()
  count = 0
  
  for i in range(len(D)):
    d = D[i]
    if d not in eaten:
      count += 1
      eaten.add(d)
      heapq.heappush(heap, (i, d))
      while len(heap) > K:
        out = heapq.heappop(heap)
        eaten.remove(out[1])
  
  return count

```
```python
from typing import List
# Write any import statements here
import heapq
import collections

def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
  # Write your code here
  
  queue = collections.deque([])
  eaten = set()
  count = 0
  
  for d in D:
    if d not in eaten:
      count += 1
      eaten.add(d)
      queue.append(d)
      while len(queue) > K:
        out = queue.popleft()
        eaten.remove(out)
  
  return count

```