[Java] Self balancing AVL binary tree

Oh. my. god.

This has definitely been the hardest one so far; I remembered the traumatic experience since the university time and also remembered why I hid it deep down.

You can check the glorious Wikipedia for the full description of the AVL trees, no need for me to repeat it there. I will however list some of the key points I found while implementing it:

• draw the thing down. It is the best help you can get while your brain tries to make sense of this magic rocket science
• TRACK THE HEIGHT, COMPUTE THE BALANCE. This kept me stuck for eons, maybe it's possible to track the balance only as well and perform some more complex update logic, but I have no intention of going down the rabbit hole again for the moment :)
• after inserting a node, backtrack to the root and perform rotations as needed. Update the heights while backtracking
• not everyone defines right and left rotations the same way. Sometimes they are inverted in the directions they will actually rotate; end result in balancing terms is the same but naming might cause confusion. For me right rotate means: take the node, pull it down right and set his left child as parent. So for me: balance -2 means left heavy therefore a right (or right-left) rotation is needed

You can find my implementation on my Gist in the BST package. The builder function is called buildBalancedAVL, along with extended test cases in BSTJTests

Lastly, I also link this super useful tool I found that helps with understanding the logic and checking the correctness of the results form the code: online AVL tree visualization

[Java] Merge sorted files

Here is a problem that takes more time to code than to figure out: given N files where each line contains a timestamp (as long) and some data sorted in ascending order, merge them in a single file also sorted in ascending order.
The files can be arbitrarily big and are passed in input as a full path list; each has content in the format:

timestamp#data

Since the files can be arbitrarily big, we might want to avoid loading them all into memory at once; we can instead keep an open pointer to each of them using O(N) additional space.

This is not enough though, since we also need to write entries to the output file in ascending order too, which would be a big issue if the input files were themselves not ordered already. As long as they are already ordered, we can avoid using a mergesort modification for example and rely on a min heap (aka PriorityQueue) instead.

We will read one line from each file and place it in the min heap which will be in size of O(N) as well and will have a O(log N) handling complexity. To understand later on which entry corresponds to which file and pointer, we use a custom structure FileEntry as object for the heap, meaning we override equals, hashCode and compareTo and we also use a HashMap from filename to BufferedReader so that we can quickly read the next line from each input file once we determine from which one we need to read next.

We keep looping over the heap until it's empty, meaning we read all the lines and also wrote them out. For each element we remove from the heap, we add, if any, a new element (the next line to read) from the same source file; if the file is finished, we remove the reader from the map.

Total runtime is O(N log N) and total space is O(N).

The hardest part here is actually the handling of file IOExceptions, as we might have many BufferedReaders active at the same time and need to gracefully try to close all of them if we encounter an error during processing. The algorithm itself is quite short, but there is a lot of file handling code around it unfortunately; also some code was added to have a more graceful error handling, but it is not strictly necessary.

You can check the implementation of mergeSortedFiles on my Gist along with some test cases (STUB!) in MergeFilesJTests. This time I was too lazy to properly create JUnit tests for these File operations, so please check out the source and edit it as needed, also do NOT run ALL tests together: you will get a "file already exists" exception since the out file is created but never automatically deleted.

[Java] Implement locking mechanism using a binary tree

This is an interesting exercise: implement a locking mechanism backed by a tree structure with parent pointers where a node can be locked if and only if none of his ancestors and descendants are locked.
Have the lock testing operation run in O(1) time, while the lock and unlock operations should run in O(H) time where H is the height of the tree.

The fact that we are given the desired runtimes is the hint we need to understand how to implement this and the parent pointer is also a key element.
A lock testing operation in constant time means we are definitely tracking the information we need on the node itself.

An O(H) lock and unlock operation means we are not scanning both branches of a node AND the ancestors every time we need to check whether any of those contains an already locked node.
The way we can accomplish this then, is if we are tracking an additional piece of information in each node and increase the complexity of both operations to maintain this information updated.

If in each node we track for example the number of locked descendants in both subtrees, we would only need to test if any ancestor is locked during the lock operation before performing the lock and we would need to reduce the count of locked nodes in our ancestors during the unlock operation.

You can check my implementation on my Gist along with some test cases in BSTLockJTests.

I was a bit lazy so I reused an existing BST implementation that is not even fully balanced, but I am expanding this code and do not like rewriting too much :)

[Java] Find duplicate element in array with binary search

Disclaimer: this solution comes from interviewcake, where they mention this as being easier to (I guess) derive than the ones we saw before using Floyd's and Brent's cycle detection algorithms, but to be honest I feel the other way around. Plus bonus points because the graph solution is marked as BEAST MODE which definitely makes us feel proud when the implementation is done :)

Anyway, we still want to keep space constant and not destroy the input, but we have no idea that graphs exist so what options are we left with?

When searching for something, a good idea is to perform a binary search. In our case though, the input structure is not really built in a way where we can safely apply the algorithm since the array is not ordered. But this problem is very specific: given a series of N+1 items in the range 1 to N, find one of the duplicates.

[Java] Find duplicate element in array in constant space and linear time v2

Well a good night's sleep always helps apparently. Yesterday we saw how to find a duplicate element in a constrained array in linear time and constant space and based the implementation for the cycle detection on Floyd's algorithm.
Today we do the same, but use Brent's algorithm instead which supposedly should be overall faster.  

You can find the implementation of findRepeatBrent on my Gist and I also provide some timings comparison in the compareFloydAndBrent method in my test cases FindRepeatJTests. Of course you need multiple runs and maybe a bigger input as well to appreciate the difference, but it appears that overall there is a small performance improvement with Brent's method.

You can also find here an implementation that is slower O(N log N) and still uses constant space, based on binary search.

[Java] Find duplicate element in array in constant space and linear time

Sooo.. spoiler alert: this one was way harder than it should be thanks to 0-index arrays.

Given an array of integers in the range 1..N and length N+1 find one of the possible duplicate elements in O(N) time and O(1) space WITHOUT altering the input.

Those constraints are quite strong since finding a duplicate in O(N) time and space is pretty easy: place all elements in a HashSet while iterating over the input and return as soon as a duplicate is found.

