Pages

HackerRank Fraudulent Activity Notifications

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;
}
  1. Check on the input parameters, not really required in a problem like this one, still I would feel bad not to have them
  2. 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
  3. It is very easy to get the median from an ordered list, just go to the center of it
  4. Loop on all the elements after the initial window
  5. Get the element to be checked for frauds
  6. When it is the case, increase the number of alerts
  7. 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);
    }
}
  1. Collections.binarySearch() assumes the collection is sorted and returns us the index of the element we search in logarithmic
  2. I would never expect this to happen in this class. Still, I could not help to write this check
  3. I needed something like the C++ lower_bound() function. Nothing like that in standard Java, to my knowledge. So I wrote it
  4. 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.

Go to the full post

Heroku Web App Basic setting

Shopping list for setting up a Java EE Web App to be deployed on Heroku.

Assuming Maven, Java 11, Tomcat 9 as web server.

pom.xml: execution

Add to the build - plugins - plugin for maven-dependency-plugin, in the executions

<execution>
<phase>package</phase>
<goals>
  <goal>copy</goal>
</goals>
<configuration>
  <artifactItems>
	<artifactItem>
	  <groupId>com.heroku</groupId>
	  <artifactId>webapp-runner</artifactId>
	  <version>9.0.41.0</version>
	  <destFileName>webapp-runner.jar</destFileName>
	</artifactItem>
  </artifactItems>
</configuration>
</execution>

The element "version" is the Tomcat version we want to use

System properties

Root level, the system.properties should specify the Java version

java.runtime.version=11

Procfile

A one-liner, I split it here to improve readability

