0

I tried to solve a question in Hackerrank. I passed all the sample test cases but couldn't pass all the hidden test cases due to the "exceeded time limit" error. The link to the problem question is: Fraudulent-activity notification

My code is as follows.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the activityNotifications function below.
int activityNotifications(vector<int> v, long int d) {
  long int n,ex;
  long double m;
  long int cap=v.size();
  long int notif=0;
  n=d;
  for(long int i=0;i<n&&n<cap;i++,n++)
  {
    ex=v[n];
    sort(v.begin()+i, v.begin()+i+d);
    if(d%2==0)
    {
        m=(v[(n+i-1)/2]+v[(n+i)/2])/2.0;
    }
    else
    {
        m=v[(n+i)/2];
    }
    if((m*2)>=ex)
    {
        notif++;
    }
  }
  return (notif-1);
 }
  int main()
  {
    vector<int>v;
    long int n,d;
    long int item;
    cin>>n>>d;
    for(long int i=0;i<n;i++)
    {
        cin>>item;
        v.push_back(item);
    }
    int res=activityNotifications(v,d);
    cout<<res;
    return 0;   
   }

How can I optimize this code? Please help.

Philona Reetha Sebastian
  • 13
  • 1
  • What inputs are you using? – tadman Mar 16 '21 at 07:14
  • 2
    @tadman sample input: 9 5 2 3 4 2 3 6 8 4 5 where 9 is the array size, 5 is the number of trailing days' data remaining are the array elements. output: 2 – Philona Reetha Sebastian Mar 16 '21 at 07:16
  • 1
    When trying to optimize, you must always thing about the algorithm. Here you are sorting an array on each step, while you know that the array was already sorted on previous step and you just removed one item and add a new one. IMHO the key is here. – Serge Ballesta Mar 16 '21 at 07:25
  • Well, as good as I understand your code, it won't be accepted anyway. For the following example(5 3 10 5 1 9 9) your code will return 1, but have to 0 – Deumaudit Mar 16 '21 at 07:27

1 Answers1

1

For now, every step requires sorting with O(dlogd) time, so overall time is about O(ndlogd)

You have to minimize time for median. There is an approach with min and max heaps (example) to treat all data untul current moment. Median is element at the larger size heap for odd d, and average of two heaps tops for even d.

But you need median in rolling window. So possible addition: make parallel data structure ref[] (list/array working in cyclic manner) with references/pointers to heap nodes. When index leaves window (of size d), remove corresponding node from a heap, then add new node with new value and update heaps and ref.

Every step will require only O(logd) time

Update: seems this topic contains links and descriptions of a lot of rolling window median methods

MBo
  • 77,366
  • 5
  • 53
  • 86