My second interview in Python went better. I wanted to keep a data structure of keys and values where I'd repeatedly retrieve and remove the minimum key and then insert a new value. This is a priority queue of fixed size k.
I wasn't sure what Python offered natively, so I went with a less efficient method of repeatedly sorting a dictionary by keys. I correctly guessed the syntax (the interviewer was lenient when I said I wasn't sure):
Note that this returns a list of keys, so the value for the minimum key is d[sorted(d)]. Here's an option for sorting by value, which also returns a list of keys:
Complexity-wise, sorting a k-length dictionary over n iterations is O(n*k*log k).
I could also use an unsorted array where I keep a pointer to the minimum index. Then finding the new minimum on each remove/insert takes O(k) for a total of O(n*k), which is better and even simpler than the sorted dictionary. It looks like Python doesn't have a native sorted array, but it does have heapq, which uses a min-heap: the standard and most efficient of these options for priority queues. It does removes and inserts in O(log k), so the total complexity is O(n*log k).