5
\$\begingroup\$

I am solving this problem: Fraudulent Activity Notifications on HackerRank. I am done with my code and is working, but it is inefficient as well for very large inputs.

I don't know but after all my efforts, I am able to give out good solution to a problem of a MEDIUM LEVEL but this timeout error happens every time for very large inputs. I have tried optimizing my code and still I get timeout errors. My agendas for this question and upcoming questions are:

  • How to put efficiency for very large inputs. What kind of intellect it requires.
  • How to reach to that level. What should I prepare for this.
  • Code optimization

I am open to learning, and I am really desperate to learn how to write a more advanced and optimized code to make myself better. I am open to do hard work.

My Algorithm:

  1. For this problem we must go from incrementing variable i till len(givenArray)-d
  2. Take a variable for the next variable to be compared, my case iterate is the variable
  3. Pass the values to the particular array to the method for counting countFraud()
  4. Add it to the count variable
  5. Increment iterate variable

Code:

# this is for counting the trailing array
def countFraud(arr, nextNum):
    count = 0
    median = 0.0
    d = len(arr)
    #for calculating the median correctly
    arr.sort()
    if d%2 != 0:
        median = arr[int(d/2)]
    else:
        n = int(d/2)
        median = (arr[n] + arr[n-1]) / 2

    #now the opeartion for count from the array
    if nextNum >= 2*median: count += 1
    return count

# Complete the activityNotifications function below.
def activityNotifications(expenditure, d):
    count = 0
    iterate = d
    # it will go upto the len of array - d, so that it will go upto the d length
    # leaving the last element everytime for the comparision
    for i in range(len(expenditure)-d):
        count += countFraud(expenditure[i:iterate], expenditure[iterate])
        iterate += 1
    return count

Now previously I was doing two loops, adding the items to the new_array and passing it to the the countFraud(). But now I have optimized it and made it sort of O(N).

I don't know but this code is not getting submitted for all TCs due to Timeout Error. There is no problem in operation part. It is just with the efficiency of the code.

Timeout Error Input Example:

200000 10000

Link for input - Input Data

Expected Output:

633

I have read upon this article: HackerRank Environment to learn about the timing issue. For Python/Python 3 it is 10 seconds. My code is definitely taking more than that for values greater than 10^3 or 4.

My code has successfully passed 3 TCs though.

\$\endgroup\$
3
\$\begingroup\$

If this wasn't a programming challenge with restricted modules, I would suggest using pandas. It has a rolling windowed median implemented, so it is quite straight forward (just have to be careful not to have an off-by-one error with the shift):

import pandas as pd

def activityNotifications(expenditure, d):
    df = pd.DataFrame(expenditure)
    return (df.shift(-1) > 2 * df.rolling(d).median())[0].sum()

For the example input you gave, this runs in about 210 ms ± 3.71 ms on my machine. This is very hard to beat, both in runtime and readability.


Unfortunately, Hackerrank does not have pandas available (or even numpy for that matter). So, we need another implementation of a windowed running median. There are multiple ways to implement it, but here is one. You keep track of two collections, one is the window you are looking at and one is a sorted version of it. The former tells you which value drops out when you add a new one, and the latter allows you to easily get the median without having to sort the window each time, if you insert elements at the right place. For this you can use the bisect modules insort (which is \$\mathcal{O}(n)\$, instead of \$\mathcal{O}(n\log n)\$ for sorting each time).

I used the RunningMedian function from here, and modified it a bit to directly count instead of collecting the medians. It is not the most beautiful code to look at, I might clean it up a bit later.

from itertools import islice
from collections import deque
from bisect import insort, bisect_left

def activityNotifications(seq, M):
    """
     Purpose: Find the median for the points in a sliding window (odd number in size) 
              as it is moved from left to right by one point at a time.
      Inputs:
            seq -- list containing items for which a running median (in a sliding window) 
                   is to be calculated
              M -- number of items in window (window size) -- must be an integer > 1
      Otputs:
         medians -- list of medians with size N - M + 1
       Note:
         1. The median of a finite list of numbers is the "center" value when this list
            is sorted in ascending order. 
         2. If M is an even number the two elements in the window that
            are close to the center are averaged to give the median (this
            is not by definition)
    """   
    seq = iter(seq)
    s = []
    m = M // 2

    # Set up list s (to be sorted) and load deque with first window of seq
    s = [item for item in islice(seq, M)]    
    d = deque(s)

    # Simple lambda function to handle even/odd window sizes    
    median = lambda : s[m] if bool(M&1) else (s[m-1]+s[m])*0.5

    # Sort it in increasing order and extract the median ("center" of the sorted window)
    s.sort()

    # Now slide the window by one point to the right for each new position (each pass through 
    # the loop). Stop when the item in the right end of the deque contains the last item in seq
    count = 0
    for item in seq:
        count += item > 2 * median()
        old = d.popleft()          # pop oldest from left
        d.append(item)             # push newest in from right
        del s[bisect_left(s, old)] # locate insertion point and then remove old 
        insort(s, item)            # insert newest such that new sort is not required        
    return count

This code takes about 871 ms ± 14.5 ms on my machine for the given testcase. It passes all testcases on Hackerrank as well. It is slower than the pandas one, but that is to be expected. Both functions give the same result.


Some additional comments about your code itself:

  • if nextNum >= 2*median: count += 1 could just be return nextNum >= 2*median. Summing bools is perfectly fine, since they are just ints underneath.
  • if d%2 != 0: can be if d % 2, because non-zero integers are truthy.
  • In actual code please follow Python's official style-guide, PEP8. It recommends naming your function activity_notifications.
  • You should add a docstring to explain what your function does.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.