FIFO Feed With Move-To-End

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is FIFO Feed With Move-To-End. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Implement the ordering logic for a Squarespace content feed. Items are retrieved in FIFO order, but adding an item already present in the feed refreshes it by moving it to the end instead of creating a duplicate.

Implement news_feed(operations). Each operation is a two-element list: ["add", item_id] or ["get"]. For every get operation, remove and return the oldest item. If the feed is empty, return None. The function returns the results of all get operations in order.

You must support each add and get in O(1) average time. Do not use collections.OrderedDict or a library queue. Items are integer IDs, and an ID is considered present until it is retrieved.

Constraints

1 <= len(operations) <= 200,000
Each operation is either ["add", item_id] or ["get"]
-10^9 <= item_id <= 10^9
At most 100,000 distinct item IDs occur
A get operation on an empty feed returns None

Function Signature

def news_feed(operations):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output