[Java] Useful keytool commands

Keytool is a tool to manage Java keystores. Here are some useful commands to:

• generate a new key and place it in a keystore:

keytool -genkey -keystore myKeystore.jks -storepass myPass -alias myKey -keyalg RSA -sigalg SHA256withRSA -keysize 2048 -validity 3650 -ext ku=digitalSignature

• verify the content of a keystore:

keytool -list -keystore myKeystore.jks -storepass myPass -v

• export the public key:

keytool -exportcert -keystore myKeystore.jks -storepass myPass -alias myAlias -rfc -file myPubKey.cer

• delete a key:

keytool -delete -alias myAlias -keystore myKeystore.jks -storepass myPass

• add a private key:

keytool -importkeystore -srckeystore myKeystore.jks -srcstorepass myPass -srcalias myAlias -destkeystore myNewKeystore.jks -deststorepass myNewPass -deststoretype JKS -destalias myNewAlias

• add a public key:

keytool -import -noprompt -alias myAlias -keystore myKeystore.jks -file myPubKey.cer -storepass myPass

[Ubuntu] Revert kernel back to older version

Intro story: So much luck in a single day.

I always keep only 2 kernel versions after every update, so that I can boot back if something goes wrong. This usually helps, except today I decided to upgrade my Ubuntu from 16.04 to 18.04 since I like spending my nights fixing stuff after unnecessary upgrades, but hey, the future is there.

So I first fully updated my current installation (1st kernel bump), then migrated to the new one (2nd kernel bump) and it turns out I got two 4.15 kernels, with only different minor version.

Double interesting, my wireless card:

02:00.0 Network controller: Realtek Semiconductor Co., Ltd. RTL8821AE 802.11ac PCIe Wireless Network Adapter

apparently has issues (read: bug) with kernel 4.15 preventing it from working at all (not even connected to the router), and even more interesting, on one version it can actually only connect to websites under google.com domain..

Anyway, quick fix was to revert back my kernel, here is how for future me to remember:

1. go to http://kernel.ubuntu.com/~kernel-ppa/mainline/ and download in the same folder: linux-headers-VERSION-generic-XXX_SYSTEM.deb, linux-headers-VERSION_all.deb, linux-image-VERSION-generic-XXX_SYSTEM.deb for your system, eg I have 64 bit system and got amd64 files
2. install them by going into the folder where you downloaded them, make sure there are only those three .deb files and run: sudo dpkg -i *.deb
3. restart the system, then press SHIFT at boot to enter the GRUB choices, then check from the top line (number 0) to the line of your kernel version. If your installation has the "Advanced" menu entry and does not display all kernels, go there and do the same counting. We need this to set a default GRUB entry to always boot in this kernel
4. edit /etc/default/grub and change the value of GRUB_DEFAULT to the number you counted OR to (exactly as shown) "1>N" if you have the "Advanced" menu option. This means you want to boot into the Nth entry (starting from 0) under the "Advanced" menu. Also set GRUB_TIMEOUT to some value in seconds that's more than 1, to have some time to block the boot process in case of mistakes
5. run sudo update-grub and you are set

Note that this is a TEMPORARY fix, you would not want to have a fully updated system run on an older version of the kernel, mainly because some obscure dependency or feature might be missing/not working, therefore check back periodically to see if your issue has been addressed and try the latest kernel version out!

[Sheet music] Michael Nyman - The heart asks pleasure first

Download it here

[Sheet music] Ludovico Einaudi - Nuvole bianche

Download it here

[Oracle] Verify if column has not null check

To test whether a column in an Oracle DB has been declared with a NOT NULL check, it is possible to query the dba_tab_columns table:
 
SELECT nullable
FROM   dba_tab_columns
WHERE  owner       = :owner
  AND  table_name  = :table
  AND  column_name = :column
;





Where owner, table_name and column_name are all upper case. That would output (always in upper case):

N = not nullable
Y  = nullable

This will NOT work if the check is done with a constraint instead

[Sheet music] Ludovico Einaudi - Una mattina

Download it here

[Java] Total votes count as of given timestamp

