Fraudulent Activity Notifications – HackerRank Solution

In this post, we will solve Fraudulent Activity Notifications HackerRank Solution. This problem (Fraudulent Activity Notifications) is a part of HackerRank Problem Solving series.

Solution – Fraudulent Activity Notifications – HackerRank Solution

C++

#include <iostream>
#include <cstdio>

using namespace std;

int arr[200010];
int temp_arr[200010];
int counts[210];

float get_median(int size) {
    int index = 0;
    for (int i = 0; i < 210 ; i++) {
        int count = counts[i];
        while (count--) {
            temp_arr[index++] = i;
            if (index > size/2) { break; }
        }
        if (index > size/2) { break; }
    }
    return size % 2 == 1 ? temp_arr[size/2] : (temp_arr[size/2] + temp_arr[size/2-1])/2.0;
}

int main() {
    int n, d;

    scanf("%d %d", &n, &d);
    for (int i = 0; i < n ; i++) {
        scanf("%d", &arr[i]);
    }

    int alarm_count = 0;
    float median = 210;

    for (int i = 0; i < d ; i++) {
        counts[arr[i]]++;
    }
    median = get_median(d);

    for (int i = d; i < n; i++) {
        if (arr[i] >= 2*median) {
            alarm_count++;
        }

        // update counts array
        counts[arr[i-d]]--;
        counts[arr[i]]++;

        median = get_median(d);
    }

    printf("%d\n", alarm_count);
    return 0;
}

Python

#!/bin/python3

import sys
import bisect as bs

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bs.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def median(a_sorted, days):
    half = len(a_sorted)//2
    
    if days % 2:
        median = a_sorted[half]
    else:
        median = (a_sorted[half-1] + a_sorted[half])/2
        
    return float(median)

def activityNotifications(log, days):
    heap = sorted(log[:days])
    res = 0
    med = 0
    to_del = 0
    
    for ind in range(days, len(log)):
        med = median(heap, days)
        #print("heap: {}".format(heap))
        #print("log[{}] = {} med = {}".format(ind, log[ind], med))
            
        if float(log[ind]) >= 2*med:
            res += 1
        
        #del heap[heap.index(log[to_del])]
        del heap[index(heap, log[to_del])]
        bs.insort(heap, log[ind])
        to_del += 1
            
    return res
        

if __name__ == "__main__":
    n, d = input().strip().split(' ')
    n, d = [int(n), int(d)]
    expenditure = list(map(int, input().strip().split(' ')))
    result = activityNotifications(expenditure, d)
    print(result)

Java

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int d = input.nextInt();
        int notifications = 0;
        Queue<Integer> queue = new LinkedList<>();
        int[] pastActivity = new int[201];
        
        //Wait for d transactions before any notifications
        for(int i = 0; i < d; i++)
        {
            int transaction = input.nextInt();
            queue.offer(transaction);
            pastActivity[transaction] = pastActivity[transaction]+1;
        }
            
        for(int i = 0; i < n-d; i++)
        {
            int newTransaction = input.nextInt();
            
            //Check if fraudulent activity may have occurred
            if(newTransaction >= (2* median(pastActivity, d)))
                notifications++;
                
            //Remove the oldest transaction
            int oldestTransaction = queue.poll();
            pastActivity[oldestTransaction] = pastActivity[oldestTransaction]-1;
            
            //Add the new transaction
            queue.offer(newTransaction);
            pastActivity[newTransaction] = pastActivity[newTransaction]+1;
        }
        
        System.out.println(notifications);
    }
    
    static double median(int[] array, int elements)
    {
        int index = 0;
        
        if(elements % 2 == 0)//Find median of even # of elements
        {
            int counter = (elements / 2);

            while(counter > 0)
            {                
                counter -= array[index];
                index++;
            }
            index--;//Remove extra iteration
            if(counter <= -1)//This index covers both medians
                return index;
            else//(counter == 0) We need to find the next median index 
            {
                int firstIndex = index;
                int secondIndex = index+1;
                while(array[secondIndex] == 0)//Find next non-zero transaction
                {
                    secondIndex++;
                }
                return (double) (firstIndex + secondIndex) / 2.0;//Calculate the average of middle two elements
            }
        }
        else//Find median of odd # of elements
        {
            int counter = (elements / 2);

            while(counter >= 0)
            {
                counter -= array[index]; index++;
            }
            return (double) index-1;
        }
    }
    
    
    static void printArray(int[] array)
    {
        System.out.println("Array");
        for(int i = 0; i < array.length; i++)
        {
            if(array[i] > 0)
                System.out.println(i+" : "+array[i]);
        }
    }
}

Note: This problem (Fraudulent Activity Notifications) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.