In this HackerRank Fraudulent Activity Notifications Interview preparation kit you have 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.
Problem solution in Python programming.
from bisect import bisect_left, insort_left
n, d = map(int, input().split())
t = list(map(int, input().split()))
noti = 0
lastd = sorted(t[:d])
def med():
return lastd[d//2] if d % 2 == 1 else ((lastd[d//2] + lastd[d//2-1])/2)
for i in range(d, n):
if t[i] >= 2*med():
noti += 1
del lastd[bisect_left(lastd,t[i-d])]
insort_left(lastd, t[i])
print(noti)Problem solution in Java Programming.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main implements Runnable {
int[] cnt;
int med(int d) {
int[] a = Arrays.copyOf(cnt, cnt.length);
int r = d / 2;
if (d % 2 == 1) {
r++;
}
int res = 0;
boolean odd = d % 2 == 1;
for (int k = 0; k <= 200; k++) {
while (r > 0 && a[k] > 0) {
a[k]--;
r--;
}
if (r == 0) {
res += k;
if (d % 2 == 0) {
d--;
r++;
if (a[k] > 0) {
return 2 * k;
}
} else {
break;
}
}
}
return res * (odd ? 2 : 1);
}
void solve() throws IOException {
int n = nextInt();
int d = nextInt();
cnt = new int[201];
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
for (int i = 0; i < d; i++) {
cnt[a[i]]++;
}
int res = 0;
for (int i = d; i < n; i++) {
int m = med(d);
//out.println(m);
if (a[i] >= m) {
res++;
}
cnt[a[i - d]]--;
cnt[a[i]]++;
}
out.print(res);
}
BufferedReader br;
StringTokenizer st;
PrintWriter out;
public void run() {
try {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
br.close();
out.flush();
out.close();
} catch (Exception e) {
e.printStackTrace();
System.exit(123);
}
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String s = br.readLine();
if (s == null)
return null;
st = new StringTokenizer(s);
}
return st.nextToken();
}
double nextDouble() throws IOException {
return Double.parseDouble(next());
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws IOException {
return Long.parseLong(next());
}
public static void main(String[] args) {
new Thread(new Main()).start();
}
}Problem solution in C++ programming.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define MAXE 210
int A[200010];
int F[MAXE];
int median2(int D) {
int p = 0;
for (int i = 0; i < MAXE; i++) {
p += F[i];
if (p * 2 > D) {
return 2 * i;
} else if (p * 2 == D) {
for (int j = i + 1; ; j++) {
if (F[j]) {
return i + j;
}
}
}
}
return -1;
}
int main() {
int N, D;
cin >> N >> D;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
int result = 0;
for (int i = 0; i < N; i++) {
if (i >= D) {
if (A[i] >= median2(D)) {
++result;
}
F[A[i - D]]--;
}
F[A[i]]++;
}
cout << result << endl;
return 0;
}Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int compfunc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int findPos (int *arr, int len, int val) {
if (val >= *(arr+len-1))
return len-1;
if (val <= *arr)
return 0;
int dis = len/2;
int pos = dis-1;
while (dis > 1) {
dis = (dis+1)/2;
if (*(arr+pos) > val)
pos -= dis;
else if (*(arr+pos) < val)
pos += dis;
else return pos;
}
return pos;
}
void removeAndAdd(int *arr, int len, int val1, int val2) {
int pos1 = findPos(arr, len, val1);
int pos2 = findPos(arr, len, val2);
if (pos1 < pos2)
memmove(arr+pos1, arr+pos1+1, (pos2-pos1)*sizeof(int));
else if (pos1 > pos2)
memmove(arr+pos2+1, arr+pos2, (pos1-pos2)*sizeof(int));
*(arr+pos2)=val2;
}
int main() {
int n, d;
scanf("%d %d", &n, &d);
int *arr = (int *) calloc(n, sizeof(int));
int *arrcpy = (int *) calloc(d, sizeof(int));
int counter=0;
for (int i=0; i<d; i++)
scanf("%d", arr+i);
memcpy(arrcpy, arr, d*sizeof(int));
qsort(arrcpy, d, sizeof(int), compfunc);
for (int i=d; i<n; i++) {
int medianx2;
scanf("%d", arr+i);
medianx2 = *(arrcpy+(d-1)/2) + *(arrcpy+(d-1)/2+(d+1)%2);
if (*(arr+i) >= medianx2)
counter++;
removeAndAdd(arrcpy, d, *(arr+i-d), *(arr+i));
}
printf("%d\n", counter);
return 0;
}Problem solution in JavaScript programming.
function processData(input) {
var arrIn = input.split('\n');
var currLine = 0;
var TOTAL = 0, MEDIAN = 1;
var days = arrIn[currLine++].split(' ').map(function(x) { return parseInt(x); });
var numFraudDays = days[MEDIAN];
var exps = arrIn[currLine++].split(' ').map(function(x) { return parseInt(x); });
var notifs = 0;
var compare_fn = function(a, b) {
return a - b;
};
//console.log(days);
//console.log(exps);
var expDays = [...exps.slice(0, days[MEDIAN])];
expDays.sort(function(a, b) { return a - b; });
//console.log(expDays);
//console.log('....TESTING....');
for ( let i = days[MEDIAN]; i < days[TOTAL]; ++i ) {
//process.stdout.write('old expDays=');
//console.log(expDays);
// get median for even
let med = 0;
if ( numFraudDays % 2 === 0 ) {
med = (expDays[days[MEDIAN]/2] + expDays[(days[MEDIAN]/2)-1]);
// get median for odd
} else {
med = expDays[Math.trunc(days[MEDIAN]/2)]*2;
}
// test if this day is greater than median and get notified
if ( exps[i] >= med ) {
notifs++;
// if ( days[MEDIAN] % 2 === 0 ) {
// console.log('med['+days[MEDIAN]/2+','+(days[MEDIAN]/2-1)+']=('+
// expDays[days[MEDIAN]/2]+' + '+expDays[(days[MEDIAN]/2)-1]+
// ')/2 = '+med);
// } else {
// console.log('med['+Math.floor(days[MEDIAN]/2)+']='+
// expDays[Math.floor(days[MEDIAN]/2)]);
// }
//console.log('med='+med+', i='+i+', exps[i]='+exps[i]);
//console.log('notifs='+notifs);
//process.stdout.write('new expDays=');
//console.log(JSON.stringify(expDays));
//console.log('');
}
// update expDays, no need to sort... binary search where the new number goes
// remove the last val of the original
var index = binarySearch(expDays, exps[i-numFraudDays], compare_fn);
expDays.splice(index, 1);
let val = exps[i];
if ( val <= expDays[0] ) {
expDays.unshift(val);
} else if ( val > expDays[expDays.length-1] ) {
expDays.push(val);
} else {
// binary search where to put new value
let result = binarySearch(expDays, val, compare_fn);
//console.log('val='+val+', result='+result);
if ( result >= 0 ) {
// value was found, insert into index result
expDays.splice(result, 0, val);
} else {
// value wasn't found, insert into -m -1 return from binarySearch
expDays.splice(-(result+1), 0, val);
}
}
//console.log('med='+med+', i='+i+', exps[i]='+exps[i]);
//console.log('notifs='+notifs);
//process.stdout.write('new expDays=');
//console.log(expDays);
//console.log('');
}
console.log(notifs);
}
function binarySearch(ar, el, compare_fn) {
var m = 0;
var n = ar.length - 1;
while ( m <= n ) {
var k = ( n + m ) >> 1;
var cmp = compare_fn(el, ar[k]);
if ( cmp > 0 ) {
m = k + 1;
} else if ( cmp < 0 ) {
n = k - 1;
} else {
return k;
}
}
return -m - 1;
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
0 Comments