23/10/2017

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

NumberBitsModuloModulo bits
1000110001
2001020010
3001130011
4010000000
5010110001
6011020010
7011130011
8100000000
9100110001


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.




22/10/2017

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

17/10/2017

[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  
  while (n2 > 0) loop  
    binval := mod(n2, 2) || binval;  
    n2   := trunc(n2 / 2);  
  end loop;  
   
  return binval;  
 end num_to_bin;  

11/10/2017

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

I was asked this at an interview and I am quite surprised by the difficulty of it; coming up with suboptimal solutions is quite easy though I have to admit.

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