Finding a duplicate in O(N log N) time and O(log N) space is also easy: sort the input - using a kickass quicksort implementation otherwise good luck keeping those costs down - and then walk over it comparing elements in pairs until the duplicate is found.

Finding it without destroying the input and without using additional space is also easy in O(N^2) time: for each element, loop over the full array until a duplicate is found.

[Sheet Music] Ludovico Einaudi - Divenire

A contemporary masterpiece, you can find here the full album.

[Java] Convert expression to reverse polish notation

The closing chapter of my RPN journey, how to convert an infix notation expression to a postfix notation one, so from 3 + 4 we get 3 4 +

Here as well it appears immediately that a String is not the most comfortable input structure, so we stick to an array.
First idea was to scan the input and tokenize it in a left side portion and right side portion for each operator we found:

3 - 4 x 5

would become first:

3, 4 x 5, -

Then finally:

3, 4, 5, x, -

[Java] Evaluate reverse polish notation in constant space

Yes it is possible, yes it took me one full day research included, but the RPN can be evaluated in O(N) time and O(1) space, sacrificing the input in the process.

There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an in place algorithm.

Consider the following expression corresponding to 3 - (4 x 5): 3 4 5 x -

For RPN reading from left to right, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so 3 4 5 x - can be rewritten as 3 20 -

We can therefore recycle the processed space (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.

[Java] Evaluate reverse polish notation using a stack

Reverse polish notation, aka the WTF! way of writing arithmetical expressions, presents an interesting exercise on stacks.

The goal is to write a program to evaluate RPN expressions eg: 3 4 + would return 7.

The input can be passed in many ways, good candidates are arrays and lists, a stack directly or a string, although in this case, you would need a separator character to understand when does a number start and end.

The idea here is to process the input sequence from left to right without creating the stack beforehand. If we encounter a number (operand), we push it onto the stack and when we encounter an operator, we pop two items from the stack, then apply the operator in the (gotcha!) REVERSE order because the stack is LIFO and this matters for the asymmetrical operations such as - and /

An interesting note, dividing by 0 a double will NOT throw an exception, we must test if we got infinite as result!

For the implementation I use a String array as input and a Double stack to allow decimal results. Only the four basic operations (sum, subtraction, multiplication, division) are supported, but the code can easily be expanded to support more and even unary operations (pop one item instead of two).

As last note: why can't we do this in constant space while parsing the string itself? Because of situations such as: 3 - (4 x 5) which translates to 3 4 5 x -

Therefore we cannot expect an operator to always follow two operands.. So: String as input = bad.

The current implementation therefore uses O(N) space and time. But you can check here for an implementation that uses O(N) time and O(1) space!

You can check the implementation on my Gist along with some test cases in RPNJTests.

You can find here the code to convert an expression to reverse polish notation.

[Java] Generate string permutations recursively

Ahhhh, string permutations. The timeless classic. Also painfully slow with its O(N!) time and space complexity. Let's put a twist on it and do it recursively just because we can.

Also, just because we can, we use StringBuilders instead of Strings. Is this a good idea? Is the cost of creating lots of StringBuilders offsetting the cost of creating a new String object everytime? That's what method timing is for, we'll leave this as "exercise" for the reader.

Anyway, enough introduction, let's go to the meat: we call a recursive method which will have as input the size of the result string to create, the string we built so far, the string of unused characters so far and the output collection.

Then, for each unused character, we add it to the current string and recurse on the remaining ones leaving that out. The base case is when we no longer have characters to use; if the string we built is the correct length, we add it to the result set and return, otherwise simply return.

Note: StringBuilder.deleteCharAt alters the source directly instead of returning a new object, therefore calling this method as StringBuilder(x.deleteCharAt) and StringBuilder(x).deleteCharAt makes quite the difference!

You can check the implementation on my Gist along with some test cases in PermutateJTests.

[Java] Zip singly linked list

List zipping means interleaving the list nodes from the top and bottom of a given list to create a new list.

Eg with this input list:

A -> B -> C -> D

the zipping is:

A -> D -> B -> C

Doing this in constant space and quadratic time is trivial, but there is a better solution that avoids scanning the list every time with two pointers running one ahead of the other to find the current last element in the list.

Again as with most linked list problems, the correct handling of the pointers is the trickiest part. The idea is to spend some time to preprocess the list in O(N) time to split it in two halves, and reverse the second half; this way, we now simply need to walk both lists and interleave the nodes in order to produce our result.

[Java] Reverse singly linked list

Here is a simple algorithm to reverse a singly linked list in O(N) time and O(1) space. The only tricky part is the correct handling of the pointers :)

The idea is to start with a previous pointer to null and a pointer to the head of the list, then:

1) track the next element in a temporary variable
2) reverse the current element pointer
3) consider the current element as the previous for next iteration
4) move the current element to the next one to handle
5) when no more elements are left to be processed, the previous pointer will be the new list head

 //reverse singly linked list  
 public static SingleLinkedListNode reverseList(SingleLinkedListNode head){  
   if(head == null) return head;  
   
   SingleLinkedListNode prev = null, next, curr = head;  
   
   /*  
   1) track next element  
   2) reverse current element pointer  
   3) track current element as previous for next iteration  
   4) move current element to the next one to handle  
   */  
   while (curr != null) {  
     next = curr.next;  
     curr.next = prev;  
     prev = curr;  
     curr = next;  
   }  
   
   //at this time this will point to the beginning of the reversed list!  
   return prev;  
 }  

You can check more singly and doubly linked lists utilities on my Gist along with some test cases in SingleLinkedListJTests.

[Java] Look and say generator

The count and say sequence is a self describing sequence where given a starting seed, each subsequent element is the concatenation of the number of times a number appeared consecutively in the previous element. For example with seed 1:

1   -> one 1
11 -> two 1
21 -> one 2, one 1

