HackerRank: Fraudulent activity notification

Question

I wanted to get some constructive feedback on my solution to the Fraudulent Activity Notification problem from HackerRank:

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 2× 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.

Given the number of trailing days d and a client's total daily expenditures for a period of n days, find and print the number of times the client will receive a notification over all n days.

For example, d = 3 and expenditures = [10, 20, 30, 40, 50]. On the first three days, they just collect spending data. At day 4, we have trailing expenditures of [10, 20, 30]. The median is 20 and the day's expenditure is 40. Because 40 ≥ 2 × 20, there will be a notice. The next day, our trailing expenditures are [20, 30, 40] and the expenditures are 50. This is less than 2 × 30 so no notice will be sent. Over the period, there was one notice sent.

Input Format

The first line contains two space-separated integers n and d, the number of days of transaction data, and the number of trailing days' data used to calculate median spending. The second line contains n space-separated non-negative integers where each integer i denotes expenditure[i].

Constraints

• 1 ≤ n ≤ 2×10⁵
• 1 ≤ d ≤ n
• 0 ≤ expenditure[i] ≤ 200

I believe having the a sort in there in raising the timeout for some problems. How would you solve it without a sort? Sorting while inserting has a much higher complexity...

#include <bits/stdc++.h>
#include <array>

using namespace std;

vector<string> split_string(string);

// Complete the activityNotifications function below.
int activityNotifications(vector<int> expenditure, int d) {
  int result=0;
  int dq_idx=0;
  double median=0;
  vector<int> dq;
  for (int i =0; i< expenditure.size()-1; i++){
    if (dq_idx >= dq.size()){
      dq.push_back(expenditure[i]);
    }else {
      dq.at(dq_idx) = expenditure[i];
    }
    dq_idx=(dq_idx+1) %d;

    if (dq.size()>=d){
      sort(dq.begin(), dq.end());
      if (d %2 ==0){
        median = 2* (dq[d/2 -1 ] + dq[(d/2)])/2;
      }else {
        median = 2 * dq[d%2];
      }
      if ((float)expenditure[i+1] >= median) {
        result++;
      }
    }
  }
  return result;
}

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

    string nd_temp;
    getline(cin, nd_temp);

    vector<string> nd = split_string(nd_temp);

    int n = stoi(nd[0]);

    int d = stoi(nd[1]);

    string expenditure_temp_temp;
    getline(cin, expenditure_temp_temp);

    vector<string> expenditure_temp = split_string(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;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Answer 1

Bad Habits

I'd get out of the habit of including bits/stdc++.h as it's non-standard and makes your compile times much longer than they need to be. Especially with such a short program.

Likewise, using namespace std can lead to problems and should be avoided.

Naming

You should use clearer variable and function names. The function name activityNotifications() sounds like it could be presenting the user with notifications. Or it could be processing activity notifications. Instead it's counting them. It might be better named countActivityNotifications().

Within the function, you have a few good variable names. Namely, median and results. I have no idea what dq stands for, which means I also have no idea what dq_idx stands for (beyond that it's an index for dq). expenditure is singular, but it holds multiple expenditures, so I'd make the name plural. d is unhelpful as well. Just because the problem description named the variables n and d doesn't mean your code should use those names. They should be numberOfExpenditureDays and numberOfTrailingDays. (If you prefer num to number and removing Of, that's fine.)

Simplify

You don't need to sort the expenditures. You can get the median by generating a histogram and finding the middle value. A histogram is just an array where each element is the number of times that value was in the input. So a histogram of expenditures would hold the count of how many expenditures were for 1 dollar, and 2 dollars, and 3 dollars, etc. Since the expenditures are between 0 and 200 dollars each, you would have 200 buckets in your histogram. Furthermore, since you're dealing with trailing days, once you have the first one calculated, you can simply update 2 values on each subsequent pass. (Decrement the expenditure from the day that's falling off the array and increment the one that's being added in.)

Your split_string() function goes to a lot of trouble to clean the string before you tokenize it. But you don't need to. You can simply not add empty strings to the results. Something like this:

void split(const std::string& s, std::vector<std::string>& results)
{
    size_t lastPos = 0;
    size_t nextPos = 0;
    while ((nextPos = s.find(" ", lastPos)) != std::string::npos)
    {
        std::string word = s.substr(lastPos, nextPos - lastPos);
        if (!word.empty()) {
            results.push_back(word);
        }
        lastPos = nextPos + 1;
    }

    if (lastPos != std::string::npos)
    {
        std::string word = s.substr(lastPos, std::string::npos);
        if (!word.empty())
        {
            results.push_back(word);
        }
    }
}

I had to read your function several times to realize what it was trying to do with std::unique(), std::string::erase(), and std::string::pop_back().

Readability

The activityNotifications() function is really hard to read due to the odd, inconsistent spacing it uses. I recommend a space before and after every operator to make it more clear. So this line, for example:

dq_idx=(dq_idx+1) %d;

is more readable when written like this:

dq_idx = (dq_idx + 1) % d;