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

08/10/2017

[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

21/09/2017

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