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