During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices by George Varghese'. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG

To paraphrase, the problem asks for a data structure with the following operations

* use_resources(name, quantity) which does resources[name] += quantity
* get_approximate_top() which returns name1 such that max(resources[name]) / 2 <=  resources[name1] <= max(resources[name])

* use_resources(name, quantity) which does resources[name] += quantity (quantity can also be negative)
* get_approximate_max() which returns name1 such that max(resources[name]) / 2 <=  resources[name1] <= max(resources[name])

Using a map in combination with a hash table gets a solution that has O(log n) complexity for use_resources and get_approximate
_top which is too slow.

Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?

private

protected

10640