Design a data structure that can be used instead of an array and avoids the "high-cost" (i.e. O(n)) of initializing the array. the data structure ought to holds n items and supports the following operations in O(1) time: * Init – Initializes the data structure to empty. * Set(i, x) – Sets item x at index i in the data structure. * Get(i) – Gets the item stored in index i (or 'empty' if nothing is there). Remark: the data structure should use O(n) space.