Given a list of timestamped votes, return the top K voted people (including ties) as of a given timestamp.
Add an input parameter to specify if the ranking should be done olympic style, eg: if 2 people are in first place, then the next place is 3rd and not 2nd; in this case, for skipped places, return an empty list.

This is NOT a streaming problem, since the list of votes is given fully in input. Since it includes some sorting, it can be solved in O(N log N) time and O(N) space.

The input is given as a list of Vote objects and we use an auxiliary structure, CandidateVote for our max heap.

The idea is to use a map from candidate to total votes count to track the total votes for each candidate as of the given timestamp (do NOT consider votes AFTER the given time) by scanning the full input in O(N).
Then, we use a MAX heap (new PriorityQueue(Collections.reverseOrder());) along with our comparator to order them descending.

Now we simply need to pick ALL the candidates tied at the same place for each position up to K. This gets a bit more complicated if we do the olympic ranking, since we need to skip places if many people are tied in one. For example:

A - 2
B - 2
C - 1

with a topK = 2 would return 1st: A,B - 2nd: empty, but with a topK = 3 would return 1st A,B - 2nd: empty - 3rd: C.

Gotchas: the usual suspects, our heap might become empty at some point, so check for it to avoid NullPointerExceptions. If we are doing olympic ranking, we need to advance in position UP TO K, while still filling the skipped ones with empty lists.

This is another exercise where proper testing goes a long way towards spotting these small mistakes, also PriorityQueue comes to the rescue one again :)

You can check my implementation of getVoteRanking on my Gist alongside the previously mentioned auxiliary data structures and some test in VoteRankingJTests.

[Java] Forced array swaps

Given a start and end array, generate a list of positions where to swap the 0 element in order to move all elements from start to end position with the following rules:

• elements can only be swapped with the 0, not between themselves
• each element can only appear once
• element 0 must be in the arrays
• there can be more than one way to obtain the desired swap, return any valid sequence

This exercise will easily tangle your brain with all those indexes flying around, so it's quite sure to make some small mistake while coding. Luckily testing and writing while testing on paper helps a lot to keep this in check.

The idea is simple: since we cannot swap elements between themselves, if we want to bring an element to a certain position, we must bring the 0 element there first, then swap it with the desired element.

While doing this, we always keep track of where did we move the 0 element, to generate our output.

Time and space complexity is O(N). As auxiliary structures we use a map from element to its current position; in this implementation we reuse the input array for our processing, but we could also easily copy it to a new array if we do not want to destroy the input, still keeping the space in O(N).

For processing, starting at index 0, we check if the elements in current (initially start) and end array match. If not, we swap the element at the current position with the element 0, then we check again and if the elements still do not match, we swap the 0 with the desired element before moving on to the next index.
Since we do at most 2 sets of constant operations (map gets and puts + list add + swaps) for each index, the total time is O(N).

Meanwhile, we always maintain our map updated and remember to track in another structure all the places where we moved the element 0.

You can check my implementation of forcedSwaps on my Gist alongside some test cases in ForcedSwapJTests.

[Java] Minimize travel distance to single array index

Given an array indicating how many people live at the specific index, return the index where to place a postbox that minimizes the total travel time to it for all people.

The following rules apply:

• people residing at the same place of the postbox have a total travel time of 0
• N people needing to take 1 step to reach the postbox have a total travel time of N
• multiple solutions could be acceptable

An obvious O(N^2) solution is to compute the total travel distance for each possible place and store it in a matrix O(N^2), then walk over it to compute the best solution.

A better solution requires some preprocessing and 2 extra O(N) arrays but runs in O(N) total time.

An even better solution uses only one extra array instead.

[Java] Find largest sum subarray - Kadane's algorithm

Given an array of integers, the maximum subarray problem is about finding the subarray with the largest sum given the following specifications:

• for an array of all negative numbers, return the smallest of them
• for an array of all positive numbers, return the sum of all element

As output we want the start and end indexes as well as the total sum for the biggest portion identified. There may be multiple solutions.

The O(N) idea is to walk the array while keeping track of the local best and global best. The local best is the sum of elements until the one being currently considered; we initialize both to the first element of the array and remember to begin the loop from the element in position 1!

At each time, the local best can either be improved by adding to it the current element, or reset to start from the current element otherwise. We make this consideration first and in case, move the start index of the current best solution to the current position, then we compare it against the global maximum updating it if needed.

