Hackerrank: Fraudulent Activity Notifications

Question

I'm having trouble on a question from Hackerrank, this solution works for smaller lists but seems to collapse when the list grows to 200,000 where I get the error "Wrong Solution". The problem is here so you could reproduce it. Im not sure if there is an error in my code whereby it would fail. Is there anyway to improve the efficiency of my solution?

When I encounter these sort of issues where it fails at very high lists or anything of the sort, how should I react? What kind of issue should I expect to solve?

Problem text (Incase link doesnt work): 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 (d) for a period of n days. Determine the number of times the client will receive a notification over all n days.

The following is the whole Hackerrank Code required to run the problem, I wrote the functions "Median" and "activityNotifications":

#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

double Median(vector<int> arr)
{
    int d = arr.size();

    double Even = (arr[(d/2)-1] + arr[((d/2)+1)-1]) / (double)2;
    double Odd = arr[((d+1)/2)-1];

    return (d%2==0)? Even: Odd;
}

int activityNotifications(vector<int> expenditure, int d) {

    int Notices = 0;

    vector<int> SpendData = vector<int>(expenditure.begin(),expenditure.end());
    sort(SpendData.begin(),SpendData.end());

    vector<int> SpendDataMedian = vector<int>(SpendData.begin(),SpendData.begin() + d);

    for (int i = d; i < expenditure.size();++i)
    {
        if ((Median(SpendDataMedian)*2) <= expenditure[i])
            {Notices++;}

        SpendDataMedian.erase(SpendDataMedian.begin());
        SpendDataMedian.push_back(SpendData[i]);

    }
    return Notices;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int d = stoi(first_multiple_input[1]);

    string expenditure_temp_temp;
    getline(cin, expenditure_temp_temp);

    vector<string> expenditure_temp = split(rtrim(expenditure_temp_temp));

    vector<int> expenditure(n);

    for (int i = 0; i < n; i++) {
        int expenditure_item = stoi(expenditure_temp[i]);

        expenditure[i] = expenditure_item;
    }

    int result = activityNotifications(expenditure, d);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

Sample input is:

9 5
2 3 4 2 3 6 8 4 5

Expected output is:

2

Answer 1

I didn't know the copies are due to HackerRank. Thanks for pointing that out @Deduplicator.

Now getting to the issues that I think are in your code purely based on the read.

1. If you are copying input to activityNotifications then you don't need to copy again SpendData inside function just manipulate the original directly.

• following

  int activityNotifications(vector<int> expenditure, int d) {
  ...
  vector<int> SpendData = vector<int>(expenditure.begin(),expenditure.end());
  sort(SpendData.begin(),SpendData.end());
  ...
  }
  

• becomes

  int activityNotifications(vector<int> expenditure, int d) {
  ...
  sort(expenditure.begin(), expenditure.end());
  ...
  }
  

2. Using "moving window" concept. If you want to use moving windows modify your code median to accept start and end and not use array size. This will save you on unnecessary erase and push_back and one another copy SpendDataMedian.

• following

  int activityNotifications(vector<int> expenditure, int d) {
  ...
  vector<int> SpendDataMedian = vector<int>(SpendData.begin(),SpendData.begin() + d);
  
  for (int i = d; i < expenditure.size();++i)
  {
      if ((Median(SpendDataMedian)*2) <= expenditure[i])
          {Notices++;}
  
      SpendDataMedian.erase(SpendDataMedian.begin());
      SpendDataMedian.push_back(SpendData[i]);
  
  }
  ...
  }
  

• becomes

  double Median(vector<int> &arr, int start, int end) {}
  
  int activityNotifications(vector<int> expenditure, int d) {
  ...
  
  for (int i = 0; i < expenditure.size()-d;++i)
  {
      if ((Median(SpendDataMedian, i, i+d)*2) <= expenditure[i+d])
          {Notices++;}
  }
  ...
  }
  

I might have messed up few things while copying from your code. So, please correct minor issues.

Answer 2

Yes, deciding for each day in isolation is easy enough. And produces reusable and well-defined abstractions.

Unfortunately, it costs you. Specifically, it needs too long. Use a running-total, thus each day needs only subtracting one trailing day, adding the last day, and comparing to that day. The cost is pretty independent of the number of trailing days considered. It is easily adapted to streams.

Additionally, you really should avoid floating-point, not necessarily due to its runtime cost, but its design cost. Or do you have the time and inclination to prove conclusively whether your handling of floating point rounding is right?

I won't go into all the bad habits hackerrank encourages, like using <bits/stdc++.h>, using namespace std;, all the useless copies, ...
If you are interested, it's repeated enough times already.

Answer 3

double Median(vector<int> arr)
Do you realize that you are copying the entire arr when you pass by value? You are doing this in many places. You probably mean to use const vector<int>& at the very least.

int activityNotifications(vector<int> expenditure, int d) {

    int Notices = 0;

    vector<int> SpendData = vector<int>(expenditure.begin(),expenditure.end());

Here you make a full local copy when passing expenditure, and then you copy the whole thing again into SpendData and you do it in an unnecessarily complex way. You could just write: auto SpendData= expenditure; I wonder if you're used to languages that have reference semantics, so you didn't realize that such initialization makes a deep copy? That could be a larger more systemic issue with you.

The use of SpendDataMedian is to delete the first item over and over, appending a different item. Note that this causes the whole thing to be copied down. You should look at a std::deque instead, which directly supports adding or removing from either end, efficiently. But, do you really need to do that? You could have median accept two iterators and work with the sliding window of values, and not need to copy them to a distinct vector of their own. You're missing out on the power of iterators -- think of median as an algorithm that is not limited to a specific type of container.