Short Problem Definition:
HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to 2x the client’s median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn’t send the client any notifications until they have at least that trailing number of prior days’ transaction data.
Fraudulent Activity Notification
time complexity is
space complexity is
I am not very happy with this solution, but it passes the tests, so I am posting it. This solution is running in O(N^2) due to the element removal from the running_median. del l[i] is O(N). O(NlogN) would be preferable.
The expenditures are actually not very large numbers [0..200], so there might be space for optimization there.
from bisect import bisect_left, insort_left def activityNotifications(expenditure, d): warnings = 0 running_median = sorted(expenditure[:d]) for i,ele in enumerate(expenditure): if i < d: continue if d % 2 == 1: median = running_median[d//2] else: median = (running_median[d//2 - 1] + running_median[d//2])/float(2) if ele >= median*2: warnings += 1 # remove previous element del running_median[bisect_left(running_median, expenditure[i-d])] # add new element insort_left(running_median, ele) return warnings