We track the result in an auxiliary structure, Range. You can check its implementation on my Gist alongside the implementation of getLargestSumSubarray and some test cases in LargestSumSubarrayJTests.

Turns out this algorithm is called Kadane's algorithm.

[Java] Topological sorting

Topological sorting of an acyclic graph is a representation of the graph where each node appears before every other node that links to it. This is useful for example for dependency checking to determine which items should be processed before others.

There are many ways of solving this problem, some easier to derive than others.
If the graph contains a cycle no solution can be obviously found.

The runtime of the proposed solution is O(V+E) where V is the number of vertexes and E the number or edges. The input could have included the list of vertexes as well, but it can also be derived from the list of edges itself, therefore I did not include it, although this means that vertexes with NO incoming edges at all, would not be included in the solution.

[Java] Find biggest square in matrix

Given an input matrix of only 0s and 1s, find the biggest square composed only of 0s. The square must be parallel to the matrix edges.

We could solve this in O(MxN)^2 time and constant space, by checking for each cell the biggest square that can be formed starting from there, but since we know a bit of dynamic programming, we decide that O(MxN) extra space is worth reducing the time to O(MxN) :)

The problem can be solved by decomposing it in smaller subproblems considering as base case the single cell; if it contains a 0, it's a valid 1x1 square.
From there, we expand considering the cell as either the BOTTOM-RIGHT corner of a bigger square which is valid if and only if the VALID (left, top, top-left) neighbours are 0s as well OR the TOP-LEFT cell of a new square starting there. Consider these cases:

0

00
00

000
000
000

The black 0 is the one we are evaluating now, the red zeroes are the neighbours we are considering for our case and the green zeroes are the cells we already evaluated before, when we were applying the logic to each of the neighbours we are considering now. The DP matrix for each of those situations would be:

1

1 1
1 2

1 1 1
1 2 2
1 2 3

Where each number indicates the number of extensions (length of one side) the particular cell contributes to the biggest square having the current cell as BOTTOM-RIGHT corner of it.

The solution would then be that number, squared.

[Java] Summarize a TreeSet

Given a TreeSet of Integers, return a string representation according to the following rules:

• if N is in the TreeSet but N-1 and N+1 are not, return N and comma separate it from the rest
• if N is in the TreeSet and N-1 or N+1 are too, return a dashed range

eg:
1,5,9 should output 1,5,9
1,2,4,5,6,7,8 should output 1-2,4-8

The idea is to track an item while iterating over the TreeSet in ascending order and tracking whether the current item is part of a range - it is if it's equal to the tracked item + 1.
When we encounter an item that breaks the current range, we check the rules and determine what to print, either a range or a single item.

Note: at the end of the iteration it is still important to check if the last element (yet unprocessed) was part of a range or not and in case add it to the result.

Runtime is O(N) and space is O(1).

You can check my implementation of summarize on my Gist alongside some test cases in TreeSetJTests.

[Java] Iterative inorder tree traversal

Some time ago we saw different ways to visit a binary tree, today we take a spin on one of those and implement an inorder traversal without recursion.

You can check the code on my Gist.

 //iterative inorder visit, use a stack as helper structure  
   private static List<Integer> doInorderVisitIterative(BST root, List<Integer> out){  
     if(root == null) return out;  
   
     BST curr = root;  
     Stack<BST> s = new Stack<>();  
   
     //keep looping as long as we have at least one valid element  
     while(!s.isEmpty() || curr != null){  
       //if current element is not null, keep stacking the left children  
       if(curr != null){  
         s.push(curr);  
         curr = curr.left;  
       }  
       //when we get a null, move up the tree (in stack view) again, visit the node, and switch to the right subtree  
       else{  
         curr = s.pop();  
         out.add(curr.getVal());  
         curr = curr.right;  
       }  
     }  
   
     return out;  
   }  

[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 :)

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

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

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

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

[Java] Regular expression matcher

Regular expressions are a pain, until they are not. Implementing a matcher is a double pain, and possibly the hardest exercise I've seen so far in terms of proper coding.

So many rules have to be carefully prioritised for it to succeed, even without fully supporting the common keywords. We have the following syntax:

