Design a data struture for integers of range 1 to 1000(non repeating) for basic operations in O(1) [closed]

Question

Design a data struture for integers of range 1 to 1000(non repeating) for following operations. 1)Insertion

2)Deletions

3)Search

4)int Anyvalid() -> This should return any valid/present number present at the time. Example if 1,5,7 are present,then return any of the 3 number.

All the operations should be 0(1)/Constant time.

I thought of bit vector but it give 0(n) in case of AnyvalidElement().. for rest all it works in 0(1).

To nitpick, if the range 1-1000 is constant, anything linear in the size of the range is in O(1). — user395760
– user395760, Commented Feb 28, 2013 at 13:45
Seems like a simpler version of stackoverflow.com/q/9575905/21727 — mbeckish
– mbeckish, Commented Feb 28, 2013 at 13:51
int anyvalid()? can return anyvalid integer? If yes. Just store the minimum element present in the DS and every element stores the pointer to the next minimum. The pointers are for deletion and just return minimum element in anyvalid(). Bit vector structure btw! — sukunrt
– sukunrt, Commented Feb 28, 2013 at 14:10

Henrik · Accepted Answer · 2013-02-28 14:13:21Z

Use a doubly linked list and an array of pointers to the list nodes.

Insert n: Add n to the front of the list, array[n] = pointer to newly added node.
Delete n: Use array to jump to the correct node in the list and remove it. Set array[n] = NULL;
Search n: check if array[n] != NULL
AnyValid: return front of the list

Collectives™ on Stack Overflow

Design a data struture for integers of range 1 to 1000(non repeating) for basic operations in O(1) [closed]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related