18/04/2018

[Java] Find k-th smallest element in BST

We saw how to find the second biggest element in a BST, now let's invert the search and look for the k-th smallest element instead.

We could do this operation in O(N) time by doing a preorder traversal of the tree and counting the elements visited so far, but this would not be taking advantage of the BST property. Since we know that, we can instead extend the Node definition to add a new value: leftSize. Each node now tracks the number of items in its left subtree, therefore allowing us to take advantage of the BST property while searching for the K-th smallest element.

The idea is as follows:
  • the smallest element is K = 1 and will definitely sit all the way on the left
  • nodes that do not have a left subtree have a leftSize of 0
  • an element is exactly in position K only when its leftSize + 1 = K

Now, to use the BST property we need to decide where to redirect the search in case the property above does not hold for the current node. Imagining the tree nodes listed sequentially we can easily figure out that:
  • if K <= leftSize of the current node, then we need to walk down the left subtree of this node. There are many nodes smaller than the current one, therefore we should search there.
  • otherwise we have to walk down the right subtree of this node BUT we also need to adjust the value of K to K - 1 - leftSize of the current node before doing the recursive call on that subtree. This is because we know the current node (-1) and all the other nodes on the left subtree (-leftSize) can be discarded since they are in a position smaller than the requested K in the preorder traversal of the tree so we need to search in the remaining ones sitting on the right subtree. We basically convert the problem to finding the (K - already checked elements)-th smallest element in a new tree rooted at the first right child of the current node.
If none of the above conditions can be met, then K is bigger than the total tree size, therefore we should return null or throw an exception.

You can check my implementation of getKthSmallestElement on my Gist alongside some test cases in BSTJTests.

And bonus: Order statistic trees already implement this feature by design :)

09/04/2018

[Java] Reverse words in char array

Given an array of characters representing a text with words separated by a single space, reverse the text. Eg:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

should read "my test case" in output.

This can be done in constant O(1) space by handling the array in place and in O(N) time.

The idea is to reverse the full array first, then find each word (they are delimited by a space) and reverse them in place again. So:

{'c', 'a', 's', 'e', ' ', 't', 'e', 's', 't', ' ', 'm', 'y'}

becomes

{'y', 'm', ' ', 't', 's ', 'e', 't', ' ', 'e', 's', 'a', 'c'}

and finally

{'m', 'y', ' ', 't', 'e', 's', 't', ' ', 'c', 'a', 's', 'e'}

The key point is to track where did we arrive with each word reversal so that we actually keep the runtime linear, I would say it is exactly 3N, once for reversing the full array, once for scanning the array while finding the delimiters and once for reversing each word starting and ending at the marked indexes.

You can check my implementation of reverseWords on my Gist alongside some test cases in ReverseWordsJTests.

[Java] Find second largest element in BST

Easy question: given a BST, find the second largest element in there.

This can be done in many ways, the most efficient one uses constant O(1) space and O(N) worst case time (tree is unbalanced).

The idea is to walk the tree until we find the biggest element (the one all the way to the right), then check if that node has children. If not, then the second biggest must be his parent; if yes, then the second biggest node is in the left subtree, all the way to the right there. If no right node exists, then it is the left children of the biggest node we found.

My implementation uses the parent pointers, but this can be done all the same without it, by simply tracking an additional node during the looping.

You can check my implementation of getSecondBiggestElement on my Gist along with some test cases in BSTJTests.

22/03/2018

[Windows] Blood Bowl 2 offline league manager

If you are a fan of Blood Bowl and purchased either Blood Bowl 2 or Blood Bowl 2: Legendary Edition on PC, you might be - as many others - extremely disappointed at the lack of an offline (hotseat) league option.

This command line tool provides capability to edit - AT YOUR OWN RISK - the SQLite database where team and player information is stored so that, with a bit of paper tracking, you can update the stats after a friendly match.

This tool is not a cheat/trainer!, it only allows you to edit offline team data, much like the "Custom team" feature of the Legendary Edition, except that feature is only usable at team creation.
This tool is based on the rules found in the Blood Bowl Living Rulebook version 6 and might NOT reflect the actual rules implemented in the game - yet, since I saw some rule tables in the DB, and need to investigate further there..

This tool is an alpha version!, it works without hiccups - but its a barebone tool with some open todos and limitations and the user experience can be further improved, but it works as a starting point if you, like me, crave this feature! :)

You can find the BBManager project on my GitHub and download the compiled jar as well.

Please refer to the project README to find out how to use the tool.

05/03/2018

[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!

Eg:
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.

03/03/2018

[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.

27/02/2018

[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.