Java solution for “Longest Increasing Subsequence”

Thursday, December 10th, 2020

The Problem

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

My solution

This is what I came up with (albeit in a short timeframe); it’s not the best or most efficient!

Main.java

package com.lstierneyltd.examples;

public class Main {
    public static void main(String[] args) throws Exception {
        final LongestIncreasingSubsequenceSolver solver =
                new LongestIncreasingSubsequenceSolver();


        solver.init(new int[]{10, 22, 9, 33, 21, 50, 41, 60});
        solver.solve(); // 5

        // Van der Corput sequence
        solver.init(new int[]{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15});
        solver.solve(); // 6

    }
}

LongestIncreasingSubsequenceSolver.java

package com.lstierneyltd.examples;

import java.util.ArrayList;
import java.util.List;
public class LongestIncreasingSubsequenceSolver {
    private int inputLength;
    private List<Integer> sequence;
    private List<Integer> input;

    public void init(final int[] inputArray) {
        inputLength = inputArray.length;
        input = new ArrayList<>(inputLength);
        sequence = new ArrayList<>(inputLength);

        int i;
        for (i = 0; i < inputLength; i++) {
            input.add(inputArray[i]);
        }

        for (i = 0; i < inputLength; i++) {
            sequence.add(i, 1);
        }
    }

    public void solve() {
        int i, j, max = 0;

        for (i = 1; i < inputLength; i++) {
            for (j = 0; j < i; j++) {
                if (input.get(i) > input.get(j) && sequence.get(i) < sequence.get(j) + 1) {
                    sequence.set(i, sequence.get(j) + 1);
                }
            }
        }
        for (i = 0; i < inputLength; i++) {
            if (max < sequence.get(i)) {
                max = sequence.get(i);
            }
        }
        System.out.println("The Longest Subsequence length was: " + max);
    }
}

Tags:
Posted in Interview Questions | No Comments »

Java CompletionService example

Friday, December 4th, 2020

Main.java

package com.lstierneyltd;

public class Main {
    public static void main(String[] args) throws Exception {
        final CompletionServiceExample completionServiceExample = new CompletionServiceExample();
        completionServiceExample.runDemo();
    }
}

CompletionServiceExample.java

package com.lstierneyltd;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

public class CompletionServiceExample {
    private static final int NUMBER_OF_THREADS = 3;
    private final List<Callable<String>> callables = new ArrayList<>();
    private final ThreadPoolExecutor threadPoolExecutor = (ThreadPoolExecutor) Executors.newFixedThreadPool(NUMBER_OF_THREADS);

    public CompletionServiceExample() {
        initCallables();
    }

    public void runDemo() throws Exception {
        final long startTime = System.currentTimeMillis();

        processCallableTasks();

        System.out.println("That took " + (System.currentTimeMillis() - startTime)/1000 + " seconds");

        shutdownThreadPoolExecutor();
    }

    private Callable<String> getCallable(int id) {
        final Callable<String> callable = () -> {
            System.out.println("Starting Callable " + id);
            final long taskStartTime = System.currentTimeMillis();

            TimeUnit.MILLISECONDS.sleep(10000);

            System.out.println("CallableTask " + id + " took " + (System.currentTimeMillis() - taskStartTime)/1000 + " seconds");

            return "Callable completed";
        };
        return callable;
    }

    private void initCallables() {
        callables.add(getCallable(1));
        callables.add(getCallable(2));
        callables.add(getCallable(3));
    }

    private void processCallableTasks() throws InterruptedException, ExecutionException {
        final CompletionService<String> completionService = new ExecutorCompletionService<String>(threadPoolExecutor);

        for(Callable<String> callable : callables) {
            completionService.submit(callable);
        }

        int received = 0;
        while(received < NUMBER_OF_THREADS) {
            Future<String> resultFuture = completionService.take(); // blocks if none available
            String result = resultFuture.get();
            System.out.println("Future done " + result);
            received++;
        }
    }

    private void shutdownThreadPoolExecutor() {
        threadPoolExecutor.shutdown();
        try {
            if (!threadPoolExecutor.awaitTermination(800, TimeUnit.MILLISECONDS)) {
                threadPoolExecutor.shutdownNow();
            }
        } catch (InterruptedException e) {
            threadPoolExecutor.shutdownNow();
        }
    }
}

Output

Starting Callable 1
Starting Callable 2
Starting Callable 3
CallableTask 3 took 10 seconds
CallableTask 1 took 10 seconds
CallableTask 2 took 10 seconds
Future done Callable completed
Future done Callable completed
Future done Callable completed
That took 10 seconds

Tags: ,
Posted in Development, Examples | No Comments »

Linux: Cowsay and Fortune

Sunday, October 4th, 2020

So I got a “new” laptop which onto which I’ve installed Ubuntu 20.04 LTS (Focal Fossa).

What’s the first thing I needing done? Docker? Node? Even plain old Java? Nope, Cowsay and Fortune!

Takes my login from

:~$

to

 ___________________________________
/ Be security conscious -- National \
\ defense is at stake.              /
 -----------------------------------
       \   ^__^
        \  (oo)\_______
           (__)\       )\/\
               ||----w |
               ||     ||
:~$

Oh and…

:~$ tail -1 ~/.bashrc
fortune -s | cowsay

Tags: ,
Posted in quick tips | No Comments »

Liferay StructureNameException when importing Lar file

Friday, November 2nd, 2018

Note: I’m no Liferay expert, in fact I’ve only been using it for a few days on a customers legacy system (Liferay 6.1.1) so YMMV.

The Problem

I was trying to import a “LAR” file (a compressed archive like a JAR which holds exported data/pages from a [different] Liferay instance). Problem was every time I tried the import I got a:

StructureNameException

This appears to have been caused by the fact that the exported files contained in the LAR were referring to locales that the importing server was not set-up to use:

<root available-locales="en_US,en_GB" default-locale="en_US">

(in this case my server was only set up to use en_US)

The Solution

In portal-ext.properties edit the following property to add the “missing” locales:

locales=en_US,en_GB

Tags:
Posted in Misc | No Comments »

Java – deliberately cause Deadlock

Tuesday, August 4th, 2015

Another interview question.

When this code is executed runnable1 will wait for a lock on “b” and runnable2 will wait for a lock on “a”.

package test;
/**
 * Deliberately try and cause deadlock
 * 
 */
public class DeadLockTest {
    public static void main(String[] args) {
    	final Object a = new Object();
        final Object b = new Object();
 
        final Runnable runnable1 = new Runnable() {
            public void run() {
                synchronized (a) {
                    try {
                        Thread.sleep(100); // Adding delay to increase chance of deadlock
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    
                    synchronized (b) { // We already have "a" abut need "b" too
                        System.out.println("In runnable1");
                    }
                }
            }
        };
 
        final Runnable runnable2 = new Runnable() {
            public void run() {
                synchronized (b) { // Has "b" but needs "a"
                    synchronized (a) {
                        System.out.println("In runnable2");
                    }
                }
            }
        };
 
        new Thread(runnable1).start();
        new Thread(runnable2).start();
    }
}

Tags:
Posted in Interview Questions | No Comments »