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

Question

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\$

Output Format

For each Action 2, print the number of scenes having <P actors on a new line.

Sample Input

  5 5 6
  0 1 2 3 4
  2 2
  1 0 2
  2 2
  2 1
  1 3 1
  2 2

Sample Output

5 4 1 3

I don't think i can post the link to the contest because you will have to join the contest to see the challenges.

Here is the code:

import java.io.*;
import java.util.*;

public class GretchenAndPlay {


    public static void main(String[] args) {

        Integer one = new Integer(1);
        Scanner sc = new Scanner(System.in);

        int numOfScenes  = sc.nextInt();
        int numOfActors = sc.nextInt();
        int numOfActions = sc.nextInt();
        sc.nextLine();

        String[] actorsAssigmentsArray = sc.nextLine().split(" ");
        HashMap<Integer,Integer> scencesMap = new HashMap<Integer,Integer>();  //stores number of actors for a specific scene

        //cachedSearchMap stores the amount of scenecs have certain amount of actors
        //For example there are 2 scences with 3 actors, 5 scences with 1 actor
        //They keys are in sorted ordered so they can be itterated to find out count the number of scenes having <P actors

        TreeMap<Integer,Integer> cachedSearchMap = new TreeMap<Integer,Integer>(); 
        Integer numActorsInScene = 0;

        for(int i = 0;i<actorsAssigmentsArray.length;i++){
            //load the scenes map and cachedsearch map
            int scenePos = Integer.parseInt(actorsAssigmentsArray[i]);
            numActorsInScene = scencesMap.remove(scenePos);
            if(numActorsInScene != null){

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

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

            }else{
                scencesMap.put(scenePos,one);
                Integer smValue = cachedSearchMap.get(one);
                if(smValue != null){
                    cachedSearchMap.put(one, smValue+1);
                }else{
                    cachedSearchMap.put(one,one);
                }
            }
        }
        for(int i = 0; i < numOfActions;i++)
        {

            int actionType = sc.nextInt();
            if(actionType == 2 ){
                int actorsCount = sc.nextInt();

                    int total = 0;
                    //itterates through search tree to sum up the scences that have <P actors
                    for(Integer num : cachedSearchMap.keySet()){
                        if(num < actorsCount){
                            total+=cachedSearchMap.get(num);
                        }else {
                            break;
                        }
                    }
                    int scenesWithOutActors = numOfScenes - scencesMap.size();
                    System.out.println(""+(total+scenesWithOutActors));


            }else if(actionType == 1){
                int actNum = sc.nextInt();

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

                int prevNumActors = scencesMap.remove(prevPos);

                    if(prevNumActors > 1){
                        scencesMap.put(prevPos,prevNumActors-1);
                    }

                //moving actors from one scene to another will require to update cachedSearchMap and add count to 
                //actors new position and subctract one from previous
               Integer prvNumValue = cachedSearchMap.remove(prevNumActors);
                if(prvNumValue != null && prvNumValue > 1){
                    cachedSearchMap.put(new Integer(prevNumActors),prvNumValue-1);
                }


               if((prevNumActors-1) > 0 ) {
                   Integer prvNumActorsOneVal = cachedSearchMap.get(prevNumActors-1);

                   if(prvNumActorsOneVal != null){
                       cachedSearchMap.put(new Integer(prevNumActors-1), prvNumActorsOneVal+1);
                   }else{
                       cachedSearchMap.put(new Integer(prevNumActors-1), one);
                   }
                }
                Integer posNumValue = scencesMap.get(pos);
                int posNumActors = 1;
                if(posNumValue != null){
                    scencesMap.put(pos, posNumValue+1);
                    posNumActors = posNumValue+1;
                }else{
                    scencesMap.put(pos, one);
                }

                Integer smValue = cachedSearchMap.remove(posNumActors-1);
                if(smValue != null && smValue > 1){
                    cachedSearchMap.put(new Integer(posNumActors-1),smValue-1); 
                }
                smValue = cachedSearchMap.get(posNumActors);
                if(smValue != null){
                    cachedSearchMap.put(new Integer(posNumActors), smValue+1);
                }else{
                    cachedSearchMap.put(new Integer(posNumActors), one);
                }
            }

        }
    }
}

Gretchen And Play Solution on Github

Answer 1

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<Integer, Integer> scencesMap, Map<Integer, Integer> 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<Integer,Integer> scencesMap = new HashMap<Integer,Integer>();

Using the diamond operator <> like this:

HashMap<Integer, Integer> 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<Integer, Integer> scencesMap = new HashMap<>();  

It doesn't really matter for your implementation that it's a hash map. Any other map would do. So use a map:

Map<Integer, Integer> scencesMap = new HashMap<>();  

The same goes here:

TreeMap<Integer,Integer> cachedSearchMap = new TreeMap<Integer,Integer>();

What you need is a sorted map, it doesn't really matter whether the sorting is implemented using trees or something else, so use the interface type:

SortedMap<Integer,Integer> cachedSearchMap = new TreeMap<>();

Answer 2

Your code could use some improvement:

---

Whitespace:

Sometimes you are missing whitespace, like in the following:

for(int i = 0;i<actorsAssigmentsArray.length;i++){

or in the following:

---

Convert to ternaries:

You have a few things that could be converted to ternaries:

            if(smValue != null){
                cachedSearchMap.put(one, smValue+1);
            }else{
                cachedSearchMap.put(one,one);
            }

into:

cachedSearchMap.put(one, smValue != null
    ? smValue + 1
    : one
);

---

new Integer:

Your usage of the variable new Integer() is a little bit inconsistent:

Some places you use it, and some places you don't.

---

one:

Is there a reason you really want to be sure it's 1?

Is passing 1 into the functions directly not enough?

---

cachedSearchMap:

You're reusing cachedSearchMap a lot, consider using a function and processing the array operations there, and then simply calling it when necessary in your code.

---

General Commments:

You have a lot of duplicate logic that could probably be moved to an function, not to mention the logic should be broken down into connected parts instead a hige massive whole.