CareerCup

Basically at any time you need to store data for 10 years only i.e 10 years * 365 days = 3650 blocks of memory. So the 1st level of data structure used will be an array. [No problem of sparse, collision etc]

Each index of the array will correspond to 1 particular date in the last 10 years. While inserting a record in the array convert date to a integer value. If system starts from 1st Jan 2000 & you want to add entry for 13th Dec 2007 then the index where you want to add = (365 * 7) + (7 * 31) [months with 31 days] + (4 * 30) [months with 30 days] + 28 [for Feb] + 13 [days of december] = 2933

This array is encapsulated in a class StockTickerCache. The Cache stands in between the actual files & provides in-memory retrieval of the records. Basically, all client application/code 'can' deal only with Cache. The Cache will maintain a Balanced Binary Search Tree for every date. So each index of the array will have a pointer to the root of the binary search tree.

Lets introduce a struct StockTicker. StockTicker contains the name & its price [which can ne null]. Each instance of StockTicker pointer is encapsulated inside the Binary Search Tree for that particular day.

We can 2 have approach to implement StockTickerCache.
Strategy 1 - StockTickerCache maintains a Balanced Binary Tree for 'only' those StockTicker which have a closing price. If the company does not support any functionality for StockTicker without a closing price then then why waste memory by maintaining extra nodes.

Strategy 2 - StockTickerCache maintains
1) Pointer to the root of a Balanced binary tree for 'ALL' StockTicker irrespective whether they have closing price information or not. The only concern is this approach will use more memory. It will also use more processing time for B) & C) because you have to visit more nodes. Advantage of this approach is future enhancements for StockTicker without any closing prince will be more easily accomplished.

Time to find array index is constant - O(1)
Time to find StockTicker in Balanced Binary Search Tree - O(logn)
In order iteration of Balanced Binary Search Tree - O(n)

Time complexity of
A) O(1) + O(logn)
B) O(1) + O(n)
C) O(n-1) * O(logn)
This involves converting the given date to array index. Iterate all array elements from i = given date to 0 [before you get a successful search]. For each array index i.e StockTickerCache pointer, get the root of the tree & iterate the tree. An unsuccessful search will mean the given StockTicker does not has any closing price for that day. Else if the search finds it then return the closing price information.

Finally, the most IMPORTANT point --> You can implement the solution using Strategy patterns to vary your algorithm either for "only" those StockTicker which have closing price or "ALL" stocktickers irrespective of the closing price. You can also configure your system to use either of the strategy based on some configuration file & factories. This way you have the benefit of 'relatively' better performance [strategy 1] as well as easy future enhancements [strategy 2] based on your settings/configuration.

Mult level indexing. B trees. I dont know what would be the best/good data structure that works well for (C). Any idea

B tree to locate the record bucket which includes all the dates when this ticket has price information. For this we can use binary tree. or some self balancing trees.

We could simply use a 2-D array to store the information. This doesn't seem to be a sparse matrix so we won't be wasting any space. A & B can be done in constant time, and C should be done in O(n) time.

It can be easily done by using a 1 dimensional array & complete binary search tree. So, your outermost data structure is 1 dimension array.

In the nutshell, each index of an array denotes entry for the File corresponding to that day. Now instead of creating links to the file, or directly accessing the file read the necessary details of the file in a Balanced Binary Tree. So, each index of the array will contain a pointer to the Balanced binary search tree for that particular day.

Warren buffett never needed to know this.....