Discussion on Fraudulent Activity Notifications Challenge

Sort by

recency

|

1187 Discussions

|

2 weeks ago+ 0 comments

My Kotlin version, which sorts the first d elements once, and then adopts binary search to remove/insert old/new elements as the window slides;

fun insertInSortedList(items: MutableList<Int>, newElement: Int) {
    val index = items.binarySearch(newElement).let { if (it < 0) -it - 1 else it }
    items.add(index, newElement)
}

fun removeItemFromSortedList(sortedList: MutableList<Int>, item: Int) {
    val index = sortedList.binarySearch(item)
    if (index >= 0) {
        sortedList.removeAt(index)
    }
}

fun median(values: List<Int>): Double {
    if (values.isEmpty()){
        return 0.0
    }
    return if (values.size % 2 == 0) {
        (values[values.size / 2-1] + values[values.size/2])/2.0

    } else {
        values[values.size/2].toDouble()
    }
}

fun activityNotifications(expenditure: Array<Int>, d: Int): Int {
    var numberOfNotifications = 0
    var startIndex = 0
    var valueToCheckIndex = d
    var sublist = expenditure.slice(startIndex..valueToCheckIndex-1).sorted().toMutableList()
    while (valueToCheckIndex < expenditure.size) {
        val m = median(sublist)
        val valueToCheck = expenditure[valueToCheckIndex]
        if (valueToCheck >= 2*m) {
            ++numberOfNotifications
        }
        removeItemFromSortedList(sublist, expenditure[startIndex])
        insertInSortedList(sublist, expenditure[valueToCheckIndex])
        ++startIndex
        ++valueToCheckIndex
    }
    return numberOfNotifications
}

1 month ago+ 0 comments

public static int activityNotifications(List expenditure, int d) { int notifications = 0; int[] count = new int[expenditure.stream().max(Integer::compareTo).get() + 1];

    for (int i = 0; i < d; i++) {
        count[expenditure.get(i)]++;
    }

    for (int i = d; i < expenditure.size(); i++) {
        double median = getMedian(count, d);

        if (expenditure.get(i) >= 2 * median) {
            notifications++;
        }

        count[expenditure.get(i - d)]--;
        count[expenditure.get(i)]++;
    }

    return notifications;
}

private static double getMedian(int[] count, int d) {
    int sum = 0;
    int mid1 = -1, mid2 = -1;
    boolean even = d % 2 == 0;
    int mid = d / 2;

    for (int i = 0; i < count.length; i++) {
        sum += count[i];

        if (even) {
            if (mid1 == -1 && sum >= mid)
                mid1 = i;
            if (mid2 == -1 && sum >= mid + 1) {
                mid2 = i;
                return (mid1 + mid2) / 2.0;
            }
        } else {
            if (sum > mid)
                return i;
        }
    }
    return 0;
}

2 months ago+ 0 comments

Similar to @coswaldors53 solution, the idea revolves around being limited to 200. If we maintain an array of the count of previous expenditures, to find the median we need to check at most 200 values for each expenditure, giving .

We need to find the two indices where the median will lie - this will be , where we shift one to the right if is even. Then, we can sweep across the array to see when the number of values visited reaches this point. If we reach this point, then we know that we have found the index where the median lies.

def activityNotifications(expenditure, d):
    hist = [0] * 200
    med_l = med_r = math.ceil(d / 2)
    if d % 2 == 0:
        med_r += 1
        
    for i in range(d):
        hist[expenditure[i]] += 1
    
    ans = 0  
    for i in range(d, len(expenditure)):
        events = 0
        curr_l = curr_r = -1
        for j in range(200):
            if curr_l == -1 and events + hist[j] >= med_l:
                curr_l = j
            if curr_r == -1 and events + hist[j] >= med_r:
                curr_r = j
            if curr_l != -1 and curr_r != -1:
                break
            events += hist[j]
 
        if expenditure[i] >= curr_l + curr_r:
            ans += 1
        hist[expenditure[i]] += 1
        hist[expenditure[i - d]] -= 1
        
    return ans

3 months ago+ 1 comment

Python solution:

def activityNotifications(expenditure, d):
    # Write your code here
    notifications=0
    
    current_count=[0 for i in range(max(expenditure)+1)]
    
    for n in expenditure[:d]:
        current_count[n]+=1
    
    for i,e in enumerate(expenditure[d:]):
        
        cum_sum=0
        for j,m in enumerate(current_count):
            cum_sum+=m
            if cum_sum>d//2:
                median=j
                break
            elif cum_sum==d/2:
                for k,l in enumerate(current_count[j+1:]):
                    if l!=0:
                        median=(j+(k+j+1))/2
                        break
                break
        print(median,e)
        if e>=(2*median):
            notifications+=1
            
        current_count[e]+=1
        current_count[expenditure[i]]-=1
            
            
    return notifications

View Thread

4 months ago+ 0 comments

JS:

function findIndex(array, element) {
  let firstIndex = 0;
  let lastIndex = array.length - 1;
  let indexOfElement;

  while (firstIndex <= lastIndex) {
    const middleIndex = Math.floor((firstIndex + lastIndex) / 2);
    if (array[middleIndex] === element) return middleIndex;

    if (array[middleIndex] > element) {
      lastIndex = middleIndex - 1;
      indexOfElement = middleIndex;
    } else {
      firstIndex = middleIndex + 1;
      indexOfElement = firstIndex;
    }
  }

  return indexOfElement;
}

function activityNotifications(expenditure, d) {
  let notifications = 0;
  const sorted = expenditure.slice(0, d).sort((a, b) => a - b);

  for (let i = d; i < expenditure.length; i++) {
    const median =
      d % 2 === 1
        ? sorted[Math.floor(d / 2)]
        : (sorted[d / 2 - 1] + sorted[d / 2]) / 2;
    if (expenditure[i] >= 2 * median) notifications += 1;

    sorted.splice(findIndex(sorted, expenditure[i - d]), 1);
    sorted.splice(findIndex(sorted, expenditure[i]), 0, expenditure[i]);
  }

  return notifications;
}

Sort by

|

1187 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge