CareerCup

Have a balanced BST holding records sorted on timestamp. The question will reduce to find nodes in given range in a bst. For descriptions keep a hash with values pointer to the nodes in the balanced BST nad return all matching descriptions.

We could use sorted or hash maps for quick search by name and the timestamp. Those maps should just deal with the same pointers to records. GetDesriptions may return a vector of strings, and the GetRecords may return a vector of records for your programming convenience.

It depends on the cache implementation technique like LRU etc.
We can use LinkedHashMap here if programming in java...

1. LinkedHashMap is the easiest, just like a LRU cache.

2. Otherwise, use a HashMap to store all the records in pairs like (Name, Record). Then use a ArrayList to sort all records based on time. This is a way to simulate LinkedHashMap.

Well, one question is: Is the data stagnant or evolving over time?
If data is stagnant / bearly changes with time, I would use an ISAM (Indexed Sequential Access Method) tree or in the latter case, a B+ Tree. Both of these trees with startTime as primary key and name as the secondary key. This is because, the primary key is efficient for range searches (because it will be clustered) while secondary key is not. There are open source libraries available to build and maintain these datastructures.

For example: jdbm2 @ google code (Sorry could not provide actual link)

If able to use C++11, use std:: unordered_multimap to hash records by name, and std::ordered_set to organize records by time. GetDescriptions() can return a std::vector of const char* for descriptions, and GetRecords,() can return std::pair of const_iterators to range of records.

The assumptions here were that return values cannot be modified; drop the const if that is not the case.