I provide here an implementation to get the nth element given any seed. Unfortunately, we have to compute all elements before getting the one of interest :(

This runs in O(M) space, where M is the length of the resulting string and O(NxM) time. Beware that M is not that small since in the worst case at each new iteration we add one character for each current one, thus doubling the size of the string!

The idea is simply to iterate from 1 to N and for each iteration, loop over all the characters in the partial output string and count the consecutive appearances to form a new partial string.

An improvement could be to identify those special seeds that will always return themselves and skip the calculation, eg: 22 will always be 22 no matter how many iterations we have.

You can check the implementation of lookAndSay on my Gist along with some sample test cases in LookAndSayJTests.

[Java] Partition array in linear time and constant space

Here is an interesting problem: given an integer array and an index, consider the element at the index as a pivot and then reorganize the array so that all the elements less than the pivot are at the start of the array, followed by the elements equal to the pivot, followed by the elements greater than the pivot.

This is trivial to do in a single pass and additional O(N) space, since we scan the array once and store the elements in one of three additional arrays (smaller, equal, greater) and then in another pass we reconstruct the result array.
We can get rid of the extra space but run in O(N^2) time by scanning for each element the array multiple times to make sure it is in the proper place, until we reach the end.

A better solution that runs in O(N) time and O(1) space, is to partition the array itself in 4 sections: smaller, equal, unclassified, larger and process one unclassified element at a time. For the unclassified section, equal is the pointer to the beginning of it and larger the pointer to the end. At the start, smaller and equals are the same and larger is the end of the array. It is not guaranteed that at each pass the array will be in a consistent state but it will be by the end of the algorithm!

[xorg] Set display to full RGB output

Depending on the monitor being used, the RGB color model supported might be either "Full RGB" or "Limited 16:235"; usually the latter is the one used by TV monitors.

To test the output setting when using xorg, first find out the name of the video connection being used by running:

xrandr

which will list the names and statuses of the available connections. Then manually change the output setting with:

xrandr --output NAME --set "Broadcast RGB" "Full"

Or use "Limited 16:235" instead.

This will not survive a reboot, therefore use whatever method suits you best to force this at every boot, eg by editing/creating the ~/.xprofile file

[Java] Test if a number is a power of two

Last trick of the day: check whether a number is a power of 2.

The breakdown is:

- 0 is never a power of anything
- a power of 2 in binary representation will always have only one bit set
- we can find the first set LSB in number and XOR it with the number itself
- if the number was a power of two the XOR will cancel out all equal bits (only one) and we are left with a 0

Which leads to our code:

 public static boolean isPower2(long n){  
  if(n == 0) return false;  
  return (n ^ getLowestSetBit(n)) == 0;  
 }  

You can check more bit magic on my Gist along with some test cases.

[Java] Calculate modulus of a number and a power of two

More bit magic!

This time we will efficiently compute the modulus of a number and a power of two. If you write down a couple sample cases you immediately spot the trick; let's use N mod 4 (0100):

Number	Bits	Modulo	Modulo bits
1	0001	1	0001
2	0010	2	0010
3	0011	3	0011
4	0100	0	0000
5	0101	1	0001
6	0110	2	0010
7	0111	3	0011
8	1000	0	0000
9	1001	1	0001

The red bit is the only set bit in our modulus, the bold bits in both the number and the result are always matching.. interesting.
We now have a very easy way of calculating the result by always returning all the bits in the number that appear after the modulo bit:

n & (mod - 1)

We already saw previously that n - 1 will provide us with a mask where all the bits after the first set LSB are set to 1. We can then AND this with the number itself to erase everything that appears before, and including, the modulo bit and return only what's right of it.

You can check more bit magic on my Gist along with some test cases.

[Java] Right propagate the lowest set bit in number

Building on top of the magic to find the first set LSB in a number, we have another magic trick to right propagate it.

Eg:

10100

would become:

10111

The code for this is:

 public static long rightPropagateLowestSetBit(long n){  
  if(n > 1) return n | getLowestSetBitPosition(n);  
  return n;  
 }  

And the breakdown:

- 0 and 1 have nothing to propagate, so return them directly
- find the lowest set bit
- bitwise OR the number with the position of its lowest set bit, that means we start counting from 0 as LSB; the position is then exactly the mask for the missing 1s we need to set.

To get the position we simply return the first set LSB - 1 and pay attention to the fact that now 0 has -1 as result :)

You can check more bit magic on my Gist along with some test cases.

[Java] Find lowest set bit in number

This is a very interesting bit magic trick: given a number, return the first (from least significant) bit set to 1.

The magic formula is:

n & ~(n - 1)

To break it down:

- (n - 1) creates a mask where the last bit set to 1 is now 0
- negating that mask gives us a new mask that is the exact opposite of n except for the bit we flipped before
- the AND operation of the original number with this mask, will then return only the bit we flipped

You can check more bit magic on my Gist along with some test cases.

[Java] Find local maximum gain in list

Here is another simple problem: given an ordered input of stock prices, find the best buy and sell times to achieve maximum gain.

The buy must happen before the sell and it is not possible to buy and sell in the same day. Return null if no gain can be achieved.

The idea is quite straightforward, in O(N) time and O(1) space, track the current maximum gain and current minimum buy date; whenever the gain can be increased, update the buy - if necessary - and store the sell data. Just as caution, it's important to remember to separately track the current and result data, otherwise it could be possible to wrongly overwrite the result before returning.

You can check on my Gist the implementation of the getMaxProfit (if only life was that easy..) method along with the test cases StockTradeJTests and the aux objects StockEntry and BuySellEntry.

[PL/SQL] Convert number to binary string

Here is a simple function to convert a number to a binary string in Oracle PLSQL. This can also easily be converted to an number array instead.

 function num_to_bin(   
  n number   
  )   
  return varchar2   
  is   
  binval varchar2(64);   
  n2  number := n;   
  begin  
  if (n == 0) then  
   return '0';  
  end if;   
  while (n2 > 0) loop   
   binval := mod(n2, 2) || binval;   
   n2  := trunc(n2 / 2);   
  end loop;   
     
  return binval;   
  end num_to_bin;   

[Java] Merge linked lists with gaps

Ok, this is a very specific exercise and a bit hard to summarize in a short title, but in the end it is just an algorithm working on lists, more specifically list of lists.

The problem is: given a list of ordered lists as input, where the content is an object (date, value), generate as output a list, ordered by date, where for each date, the value is the sum of the values for that date in each list. If a list does not contain that date, use the previous value, if any. The date can be represented as a long to ease the comparison logic, otherwise we would need to provide a comparator.

