Posts Tagged ‘java’
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: java
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: java, threads
Posted in Development, Examples | 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: java
Posted in Interview Questions | No Comments »
Java – deliberately cause OutOfMemoryException
Tuesday, August 4th, 2015
package test;
import java.util.ArrayList;
import java.util.List;
public class OutOfMemory {
public static void main(String[] args) {
final List<String>list = new ArrayList<String>();
int i = 1;
while(true) {
list.add(new String(System.nanoTime()+""));
list.addAll(list);
System.out.println(i+ " " + Runtime.getRuntime().freeMemory());
i++;
}
}
}
After a few seconds should output something like:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:2245)
at java.util.Arrays.copyOf(Arrays.java:2219)
at java.util.ArrayList.grow(ArrayList.java:213)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:187)
at java.util.ArrayList.addAll(ArrayList.java:532)
at test.OutOfMemory.main(OutOfMemory.java:12)
Tags: java
Posted in Interview Questions | No Comments »
Java to XML, XML to Java (Marshalling and Unmarshalling)
Wednesday, July 13th, 2011
Introduction
JDK6 and JAXB2.x (which comes with JDK6) make marshalling Java to XML and unmarshalling XML to Java a snap, almost trivial.
Example
Java to XML
package foo.bar;
import java.math.BigDecimal;
import javax.xml.bind.JAXBContext;
import javax.xml.bind.Marshaller;
public class JavaToXML {
public static void main(String[] args) throws Exception {
JAXBContext context = JAXBContext.newInstance(Product.class);
Marshaller m = context.createMarshaller();
m.setProperty(Marshaller.JAXB_FORMATTED_OUTPUT, true);
Product object = new Product();
object.setCode("WI1");
object.setName("Widget Number One");
object.setPrice(BigDecimal.valueOf(300.00));
m.marshal(object, System.out);
}
}
XML to Java
package foo.bar;
import java.io.File;
import javax.xml.bind.JAXBContext;
import javax.xml.bind.JAXBException;
import javax.xml.bind.Unmarshaller;
public class XMLToJava {
public static void main(String[] args) {
try {
JAXBContext jc = JAXBContext.newInstance(Product.class);
Unmarshaller u = jc.createUnmarshaller();
File f = new File("product.xml");
Product product = (Product) u.unmarshal(f);
System.out.println(product.getCode());
System.out.println(product.getName());
System.out.println(product.getPrice());
} catch (JAXBException e) {
e.printStackTrace();
}
}
}
product.java
Note: the @XmlRootElement is vital here!
package foo.bar;
import java.math.BigDecimal;
import javax.xml.bind.annotation.XmlRootElement;
@XmlRootElement
public class Product {
private String code;
private String name;
private BigDecimal price;
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public BigDecimal getPrice() {
return price;
}
public void setPrice(BigDecimal price) {
this.price = price;
}
}
product.xml
<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<product>
<code>WI1</code>
<name>Widget Number One</name>
<price>300.0</price>
</product>
Tags: java, jaxb, xml
Posted in Examples | 8 Comments »