[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

[Sheet music] Ludovico Einaudi - Una mattina

Download it here

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

[Java] Topological sorting

Topological sorting of an acyclic graph is a representation of the graph where each node appears before every other node that links to it. This is useful for example for dependency checking to determine which items should be processed before others.

There are many ways of solving this problem, some easier to derive than others.
If the graph contains a cycle no solution can be obviously found.

The runtime of the proposed solution is O(V+E) where V is the number of vertexes and E the number or edges. The input could have included the list of vertexes as well, but it can also be derived from the list of edges itself, therefore I did not include it, although this means that vertexes with NO incoming edges at all, would not be included in the solution.

[Java] Find biggest square in matrix

Given an input matrix of only 0s and 1s, find the biggest square composed only of 0s. The square must be parallel to the matrix edges.

We could solve this in O(MxN)^2 time and constant space, by checking for each cell the biggest square that can be formed starting from there, but since we know a bit of dynamic programming, we decide that O(MxN) extra space is worth reducing the time to O(MxN) :)

The problem can be solved by decomposing it in smaller subproblems considering as base case the single cell; if it contains a 0, it's a valid 1x1 square.
From there, we expand considering the cell as either the BOTTOM-RIGHT corner of a bigger square which is valid if and only if the VALID (left, top, top-left) neighbours are 0s as well OR the TOP-LEFT cell of a new square starting there. Consider these cases:

0

00
00

000
000
000

The black 0 is the one we are evaluating now, the red zeroes are the neighbours we are considering for our case and the green zeroes are the cells we already evaluated before, when we were applying the logic to each of the neighbours we are considering now. The DP matrix for each of those situations would be:

1

1 1
1 2

1 1 1
1 2 2
1 2 3

Where each number indicates the number of extensions (length of one side) the particular cell contributes to the biggest square having the current cell as BOTTOM-RIGHT corner of it.

The solution would then be that number, squared.

[Java] Summarize a TreeSet

Given a TreeSet of Integers, return a string representation according to the following rules:

• if N is in the TreeSet but N-1 and N+1 are not, return N and comma separate it from the rest
• if N is in the TreeSet and N-1 or N+1 are too, return a dashed range

eg:
1,5,9 should output 1,5,9
1,2,4,5,6,7,8 should output 1-2,4-8

The idea is to track an item while iterating over the TreeSet in ascending order and tracking whether the current item is part of a range - it is if it's equal to the tracked item + 1.
When we encounter an item that breaks the current range, we check the rules and determine what to print, either a range or a single item.

Note: at the end of the iteration it is still important to check if the last element (yet unprocessed) was part of a range or not and in case add it to the result.

Runtime is O(N) and space is O(1).

You can check my implementation of summarize on my Gist alongside some test cases in TreeSetJTests.

[Java] Iterative inorder tree traversal

Some time ago we saw different ways to visit a binary tree, today we take a spin on one of those and implement an inorder traversal without recursion.

You can check the code on my Gist.

 //iterative inorder visit, use a stack as helper structure  
   private static List<Integer> doInorderVisitIterative(BST root, List<Integer> out){  
     if(root == null) return out;  
   
     BST curr = root;  
     Stack<BST> s = new Stack<>();  
   
     //keep looping as long as we have at least one valid element  
     while(!s.isEmpty() || curr != null){  
       //if current element is not null, keep stacking the left children  
       if(curr != null){  
         s.push(curr);  
         curr = curr.left;  
       }  
       //when we get a null, move up the tree (in stack view) again, visit the node, and switch to the right subtree  
       else{  
         curr = s.pop();  
         out.add(curr.getVal());  
         curr = curr.right;  
       }  
     }  
   
     return out;  
   }