For example consider this representation

      5/5  5/6  6/11  6/12
    A 10        20
    B 20   10         20
    C      10         20

The input would be given as a list of lists:

[
 [(5/5, 10), (6/11, 20)]
,[(5/5, 20), (5/6, 10), (6/12, 20)]
,[(5/6, 10), (6/12, 20)]
]

The result has to be: [(5/5, 30), (5/6, 30), (6/11, 40), (6/12, 60)]

Because we track the following phantom values, the "holes":

      5/5  5/6  6/11  6/12
    A 10  [10]  20   [20]
    B 20   10  [10]   20
    C [0]  10  [10]   20

[Java] Biggest matrix subgroup value

Given a 2D input matrix with non negative values, consider the subgroupings as all positive values surrounded by zeroes eg:
________
|001003|
|002304|
--------

(1,2,3) and (3,4) are groupings. A matrix with all positive values is a single grouping, an empty matrix has group value 0.

The idea is to approach this as a graph walk where each point in the matrix is a node; therefore we can walk the full matrix and every time we encounter a positive value, we start searching for and queuing all contiguous values that are part of the same group and keep summing them up while marking the positions as visited.

When we cannot move anymore (queue is empty), we update, if necessary, the current max result and keep walking the matrix. Since we mark the nodes as visited, we will not process each point more than once so the total runtime is O(MxN) and total space is also in O(MxN) because at most we queue the full matrix.

Since we are adding points to a queue for later processing, we have to be very careful of the double processing possibility; this means that we have to mark each point we add as visited immediately after it is added and use a Point auxiliary structure so that we can store the data for later processing. If we skip this, we might enqueue the point for processing twice and change its value in between to mark it as visited!

As bonus, this logic scales well to higher dimensional matrices, what needs to be adjusted is the looping and queuing logic to accommodate the extra dimensions.

You can check the implementation on my Gist along with the definition of the Point class and some test cases.

[Firefox] Open magnet links with external program

For some reason Mozilla Firefox is not set to request which external program to run when you click on a magnet link, instead it will try to open and display it in the browser itself.

The fix is a simple boolean variable to add in the about:config section. Name it network.protocol-handler.expose.magnet and set its value to false.

[Sheet music] Morrowind - Call of magic

Download it here

[Java] Implement a LRU cache

Here is an interesting and quite simple exercise: implement a LRU cache in Java.

When thinking about the problem, it appears immediately that we cannot do away with a single "basic" data structure, so we must combine at least two of them in a custom class. We use a HashMap for fast object retrieval and a custom doubly linked list to keep track of the objects access order, from MRU to LRU.

In this solution we have the put and get operations working in O(1) and we use additional O(N) space where N is the max cache size.

You can check the implementation on my Gist along with the definition of the ListNode class and some test cases.

[Sheet music] Hans Zimmer & Lisa Gerrard - Now we are free

Download it here

[Sheet music] Yann Tiersen - Comptine d'un autre ete large version

This sheet music is an improvement over the original version, download it here.

Convert Ghostscript to PDF

To convert a Ghostscript file to PDF it's quite useful to have the utility ps2pdf installed on your system; it will come as part of the Ghostscript installation.

Then, make sure you have the gs command on the path and run either of these scripts depending on the PDF version you want to generate (note that the official documentation will be constantly updated, this page not!) :

• ps2pdf12 produces PDF 1.2 output (Acrobat 3-and-later compatible).
• ps2pdf13 produces PDF 1.3 output (Acrobat 4-and-later compatible).
• ps2pdf14 produces PDF 1.4 output (Acrobat 5-and-later compatible).
• ps2pdf per se currently produces PDF 1.4 output. However, this may change in the future. If you care about compatibility with a specific output level,use the -dCompatibilityLevel=1.x switch in the command line, or one of the specific version aliases ps2pdf12, ps2pdf13, or ps2pdf14.

Another thing to be aware of is that you might receive some errors while generating the PDF such as /invalidfileaccess in /findfont 

This might mean that you are missing a specific font installed on your system, but if that is not the case, maybe the font or some other file is not accessible due to permissions restrictions. You can try by running the utility again and adding -dnosafer as option.

[Sheet music] Leonard Cohen - Hallelujah

You cannot feel anything but peace after hearing this. Download it here

[Sheet music] Yiruma - River flows in you

Download it here

[Sheet music] Fabrizio de Andre - Il pescatore

A masterpiece. A poem in a song. Download it here

[Sheet music] Alan Walker - Faded

Download it here

[Sheet music] Alan Silvestri - Forrest Gump main theme

Download it here

[Sheet music] Guns n Roses - November Rain

Download it here

[Sheet music] Whitesnake - Here I go again

Download it here

[Java] Xchange me, sir - Sample REST project to get xrates to EUR

Project description Xchange me, sir:

Implement a simple foreign exchange rate service that uses data provided by the European Central Bank. Provide a REST API to retrieve the exchange rate to EUR from any other currency provided by the ECB and allow querying current (https://www.ecb.europa.eu/stats/eurofxref/eurofxref-daily.xml) and past (https://www.ecb.europa.eu/stats/eurofxref/eurofxref-hist-90d.xml) data. Use an asynchronous job to retrieve and update the xrates storing them locally in memory and have the REST API use the data in memory to return this information.

[Java] Reverse doubly linked list

Here is a O(N) time and O(1) space method to reverse a doubly linked list:

 //reverse doubly linked list  
   public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){  
     if(head == null) return head;  
   
     DoubleLinkedListNode prev = null;  
   
     while(head != null){  
       DoubleLinkedListNode next = head.next;  
       head.next = prev;  
       prev = head;  
       head = next;  
     }  
   
     return prev;  
   }  

You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.

[Java] Find if binary tree is complete

A binary tree is complete if for each level, there are no holes between two children. For example:

complete =
        A
      B  C
there are no holes between B and C

complete =
        A
       B
there are no holes after B

non complete =
       A
        C
there is a hole before C

