Gretchen and the Play solution from Indeed Contest on hackerrank.com

This was one of the tougher challenges on hackerrank.com because the solution had to run under 4s time limit. I had to do a lot of optimization for this one. I had to switch from using Java 8 to Java 7 which for some reason ran much faster and didn't time out on some of the cases.

Any comments on the solution and coding style would be greatly appreciated.


Problem Statement



Gretchen is directing a new play with \$M\$ scenes performed by \$N\$ actors,
where each actor only appears in exactly one scene. To ensure that the
distribution is perfect, she performs the following actions:


Assign actor \$Ni\$ to scene \$Mi\$. Count the number of scenes having less
than \$P\$ actors assigned to them. Given a list of actions, determine the
distribution of actors in Gretchen's play.


Input Format


The first line contains three space-separated integers, \$M\$, \$N\$, and \$Q\$,
respectively; \$M\$ is the number of scenes, \$N\$ is the number of actors,
and \$Q\$ is the number of actions Gretchen plans to perform. \$N\$ and \$M\$ use
zero-based indexing.


The second line contains \$N\$ space-separated integers; the \$ith\$ integer
represents the scene, \$Mi\$, that actor \$Ni\$ is initially assigned to.


The \$Q\$ subsequent lines describe Gretchen's actions; each of these
lines starts with an integer, \$A\$, which corresponds to Action 1 or
Action 2 (as detailed in the Problem Statement).


When \$A=1\$ (Action 1), it will be followed by two space-separated
integers, \$Ni\$ and \$Mi\$, respectively; this action says to assign actor \$Ni\$
to scene \$Mi\$.


When \$A=2\$ (Action 2), it will be followed by a single integer, \$P\$; this
action says to count the number of segments having \$<P\$ actors assigned
to them.


Note: All Action 1 actions are permanent, so each Action 1 affects all
future actions.


Constraints:

\$1≤M,N,Q≤105\$

\$0≤Mi≤M−1\$

\$0≤Ni≤N−1\$

\$1≤P≤N\$


O

Method decomposition

The single biggest issue is that all the logic is in a single main method.
It's really hard to see what it's doing,
and there's gotta be a way to break it down to smaller pieces,
smaller methods, corresponding to the logical steps.

actorsAssigmentsArray

This is a String[], created by splitting an input line, and then later parsing the values to integers. But the parsing happens later. It's difficult to follow the logic of the code, when you do some partially (getting the numbers as a String[]) and finish the remaining part of the task later. The logical flow would be much clearer to just create an int[] and be done with it.
In fact, this makes a good candidate for the first helper method to extract from main:

private int[] readActorsAssignments(Scanner scanner, int numOfActors) {
    int[] actorsAssignments = new int[numOfActors];
    for (int i = 0; i < numOfActors; ++i) {
        actorsAssignments[i] = scanner.nextInt();
    }
    return actorsAssignments;
}

Notice the numOfActors. It's ironic that in your code this variable exists in main, but it was actually unused. Now it has a purpose (no accident), when calling this method. In main, you can replace this:

String[] actorsAssigmentsArray = sc.nextLine().split(" ");

with this:

int[] actorsAssignments = readActorsAssignments(sc, numOfActors);

Notice the readability improvement. The correct use of type, int[] instead of String[] leads to other improvements. For example, this:

int prevPos = Integer.parseInt(actorsAssigmentsArray[actNum]);
int pos = sc.nextInt();
actorsAssigmentsArray[actNum] = ""+pos;

becomes the much cleaner:

int prevPos = actorsAssignments[actNum];
int pos = sc.nextInt();
actorsAssignments[actNum] = pos;

Iterate over elements, not indexes

In this loop:

for(int i = 0;i<actorsAssigmentsArray.length;i++){
    int scenePos = Integer.parseInt(actorsAssigmentsArray[i]);
    // ...

You don't really need the index variable i.
You need just the elements.
Together with the improvements in the previous point,
this loop becomes much simplified and natural:

for (int scenePos : actorsAssignments) {
    // ...

Another helper method

Looking at the comment in the first for-loop:

//load the scenes map and cachedsearch map

Hm, that sounds like a clear logical step, something that could fit nicely in a helper method:

private void loadScenesAndCachedSearch(
        int[] actorsAssignments, Map scencesMap, Map cachedSearchMap) {

    for (int scenePos : actorsAssignments) {
        Integer numActorsInScene = scencesMap.remove(scenePos);
        if (numActorsInScene != null) {
            scencesMap.put(scenePos, numActorsInScene + 1);
            Integer prvSmValue = cachedSearchMap.get(numActorsInScene + 1);
            if (prvSmValue != null) {
                cachedSearchMap.put(numActorsInScene + 1, prvSmValue + 1);
            } else {
                cachedSearchMap.put(numActorsInScene + 1, 1);
            }

            Integer smValue = cachedSearchMap.remove(numActorsInScene);
            if (smValue != null && smValue > 1) {
                cachedSearchMap.put(numActorsInScene, smValue - 1);
            }

        } else {
            scencesMap.put(scenePos, 1);
            Integer smValue = cachedSearchMap.get(1);
            if (smValue != null) {
                cachedSearchMap.put(1, smValue + 1);
            } else {
                cachedSearchMap.put(1, 1);
            }
        }
    }
}

A few interesting things to note here:

• No more need for the comment: the method name expresses the same thing

• The numActorsInScene variable that used to be outside the loop is now inside. That's a good thing. There was no need for it outside, it really belonged in this scope.

Unnecessary boxing and object creation

Instead of this:

Integer one = new Integer(1);

You can write simply:

Integer one = 1;

It's not only about simplicity. The new keyword always creates a new object. If you let the compiler to autobox, it can optimize, for example reuse an immutable instance with the value of 1. Avoid creating objects when you don't really need them.

Also, there's no need for this variable. "one" means 1, so you can just write 1. If it means something else, because for example it might take on a different value in a later evolution of your program, then it should have a different name instead of "one", to avoid misleading.

The diamond operator <>

As of Java 7, you can simplify expressions like this:

HashMap scencesMap = new HashMap();

Using the diamond operator <> like this:

HashMap scencesMap = new HashMap<>();

Declare variables and methods using interface types

It's recommended to think in terms of interfaces than concrete implementations. For example here:

HashMap scencesMap = new HashMap<>();

It doesn't really matter for your implementation that it's a hash

StackExchange Code Review Q#114039, answer score: 7