
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
October 5th, 2018, 12: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 02:23 AM. 
October 5th, 2018, 03:19 AM  #2 
Global Moderator Joined: Dec 2006 Posts: 20,942 Thanks: 2210 
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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
effitient array data structure  baxy  Computer Science  1  October 6th, 2013 07:19 AM 
Data structure and Algorithms  Christ1m  Computer Science  2  March 23rd, 2011 03:36 PM 
Estimating the term structure from (insufficient) bond data  tach  Economics  0  November 17th, 2009 02:57 PM 
Hausdorff space, structure  eskimo343  Real Analysis  0  March 21st, 2009 02:43 PM 