Apply Insert, Update, and Remove Operations to a Keyed Store

Problem Statement

You are given a sequence of operations to apply to an initially empty key-value store. Each operation is represented as a list of strings and follows one of three commands:

1. ["INSERT", key, value]: Inserts key with the given value into the store. If key already exists, the operation is ignored.
2. ["UPDATE", key, value]: Updates the value associated with key to value. If key does not exist in the store, the operation is ignored.
3. ["REMOVE", key]: Removes key and its associated value from the store. If key does not exist in the store, the operation is ignored.

Process all operations in the order they are given and return the final contents of the store as a list of [key, value] pairs sorted in lexicographical order by key.

Interface

def process_store_operations(operations: list[list[str]]) -> list[list[str]]:
    pass

Input and Output Format

• Input: operations, a list of commands where each command is either ["INSERT", key, value], ["UPDATE", key, value], or ["REMOVE", key].
• Output: A list of [key, value] string pairs representing the final state of the store, sorted by key in ascending lexicographical order.

Constraints

• 1 <= len(operations) <= 10^5
• 1 <= len(key), len(value) <= 50
• key and value consist only of alphanumeric characters ([a-zA-Z0-9]).
• The command string is always one of "INSERT", "UPDATE", or "REMOVE" with the correct number of arguments.

Examples

Example 1

operations = [
    ["INSERT", "apple", "10"],
    ["INSERT", "banana", "20"],
    ["UPDATE", "apple", "15"],
    ["INSERT", "apple", "30"],  # Ignored: "apple" already exists
    ["REMOVE", "banana"],
    ["UPDATE", "orange", "5"],  # Ignored: "orange" does not exist
    ["INSERT", "cherry", "25"]
]

# Output: [["apple", "15"], ["cherry", "25"]]

Explanation:

• "apple" is inserted with "10", then updated to "15". The second insert for "apple" is ignored.
• "banana" is inserted with "20" and then removed.
• Updating "orange" does nothing since it was never inserted.
• "cherry" is inserted with "25".
• The final records sorted by key are ["apple", "15"] and ["cherry", "25"].

Example 2

operations = [
    ["REMOVE", "missing_key"],
    ["INSERT", "k1", "v1"],
    ["REMOVE", "k1"],
    ["UPDATE", "k1", "v2"]
]

# Output: []

Explanation:

• Removing "missing_key" does nothing.
• "k1" is inserted, then removed.
• The subsequent update on "k1" is ignored because "k1" was already removed.

Edge Cases

• Operations performed on keys that have never been inserted.
• Re-inserting a key that was previously removed.
• All keys being removed by the end of operations (empty result).