Hash Map with Doubly Linked List Ordering

Problem

Simulate an ordered map that keeps keys in least-recently-used order with a doubly linked list on top of a hash map.

capacity is the maximum number of keys. operations contains "set" (keys[i], values[i], evicting the LRU key when full), "get" (value or -1, marking the key as recently used), "delete" (True when the key existed), "peek_lru" and "peek_mru" (key or None), or "to_list" (all keys from LRU to MRU).

Return the list of recorded results (None for set).

Hint

Both get and set must move the key to the most-recently-used end of the list.

Test cases

case 1

in: [2,["set","set","get","peek_lru","peek_mru","set","to_list"],[1,2,1,0,0,3,0],[10,20,0,0,0,30,0]]

expected: [null,null,10,2,1,null,[1,3]]

case 2

in: [1,["set","get","delete","get"],[1,1,1,1],[5,0,0,0]]

expected: [null,5,true,-1]

case 3

in: [2,["get","peek_lru"],[9,0],[0,0]]

expected: [-1,null]

case 4

in: [2,["set","delete","set","to_list"],[1,1,2,0],[1,0,2,0]]

expected: [null,true,null,[2]]

Starter codePython

def ordered_map_ops(capacity, operations, keys, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor