"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!!
Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc.
Team Cracking The Code
About Me
▼
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.
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 :)
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)).
ReplyDelete@mohit how u will initialize in O(1)
ReplyDeletehow 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