Build a Bounded Vocabulary

Task

Write build_vocabulary(token_counts, reserved_tokens, max_size). A token vocabulary is a dictionary assigning one integer ID to each retained token. token_counts maps ordinary token strings to their counts. reserved_tokens is a supplied list of special tokens in the order they must receive IDs. Its items are unique. max_size is the largest allowed number of vocabulary entries, including reserved tokens.

Keep every reserved token first and ignore its count. After the reserved tokens, consider the other tokens in descending count order. Break equal-count ties by token string ascending. Stop when the vocabulary has max_size items. Assign contiguous IDs beginning at 0. The inputs must not be changed.

Example

<pad> is reserved even though its count is ignored. cat wins the final available slot over dog because their counts tie and cat comes first.

Your implementation

Edit solution.py and keep this function name and signature:

Return a new dictionary whose values are contiguous integer IDs. Do not add a reserved token twice, use a reserved token's count, print, ask for input, or mutate any argument. max_size is guaranteed to be at least the number of reserved tokens.