Google Interview Question Software Engineer / Developers
Country: United States
store in two tables like:
| Query Id | Query Body |
and
| Query Id | Query Date | Occurrence
initialize min heap of size 10;
for each query:
select sum(Occurrence) as qo where query date is in the given interval and query id = current query id
remove the heap min
place (qo, query id) node in the min heap
in the end the heap will contain top 10 queries made during the given dates interval.
funny, when I think about it - DB would be the solution in real world. But the interviewer directed to use Hash-table. When the hash function is unknown but maps strings to bits combinations.
@adam, could you please explain more in detail what is the bits combinations and how to come up with the result with certain days? Thanks.
it means: we can find a hash function that maps english words to 2 byte value (the picture enables 2^ 16 different binary words, more that needed for the english language). Then a sentence is mapped to a btye[] or even long type. This is the key for the hash table. teh value is a counter. We keep aside the max counter + it's key. At any moment we can print it.
using hash table to store the query body and occurrence, it can be done in O(n) time. And then keep a min heap of 10 capacity to find the top 10. If the new one is bigger than the top of our min heap, it can replace the min heap top and keep the min heap property in O(log10). The total time would be O(n+n*log10), at most O(n)
- shengzhc March 10, 2013