web: java $JAVA_OPTS
        -jar target/dependency/webapp-runner.jar
        --port $PORT target/*.war

Go to the full post

HackerRank Array Manipulation

Think of an array of 64-bit integers initialized to zero. It could be quite large, up to ten million elements. We change it applying up to 20 thousand times a series of simple operation: add to all its elements in a specified range an increase that could be in the order of billions. At the end, we want to know the max value in the array.

Please, try it on HackerRank before checking the Java solution here below. It is tagged as hard but, as you get its point, it is not actually so complicated.

The naive solution of applying the required operations just as stated in the problem description would obviously work, but a too high cost. It would be too slow, and a few test cases are bound to fail on a timeout.

We have to be smarter than that, we should avoid modifying all those elements in the array all over again. If you know what a partial sum is, you have already seen the (green) light to this problem.

We could keep track of just the increase and the interval! When asked to add 10 to all the elements between, say, 1_000 and 2_001_000, we could just add 10 to the element 1_000, and then subtract 10 to the element 2_001_001. The elements in the array won't store the actual value but the variation from the previous one.

We just need to do a final single pass on every element to apply the partial sum algorithm to convert our array of variations in an actual array of values, as expected by the user. And then check what is the max in it.

Once the approach is clear, the code is pretty simple.

long[] data = new long[n + 1]; // 1

for(int[] query: queries) { // 2
    data[query[0]-1] += query[2]; // 3
    data[query[1]] -= query[2]; // 4
}

for(int i = 1; i < data.length; i++) { // 5
    data[i] += data[i-1];
}

return LongStream.of(data).max().orElseThrow(); // 6
  1. The caller specify the size of the array as n, it simplify the partial sum algorithm having one element more at the right
  2. Looping on all the queries passed in. First two components are the one-based indeces of the subinterval on which we should apply the change. The third value is the increase
  3. Being one-based, remember to decrease the index
  4. Remember also that we should decrease the first element outside the interval on the right
  5. Unfortunately, I don't know any standard Java functionality to generate the partial sum of an array, like C++ partial_sum() or Python accumulate(). So I did it "by hand"
  6. It is not strictly a necessity using streams here. In any case I guess it is clear what the code means. By the way, orElseThrow() is Java 10, if you want to run this code on Java 8 (as HackerRank asks) you'd better fallback to getAsLong()

Full Java code and relative test case pushed to GitHub.

Go to the full post

Conditionally disabling/enabling JUnit 5 Jupiter test

I have an application that uses JDBC for database connectivity, and I want it configurable for running on Oracle DB, MySql, or SQLite.

As we are well aware, any DBMS is entitled of its own approach to SQL . Testing features in this situation could become complex. Luckly, the new (JUnit 5.7) @DisabledIf and @EnabledIf annotations are here to help us.

Let's see what we can use when we deal with the Jupiter test-disabling features.

If we simply don't want to run a test, we have the @Disabled annotation. Clear and brutal. Here I need something more fine-grained.

OS-based features could be appropriately tested by @EnabledOnOs and @DisabledOnOs. Cool, but this is not the current issue.

The annotation family Enabled/Disabled on JRE are very interesting too, but still not applicable here.

We could set a system property and test it through @DisabledIfSystemProperty (or its Enabled companion). That could do. Still, I won't really have any other use for that property in my application out of testing. I'd prefer not use it.

Even worse with @DisabledIfEnvironmentVariable (and Enabled), that require setting a variable at Operating System level. I don't want that my application required such a wide configuration.

Up to JUnit 5.5, there was a powerful couple of annotations, @DisabledIf and @EnabledIf, that made use of a configurable script engine. Very nice indeed. But they have been cut in 5.6. Damn it. (See Nashorn for more information on this point)

Sometimes They Come Back

Since JUnit 5.7, stripped down to the bone, but @DisabledIf and @EnabledIf are back!

We could pass them just a method name in a string, that should be anyone in the current class or a static method if defined in another class.

The method should return a boolean, not accept any parameter, and, when static and external, it has to be referred to using a notation like "com.example.Conditions#isEncryptionSupported".

It could be worse. It could be rainy.

What I did

I have a configuration file where the user set up a few required properties, among them, the DBMS chosen name, something like

dbms.user=me
dbms.password=password
dbms.name=mysql
dbms.url=jdbc:mysql://localhost:3306/me

Then I have a utility class that access the configuration in its static initializer and makes them available to the application.
In it, and this is the clumsy bit, I provide three static boolean methods to fulfill the requirements.

public abstract class Config {
    // ...

    public static boolean isMySql() {
        return active == Dbms.MYSQL;
    }

    public static boolean isOracle() {
        return active == Dbms.ORACLE;
    }

    public static boolean isSqLite() {
        return active == Dbms.SQLITE;
    }
}

Finally, I let JUnit to decide if it should run a test or not referring to those methods.

So, for instance, I want to disable every test on stored procedure for SQLite because it does not support this feature.

@Test
@DisabledIf("jd.Config#isSqLite")
void getCoderSalaryPlain() throws SQLException {
    // ...

When a feature is supported in a specific way by a given DBMS, I enable a test just for it. This test is specific for MySQL

@Test
@EnabledIf("jd.Config#isMySql")
void getCoderSalaryMissingMySql() throws SQLException {
    // ...

OK, I guess you've got the gist. If you want to see the actual code, you could find it on GitHub. Here is the Configuration class and here a JUnit test case that uses both @DisabledIf and @EnabledIf.

Go to the full post

Creating an executable JAR with Maven

I have a very simple mavenized Java project that results in a JAR, both in its "slim" and "fat" flavor. Here I want to make the result executable and, along the way, get rid of the "slim" one. The expected result is a JAR file that I could run like this
java -jar myApp.jar
To to that, I have to provide a manifest in the JAR, pointing out to the class that should be run. This is a task that is easily done with Maven. It is enough to to add an "archive" element to the maven-assembly-plugin in the build section of the project POM.
<archive>
    <manifest>
        <mainClass>simple.Main</mainClass>
    </manifest>
</archive>
Let's say that I have no use anymore for the "slim" JAR, and I don't want Maven to generate it anymore. I can get this effect disabling the execution for the relevant plugin, maven-jar, setting its phase to nothing.
<plugin>
	<artifactId>maven-jar-plugin</artifactId>
	<version>3.2.0</version>
	<executions>
		<execution>
			<id>default-jar</id>
			<phase />
		</execution>
	</executions>
</plugin>
Now, running the usual maven command, I should get the expected behavior.
mvn clean package
Full code is on GitHub, here is the POM file.

Go to the full post

Test on build with Maven

Let's add some testing to the tiny mavenized Java app seen in the previous couple of posts.

Actually, the app is so tiny that there is that there's nothing to test. This is easily solved, adding a method to the Main class
public static String getLoggerClassName() {
    return LOG.getClass().getName();
}
I plan to use JUnit 5 (aka Jupiter) as testing framework, asserting via Hamcrest, so I add both these dependencies to the POM.
<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter-engine</artifactId>
    <version>5.6.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.hamcrest</groupId>
    <artifactId>hamcrest</artifactId>
    <version>2.2</version>
    <scope>test</scope>
</dependency>
As I said, I plan to use JUnit and Hamcrest for testing only. I don't want to bother the user with them. That's the reason why I signaled to Maven that their scope is test.

Now I write a test for the newly added method
@Test
void getLoggerClassName() {
    String actual = Main.getLoggerClassName();
    assertThat(actual, is("ch.qos.logback.classic.Logger"));
}
I can run it from Eclipse in the usual way, anything works fine.

I build the app with Maven, clean package, and I get both my jars, slim and fat, as before. In both cases without the test dependencies, and that's good. Still, something is missing. Tests are not executed in this phase. Bad. I'd like to check anything works fine when I build my jar.

The issue is in the Maven Surefire Plugin. By default, an ancient version is executed that do not work nicely with JUnit 5. So, I force Maven to use a newer one. It's name is a bit scary, having an M in its version number. M as Milestone. However, it looks like we have to live with it. So I use it.
<plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-surefire-plugin</artifactId>
    <version>3.0.0-M4</version>
</plugin>

Actually, there's no need to specify the group id in this case, since maven plugins is the default. Your choice.

That's it. Now the Maven package build trigger also the execution of the tests. Nice.

I have pushed the full code on GitHub. So, please, check there for details.

Go to the full post

Jar with dependencies through Maven

I'm creating a Java desktop app, a very simple one, see the previous post if you don't believe me, using Maven as build manager. The second step here is adding a dependency, and let Maven build a "fat" jar including them, to ease its deployment.

Say that I just want to use Logback classic in my application. I search for it on MvnRepository, I stay away from the alpha version so I go for 1.2.3.

Given that, modify my pom.xml is mostly a matter of copy and paste. Just remember that any dependency belongs to the dependencies element.
<project ...>
    <!-- ... -->
    <dependencies>
     <dependency>
      <groupId>ch.qos.logback</groupId>
      <artifactId>logback-classic</artifactId>
      <version>1.2.3</version>
     </dependency>
    </dependencies>
</project>
Now I can Logback, and I'm going to do it through SLF4J.
import org.slf4j.Logger;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Main {
    private static final Logger LOG = LoggerFactory.getLogger(Main.class);

    public static void main(String[] args) {
        // ...
        LOG.info("Hello");
    }
}
I run my application in Eclipse, everything goes as expected, getting as console output the required log
14:32:12.986 [main] INFO simple.Main - Hello
Now I run a maven build, as done in the previous post, setting the goals to clean package, and generate a jar.

I run it from the shell in the usual way
java -cp simple-0.0.1-SNAPSHOT.jar simple.Main
And I get a nasty feedback
Exception in thread "main" java.lang.NoClassDefFoundError:
    org/slf4j/LoggerFactory at simple.Main.(Main.java:7)
Caused by: java.lang.ClassNotFoundException: org.slf4j.LoggerFactory
    at java.base/jdk.internal.loader....
    ...
    ... 1 more
However, this is an expected behavior. Maven generates by default a "slim" jar, avoiding to include in it the dependencies. The user has to specify in the classpath where Java has to find them.

When we want to create a "fat" jar, we should say to Maven explicitly to do it. We do that with the Maven Assembly Plugin.

Maven, please, when you build this project, use the maven-assembly-plugin, version 3.3, when packaging. And, remember to build also a "fat" jar with all the dependencies!
<build>
 <plugins>
  <plugin>
   <artifactId>maven-assembly-plugin</artifactId>
   <version>3.3.0</version>
   <executions>
    <execution>
     <phase>
      package
     </phase>
     <goals>
      <goal>single</goal>
     </goals>
    </execution>
   </executions>
   <configuration>
    <descriptorRefs>
     <descriptorRef>jar-with-dependencies</descriptorRef>
    </descriptorRefs>
   </configuration>
  </plugin>
 </plugins>
</build>
Now, when I run the Maven build step, I get both slim and fat jar, here is how I run the latter
java -cp simple-0.0.1-SNAPSHOT-jar-with-dependencies.jar simple.Main
It works fine, so I push the changes on github.

Go to the full post

Simple Maven Eclipse Project

What I'm about to do here is creating a simple desktop app using Apache Maven as build automation tool.

To follow me, ensure you have on your machine:
  1. Java JDK - I use version 11, the currently latest available LTS, but the app is so simple that virtually any JDK will do
  2. Eclipse IDE - Actually, on my machine I have Spring Tool Suite (STS) 4.6, but again, the job is so basic, that almost any Eclipse-based IDE would be alright

From Eclipse, I select the "Maven Project" wizard from "File | New | Project ...", there I go for creating a simple project, skipping archetype selection. Then I have to specify a group and artifact id for my stuff. I enter "dd" as group id and "simple" as artifact id.

The other fields have a good default - so I keep them as suggested and I just push the "Finish" button.

Since I used a very minimal approach, I'm not surprised by the warning in my project. I go straight to my pom.xml to complete it.

I want to set the character set used in my source code, using UTF-8 (strictly not a necessity, still a good idea), and, most importantly, I want to set both the source and target compiler to JDK 11.
I do that specifying these properties inside the project element:
<properties>
    <project.build.sourceEncoding>
        UTF-8
    </project.build.sourceEncoding>
    <maven.compiler.source>
        11
    </maven.compiler.source>
    <maven.compiler.target>
        11
    </maven.compiler.target>
</properties>
Here you can see the full pom.xml.

Theoretically, Eclipse should trigger a project rebuild as you save a change in the Maven configuration file. Unfortunately, this is not what often happens. However, you could force the job by pushing Alt-F5, or right-clicking on the project name in the Project Explorer, then select Maven | Update Project...

I add a plain vanilla class, simple.Main, with a main function to perform the usual hello job and I have the first version of my application.

Now I'd like to use maven to generate my app jar. To do that, I have to specify which goals my maven build target should achieve. I right click on the project folder in the Eclipse Package Explorer, then in the Run as menu I select the "Maven build ..." item. As goals I specify "clean package", meaning that I want to clean everything up, so to recompile all source files and then package them in a jar file.

Now I can run this target. In the console window I see the feedback from Maven until I get the final result, a jar, named in my case simple-0.0.1-SNAPSHOT.jar, has been put in the project target directory.

To see if it works as I expect, I open a shell, go to the target directory, and there I execute the jar:
java -cp simple-0.0.1-SNAPSHOT.jar simple.Main
I'm happy to get back the expected hello message, so I put the project on Github.

Go to the full post

At least one JAR was scanned for TLDs yet contained no TLDs

As soon as I added a jar to my Tomcat base web application, I got this new info log message.
INFO [main] org.apache.jasper.servlet.TldScanner.scanJars
At least one JAR was scanned for TLDs yet contained no TLDs
It makes sense, since it was a JDBC driver, and I would have been very surprised if it contained a TLD.

Let's see how to get rid of it.

Firstly, I read the rest of the logging message
Enable debug logging for this logger for a complete list
of JARs that were scanned but no TLDs were found in them.
Skipping unneeded JARs during scanning can
improve startup time and JSP compilation time.
Actually, I already knew the name of the JAR culprit, since I just added it, so I could have skipped directly to the second step. However, I followed the instructions and ...

Tomcat logging properties

I (temporarily) changed the logging.properties for my Tomcat instance, adding this line
org.apache.jasper.servlet.TldScanner.level = FINE

After that, my log file got more interesting, and I focused my attention to this line.
FINE [main] org.apache.jasper.servlet.TldScanner$TldScannerCallback.scan
No TLD files were found in [... x.jar] Consider adding the
JAR to the tomcat.util.scan.StandardJarScanFilter.jarsToSkip
property in CATALINA_BASE/conf/catalina.properties file.
Very clear indeed.

Tomcat Catalina properties

I easily found the tomcat.util.scan.StandardJarScanFilter.jarsToSkip property in file catalina.properties from my Tomcat configuration folder. It is a longish comma separated string containing a list of JAR that are known not to contain TLD.

I just added the name of my JAR to it, and the case was closed.

Go to the full post

Testing Spring Boot with JUnit5

I decided that is time to move my tests in Spring app from JUnit 4 to Jupiter. It is not too complicated, given that Spring is already supporting JUnit 5, even though the default is still the previous version. However it requires being careful in a couple of steps.

Firstly, I have changed the POM in this way:
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-test</artifactId>
    <scope>test</scope>
    <exclusions>
        <exclusion>
            <!-- get rid of JUnit 4 -->
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
        </exclusion>
    </exclusions>
</dependency>

<!-- using JUnit 5 instead -->
<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter-engine</artifactId>
    <!-- using the version set by Spring -->
    <scope>test</scope>
</dependency>
I have excluded JUnit 4 from the spring-boot-starter-test dependency, and then I have inserted a new dependency for Jupiter, all of them are obviously in the test scope. Notice that I didn't set the version for JUnit 5, accepting instead the one proposed by Spring. Just to stay on the safe side.

The changes in "normal" testing are quite simple, usually limited in using the right imports for the new library. Something a bit more engaging is to be done for Spring Application test. What I had for JUnit 4 was something like this
@RunWith(SpringRunner.class)
@SpringBootTest
public class MyApplicationTests {
    // ...
In Jupiter, however, the annotation RunWith has been replaced with the more powerful ExtendWith, so the code has to be changed to
@ExtendWith(SpringExtension.class)
@SpringBootTest
public class MyApplicationTests {
    // ...
Not too bad, isn't it?

Go to the full post

Another interesting MOOC for Java developer

I've just completed the EdX MOOC Data Structures and Software Design by University of Pennsylvania. I would suggest it to someone with a high-beginner or lower-intermediate experience as Java software developer. I think that the lessons would sound reasonably interesting even if your level is higher, however you could be get a bit bored by the exercises - kind of too simple. This is why I didn't push anything on my GitHub account. To have some fun, I didn't use any IDE, just solved the problems in the old way, using a dumb editor, compiling and running them from command line :D Homework 11 is, in my opinion, the most interesting one in the course. We have to refactor a poorly written, albeit working, piece of code to make it fast enough to match the requirements.

Go to the full post

A nice Java testing MOOC

I've just finished the first week of the MOOC "Automated Software Testing: Practical Skills for Java Developers" provided by TU Delft on EdX. It looks to me they did a good job. Maybe, if you are a native English speaker, the speakers' accent could sometimes sound a bit weird. However, as continental European, I kind of enjoy it (and I know that my Italian accent sounds even funnier).

The course is focused on Java, JUnit 5, using IntelliJ as IDE.

It looks like a brand new production, so be ready to step into typos and minor mistakes here and there. The most annoying of them, is the one in Question 11 on the Quizzes.

We have to write tests to detect where is the bug in a function named mirrorEnds() that sort of detect how much a string is palindromic. Unfortunately, a wrong solution has to be selected to get the point on it!

If you are taking the course, I suggest you to have a look at the discussion forum to get help.

And, if you want to compare your code with mine, please find my forked repository on GitHub.

Go to the full post