We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Fraudulent Activity Notifications
  5. Discussions

Fraudulent Activity Notifications

Sort by

recency

|

1179 Discussions

|

  • quangluan0305201
     + 0 comments

    include

    using namespace std;

    int test(const vector &a, int n, int d) { int res = 0; vectorb(a.begin(), a.begin() + d); sort(b.begin(), b.end()); for(int i = d; i < n; i++) { int sum = 0; if(d % 2 == 1) { sum = 2 * b[d / 2]; } else { sum = b[d / 2] + b[d / 2 - 1]; } if(a[i] >= sum) { res++; } b.erase(lower_bound(b.begin(), b.end(), a[i - d])); b.insert(lower_bound(b.begin(), b.end(), a[i]), a[i]); } return res; }

    int main() { int n, d; cin >> n >> d; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } cout << test(a, n, d) << endl; return 0; }

  • logan_schultheis
     + 0 comments

    Python3 using bisect library

    from bisect import bisect, insort
def activityNotifications(expenditures, d):
    res = 0
    vals = sorted(expenditures[:d])
    for first_val, cur_val in zip(expenditures, expenditures[d:]):    
        if d % 2:
            median2 = 2 * vals[d//2]
        else:
            median2 = vals[d//2] + vals[d//2-1]
        if cur_val >= median2:
            res += 1
        vals.pop(bisect(vals, first_val) - 1)
        insort(vals, cur_val)
    return res

  • agentkaumal88
     + 0 comments

    C#

    public static int activityNotifications(List<int> expenditure, int d)
{
    var totalNotifications = 0;
    int[] frequency = new int[201]; // Create a frequency array.

    if (expenditure.Count > d)
    {
        for (int i = 0; i < d; ++i)
        {
            frequency[expenditure[i]]++;
        }

        for (int i = d; i < expenditure.Count; i++)
        {
            var median = GetMedian(frequency, d);

            if (expenditure[i] >= 2 * median)
            {
                totalNotifications++;
            }

            frequency[expenditure[i - d]]--; // Remove element from the frequency.
            frequency[expenditure[i]]++; // Add element to the frequency.
        }
    }

    return totalNotifications;
}

public static double GetMedian(int[] frequency, int d)
{
    var sum = 0;
    double median = 0;

    if (d % 2 == 1)
    {
        var mid = d / 2;
        for (int i = 0; i < frequency.Length; ++i)
        {
            sum += frequency[i];
            if (sum > mid)
            {
                median = i;
                break;
            }
        }
    }
    else
    {
        var mid1 = d / 2 - 1;
        var mid2 = d / 2;
        int median1 = -1, median2 = -1;

        for (int i = 0; i < frequency.Length; ++i)
        {
            sum += frequency[i];
            if (sum > mid1 && median1 == -1)
            {
                median1 = i;
            }
            if (sum > mid2)
            {
                median2 = i;
                median = (median1 + median2) / 2.0;
                break;
            }
        }
    }

    return median;
}

  • Georve
     + 1 comment

    i did this solution: but only 5/8. what is wrong?

    public static int activityNotifications(List expenditure, int d) { int counter=0; int sum=0;

        for(int i=0;i<d;i++){
        sum+=expenditure.get(i);
    }
    for(int i=d; i<expenditure.size();i++){
        double avg=(double)sum/d;
        if(expenditure.get(i)>=2*avg){
            counter++;
        }

        sum-=expenditure.get(i-d);
        sum+=expenditure.get(i);

    }
   return counter;
}

  • yonatanimm
     + 0 comments

    Java 8 Solution

    public static int activityNotifications(List<Integer> expenditure, int d){
        final int size = expenditure.size();
        if(d>=size){
            return 0;
        }
        
        int notifications = 0;
        List<Integer> dList =  expenditure.subList(0,d).stream().sorted().collect(Collectors.toList());
        for(int i=d; i<size; i++){
            int doubledMedian = getDoubledMedian(dList);
            int current = expenditure.get(i);
            if(current >= doubledMedian){
                notifications++;
            }
            Integer firstDay = expenditure.get(i-d);
            dList.remove(firstDay);
            addItemToSortedList(dList, current);
            firstDay = current;  
        }
        return notifications;
    }
    
    final static int getDoubledMedian(List<Integer> sortedList){
        final int size = sortedList.size();
        final int index = size/2;
        if(size%2 != 0){
            return 2*sortedList.get(index);
        }
        return sortedList.get(index-1) + sortedList.get(index);
    }
    
    final static void addItemToSortedList(List<Integer> dList, int newItem){
        int index = Collections.binarySearch(dList, newItem);
        if(index < 0){
            dList.add(-(index+1),newItem);
            return;
        }
        dList.add(index,newItem);
    }