I did the exact same counter problem when I did a phone interview with Google last week. Below is an outline of how I went about solving the problem. Please note, this question was the third question asked during my one hour phone interview. If this question had been asked first, I would have probably not been able to do as good of a job on it. Since it was asked third, I was sufficiently 'in the zone' so the code came out relatively easily.
I started out by writing a quick doctest to define the interface:
>>> counter = Counter()
>>> counter.increment()
>>> counter.query(‘minute’)
1
>>> counter.query(‘hour’)
23