A café's till shows two live numbers above the espresso machine: how many of a given drink were ordered recently, and how many different drinks were ordered recently.
Build DrinkCounter(window), where window is a positive number of seconds:
order(t, drink) -> Nonerecords one order ofdrink(a string) at integer secondt.count(t, drink) -> intreturns how many orders ofdrinkfall in the window ending att.variety(t) -> intreturns how many distinct drinks have at least one order in the window ending att.
The window ending at t holds the orders with t - window < time <= t, just like the Basics drill: an order exactly window seconds old has dropped out. Across all calls t never decreases, and many orders can share a second.
c = DrinkCounter(60)
c.order(0, "latte")
c.order(10, "mocha")
c.order(30, "latte")
c.count(30, "latte") # 2
c.variety(30) # 2
c.count(60, "latte") # 1 (the order at 0 is 60 seconds old: gone)
c.variety(75) # 1 (only the latte at 30 is left)
c.count(75, "tea") # 0
c.variety(90) # 0
The café is busy: with hundreds of thousands of orders, every call must be fast. Don't rescan the history, and don't loop over all drinks in variety.
Show hint
keep a deque of (t, drink) plus a dict drink -> count for the orders still in the window. Before answering any call, pop expired orders from the left and decrement their count, deleting a drink from the dict when it reaches 0; then variety is just len(dict).