You can the code on my Gist (isTreeComplete) along with some test cases:

 /*  
   is tree complete  
   A tree is complete if for each level, there are no holes between children:  
   complete =  
     A  
    B C  
    no holes between B and C  
   
    complete =  
     A  
     B  
    no holes after B  
   
    non complete =  
     A  
     C  
    hole before C  
   */  
   public static boolean isTreeComplete(BST root){  
     //null root is always complete  
     if(root == null) return true;  
   
     /*  
     otherwise, we must NOT have null nodes between two nodes at each level  
     so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one  
     */  
     Queue<BST> levels = new LinkedList<>();  
     boolean has_null = false;  
   
     levels.add(root);  
   
     while(!levels.isEmpty()){  
       BST t = levels.remove();  
   
       //if current node is not null  
       if(t != null) {  
         //if we had a null, fail  
         if(has_null) return false;  
         //otherwise add its children  
         levels.add(t.left);  
         levels.add(t.right);  
       }  
   
       //track if the node we just saw was null. CAUTION: do not overwrite it!  
       has_null = has_null || t == null;  
     }  
   
     //if we navigated the whole tree without problem, it is complete  
     return true;  
   }  

[Java] Find if a binary tree is balanced

A binary tree is balanced if the left and right branches do not differ in depth for more than one level.

Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:

 /*  
   is tree balanced  
   A tree is balanced if the left and right branches do not differ for more than 1 level in length  
   */  
   private static Entry isTreeBalancedAux(BST root){  
     //null root is always balanced  
     if(root == null) return new Entry(true, -1);  
   
     Entry left, right;  
   
     //check subtrees  
     left = isTreeBalancedAux(root.left);  
     right = isTreeBalancedAux(root.right);  
   
     //if they are not balanced, we have our answer  
     if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);  
   
     //otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced  
     if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);  
   
     //finally, if all is good, return the max depth from this node incuding itself and mark it as balanced  
     return new Entry(true, Math.max(left.height, right.height) + 1);  
   }  
   
   public static boolean isTreeBalanced(BST root){  
     return isTreeBalancedAux(root).isBalanced;  
   }  

I use an additional data structure (Entry) to pass around two pieces of information:

- is the tree balanced so far
- what is the current depth of the path being analyzed

[Java] Find depth of binary tree

Here is a simple method to find the depth of a given binary tree, no matter if it's balanced or not.

The null tree has depth -1, the root has depth 0 and so on. By looking at the depth it is immediately possible to get the max number of elements at that depth: 2^depth.

You can check the code on my Gist (getTreeDepth) along with some test cases:

 //find depth of the tree  
   public static int getTreeDepth(BST root){  
     if(root == null) return -1;  
   
     return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;  
   }  

[Java] LinkedList sum

Here's a simple exercise: given two positive numbers represented as linked lists, return their sum as a new linked list.

This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:

A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1

You can check the code and some tests on my Gist (LinkedListSumJTests):

 /*  
   Given two lists representing integer numbers  
   with the least significant digit in the head position  
   return a new list containing the sum  
   */  
   public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){  
     if(x == null && y == null) return null;  
   
     int carry = 0, curr = 0, val = 0;  
     SingleLinkedListNode result = null, n = null;  
   
     //keep going until we have data in either list and do not forget the last carry!  
     while(x != null || y != null || carry != 0){  
       curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry  
       val = curr % 10; //take only LSD  
   
       //track if we have a carry  
       carry = (curr >= 10) ? 1 : 0;  
   
       if(n == null){  
         n = new SingleLinkedListNode(val);  
         result = n;  
       }  
       else{  
         n.next = new SingleLinkedListNode(val);  
         n = n.next;  
       }  
   
       //move to next digit  
       if(x != null) x = x.next;  
       if(y != null) y = y.next;  
   
     }  
   
     return result;  
   }  

[Java] Rolling average for both sorted and unsorted streams

The rolling, moving, running, whatever movement verb you like median or average is a problem regarding the online calculation of the average element in a streaming dataset.

The pro version requires you to sort the data on the fly in order to produce the median result:

input = 9, 4, 10, 3, 3
output = 4 because sorted input is: 3, 3, 4, 9, 10

The base version just wants the actual median element of the stream:

input = 9, 4, 10, 3, 3
output = 10

If the stream length is odd, the median is the actual median element, otherwise it's the average of the two elements near the middle of the stream.

The solution to both returns the median in constant O(1) time and keeps it updated in O(N) time. Also they both use additional O(N) space.

[Java] Reconstruct binary tree from visits

An alternative way to represent a binary tree is to use an array. If the tree is a binary search tree and is also perfectly balanced, it's easy to find each node with the formula:

node         = idx of node in array
left child   = 2 * idx of node in array + 1
right child = 2 * idx of node in array + 2

But if the tree is not balanced, we need more information. For example, given a inorder and a postorder visit of the tree, we can rebuild it easily.

The idea is as such:

• in the preorder visit array at position 0 we have the root
• in the inorder visit array before the index of the root found at previous step, we have the left subtree and after we have the right subtree
• we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot

CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays. However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object, without considering the content.

[Java] Binary Tree visits

Given a binary tree, we have many ways of visiting it, depending on our goals:

• BFS: search tree by levels
• DFS inorder: visit root first, then left, then right
• DFS preorder: visit left, then root, then right. Useful to retrieve the tree values in ascending order
• DFS postorder: visit left, then right, then root. Useful when deleting the tree

You can check the code on my Gist.

BFS:

 public static List<Integer> BFSVisitList(BST root){  
     if(root == null) return null;  
   
     List<Integer> out = new ArrayList<>();  
   
     Queue<BST> q = new LinkedList<BST>();  
     q.add(root);  
   
     while(!q.isEmpty()){  
       BST t = q.remove();  
       out.add(t.getVal());  
       if(t.left != null) q.add(t.left);  
       if(t.right != null) q.add(t.right);  
     }  
   
     return out;  
   }  
   
   public static int[] BFSVisit(BST root){  
     if(root == null) return null;  
   
     int[] res = null;  
     List<Integer> out = BFSVisitList(root);  
   
     if(out != null) res = out.stream().mapToInt(i -> i).toArray();  
   
     return res;  
   }  

