Group Photos and Sort Feed Items

Problem Statement

In a neighborhood social network, users frequently share single photos in quick succession. To prevent the main feed from feeling cluttered, the feed service collapses consecutive photo posts uploaded by the same user into a single album item before delivering the final feed to the client.

You are given a list of feed items in their original ingestion order. Each item is represented as a dictionary with the following structure:

• id (str): Unique identifier of the item.
• user_id (str): Identifier of the author.
• type (str): Item type, either "photo" or "text".
• timestamp (int): Unix epoch timestamp in seconds.
• content (str): Text content or photo image URL.

Requirements

1. Group Consecutive Photos: Scan the input feed in order. When two or more consecutive items have type == "photo" and share the same user_id, group them into a single item of type == "album".
   • A single photo not adjacent to another photo by the same user remains an individual "photo" item unchanged.
   • The newly formed album item must have:
     • id: "album_" + first_photo_id (where first_photo_id is the id of the earliest photo in the run).
     • user_id: The author's user_id.
     • type: "album".
     • timestamp: The maximum timestamp among the photos in the group.
     • photos: A list of strings containing the content (URLs) of the grouped photos in their original relative order.
2. Sort Feed Items: After grouping, sort the transformed feed items in descending order of timestamp.
   • If two or more items have identical timestamps, preserve their relative order from the grouped list (stable sort).

Function Signature

def transform_feed(items: list[dict]) -> list[dict]:
    pass

Examples

Example 1

Input:

items = [
    {"id": "p1", "user_id": "alice", "type": "photo", "timestamp": 100, "content": "url1.jpg"},
    {"id": "p2", "user_id": "alice", "type": "photo", "timestamp": 105, "content": "url2.jpg"},
    {"id": "t1", "user_id": "bob",   "type": "text",  "timestamp": 110, "content": "Hello neighbors!"},
    {"id": "p3", "user_id": "alice", "type": "photo", "timestamp": 95,  "content": "url3.jpg"}
]

Output:

[
    {"id": "t1", "user_id": "bob", "type": "text", "timestamp": 110, "content": "Hello neighbors!"},
    {"id": "album_p1", "user_id": "alice", "type": "album", "timestamp": 105, "photos": ["url1.jpg", "url2.jpg"]},
    {"id": "p3", "user_id": "alice", "type": "photo", "timestamp": 95, "content": "url3.jpg"}
]

Explanation:

• p1 and p2 are consecutive photos by alice, so they merge into an album with ID album_p1 and timestamp max(100, 105) = 105.
• p3 is separated from p1 and p2 by t1, so it is not grouped with them.
• Sorting by timestamp descending yields t1 (110), then album_p1 (105), then p3 (95).

Constraints

• 0 <= len(items) <= 100,000
• timestamp is a non-negative integer (0 <= timestamp <= 2 * 10^9).
• user_id, id, and content are non-empty strings.
• type is guaranteed to be either "photo" or "text".