New answers tagged

3

One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all of your operations in $O(\log n)$ time. Operation 1 can be implemented by finding the leaf where the member $m$ resides (either add a pointer to the member ...


2

Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first. I'd go with three queues: all animals, dogs, cats. Enqueue: Create an instance of dog/cat, push into all animals queue. Next, push the same instance to the dog/cat queue ...


Top 50 recent answers are included