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:
  1. 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
  2. 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
  3. 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
  4. 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
  5. run sudo update-grub and you are set
Note that this is a TEMPORARY fix, you would not want to have a fully updated system run on an older version of the kernel, mainly because some obscure dependency or feature might be missing/not working, therefore check back periodically to see if your issue has been addressed and try the latest kernel version out!


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

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.

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:
  • 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
This exercise will easily tangle your brain with all those indexes flying around, so it's quite sure to make some small mistake while coding. Luckily testing and writing while testing on paper helps a lot to keep this in check.

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.