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.
Pages
▼
31/10/2017
[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!
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!
29/10/2017
[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
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
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:
You can check more bit magic on my Gist along with some test cases.
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):
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.
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:
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.
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.
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.
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
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;
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.
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
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.
________
|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.
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.