• alphanumeric - matches exactly that character
• . - matches any character
• * - must follow . or an alphanumeric character, means we can match multiple instances of the preceding character
• ^ - must be the first character, means the matching has to begin from the start
• $ - must be the last character, means the matching has to occur at the end

In the absence of ^ and $, the match can occur anywhere in the string.

[Java] Fisher-Yates array shuffle

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence. It can be coded to run in-place and in O(N) time where N is the input array size.

The idea is quite simple yet effective: while scanning the array from the end, select a random index with which to swap that element for among an always shrinking set of possibilities. Namely, use a getRandom function that accepts a floor and a ceiling as input and reduce the ceiling by 1 at each iteration, until the whole array has been processed.

You can check my implementation of FisherYatesShuffle on my Gist alongside some test cases in FisherYatesJTests.

Note: since we are supposed to generate truly random permutations of the input array, we have no simple way of checking for errors except to verify the output distribution itself to determine whether a bias exists or not. Therefore the current test could be extended to record for all the algorithm iterations the result of the shuffle and compare the results at the end among themselves.

[Java] Word squares tester

This exercise looked scarier than it is, although the real difficulty is not much on the algorithm itself but rather on the correct and clean implementation of it.

A “word square” is an ordered sequence of K different words of length K that, when written one word per line, reads the same horizontally and vertically. For example:

BALL
AREA
LEAD
LADY

Given an arbitrary list of words, return all the possible word squares it contains. Reordering is allowed.

For example, the input list:

[AREA, BALL, DEAR, LADY, LEAD, YARD]

should output:

[(BALL, AREA, LEAD, LADY), (LADY, AREA, DEAR, YARD)]

[Java] Calculate maximum capacity of 2D shaped object

This problem looked harder than it actually is:

Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.

Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.

Example: Given [1,3,2,4,1,3,1,4,5,2,2,1,4,2,2], return 15 (3 bodies of water with volumes of 1,7,7 yields total volume of 15)

[Java] Decompress k[value] format strings

Here is an interesting problem: decompress a compressed string.

Your input is a compressed string of the format number[string] and the decompressed output form should be the string written number times. For example:

3[abc]4[ab]c

Would be output as

abcabcabcababababc

Number can have more than one digit. For example, 10[a] is allowed, and just means aaaaaaaaaa

One repetition can occur inside another. For example, 2[3[a]b] decompresses into aaabaaab

Characters allowed as input include digits, small English letters and brackets [ ].

Digits are only to represent amount of repetitions.

Letters are just letters.

Brackets are only part of syntax of writing repeated substring.

Input is always valid, so no need to check its validity.

This can be done in one pass of the string by either applying recursion or explicitly using a stack for an additional O(N) space and overall O(N) time.

Gotchas are:

• treat 0 repetitions and missing k correctly
• remember that when concatenating data that comes from the stack we are actually prepending
• run a last round of popping after the string is fully parsed

You can check the implementation of decompress on my Gist alongside some test cases in DecompressJTests.

[Java] Neighbour evaluation concise logic

Here is a nice trick I was taught while doing some exercises. Consider the need to perform some loop over neighbouring places for example in an array or matrix or whatever, the basic idea would be to pick a starting point and queue up all valid points reachable from that which we did not visit yet. Assume a matrix M of size N:

A B C
D X F
G H I

And X is our starting point. We could do:

 if(i - 1 >= 0 && !visited.get(M[i - 1][j])) //do something  
 if(i - 1 >= 0 && j - 1 >= 0 && !visited.get(M[i - 1][j - 1])) //do something   
 if(i - 1 >= 0 && j + 1 < N && !visited.get(M[i - 1][j + 1])) //do something     
 if(j - 1 >= 0 && !visited.get(M[i][j - 1])) //do something  
 if(j + 1 < N && !visited.get(M[i][j + 1])) //do something  
 if(i + 1 < N && j - 1 >= 0 && !visited.get(M[i + 1][j - 1])) //do something  
 if(i + 1 < N && !visited.get(M[i + 1][j])) //do something  
 if(i + 1 < N && j + 1 < N && !visited.get(M[i + 1][j + 1])) //do something  

