CareerCup

if you just remove the word cache from the Qs it seems to be pretty simple...just use a MaxHeap to keep track of the max in a decreasing order and to retrieve the max at any time...

For normal cache operation, we can use LRU (least recently used) algorithm. It has various implementations like stack, time counter. For maintaining max no. data, we can check the current data against the last max data.

how do ensure "efficient retrieval of the maximum element"?

using LRU and a different technique to pick the max are contradictory to each other. i guess you got the point! so your approach will not work. Else prove otherwise.

Like googler, the first thing that came to my mind was a Heap.
However, bebo's approach might have some weight. If you lay down the data as a non-tree data structure and find the max element upfront and then with each incoming element you check if its greater than the current max, you'd always have a pointer to the max element. ie, max element retrieval is O(1) just like maxheap. The rest of the cache ops can be done by LRU or other algos as required.
Having said that I'd give the maxheap soln anyday.

a

isn't this a priority queue? it could be implemented as a heap, but it can also implemented as the other data structure.

How about this. We maintain a heap to model a cache and with that said we have access to the max element which shall be at its root.
In an event of retrieval only {cache hit}, we get the maximum element in O(1).
In case of an insert {cache miss} into the cache without a page swap, we can compare the root with the inserted element and decide on the max.
In case of an insert {cache miss} accompanied by a page swap out, we may have to reheap the cache contents after the swappping & insert happens, as we are not sure
if the previous maximum has been swapped out or not and/or if its greater than the
newly inserted element.

Heap + LRU = Priority Queue (where recent items in the queue have highest priority)

I would use a splay tree here. They've got the great propery of always keeping the last accessed node as the root and recently used items close to the root, so it's a great cache...and they are a normal, well balanced BST so we can perform all sorts of operations on it quickly (find min, max, etc...)

how do you retrieve an item? heap stores the max and min item at the root. But not good at finding an element.

how about min-max heap I mean double ended priority queue? min heap will store the age value and max heap will store the maximum magnitude of the element. And as in min-max implementation the same elements in both heaps can point to each other.

linkedhashmap

use max-heap + hashtable + linked-list (latter two is for LRU). Read question as implement a LRU cache supporting the retriveal of max-element like cache.getMax()