FIFO Feed With Move-To-End | Dataford Interview Questions

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 question is FIFO Feed With Move-To-End. Start with the requirements in the Question tab.

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

Problem

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 question is FIFO Feed With Move-To-End. Start with the requirements in the Question tab.

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