CareerCup

You can use Doubly Linked list and maintain a Hash or map of number as key and the address of nodes as the value.
suppose there are multiple entries of any number in queue then instead of using map we use multi valued maps, so that we cam delete the numbers in const. time.

First of all it is important to know what removeElement(n) means. Should it remove ALL nodes where the value is n or just the first one.

Suppose that it should remove all AND suppose that removing really wants to remove items that were inserted into the queue and not called with infitine random values.

In this case you can build up hastable when removeElement(n) is called, add n there, and modify get() to skip the elements if found in the hashtable. Furthermore modify put so when "n" is added again remove it from the hash-table.

If removeElement(n) should remove only the first instance some modifications needed to the additional hash-table handling (get should skip the element and remove it from the hash table as well)

We can use normal incremental Array...

put O(n) -- @ the time of putting we can check if space available in array fine.. else increase it by some constant number let say 20..
get O(1)
removeEle O(1)

This is more of an LRU cache design.

If your a JAVA guy take a look at LinkedHashMap or you can replace the HashMap
part with a TreeMap equivalent and maintain a double linked list (prefered).

If your a c/c++ guy, see how linux caches or file system inodes are implemented.
They use some sort of array of lists with a double linked list running across
these lists.

The double linked list is basically a queue to maintain recent entry order.

With RedBlack trees and queue.
PUT(i) - O(log(N))
GET() - O(1)
GET(i) - O(log(N))
DELETE(i) - O(log(N))

Any bucket based hashmap w/ double linked list between the nodes would do (LinkedHashMap in java). you have O(1) - getFirst(), O(1) for put(key, val) and get(key).

Alternatively any self-balancing tree also w/ double linked list between the nodes. However, rebalancing Red-Black (for example) is a little trickier than normal since you can't just swap values but you have to swap the nodes for real.