In this post, we will solve HackerRank Fraudulent Activity Notifications Problem Solution.
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 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.
Given the number of trailing days d and a client’s total daily expenditures for a period of n days, determine the number of times the client will receive a notification over all n days.
Example
expenditure [10, 20, 30, 40, 50]
d = 3
On the first three days, they just collect spending data. At day 4. trailing expenditures are [10, 20, 30]. The median is 20 and the day’s expenditure is 40. Because 40 > 2 x 20, there will be a notice. The next day, trailing expenditures are [20, 30, 40] and the expenditures are 50. This is less than 2 x 30 so no notice will be sent. Over the period, there was one notice sent.
Note: The median of a list of numbers can be found by first sorting the numbers ascending.
If there is an odd number of values, the middle one is picked. If there is an even number of
values, the median is then defined to be the average of the two middle values.
Function Description
Complete the function activityNotifications in the editor below.
activityNotifications has the following parameter(s):
- int expenditure[n]: daily expenditures
- int d: the lookback days for median spending
Returns
- int: the number of notices 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 respectively.
The second line contains n space-separated non-negative integers where each integer i
denotes expenditure[i].
Output Format
Sample Input 0
STDIN Function ----- -------- 9 5 expenditure[] size n =9, d = 5 2 3 4 2 3 6 8 4 5 expenditure = [2, 3, 4, 2, 3, 6, 8, 4, 5]
Sample Output 0
2Explanation 0
Determine the total number of notifications the client receives over a period of n = 9 days. For the first five days, the customer receives no notifications because the bank has insufficient transaction data: notifications = 0.
On the sixth day, the bank has d = 5 days of prior transaction data, {2, 3, 4, 2, 3}, and median = 3 dollars. The client spends 6 dollars, which triggers a notification because 6 > 2× median: notifications = 0+1=1.
On the seventh day, the bank has d = 5 days of prior transaction data, {3, 4, 2, 3, 6}, and median = 3 dollars. The client spends 8 dollars, which triggers a notification because 8 > 2x median: notifications = 1+1=2.
On the eighth day, the bank has d = 5 days of prior transaction data, {4, 2, 3, 6, 8}, and median = 4 dollars. The client spends 4 dollars, which does not trigger a notification because 4 < 2 × median: notifications = 2.
On the ninth day, the bank has d = 5 days of prior transaction data, {2, 3, 6, 8, 4}, and a transaction median of 4 dollars. The client spends 5 dollars, which does not trigger a notification because 5 < 2 x median: notifications = 2.
Sample Input 1
5 4
1 2 3 4 4
Sample Output 1
0There are 4 days of data required so the first day a notice might go out is day 5. Our trailing expenditures are [1, 2, 3, 4] with a median of 2.5 The client spends 4 which is less than
2 x 2.5 so no notification is sent.
Fraudulent Activity Notifications C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int needNotify(int *arr, int *expendCount, int date, int medianIndex, int isOdd) {
int doubleMedian = 0;
int count = 0;
int newcount = 0;
for(int i = 0; i<201; i++) {
if (expendCount[i]>0) {
newcount = count + expendCount[i];
if (newcount >= medianIndex+1) {
if (doubleMedian == 0)
doubleMedian = i * 2;
else
doubleMedian += i;
break;
} else if (!isOdd && newcount >= medianIndex) {
doubleMedian = i;
}
count = newcount;
}
}
if (arr[date] >= doubleMedian)
return 1;
return 0;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int totalDays = 0;
int minDays = 0;
int fraudNotify = 0;
scanf("%d", &totalDays);
scanf("%d", &minDays);
int transactions[totalDays];
int expendCount[201];
int medianIndex = minDays/2;
int isOdd = minDays%2;
int checkStart = 0;
for(int i = 0; i < totalDays; i++)
scanf("%d", &transactions[i]);
memset(expendCount, 0, sizeof(int)*201);
if (totalDays > minDays) {
for(int i = 0; i < minDays; i++) {
expendCount[transactions[i]] ++;
}
for(int i = minDays; i < totalDays; i ++, checkStart++) {
fraudNotify += needNotify(transactions, expendCount, i, medianIndex, isOdd);
if (i < totalDays) {
expendCount[transactions[checkStart]] --;
expendCount[transactions[i]] ++;
}
}
}
printf("%d", fraudNotify);
return 0;
}Fraudulent Activity Notifications C++ Solution
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int, int>>> vvpii;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, d;
cin >> n >> d;
bool odd = d % 2 == 1;
multiset<int, greater<int>> low;
multiset<int> high;
low.insert(-1000);
high.insert(1000);
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> b(a.begin(), a.begin()+d);
sort(b.begin(), b.end());
for (int i = 0; i < d; i++) {
if (i < (d+1)/2) {
low.insert(b[i]);
} else {
high.insert(b[i]);
}
}
int median; // scaled median
if (odd) {
median = *(low.begin())*2;
} else {
median = (*(low.begin()) + *(high.begin()));
}
int ans = 0;
for (int i = d; i < n; i++) {
int newa = a[i];
int olda = a[i-d];
if (newa >= median) ans++;
if (olda <= *(low.begin())) {
low.erase(low.find(olda));
} else {
high.erase(high.find(olda));
}
if (newa <= *(low.begin())) {
low.insert(newa);
} else {
high.insert(newa);
}
if (odd) {
if (low.size() < high.size()) {
low.insert(*(high.begin()));
high.erase(high.begin());
} else if (low.size()-high.size() == 3) {
high.insert(*(low.begin()));
low.erase(low.begin());
}
median = *(low.begin())*2;
} else {
if (low.size() < high.size()) {
low.insert(*(high.begin()));
high.erase(high.begin());
} else if (low.size() > high.size()) {
high.insert(*(low.begin()));
low.erase(low.begin());
}
median = *(low.begin()) + *(high.begin());
}
}
cout << ans << endl;
return 0;
}Fraudulent Activity Notifications C Sharp Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FraudulentActivityNotifications
{
class Program
{
static void Main(string[] args)
{
Int32 result = 0;
Int32[] data = Console.ReadLine().Split(' ').Select(e => Int32.Parse(e)).ToArray();
Int32 n = data[0];
Int32 d = data[1];
Int32[] workArray = new Int32[201];
Boolean even = d % 2 == 0 ? true : false;
String testString = Console.ReadLine();
Int32[] expen = testString.Split(' ').Select(e => Int32.Parse(e)).ToArray();
for (Int32 i = 0; i < d; i++)
{
workArray[expen[i]]++;
}
for (Int32 i = d; i < n; i++)
{
Int32 doubledMedian = GetSquaredMedian(workArray, d - 1, even);
if (doubledMedian <= expen[i])
{
result++;
}
workArray[expen[i - d]]--;
workArray[expen[i]]++;
}
Console.WriteLine(result);
}
static Int32 GetSquaredMedian(Int32[] workArr, Int32 lastIndex, Boolean even)
{
Int32 result = 0;
Int32 median = lastIndex / 2;
Int32 countedElems = workArr[0];
Int32 cnt = 0;
while (countedElems - 1 < median)
{
cnt++;
countedElems += workArr[cnt];
}
if (!even)
{
result = cnt * 2;
}
else
{
if (countedElems - 1 > median)
{
result = cnt * 2;
}
else
{
result = cnt;
cnt++;
while (workArr[cnt] == 0)
{
cnt++;
}
result += cnt;
}
}
return result;
}
}
}Fraudulent Activity Notifications Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'activityNotifications' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY expenditure
* 2. INTEGER d
*/
public static int activityNotifications(List<Integer> expenditure, int d) {
int cont = 0;
int acum=0;
int tempIndex = d-1;
List<Integer> tmpExp2 = expenditure.subList(cont, d).stream().sorted().collect(Collectors.toList());
for (int i = d; i < expenditure.size(); i++) {
if(expenditure.get(i)>=median(tmpExp2)) {
acum++;
}
if (expenditure.get(i) == expenditure.get(i-d)) {
continue;
}
int rmIndex = Collections.binarySearch(tmpExp2, expenditure.get(i-d));
tmpExp2.remove(rmIndex);
tempIndex = Collections.binarySearch(tmpExp2, expenditure.get(i));
if (tempIndex < 0) {
tempIndex = (-1 * tempIndex) -1;
}
tmpExp2.add(tempIndex, expenditure.get(i));
cont++;
}
return acum;
}
public static int median(List<Integer> tmpExp2) {
if (tmpExp2.size() % 2 == 0) {
return (int) (((tmpExp2.get((tmpExp2.size() / 2) - 1) + (tmpExp2.get(tmpExp2.size() / 2)))));
} else {
return ((tmpExp2.get(tmpExp2.size() / 2))*2);
}
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int d = Integer.parseInt(firstMultipleInput[1]);
List<Integer> expenditure = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.activityNotifications(expenditure, d);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}Fraudulent Activity Notifications JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function activityNotifications(expenditure, d) {
// Complete this function
var start = d;
var c = 0;
var buffer = [];
var counts = [];
function count(val) {
if (!counts[val]) {
counts[val] = 1;
} else {
counts[val]++;
}
}
function uncount(val) {
counts[val]--;
}
function median() {
if (d % 2 === 0) {
var middle = Math.floor(d / 2);
var counter = 0;
var a = -1
for (var i = 0; i < counts.length; i++) {
counter += counts[i] ? counts[i] : 0;
if (counter === middle || middle < counter) {
if (a === -1)
a = i;
}
if (counter === middle + 1 || middle + 1 < counter ) {
return (i + a) / 2;
}
}
} else {
var middle = Math.floor(d / 2);
var counter = 0;
for (var i = 0; i < counts.length; i++) {
counter += counts[i] ? counts[i] : 0;
if (counter > middle) {
return i;
}
}
throw new Error('unexpected no median');
}
}
for (var i = 0; i < expenditure.length; i++) {
var exp = expenditure[i];
if (i >= d) {
var m = median();
if (expenditure[i] >= m * 2) {
c++;
}
}
count(exp);
buffer.push({
i,
exp,
});
if (i >= d) {
uncount(buffer.shift().exp);
}
}
return c;
}
function main() {
var n_temp = readLine().split(' ');
var n = parseInt(n_temp[0]);
var d = parseInt(n_temp[1]);
expenditure = readLine().split(' ');
expenditure = expenditure.map(Number);
var result = activityNotifications(expenditure, d);
process.stdout.write("" + result + "\n");
}Fraudulent Activity Notifications Python Solution
# https://www.hackerrank.com/challenges/fraudulent-activity-notifications
from __future__ import print_function
try: input = raw_input
except: pass
import heapq
class MaxHeapObj(object):
def __init__(self,val): self.val = val
def __lt__(self,other): return self.val > other.val
def __eq__(self,other): return self.val == other.val
def __str__(self): return str(self.val)
class MinHeap(object):
def __init__(self): self.h = []
def heappush(self,x): heapq.heappush(self.h,x)
def heappop(self): return heapq.heappop(self.h)
def __getitem__(self,i): return self.h[i]
def __len__(self): return len(self.h)
class MaxHeap(MinHeap):
def heappush(self,x): heapq.heappush(self.h,MaxHeapObj(x))
def heappop(self): return heapq.heappop(self.h).val
def __getitem__(self,i): return self.h[i].val
class RollingMedian(object):
# shift from a->b, until nb->ntgt, keep only entries >= minage
# and remove any old entries from b
@staticmethod
def _shift_heaps(a,b,nb,ntgt,minage):
while len(b) > 0 and b[0][1] < minage: b.heappop()
while nb < ntgt:
x = a.heappop()
if x[1] >= minage:
b.heappush(x)
nb += 1
def __init__(self,dist):
self.l,self.r = MaxHeap(),MinHeap()
self.nl = self.nr = 0 # size of heaps
self.hist = [None]*dist
self.idx = 0
def add(self,x,i):
old = self.hist[self.idx]
self.hist[self.idx] = (x,i)
self.idx = (self.idx+1)%len(self.hist)
if old is not None:
if len(self.l) > 0 and old[0] <= self.l[0][0]: self.nl -= 1
else: self.nr -= 1
if self.nl == 0 or x <= self.l[0][0]:
self.l.heappush((x,i))
self.nl += 1
else:
self.r.heappush((x,i))
self.nr += 1
tot = self.nl+self.nr
nr = tot//2
nl = tot - nr
minage = i-len(self.hist)+1
# print("add()",len(self.l),len(self.r),self.nl,self.nr,nl,nr,"minage:",minage)
RollingMedian._shift_heaps(self.l, self.r, self.nr, nr, minage)
RollingMedian._shift_heaps(self.r, self.l, self.nl, nl, minage)
self.nl,self.nr = nl,nr
# print(" ",nl,nr)
def median(self):
# print("median()",len(self.l),len(self.r),self.nl,self.nr)
if len(self.l) == 0: return None
return (self.l[0][0]+self.r[0][0])/2.0 if self.nl==self.nr else self.l[0][0]
n,k = (int(x) for x in input().strip().split(' '))
l = [int(x) for x in input().strip().split(' ')]
rm = RollingMedian(k)
alerts = 0
for i,x in enumerate(l):
med = rm.median()
rm.add(x,i)
# print(i,x,med)
alerts += (i >= k and x >= med*2)
print(alerts)Other Solutions
