Suppose I have a list with N sorted dates and M non-overlapping sorted periods with start date, end date (inclusive), and a tax rate for example. I have to make an efficient algorithm retrieve all tax rates for all dates. If there is not period including this date it should raise an error.
Given the brute-force approach I could have a O(N * M) with two nested loops. It is possible to break the inner loop when one date is found (maintains the code worst-case complexity). Another optimization would be to store the index of last period, since the lists are sorted, then I believe I got O(N + M). Is there a more optimal way of doing that? Maybe using other data structures?
Working code in Python:
import collections
import datetime
import sys
from typing import List
RatePeriod = collections.namedtuple("RatePeriod", ["start_date", "end_date", "rate"])
periods = [
RatePeriod(datetime.datetime(2019, 1, 3), datetime.datetime(2019, 4, 1), 10.7),
RatePeriod(datetime.datetime(2019, 4, 2), datetime.datetime(2019, 12, 2), 20.5),
RatePeriod(datetime.datetime(2019, 12, 3), datetime.datetime(2020, 1, 2), 37.8),
]
def get_rates(dates: List[datetime.datetime]) -> List[float]:
rates = []
last_period = 0
for idx, date in enumerate(dates, 1):
for idx2 in range(last_period, len(periods)):
period = periods[idx2]
last_period = idx2
if period.start_date <= date <= period.end_date:
rates.append(period.rate)
break
if len(rates) < idx:
sys.exit("No period found for date: {}".format(date))
return rates
series = [
datetime.datetime(2019, 2, 20),
datetime.datetime(2019, 3, 6),
datetime.datetime(2019, 12, 14),
]
result = get_rates(series)
expected = [10.7, 10.7, 37.8]
assert result == expected