2
\$\begingroup\$

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×105
  • 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;
}
\$\endgroup\$
  • \$\begingroup\$ Is % in median = 2 * dq[d%2]; a copy-paste typo? \$\endgroup\$ – vnp Dec 19 '18 at 21:32
  • 3
    \$\begingroup\$ Besides, the algorithm doesn't look correct to me. It may accidentally produce the correct result, but... once dq is sorted, the dq.at(dq_idx) is not the oldest expenditure anymore, so you overwrite the wrong one. \$\endgroup\$ – vnp Dec 19 '18 at 22:02
  • \$\begingroup\$ @vnp: that's correct. it was a typo and I see your point about the sorting... good catch \$\endgroup\$ – tandem Dec 20 '18 at 8:33
1
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Few comments: 1) I started with dq because I wanted to have a fixed size double ended deque, and realised that might not be the cleverest idea from the box. 2) Thanks for the input on split string and readability. I'll improve on that. Let me give a shot to the function I am supposed to write. \$\endgroup\$ – tandem Dec 20 '18 at 19:16
  • \$\begingroup\$ I'll accept it as soon as I get my solution on board. please bear with me. \$\endgroup\$ – tandem Dec 20 '18 at 19:18

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.