Don't be too impressed by its name, this problem boils down to calculating the median for a moving window in a list of integers. It is not conceptually difficult, it just asks some attention in choosing the algorithm, since they are doing some check on the resulting performances. I do suggest you to try it yourself going to Sorting - Fraudulent Activity Notifications on HackerRank and then compare your solution with mine.
The structure of the algorithm is quite simple. Get the initial window from the input list, then loop on all the other elements checking if there is a fraud alert (i.e. calculate the median) and moving the window on. Let's see my result code. Since in these days I'm mainly work in Java, that is the language I've used for the implementation.
public static int activityNotifications(List<Integer> expenditures, int d) {
if (expenditures == null || d == 0 || expenditures.size() <= d) { // 1
return 0;
}
List<Integer> window = new ArrayList<>(expenditures.subList(0, d)); // 2
window.sort(null); // 3
int result = 0;
for (int i = d; i < expenditures.size(); i++) { // 4
Integer current = expenditures.get(i); // 5
if (fraudAlert(window, current)) { // 6
result += 1;
}
move(window, expenditures.get(i - d), current); // 7
}
return result;
}
- Check on the input parameters, not really required in a problem like this one, still I would feel bad not to have them
- Setting up the window, getting the first "d" elements from the input list. I used List.subList() to get them, and I push them in a new list, so that I can work freely on them - remember that subList() returns a view of the original list, and we don't want to mess with it
- It is very easy to get the median from an ordered list, just go to the center of it
- Loop on all the elements after the initial window
- Get the element to be checked for frauds
- When it is the case, increase the number of alerts
- The oldest element goes out of windows, the current one goes in
Good, right?
I don't think there is much to say on the fraudAlert() method, it just calculates the median and performs the check as required by the problem. If you want, please have a look at it on GitHub.
It is interesting the move() method. For performance reasons, we need a way to modify the window in a way that won't require to sort it again from scratch. My first idea was writing a custom selection sort that would take in account all the information we have to reduce its temporal complexity to the minimum. Alas, it didn't work. Besides, the code was getting too unreadable.
So I decided to move in another direction. It easy and cheap (logarithmic) to find the position of an element in a sorted collection - or the position where it should go, if not in.
private static void move(List<Integer> window, Integer exiting, Integer entering) {
int posExit = Collections.binarySearch(window, exiting); // 1
if (posExit == -1) { // 2
throw new IllegalStateException("Can't find " + exiting + " in window");
}
int posEnter = lowerBound(window, entering); // 3
if (posEnter > posExit) { // 4
window.add(posEnter, entering);
window.remove(posExit);
} else if (posExit > posEnter) {
window.remove(posExit);
window.add(posEnter, entering);
} else {
window.set(posExit, entering);
}
}
- Collections.binarySearch() assumes the collection is sorted and returns us the index of the element we search in logarithmic
- I would never expect this to happen in this class. Still, I could not help to write this check
- I needed something like the C++ lower_bound() function. Nothing like that in standard Java, to my knowledge. So I wrote it
- Then it is just a matter of removing and adding values
Since I used an ArrayList, I feared the possibly high number of writes for adding and removing could have a negative impact on performances, and I was ready to think of using a linked list (maybe a custom one) to reduce them. However this solution passed all the test on HackerRank, so I didn't bother.
I don't have much to say on lowerBound(), too. Very close to a "normal" binary search.
Well, that's it. I guess. Here is the link to the class on GitHub.
