Monday, July 11, 2011
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.
Subscribe to:
Post Comments
(
Atom
)
2 comments :
can we use hashtable here using dynamic array which provide insertion ,deletion and search in O(1) time. And for space O(n) for hashed-keys + O(n) for actual values. (assuming the hashing computation O(1)).
@mohit how u will initialize in O(1)
how u will insert in O(1) if range is not known ...think in terms of array indirection u might be able to come up with desired approach :)
Shashank
Post a Comment