CareerCup

Here is the strategy one can follows
Lets say Kindle is used for reading materials. and we have the data with us stored in the cloud.
Two point we have keep in the mind are following

Need to give priority to user previous searches
	Need to give different priority to cloud entities

An entities are the reading materials
Here is the storage plan for Kindle locally

We will create trie of searches, Whenever user do a search, we store that information into the trie, if it is already present in the trie, we increment it's search count.
Each node in the trie have an integer value which tells how much time a search lead to this point.

Here is how we keep cloud data.

We create trie in the cloud as well, which is readonly from the user prospective, and can only be updated by internal systems. this makes multiple reads easier.
Here each node store the popularity index for an entity represented upto this point.

Now here is how we fulfil user ask for autocomplete result.

Whenever user start typing, start searching in internal data, and we show the result which are searched maximum times by this user, along with that we also do parallel search in cloud, and get the data from that as well, as soon as we go out of our internal band, we start showing cloud data, now because cloud data were searched along with local data, user will not see any delay, other then, the time our service is taking from getting data from the cloud for further queries.

Now here we can trade off, based upon business requirement, which is like, lets say someone launches a new book and want amazon to tell his kindle users, we can priorities this book more then others.

Complexity : O(length of user query search) Time + O(data stored in kindle)
Now here we can optimized the search in the trie by telling it where to go and fine maximum searched item, but for that we have to store one more entity at each node which will tell where to go to find max, this will increase our insert time to little extend.

You can use something like a suffix tree for better results.
For a simple answer you can use trie