But here is an equivalent and more concise way of achieving the same. Consider the same matrix but focus on the changes on i and j you would do:

(-1,-1) (-1,0) (-1,+1)
(0,-1)     X   (0,+1)
(+1,-1) (+1,0) (+1,+1)

Then this can easily be converted into (and even adapted to more dimensions):

 int[] di = {-1, -1, -1, 0, 0, 1, 1, 1};  
 int[] dj = {0, -1, 1, -1, 1, -1, 0, 1};  
   
 for(int n = 0; n < di.length; n++){  
  int x = i + di[n], y = j + dj[n];  
  if(x >= 0 && x < N && y >= 0 && y < N && !visited.get(M[x][y])) //do something  
 }  

[Java] Find longest word that can be made as subsequence of given word

Here is another interesting problem: given a string and a list of strings, determine, if any, the longest string from the list that can be built as a subsequence of the given string, by only deleting characters in it. For example, given "asd" and {"a", "ccc", "sd", "sda"} return "sd".

The complex part when working with string is as usual the fact that we potentially need to scan the string many time over and over in order to reach our goal.

In this case, we could simply check for each given string in the list, if it can be built from the given input string by looping over that and match each character until we have our answer; this takes O(L) time where L is the length of the INPUT string for a SINGLE word. So overall we would need O(NxL) time where N is the number of strings in the list.

We know we can do some preprocessing to make our runtime better, at the expense of space of course. Since the input string can be very long and our result can start anywhere in there, we could do this in O(N+L) time by simultaneously process ALL words (N) for each character in the input string(L), using an additional O(N) space.

[Java] Minesweeper

Minesweeper. Do I need to say more?

The most interesting part is how to efficiently and randomly create the board.

There are many, many, many (and more) ways of doing so, I'll describe my idea here:

• the board size for an average game will not be so big that I can't afford to store an additional O(N^2) piece of information. This is the key point, without this assumption, the rest is not applicable!
• if I do store that piece of information, then I can acceptably randomize it in O(N)
• since the random distribution is from 1 to board_size (all the valid spots for a mine, N^2 spots) but the board is actually a matrix and therefore has 2 indices, I need a way to convert from the random spot to the matrix spot reliably
• if we have too many mines, it's best to randomly place empty spots instead
• after the initial placement, we need a pass on the matrix to fill the remaining spots with the correct count of the neighbouring mines

The randomization can be done with a call to Collections.shuffle, while the conversion from board spot to the matrix spot can be done easily after some considerations. Consider this sample matrix:

1 2 3
4 5 6
7 8 9

Given any of those numbers, can you determine the exact matrix location? Meaning can you return a i and j that indicate where that number would be placed in the matrix? For example 1 would be 0,0 and 8 would be 2,1.

Yes, but rows and columns have to be treated differently AND, since we do care about randomness but not precision, we can even avoid adjusting the result to reflect the exact position - we can't get the same position twice anyway.

For columns we can simply use the modulus operator, this way the last column is 0 and not 2, but since we are going for random spots we don't care to correct it. Basically we are flipping the matrix over on the Y axis :)

For rows instead, we can simply use division and then round the values UP to get something in range 1 .. board_length which we convert to 0-based.

The method looks like this (can be reduced to fewer lines, but debugging is easier this way!):

 private int decodeCoordinate(int value, boolean is_column){  
     //column we can find with modulus  
     //last column is 0 if we do this calculation, but we are going for random spots so we don't care to correct it  
     if(is_column) return value % fieldLength;  
   
     //rows we can find with a normal division and then picking the ceiling of it, converting to 0-based!  
     double a = (double) value, b = (double) fieldLength;  
     int c = (int) Math.ceil(a / b);  
     return c - 1;  
   }  

You can check the implementation on my Gist alongside some test cases in MinesweeperJTests. I plan to pick this up again to finish it, so some parts are extra and do not yet tie in to the final code :)

[Java] Make bricks and make chocolate problems

Among some exercises offered by Google, I found a couple interesting ones that are a bit harder to code cleanly than I would have thought: makeBricks and makeChocolate.

The basic idea is the same in both cases but the return value in one case is a simple yes/no while in the second case is a number:

