[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


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


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


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


[Java] Find largest sum subarray

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.