08/28/20

# HackerRank ‘Fraudulent Activity Notifications’ Solution

##### 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.

##### Complexity:

time complexity is O(N^2)

space complexity is O(N)

##### Execution:

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.

##### Solution:
```from bisect import bisect_left, insort_left

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])]