DFS - inorder:

 private static List<Integer> doInorderVisit(BST root, List<Integer> out){  
     if(root != null){  
       doInorderVisit(root.left, out);  
       out.add(root.getVal());  
       doInorderVisit(root.right, out);  
     }  
     return out;  
   }  
   
   public static List<Integer> inorderVisitList(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doInorderVisit(root, out);  
   
     return out;  
   }  
   
   public static int[] inorderVisit(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doInorderVisit(root, out);  
   
     return out.stream().mapToInt(i -> i).toArray();  
   }  

DFS - preorder:

 private static List<Integer> doPreorderVisit(BST root, List<Integer> out){  
     if(root != null){  
       out.add(root.getVal());  
       doPreorderVisit(root.left, out);  
       doPreorderVisit(root.right, out);  
     }  
     return out;  
   }  
   
   public static List<Integer> preorderVisitList(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doPreorderVisit(root, out);  
   
     return out;  
   }  
   
   public static int[] preorderVisit(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doPreorderVisit(root, out);  
   
     return out.stream().mapToInt(i -> i).toArray();  
   }  

DFS - postorder:

 private static List<Integer> doPostorderVisit(BST root, List<Integer> out){  
     if(root != null){  
       doPostorderVisit(root.left, out);  
       doPostorderVisit(root.right, out);  
       out.add(root.getVal());  
     }  
     return out;  
   }  
   
   public static List<Integer> postorderVisitList(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doPostorderVisit(root, out);  
   
     return out;  
   }  
   
   public static int[] postorderVisit(BST root){  
     if(root == null) return null;  
     ArrayList<Integer> out = new ArrayList<>();  
     out = (ArrayList) doPostorderVisit(root, out);  
   
     return out.stream().mapToInt(i -> i).toArray();  
   }  

The code works with Java 8 because converting a List to an array[] is now super simple thanks to the black magic behind list.stream().mapToInt(i -> i).toArray()

[Java] Remove kth to last node in a singly LinkedList

Here is a simple method to remove the k-th to last element from a singly LinkedList (not the standard one). Runtime is going to be O(N) and space is going to be O(1). Keep scrolling for a better version that still runs in O(N) time - although actual better running time! - and O(1) space using two pointers.

The idea is simply to walk the list first to find out how many elements are there, then calculate which element we want to remove and walk the list again until we find and remove it. It is not possible to remove the head element, so we must return the, potentially new, head node after editing the list in place.

We count elements in the list starting from 1 so k = 0 means remove the last element and k = length - 1 means remove the first element. If k = length, we are asking to remove element 0 which does not exist.

You can check my Gist for the code with tests (RemoveKtoLastNode) and the LinkedList data structure (SingleLinkedListNode):

 //CAUTION: must return a value because otherwise we would not be able to remove the head element  
   public static SingleLinkedListNode removeKtoLastNode(SingleLinkedListNode head, int k){  
     if(head == null) return head;  
   
     int length = head.length();  
     /*  
     list is 1 to length, so check k is in that range  
     CAUTION: we are removing kth to last so k = 0 means remove last  
     k = length -1 means remove first  
     */  
     if(k < 0 || k > length - 1) return head;  
   
     int n, count = 1;  
     SingleLinkedListNode prev = head, next;  
   
     //find out which element we want to remove  
     n = length - k;  
   
     //if it's the head, just return next  
     if(n == 1){  
       return prev.next;  
     }  
   
     //otherwise walk through the list and delete the desired element  
     while(prev != null){  
       next = prev.next;  
       //CAUTION: check with count + 1 so we do not skip the element we want to delete. next will be it!  
       if(n == count + 1){  
         if(next != null) prev.next = next.next;  
         //CAUTION: avoid NullPointerException when we are deleting tail  
         else prev.next = null;  
         return head;  
       }  
       prev = prev.next;  
       count++;  
     }  
   
     return head;  
   }  

The alternative method using two pointers instead does not require us to calculate the list length beforehand, instead we let a pointer walk the list and start running a second pointer only after the first one has done K+1 steps. This means that when the first pointer reaches the end, the second will be exactly before the element to delete.
There is just one thing to be careful about: at the end the slow pointer might not be pointing anywhere. This means we might want to remove the head element or we got a K greater than the length of the list.

Here is the snippet from my Gist:

   
   
   //CAUTION: must return a value because otherwise we would not be able to remove the head element  
   public static SingleLinkedListNode removeKtoLastNodePointers(SingleLinkedListNode head, int k){  
     if(head == null || k < 0) return head;  
   
     int fast_idx = 0;  
     SingleLinkedListNode fast = head, slow = null;  
   
     /*  
     keep two pointers running after each other  
     the slow one starts k+1 steps after the fast one  
     when the fast one reaches the end of the list, the slow one should be exactly before the element to remove  
     */  
     while(fast.next != null){  
       if(slow != null) slow = slow.next;  
       fast = fast.next;  
       fast_idx++;  
       if(fast_idx == k + 1) slow = head;  
     }  
   
     //if the slow one is actually pointing somewhere, remove the following node  
     if(slow != null) slow.next = slow.next.next;  
   
     //otherwise if we want to remove the head (k = list length), just return the next from head  
     if(fast_idx == k) return head.next;  
   
     return head;  
   }  

[Java] Remove duplicates from a singly LinkedList

Here is a simple method to remove all duplicate nodes from a singly LinkedList (not the standard one) without using additional data structures. This means the runtime is going to be O(N^2) and space is going to be O(1).

The idea is simply to walk the list with a pointer and for each element walk the remainder of the list using two pointers. When we find a match to the element we are currently evaluating, we remove it. It is not possible to remove the head element, so we can edit the list in place.

You can check my Gist for the code with tests (RemoveDuplicates) and the LinkedList data structure (SingleLinkedListNode):

 public static void removeDuplicates(SingleLinkedListNode head){  
     SingleLinkedListNode curr, prev, next;  
   
     curr = head;  
   
     //for each single node  
     while(curr != null){  
       //track 2 nodes at the same time  
       prev = curr;  
       next = prev.next;  
       //walk the whole list  
       while(next != null){  
         /*  
         if the next node is a duplicate, delete it by linking the previous to the next.next  
         CAUTION: do NOT move the previous node because we could lose a value  
         */  
         if(next.data == curr.data) prev.next = next.next;  
         //only move previous if the next one was unique  
         else prev = prev.next;  
         //move next to the new next element  
         if(prev != null) next = prev.next;  
       }  
       curr = curr.next;  
     }  
   }  

