Finding the number of times the code will generate an alert depending upon whether the transaction is fraudulent

Question

Please refer to this problem from Hackerrank

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 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.

I have written the following code. However, the code is working for some of the test cases and is getting 'terminated due to timeout' for some. Can anyone please tell how can I improve the code?

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the activityNotifications function below.
    static int activityNotifications(int[] expenditure, int d)     {
        //Delaring Variables

        int iterations,itr,length,median,midDummy,midL,midR,               midDummy2,i,i1,temp,count;
        float mid,p,q;
        length = expenditure.length;
        iterations = length-d;
        i=0;
        i1=0;
        itr=0;
        count = 0;

        int[] exSub = new int[d];

        while(iterations>0)
        {

            // Enter the elements in the subarray
            while(i1<d)
            {
                exSub[i1]=expenditure[i+i1];
                //System.out.println(exSub[i1]);
                i1++;
            }

            //Sort the exSub array
            for(int k=0; k<(d-1); k++)
            {
                for(int j=k+1; j<d; j++)
                {
                    if(exSub[j]<exSub[k])
                    {
                        temp = exSub[j];
                        exSub[j] = exSub[k];
                        exSub[k] = temp;
                    }
                }
            }

            //Printing the exSub array in each iteration


            for(int l = 0 ; l<d ; l++)
            {
                System.out.println(exSub[l]);
            }


            i1=0;


            //For each iteration claculate the median

            if(d%2 == 0) // even
            {
                midDummy = d/2;
                p= (float)exSub[midDummy];
                q= (float)exSub[midDummy-1];  
                mid = (p+q)/2;                            
                //mid = (exSub[midDummy]+exSub                                   [midDummy-1])/2;
                //System.out.println(midDummy);
            }
            else // odd
            {

                midDummy2 =d/2;
                mid=exSub[midDummy2];
                //System.out.println(midDummy2);
            }

            if(expenditure[itr+d]>=2*mid)
            {
                count++;
            }
            itr++;
            i++;
            iterations--;

            System.out.println("Mid:"+mid);
            System.out.println("---------");

        }

        System.out.println("Count:"+count);
        return count;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nd = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] expenditure = new int[n];

        String[] expenditureItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int expenditureItem = Integer.parseInt(expenditureItems[i]);
            expenditure[i] = expenditureItem;
        }

        int result = activityNotifications(expenditure, d);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Answer 1

close

You had an opportunity to acquire (and then close) this resource using try-with-resource

private static final Scanner scanner = new Scanner(System.in);

Similarly for this one:

new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

streaming input

You're reading 200,000 numbers here:

    String[] expenditureItems = scanner.nextLine().split(" ");

They won't fit in the lower levels of the cache hierarchy, they are spilling to RAM. Consider reading as you compute. You never need much more than d numbers to be resident at once.

no-op

This doesn't appear to do anything for you. Consider deleting it.

    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

temp var

The compiler optimizes it away, but needlessly introducing a temp variable makes your code harder to read:

        int expenditureItem = Integer.parseInt(expenditureItems[i]);
        expenditure[i] = expenditureItem;

Just phrase it as:

        expenditure[i] = Integer.parseInt(expenditureItems[i]);

Not sure why you wanted to allocate 200,000 strings and then 200,000 ints, when you could have streamed through them one string at a time.

Integer.toString

In addition to needless temp var, it seems you chose to define an inconvenient API:

    int result = activityNotifications(expenditure, d);
    bufferedWriter.write(String.valueOf(result));

You might find it slightly more convenient to write the result if activityNotifications returned Integer.

API

You might have found it convenient to pass in two separate arrays, one containing d entries and the other containing the n - d entries that you have to make decisions on.

Ok, it appears you spend almost no time in main, relative to what activityNotifications consumes.

sort

The pair of nested loops headed by

        //Sort the exSub array

is quite insane. You know d shall be "large".

You have an opportunity to use Arrays.sort() with cost O(d log d), yet you went for the quadratic solution, O(d**2).

printing

I don't understand the comment "Printing the exSub array in each iteration". Why would you want to spend time doing that? Only the return value count is relevant for evaluating your submission. Similarly for your debug print of mid.

algorithm - heap

You (re-)sort d elements every single time. Even though only a single value entered the d-day window, and a single value left. Maintain a heap, at cost of O(log d) for each operation.

algorithm - counting values

Go back and read the problem.

Are expenditures floats of arbitrary precision? No, they are integers.

Can expenditures have arbitrary magnitudes as large as the U.S. debt? No, only two hundred and one distinct values are allowed.

Recall that a median value separates the low half from the high half of the values. Maintain 201 counts, and a circular FIFO list of daily expenditures (or continue using the giant n-entry input array, indexing it d behind today). Increment a count corresponding to today's expenditure, and decrement a count for the day exiting the d-day window. Identify the point at which the sum of the low counts matches the sum of the high counts, that's your median. You can do it in time proportional to 201 (much less than d), or you can choose to do it faster than that by maintaining cumulative sums and remembering what yesterday's median was. Good luck!