We want to make a row of bricks that is goal meters long. We have a number of small bricks (1 meter each) and big bricks (5 meters each). Return true if it is possible to make the goal by choosing from the given bricks. - Yes they said inches but this is 2018 and we like our metric system :)

and

We want make a package of goal kilos of chocolate. We have small bars (1 kilo each) and big bars (5 kilos each). Return the number of small bars to use, assuming we always use big bars before small bars. Return -1 if it can't be done.

[Sheet music] Luis Fonsi - Despacito

Download it here

[Java] Unbounded knapsack algorithm

Taking up again the knapsack challenge I tried some time ago, I decided to solve an easier problem first, the unbounded knapsack.

We already know we need to compute some values in order to find the perfect solution to the problem from past experience :) so this time we'll build our information data structure incrementally, starting from considering the bag with capacity 0 and working up to the input capacity.

The important thing is to convince ourselves that there is NO BETTER SOLUTION than considering all possibilities, with some interesting ways to reduce the number of possibilities though ;)

At each weight increase we want to know what would the best pick(s) be from our items if the maximum weight was the one we're currently evaluating. Therefore the key part is: we need to check ALL items every time to determine whether it's best to pick the item alone OR the item PLUS some of the previous items OR even MORE of the previous items.

If we care only about the maximum value we can achieve, we can easily track this with an integer array or similar, but we would lose the information regarding which and how many items make up our best solution; we can fix this by using some object to track the partial information and update our result in a nice way before returning from the function.

By knowing the best pick at each step, we will reach in O(NxK) time and O(k) space the best solution where N is the number of items and k is the maximum weight the bag can carry.

We can put some improvements in place, for example we can preprocess the items to discard any item that weighs more than what our bag can carry or any item for which a better item exist (more value for same or less weight).

You can check my implementation of fillUnboundedKnapsack on my Gist alongside with some tests in KnapsackJTests and the supporting structures I use.

[Java] Find maximum number of concurrent events in a calendar

This problem can be generalized to: find the maximum number of overlapping entries in a time series. We will focus on a calendar example where each event has a start and end time; you can find here the implementation of the CalendarEntry and CalendarEvent classes.

This problem is very similar to the one about verifying if all open parentheses in an expression have a matching closing parenthesis. In both cases we need to be able to find start and end points of an interval and verify where do they reside.

But the calendar entries might not be given in a sorted order already so to solve our problem we need to first split them in bot start and end points, then sort the points by comparing the times and breaking ties by giving precedence to the start points - this is very important! - if precedence is given to the end points we are not tracking the information we need, therefore double check that compareTo override :)

After the input data is sorted, we simply need to walk through the sorted list/array/whatever and keep a counter that we increase every time we encounter a start point and decrease when an end point is found. The maximum value of the counter is also the maximum number of concurrent events in the calendar.

You can check the implementation of getMaxCalendarOverlap on my Gist alongside some test cases in CalendarJTests.

[Java] Bellman-Ford algorithm

Let's start the new year with something not overly complicated like a proven graph algorithm, Bellman-Ford.

This is a good example of an algorithm for which choosing a good data structure can be the difference between a walk in a park or in hell during implementation.
A key point here is to represent the graph a two lists: Vertices and Edges. Using a different data structure instead can lead to a very messy code and complex implementation; for example I would advise not to keep a list of out edges in each Vertex and track the out vertex in the edge itself - even though the uploaded classes allow you to do so, but I keep them for the next exercises.

Also another important point is to understand exactly how a negative cycle can be detected and tracked into the resulting data structure. While we only need (V - 1) x E iterations to create the table, we need instead VxE iterations to be absolutely sure no negative cycle exists.

Another gotcha: we use "infinity" to mark the unknown distances at the beginning, but when we update the distances themselves if we are starting from infinity it means we don't know yet how to reach that specific node, so we should skip tracking it in the table. At the end, if the node is not present in the table or the distance to the node is "infinity", it means it's unreachable.

The last important step is to remember to update the path cost to "negative infinity" for all nodes in our graph that are in a negative cycle reachable from the given starting node; this gives us a full understanding of which paths are actually valid.

You can check my implementation on my Gist along with some test cases in BellmanFordJTests. Remember to check out the Vertex and Edge classes too.