My Math Forum Data structure for finding max, inserting and deleting in O(1) and O(n) space

 Computer Science Computer Science Forum

 October 5th, 2018, 01:45 AM #1 Member   Joined: Mar 2015 From: USA Posts: 34 Thanks: 1 Data structure for finding max, inserting and deleting in O(1) and O(n) space This is an interview question. I needed to implement a data structure that supports the following operations: 1. Insertion of an integer - $O(1)$ 2. Deletion of an integer (If for example we call delete(7) so 7 is deleted from the data structure, if the integer 7 exists in it) - $O(1)$. 3. Return maximum integer in the data structure (without deleting it) - $O(1)$. You can assume the numbers that will be inserted are integers in the range $[0,n]$. You can also use $O(n)$ space. I thought of something like the purpose here , but we have $O(\log n)$ here. Do you know how can we implement these operations in $O(1)$? Last edited by skipjack; October 5th, 2018 at 03:23 AM.
 October 5th, 2018, 04:19 AM #2 Global Moderator   Joined: Dec 2006 Posts: 20,310 Thanks: 1978 In theory, this can't be done. In practice, though, there would have to be a fixed maximum value of $n$, which means that any structure that supported the operations would do, as the constant time could just reflect the worst case.

 Tags data, deleting, finding, inserting, max, space, structure

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post baxy Computer Science 1 October 6th, 2013 08:19 AM Christ1m Computer Science 2 March 23rd, 2011 04:36 PM tach Economics 0 November 17th, 2009 03:57 PM eskimo343 Real Analysis 0 March 21st, 2009 03:43 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top