- generate a new key and place it in a keystore:
- verify the content of a keystore:
- export the public key:
- delete a key:
- add a private key:
- add a public key:
26/08/2018
[Java] Useful keytool commands
Keytool is a tool to manage Java keystores. Here are some useful commands to:
15/08/2018
[Ubuntu] Revert kernel back to older version
Intro story: So much luck in a single day.
I always keep only 2 kernel versions after every update, so that I can boot back if something goes wrong. This usually helps, except today I decided to upgrade my Ubuntu from 16.04 to 18.04 since I like spending my nights fixing stuff after unnecessary upgrades, but hey, the future is there.
So I first fully updated my current installation (1st kernel bump), then migrated to the new one (2nd kernel bump) and it turns out I got two 4.15 kernels, with only different minor version.
Double interesting, my wireless card:
02:00.0 Network controller: Realtek Semiconductor Co., Ltd. RTL8821AE 802.11ac PCIe Wireless Network Adapter
apparently has issues (read: bug) with kernel 4.15 preventing it from working at all (not even connected to the router), and even more interesting, on one version it can actually only connect to websites under google.com domain..
Anyway, quick fix was to revert back my kernel, here is how for future me to remember:
I always keep only 2 kernel versions after every update, so that I can boot back if something goes wrong. This usually helps, except today I decided to upgrade my Ubuntu from 16.04 to 18.04 since I like spending my nights fixing stuff after unnecessary upgrades, but hey, the future is there.
So I first fully updated my current installation (1st kernel bump), then migrated to the new one (2nd kernel bump) and it turns out I got two 4.15 kernels, with only different minor version.
Double interesting, my wireless card:
02:00.0 Network controller: Realtek Semiconductor Co., Ltd. RTL8821AE 802.11ac PCIe Wireless Network Adapter
apparently has issues (read: bug) with kernel 4.15 preventing it from working at all (not even connected to the router), and even more interesting, on one version it can actually only connect to websites under google.com domain..
Anyway, quick fix was to revert back my kernel, here is how for future me to remember:
- go to http://kernel.ubuntu.com/~kernel-ppa/mainline/ and download in the same folder: linux-headers-VERSION-generic-XXX_SYSTEM.deb, linux-headers-VERSION_all.deb, linux-image-VERSION-generic-XXX_SYSTEM.deb for your system, eg I have 64 bit system and got amd64 files
- install them by going into the folder where you downloaded them, make sure there are only those three .deb files and run: sudo dpkg -i *.deb
- restart the system, then press SHIFT at boot to enter the GRUB choices, then check from the top line (number 0) to the line of your kernel version. If your installation has the "Advanced" menu entry and does not display all kernels, go there and do the same counting. We need this to set a default GRUB entry to always boot in this kernel
- edit /etc/default/grub and change the value of GRUB_DEFAULT to the number you counted OR to (exactly as shown) "1>N" if you have the "Advanced" menu option. This means you want to boot into the Nth entry (starting from 0) under the "Advanced" menu. Also set GRUB_TIMEOUT to some value in seconds that's more than 1, to have some time to block the boot process in case of mistakes
- run sudo update-grub and you are set
26/05/2018
[Oracle] Verify if column has not null check
To test whether a column in an Oracle DB has been declared with a NOT NULL check, it is possible to query the dba_tab_columns table:
SELECT nullable
FROM dba_tab_columns
WHERE owner = :owner
AND table_name = :table
AND column_name = :column
;
Where owner, table_name and column_name are all upper case. That would output (always in upper case):
N = not nullable
Y = nullable
This will NOT work if the check is done with a constraint instead
SELECT nullable
FROM dba_tab_columns
WHERE owner = :owner
AND table_name = :table
AND column_name = :column
;
Where owner, table_name and column_name are all upper case. That would output (always in upper case):
N = not nullable
Y = nullable
This will NOT work if the check is done with a constraint instead
10/05/2018
[Java] Total votes count as of given timestamp
Given a list of timestamped votes, return the top K voted people (including ties) as of a given timestamp.
Add an input parameter to specify if the ranking should be done olympic style, eg: if 2 people are in first place, then the next place is 3rd and not 2nd; in this case, for skipped places, return an empty list.
This is NOT a streaming problem, since the list of votes is given fully in input. Since it includes some sorting, it can be solved in O(N log N) time and O(N) space.
The input is given as a list of Vote objects and we use an auxiliary structure, CandidateVote for our max heap.
The idea is to use a map from candidate to total votes count to track the total votes for each candidate as of the given timestamp (do NOT consider votes AFTER the given time) by scanning the full input in O(N).
Then, we use a MAX heap (new PriorityQueue(Collections.reverseOrder()); ) along with our comparator to order them descending.
Now we simply need to pick ALL the candidates tied at the same place for each position up to K. This gets a bit more complicated if we do the olympic ranking, since we need to skip places if many people are tied in one. For example:
A - 2
B - 2
C - 1
with a topK = 2 would return 1st: A,B - 2nd: empty, but with a topK = 3 would return 1st A,B - 2nd: empty - 3rd: C.
Gotchas: the usual suspects, our heap might become empty at some point, so check for it to avoid NullPointerExceptions. If we are doing olympic ranking, we need to advance in position UP TO K, while still filling the skipped ones with empty lists.
This is another exercise where proper testing goes a long way towards spotting these small mistakes, also PriorityQueue comes to the rescue one again :)
You can check my implementation of getVoteRanking on my Gist alongside the previously mentioned auxiliary data structures and some test in VoteRankingJTests.
Add an input parameter to specify if the ranking should be done olympic style, eg: if 2 people are in first place, then the next place is 3rd and not 2nd; in this case, for skipped places, return an empty list.
This is NOT a streaming problem, since the list of votes is given fully in input. Since it includes some sorting, it can be solved in O(N log N) time and O(N) space.
The input is given as a list of Vote objects and we use an auxiliary structure, CandidateVote for our max heap.
The idea is to use a map from candidate to total votes count to track the total votes for each candidate as of the given timestamp (do NOT consider votes AFTER the given time) by scanning the full input in O(N).
Then, we use a MAX heap (new PriorityQueue
Now we simply need to pick ALL the candidates tied at the same place for each position up to K. This gets a bit more complicated if we do the olympic ranking, since we need to skip places if many people are tied in one. For example:
A - 2
B - 2
C - 1
with a topK = 2 would return 1st: A,B - 2nd: empty, but with a topK = 3 would return 1st A,B - 2nd: empty - 3rd: C.
Gotchas: the usual suspects, our heap might become empty at some point, so check for it to avoid NullPointerExceptions. If we are doing olympic ranking, we need to advance in position UP TO K, while still filling the skipped ones with empty lists.
This is another exercise where proper testing goes a long way towards spotting these small mistakes, also PriorityQueue comes to the rescue one again :)
You can check my implementation of getVoteRanking on my Gist alongside the previously mentioned auxiliary data structures and some test in VoteRankingJTests.
09/05/2018
[Java] Forced array swaps
Given a start and end array, generate a list of positions where to swap the 0 element in order to move all elements from start to end position with the following rules:
The idea is simple: since we cannot swap elements between themselves, if we want to bring an element to a certain position, we must bring the 0 element there first, then swap it with the desired element.
While doing this, we always keep track of where did we move the 0 element, to generate our output.
Time and space complexity is O(N). As auxiliary structures we use a map from element to its current position; in this implementation we reuse the input array for our processing, but we could also easily copy it to a new array if we do not want to destroy the input, still keeping the space in O(N).
For processing, starting at index 0, we check if the elements in current (initially start) and end array match. If not, we swap the element at the current position with the element 0, then we check again and if the elements still do not match, we swap the 0 with the desired element before moving on to the next index.
Since we do at most 2 sets of constant operations (map gets and puts + list add + swaps) for each index, the total time is O(N).
Meanwhile, we always maintain our map updated and remember to track in another structure all the places where we moved the element 0.
You can check my implementation of forcedSwaps on my Gist alongside some test cases in ForcedSwapJTests.
- elements can only be swapped with the 0, not between themselves
- each element can only appear once
- element 0 must be in the arrays
- there can be more than one way to obtain the desired swap, return any valid sequence
The idea is simple: since we cannot swap elements between themselves, if we want to bring an element to a certain position, we must bring the 0 element there first, then swap it with the desired element.
While doing this, we always keep track of where did we move the 0 element, to generate our output.
Time and space complexity is O(N). As auxiliary structures we use a map from element to its current position; in this implementation we reuse the input array for our processing, but we could also easily copy it to a new array if we do not want to destroy the input, still keeping the space in O(N).
For processing, starting at index 0, we check if the elements in current (initially start) and end array match. If not, we swap the element at the current position with the element 0, then we check again and if the elements still do not match, we swap the 0 with the desired element before moving on to the next index.
Since we do at most 2 sets of constant operations (map gets and puts + list add + swaps) for each index, the total time is O(N).
Meanwhile, we always maintain our map updated and remember to track in another structure all the places where we moved the element 0.
You can check my implementation of forcedSwaps on my Gist alongside some test cases in ForcedSwapJTests.
07/05/2018
[Java] Minimize travel distance to single array index
Given an array indicating how many people live at the specific index, return the index where to place a postbox that minimizes the total travel time to it for all people.
The following rules apply:
An obvious O(N^2) solution is to compute the total travel distance for each possible place and store it in a matrix O(N^2), then walk over it to compute the best solution.
A better solution requires some preprocessing and 2 extra O(N) arrays but runs in O(N) total time.
An even better solution uses only one extra array instead.
The following rules apply:
- people residing at the same place of the postbox have a total travel time of 0
- N people needing to take 1 step to reach the postbox have a total travel time of N
- multiple solutions could be acceptable
An obvious O(N^2) solution is to compute the total travel distance for each possible place and store it in a matrix O(N^2), then walk over it to compute the best solution.
A better solution requires some preprocessing and 2 extra O(N) arrays but runs in O(N) total time.
An even better solution uses only one extra array instead.
06/05/2018
[Java] Find largest sum subarray - Kadane's algorithm
Given an array of integers, the maximum subarray problem is about finding the subarray with the largest sum given the following specifications:
- for an array of all negative numbers, return the smallest of them
- for an array of all positive numbers, return the sum of all element
As output we want the start and end indexes as well as the total sum for the biggest portion identified. There may be multiple solutions.
The O(N) idea is to walk the array while keeping track of the local best and global best. The local best is the sum of elements until the one being currently considered; we initialize both to the first element of the array and remember to begin the loop from the element in position 1!
At each time, the local best can either be improved by adding to it the current element, or reset to start from the current element otherwise. We make this consideration first and in case, move the start index of the current best solution to the current position, then we compare it against the global maximum updating it if needed.
We track the result in an auxiliary structure, Range. You can check its implementation on my Gist alongside the implementation of getLargestSumSubarray and some test cases in LargestSumSubarrayJTests.
Turns out this algorithm is called Kadane's algorithm.
Subscribe to:
Posts (Atom)