O(1) Get and Add Data Structure

Given a stream of commands, design a data structure whose supported operations each have an amortized running time of O(1). The data structure must provide these two APIs: get(key): return the value stored for key, or return -1 when no such key is present. add(key, value): store the pair (key, value); when key is already in the data structure, replace its previous value. Requirements The amortized complexity of both operations must be O(1). You may allocate extra memory as…