[Java] Find if two strings are interleaved

A string is the result of interleaving two other strings if it contains ALL characters from both strings in the same order as they appear in the source strings. When determining which character to place in the interleaved string, it is possible to choose each time 0+ characters from either string!

ABACCA is the interleaving of ABC and ACA -> AB, A, C, CA
ABACAC is also the interleaving of ABC and ACA -> AB, AC, A, C
ABAACC is NOT the interleaving of ABC and ACA -> AB, A, we expect now a C but find an A instead

The 0+ choice makes things a bit hard, contrarily to the O(N) case where we could pick only 1 character from each string at a time.
It means we might create the result string in more than one way and need therefore to examine all the possibilities before returning our verdict.


[Java] 0/1 knapsack problem with dynamic programming

Some time ago we saw a good heuristic for the 0/1 knapsack problem, but it was a heuristic and as the testing demonstrate, there are cases where the optimal solution is missed.

The only way to determine the actual optimal solution is to consider all possibilities and therefore compute a 2D (or more, depending on the constraints) matrix which we would later scan to identify which items have been chosen to reach the computed optimal solution.
The matrix rows indicate the items and the columns indicate all weights from 0 up to the maximum bag capacity.


[Java] Maximise alternate picks on array - dynamic programming

Last time we saw how to find the maximum achievable value in a situation where two players alternate in picking items from an array boundaries. Solution works, but runs in O(2^N) which becomes quickly unacceptable.

If we introduce a bit more complexity, we can take that time and space down to O(N^2), which is still not awesome but definitely better than before. The key is to track calculations that have already been done to reuse those values later on; this translates in us keeping a matrix of size 2xN^2 where for each player we track the best pick at a specific point in time. When we get to evaluate that pick again, if the result is already cached, we can simply return it and avoid extra function calls.

This performance change can be easily tracked by keeping a global counter starting at 0 and increasing it by 1 at the beginning of the helper function. At the end of the algorithm we will see the total number of functions calls for both methods.

You can check my implementation of getMaxGoldFromPots on my Gist alongside some test cases in GoldPotsJTests.

Note: The test cases are exactly the same, therefore to try either approach simply rename the function calls in the JUnit tests.


[Java] Maximise alternate picks on array

Here's a simple game: gold pots with different amounts of coins are placed in a single line. Two players alternate in choosing one pot to pick from either side.
Find the maximum amount of gold a player can get.

And the solution is intuitive enough with only a big gotcha: while the game progresses, the same player does NOT always pick, therefore he will have turns where his total does NOT increase AND he is left with the WORST choice for the next turn.

This translates into a recursive algorithm where Math.max and Math.min are our friends. We must carefully track which player would get to pick during recursion and adapt the branching on PICK + MAX or only MIN depending on whose turn is it. The base case is when a single pot is left - and even here we must check for whose turn it is!

For complexity, since we are deciding between two options at each step, we get a scary O(2^N) time and space due to the stack recursion.

You can find my implementation of getMaxGoldFromPotsNoDP on my Gist alongside some test cases in GoldPotsJTests.

A slightly more complex solution that has overall better performance O(N^2) can be found in getMaxGoldFromPots instead.


[Java] Loop over digits in a number

Well of course we could just convert the number to String and take it up from there, but since we're real men who know about the modulo operator, we can instead do:

 while(number > 0) {  
  digit = number % 10;
  number /= 10; //discard the digit and advance to the next spot  

And would also be careful to declare number as a copy of our input number so as not to destroy it.

[Java] Count number of bits set to 1 in a byte type

Some more Java byte type related fun, how to count the number of bits set to 1 in a given byte.

 public int count(){  
  int tot = 0;  
  for(byte b = 0b00000001; b != 0b00000000; b = (byte)(b << 1)){  
   if((b & res) == b) tot++;  
  return tot;  

We can loop over it with some gotchas:
  • properly initialize our loop variable as byte value: 0bVALUE and set the rightmost bit to 1, using the same length as our byte variable we want to test
  • break the loop at 0b0, which is when we overflow with the shift
  • convert back to byte with a cast the result of << operation
  • check if the bit is set with a bitwise AND operation first

[Java] Set a specific bit in a byte type

First of all let's start by saying that quite counter intuitively, Boolean in Java is not a single bit but either a 32 or 64 bit entity while a boolean[] uses a byte for each element :)

Now that the shock is passed, let's see how to set a specific bit in a byte object:

 public void set(int bit){  
  byte b = (byte)(1 << (bit - 1));  
  res |= b;  

Assuming res is our byte variable. And yes, the cast is there since the shift operation << returns an int, therefore it must be cast back to byte type, otherwise the bitwise OR would later fail!

And the -1 is of course because we start with position 0 on the right. Note that using the bitwise OR will set the bit ONCE and never revert it back!