Data structure insert,delete,mode -

here interview problem: designing data structure range of integers {1,...,m} (numbers can repeated) support insert(x), delete(x) , return mode return number.

the interviewer said can in o(1) operation preprocessed in o(m). accepted can insert(x) , delete(x) in o(log(n)), return mode in o(1) preprocessed in o(m).

but can give in o(n) insert(x) , delete(x) , return mode in o(1), how can give o(log (n)) or/and o(1) in insert(x) , delete(x), , return mode in o(1) preprocessed in o(m)?

when hear o(log x) operations, first structures comes mind should binary search tree , heap. reference: (since i'm focussing on heap below)

a heap specialized tree-based data structure satisfies heap property: if parent node of b key of node ordered respect key of node b same ordering applying across heap. ... keys of parent nodes greater or equal of children , highest key in root node (this kind of heap called max heap) ....

a binary search tree doesn't allow construction (from unsorted data) in o(m), let's see if can make heap work (you can create heap in o(m)).

clearly want frequent number @ top, heap needs use frequency ordering.

but brings problem - insert(x) , delete(x) both require through entire heap find correct element.

now should thinking "what if had sort of mapping index position in tree?", , we're going have. if / of m elements exist, have array, each index i's element being pointer node in heap. if implemented correctly, allow heap node in o(1), modify appropriately, , move, taking o(log m) both insert , delete.

if few of m elements exist, replacing array (hash-)map (of integer heap node) might idea.

returning mode take o(1).

---

o(1) operations quite bit more difficult.

the following structure comes mind:

3     2 ^     ^ |     |          5     7     4     1  12    14    15    18 

to explain what's going on here - 12, 14, 15 , 18 correspond frequency, , numbers above correspond elements said frequency, both 5 , 3 have frequency of 12, 7 , 2 have frequency of 14, etc.

this implemented double linked-list:

          /-------\                     /-------\ (12) <-> 5 <-> 3 <-> (13) <-> (14) <-> 7 <-> 2 <-> (15) <-> 4 <-> (16) <-> (18) <-> 1   ^------------------/ ^------/ ^------------------/ ^------------/ ^------/ 

you may notice that:

i filled in missing 13 , 16 - these necessary, otherwise we'll have update elements same frequency when doing insert (in example, would've needed update 5 point 13 when doing insert(3), because 13 wouldn't have existed yet, would've been pointing 14).

i skipped 17 - optimization in terms of space usage - makes structure take o(m) space, opposed o(m + maxfrequency). exact conditions skipping number doesn't have elements @ frequency, or 1 less frequency.

there's strange things going on above linked-list. these mean 5 points 13 well, , 7 points 15 well, i.e. each element keeps pointer next frequency.

there's strange things going on below linked-list. these mean each frequency keeps pointer frequency before (this more space efficient each element keeping pointer both it's own , next frequency).

similarly above solution, we'd keep mapping (array or map) of integer node in structure.

to insert:

• look node via mapping.
• remove node.
• get pointer next frequency, insert after node.
• set next frequency pointer using element after insert position (either next frequency, in case can make pointer point that, otherwise can make next frequency pointer point same element element's next frequency pointer).

to remove:

• look node via mapping.
• remove node.
• get pointer current frequency via next frequency, insert before node.
• set next frequency pointer node.

to mode:

return last node.