Coding Interview Question Fraudulent Activity Notification Problem

A detailed explanation of the fraudulent activity notification problem that was posted on hackerrank as well as an efficient solution.

[ausreir]

I'm not sure what everyone else did and I apologise for any inaccuracies in advance.

The algorithm presented is correct, but the code in this video has a few bugs. Firstly, it should be expenditure[current], rather than [current]. There is also a bug regarding how median is found when d is even. Running the test cases on Pythontutor is immensely helpful when attacking these minor niggles.

I learned a lot from doing this problem and watching this video. Thank you.

[ijyotir]

Kudos for the explanation, only after listening to your explanation the below code made sense to me .


def notif (expenditure, d):

notif = 0 ; MAX = 200 ; c = [0] * (MAX+1)
for e in expenditure[:d]: c[e] += 1

def median2():
s = 0
for x in range(MAX+1):
s += c[x]
if 2*s >= d : break
if d%2 == 1 or 2*s > d : return 2*x
return x + next( y for y in range(x+1, MAX+1) if c[y] )

for i in range(d, len(expenditure)):
if expenditure[i] >= median2() : notif += 1
c[expenditure[i-d]] -= 1 ; c[expenditure[i]] += 1
return notif

[MrAsdfghjkl]

Great explanation! Could you explain how you got the idea of relating counter to the position of the median? I don't understand the relation between them.

[flyawaytothesky]

This helped a lot thanks. Was stuck on this for a while. I was really close though and my strategy was very similar to yours. I guess just 1-2 extra steps that pushed me past the time limit mm

[davidvisalon]

This is a smart way of doing it! Thanks

[rajatnagpure]

he explains really well! keep posting bro.

[philipdimeski]

I have a question about the way you are calculating the median position. In your example you +1 if the trailing_days % 2 == 0. Is this correct?
If my trailing_days is 5 then wouldn't the median be element in the 3rd position (or 2nd position is your are start indexing at 0)?
With your code it looks like the median when the trailing days is 5 would be 2?

[stark_mark]

Can't we use dict() instead of a queue??

[PerfectBlue]

thank you for your video but couldn't you write the code as you explain

[mdwahidmunir]

Sir in line 12 the condition is counter < median_position. So the loop breaks when counter > median_position. In line 21 the condition is given as counter>median_position, so if this is the case then counter is already greater than median_position. Hence the if statement of line 21 is always true. Sir I am having confusion in this and the else statement of line 23.. It will be grateful if you clear this portion .

[amitrokade]

Why Dont you check if the previous value is zero on line 16?

[ilefdey]

For some reason this does not work for bigger test_cases, it gives a wrong answer.