My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
October 5th, 2018, 12:45 AM   #1
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.
Lobinho is offline  
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.
skipjack is online now  

  My Math Forum > Science Forums > Computer Science

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

Copyright © 2019 My Math Forum. All rights reserved.