[Java] Compress string by counting character repetitions

Here is a simple method to compress a string by counting the character repetitions and producing a new string  containing that information; if the compressed string is longer, just keep the original one.

The idea is simply to walk the string keeping track of the current count for each item we encounter in two separate arrays. Then we walk both arrays at the same time and concatenate each character with the number of appearances he had; lastly we check if the compressed string is shorter and decide what to return.

You can check my Gist for the code (stringCompress) with tests:

 public static String stringCompress(String s){  
     if(s == null || s.length() <= 1) return s;  
   
     int[] counts = new int[s.length()];  
     char[] chars = new char[s.length()];  
     char c;  
     int j = 0;  
   
     counts[0] = 1;  
     chars[0] = s.charAt(0);  
   
     //for each character in string, count how many times it appears  
     for(int i = 1; i < s.length(); i++){  
       c = s.charAt(i);  
   
       if(c == chars[j]) counts[j]++;  
       else{  
         j++;  
         chars[j] = c;  
         counts[j] = 1;  
       }  
     }  
   
     //if we compressed the string a bit, then our arrays have some space left, mark the premature end  
     if(j < counts.length - 1) counts[++j] = -1;  
   
     //we do not want to create a new String everytime while we concatenate  
     StringBuilder sb = new StringBuilder();  
   
     j = 0;  
     while(j < counts.length){  
       if(counts[j] == -1) break;  
       //for each character in original string, concatenate it alongside the number of occurrences  
       sb.append(chars[j]);  
       sb.append(counts[j]);  
       j++;  
     }  
   
     //if the compressed string is longer, return original string instead  
     if(sb.length() > s.length()) return s;  
   
     return sb.toString();  
   }  

[Java] String replaceAll method from space to %20

Here is a simple method to replace all occurrences of space in a string with '%20' without using the replaceAll method.

The idea is to first count how many spaces are there in the string, then allocate a char array of appropriate size and fill it up correctly.

You can check my Gist for the code (replaceSpace) with tests:

 public static String replaceSpace(String s){  
     if(s == null || s.length() == 0) return null;  
   
     int space_count = 0;  
     char c;  
   
     //count how many white spaces we have  
     for(int i = 0; i < s.length(); i++){  
       c = s.charAt(i);  
       if(c == ' ') space_count++;  
     }  
   
     if(space_count == 0) return s;  
   
     //allocate space for new string replacement. CAREFUL: we replace 1 char with 3 so we need 2 extra spaces!  
     char[] res = new char[s.length() + space_count * 2];  
   
     //prepare result string. CAREFUL: can't use same index otherwise we skip characters in either string or char[]  
     for(int i = 0, j = 0; j < s.length(); i++, j++){  
       c = s.charAt(j);  
   
       if(c == ' '){  
         res[i] = '%';  
         res[++i] = '2';  
         res[++i] = '0';  
       }  
       else res[i] = c;  
     }  
   
     return new String(res);  
   }  

[Java] Find most consecutively repeated character in string

Here is a simple method to find the most consecutively repeated character in a string. In my view punctuation and case should not be ignored.

The idea is simply to walk the string keeping track of the current count for the item we're evaluating. When we encounter a different character, we check if the item we were evaluating appeared more times than the current max and if so, we set it as the current max.

You can check my Gist for the code (maxRepChar) with tests:

 public static Entry maxRepChar(String s){  
     Entry max = new Entry(), curr = new Entry();  
     char c;  
   
     if(s == null || s.length() == 0) return null;  
   
     //initialize with first item in string  
     curr.count = 0;  
     curr.c = s.charAt(0);  
     max.count = 0;  
   
     for(int i = 0; i < s.length(); i++){  
       c = s.charAt(i);  
   
       /*  
       keep incrementing the current counter for the item we're evaluating now  
       as long as we have a subsequent uninterrupted stream  
       */  
       if(c == curr.c) curr.count++;  
       else{  
         /*  
         when we interrupt the stream, check if the item we're evaluating  
         appeared more times than the current maximum, if so, set it as max  
         */  
         if(curr.count > max.count){  
           max.count = curr.count;  
           max.c = curr.c;  
         }  
   
         //and reset the counter for current item  
         curr.c = c;  
         curr.count = 1;  
       }  
     }  
   
     //don't miss the case when the max run untils end of string  
     if(curr.count > max.count){  
       max.count = curr.count;  
       max.c = curr.c;  
     }  
   
     return max;  
   }  

The Entry class is simply a helper structure:

char c;
int count = 0;

[Java] Check whether a string is palindrome

Here is a simple method to test if a string is palindrome. In my view punctuation should be ignored as well as case.

The idea is simply to walk the string from the borders towards the middle at the same time, skipping characters that are not alphanumeric until we either reach the middle or find two characters which are not same. Also, a single character is palindrome.

You can check my Gist for the code (isPalindrome) with tests:

 public static boolean isPalindrome(String s){  
     if(s == null || s.length() < 1)return false;  
   
     for(int i = 0, j = s.length() - 1; j > i; ){  
       if(!Character.isLetterOrDigit(s.charAt(i))){  
         i++;  
         continue;  
       }  
       if(!Character.isLetterOrDigit(s.charAt(j))){  
         j--;  
         continue;  
       }  
       if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))return false;  
       else{  
         i++;  
         j--;  
       }  
     }  
     return true;  
   }  

[Java] Trie data structure for text input prediction

A Trie is a very useful data structure with a confusing name, which is luckily easier to use than to pronounce.

I have seen it mainly used in input text suggestion or String analysis. The structure is a Tree where each node can have a label and multiple children; nodes with a label represent a full piece of data (eg a word) while nodes without label are used only for navigation or substring evaluation for example.

The list of children can be implemented with different data structures, I propose a version using a HashMap for faster searching: given an input String s, starting from the first character keep calling get(char) until we reach a word to suggest. Each get is O(1) so we are only paying O(M) (worst case is we're going to predict the longest string present).

Using a List would require us to scan the list until we find the entry for the next character which I think due to big-O magic can be assumed to still be O(1) since the list is at most as big as the alphabet we are using and therefore we can call it constant size, but still sounds like an unnecessary operation to me.

LinkedHashMap would not help much unless we associate some meaning with the insertion order eg: most often used words first.

TreeMap would slow the process down but guarantee to retrieve words in the desired order (eg alphabetical).

[Java] 0/1 Knapsack problem O(n log n) heuristic

The 0/1 knapsack problem is a fairly common problem in daily life and it's unfortunately one of those problems where you must accept that the optimal solution cannot be computed as quickly as you would like, no matter how hard you think about the problem. As a friend put it, "if the solution looks like black magic, there is probably something wrong with it".

The problem description states: given a recipient with a fixed capacity and a set of items, each with a specific weight and value, the goal is to find the subset that maximises the total value of the chosen items while not exceeding the maximum recipient capacity.
In the 0/1 version, you cannot break an object (not possible to only take a fraction of it) so you can only either take it or not.

Sometimes calculating the optimal solution is too expensive or simply unfeasible (eg online knapsack) so a different, possibly suboptimal approach has to be taken. The one described here uses a greedy algorithm and aims at maximising the total value by selecting items after ordering them by desirability in terms of value per space left after they are picked.

[SQL] Excel COUNTIFS - count columns matching criteria in a row

Excel in his arsenal of useful functions has COUNTIFS, basically a count of how many elements in a one dimensional range match a specific criteria. It says multidimensional, but it's not, it's either the same criteria twice for more dimensions or a different criteria. Key point: one list at a time.

However this is a very basic need which is not immediately achievable in SQL as well since we cannot loop over columns in a row. That is, unless we remember that PIVOTing is actually a thing. In this specific case we use the inverse operation, UNPIVOT.

[Java] Mergesort sorting algorithm for int arrays

Mergesort is well known as one of the best sorting algorithms out there with a O(n log n) worst case runtime; it doesn't get much better than this without strange big-O tricks.

But while understanding how it works is easy, implementing it is a different story given that it combines two nested function calls in the recursion and requires careful array index management. Also Java pass by value adds a small gotcha for good measure.

You can find my implementation for int[] arrays (as in: not Integer, not ArrayList, not List, not whatever else. Pure and simple int primitive data type with old fashioned array, the kind that does not change size once created if you can still remember those) on my Gist along with some test cases.

[Python] BloggerBackup script to backup Blogger posts

This script allows users to quickly download posts from their Blogger blog in order to keep a backup copy. On Windows there is the amazing BloggerBackupUtility but sadly that's not available for Linux as well, hence this small project comes to life.

You can get the utility here or check out the source code here. To run it, you must have Python 3 installed.

Usage is:

 bloggerbackup --api-key <API key> --blog <blog URL> --backup-dir <backup directory> [--start-date <date>] [--end-date <date>] [--verbose]  

options:

   --help - prints this help  
   
   --api-key <api key> - mandatory API key used to issue queries  
   
   --blog <blog URL> - mandatory URL of the blog to operate on  
   
   --backup-dir <backup directory> - mandatory directory where to put the posts backup  
   
   --start-date <date> - optional, date from which to begin fetching posts in RFC 3339 format: yyyy-MM-ddTHH:mm:ss+HH:mm  
   
   --end-date <date> - optional, date where to stop fetching posts in RFC 3339 format: yyyy-MM-ddTHH:mm:ss+HH:mm  
   
   --verbose - optional, prints debug information while processing  

The script is extremely barebone and definitely improvable. Also, it requires you to setup an own API key in order to issue queries in the free tier. To do so, visit the Google credentials page.

[Java] BST element distance - parent pointer

Well, that's a bit anticlimactic. After playing with the other approaches, the one that initially gave me the most pain was also quite fast to implement as soon as the AHA! moment came.

However spoiler alert: the results are quite disappointing.

[Java] BST element distance - lowest common ancestor

So I was thinking about the parent pointer approach to find the distance between to elements in a binary search tree and avoiding using the path lists approach, which means finding the lowest common ancestor; that's the lowest node in the tree that is common to both paths to the two elements.
If the elements are one the child of the other, then it will be equal to the parent, otherwise it will either be the root if the elements are on completely different branches or the divergence node if the elements are in the same subtree.

Then I got down to coding and when I got to the LCA logic, finally, ... I did not use the parent pointer yet again :(

[Java] BST element distance - path lists

The exercise that stole too much time from me last time was about binary search trees. The description is quite simple: find the distance between two elements in a given tree; that means how many hops do you need to do to navigate to element B from element A; if the elements are the same, distance is 0, if one or both elements are missing, distance is -1.

[Java] Scorecard algorithm

Some time ago I took an online coding test which left me with an unfinished exercise; I played too long with the other one and had no time to finish this :(

However it seemed quite easy and interesting so I decided to finish it later, here is the description of the exercise as I remember it and my solution:

Bill plays some kind of game where the score is tracked on a scorecard; in addition to simple scoring moves, he can attempt (and possibly fail) more rewarding moves that will influence the score calculation.

Bill starts with a score of 0 and cannot earn negative points.

Bill can alter his total score by:

• scoring a point (integer) - it will be added to the total score
• doubling a previous score ("X") - the previous score will be doubled before adding it to the total score. If there is no previous score, it counts as 0
• summing two previous scores ("+") - the two precedent scores will be summed together before adding the result to the total score. If there are no predecessors, it counts as 0; if there is only one predecessor, it will be added again to the total score
• failing a move ("Z") - the previous score will be ignored from the total score and its value will also not be considered for subsequent special moves. If there is no previous score, this has no effects

[Sheet music] Johann Pachelbel - Kanon

Simplified version but still very relaxing. Download it here: part 1 and part 2.

[Oracle] Aurora module exception when compiling Java code on the DB

Sometimes it is possible to receive an exception when compiling Java code or running tools that generate Java code on the Oracle DB with this signature:

ORA-29516: Aurora assertion failure: Assertion failure at some_source:some_line_number

It is usually easy to prevent this error by disabling the JIT compilation on the DB:

alter session set java_jit_enabled = false;