[Java] Using annotation processing (and validating it) to execute logic at runtime

Sample project showcasing how to use annotations to perform runtime logic to log changes in object values.

Remember it is a SAMPLE, so obviously (lazy me) most null-safe checks and so are not included and obviously some logic is a showcase, should be replaced with a real business scenario to implement.

In this SAMPLE, we tag fields to be included in a diff logic to then print to output when those fields values change by comparing two instances of the same object.

Logic can obviously be made much more complex including collections and maps and whatnot (Java Generics are your friends there).

Also worth mentioning JaVers can do most of it for you, unless you have fancy business requirements that force you to write custom code..

Key points:

- How to create an annotation

- How to create an annotation processor to validate the annotation parameters at compile time

- How to register an annotation processor

- How to configure a multi-module Maven project to use a custom annotation processor (also, in the pom of the root project ensure the module containing the processor is built BEFORE everything else)

- How to test an annotation processor by generating classes at runtime and trigger compilation tasks agains them. Includes verifying compilation warnings are properly triggered as expected.

- How to use reflection to get fields annotated with a given annotation (and then execute whatever logic on them)

- How to use reflection to invoke methods (including static methods)

The full project is available on my GitHub repo with commented code: https://github.com/steghio/diff-annotation-processing

[Java] Prim algorithm to find Minimum Spanning Tree in a graph

The minimum spanning tree (MST) is a subset of all edges in a weighted, undirected, connected graph such that the resulting graph is still connected and the sum of all edge weights is minimal.

If we are not given a list of edges, but only a list of vertices and a formula to calculate the edge weight given two graph nodes, we can run a preprocessing step to generate ALL possible edges between ALL graph nodes and calculate their weight in O(V^2).

Then, starting from a random node, we greedily choose one reachable vertex which has minimal distance from the current node. We continue exploring until all graph nodes have been touched.

There might be multiple valid MSTs for a given graph, this algorithm will return one of them.

We use a queue sorted by weight to determine which edge (and therefore node) to visit next, this ensures that if a node is reachable via multiple edges, we always pick the smallest weight for it. Since the graph is fully connected, we are ensured eventually we will have picked ONE edge between each node in the graph, and the sum of weight of all the chosen edges is minimal.

This runs using O(E) space since we might add all edges to the queue and O(E log(E)) time since for each edge we add to the queue we pay the O(log(E)) cost of insert and remove operation.

If the graph was NOT connected, this will NOT return the MST, only the MST for the connected component where the chosen start node resides. We could adapt the algorithm to verify whether there are extra nodes not yet visited, and repeat the processing for each until we have created a MST for each connected component in the graph.

In case the graph is not conencted, an alternatve can also be Kruskal's algorithm.

You can find my implementation of primMinimumSpanningTree on my Gist along with some tests in PrimMSTJTests.

[Java] Graph union find algorithm

For an undirected graph, we can compute the disjointed sets that represent all connected nodes in the subgraph where each node resides.

For each set, we elect a representative, all nodes reachable in a set will have the same representative. The resulting view will be a tree where the representative sits at the root and all connected nodes are its children.

Example applications include: quickly verify whether 2 nodes in a graph have a path to each other (they must belong to same set) or calculating the minimum number of edges to add to a graph to make it fully connected (or the opposite).

It is based on 2 operations:

find(Vertex x)

which will return for a given node, the representative of its subset. We recurse up the tree where this node resides until the representative is found. We optimize the operation for future searches by including path compression, where once a representative is found, all nodes along the same path are updated to track it. This makes it so that the find operation runs in O(inverse Ackermann(V)), which is considered O(1) but more realistically is O(log(log(...(V))) or how many times we need to apply log(x) to its result starting with V until the output is less than 1. It is an extremely slowly increasing sequence.

union(Vertex x, Vertex y)

which will connect the subtree where node x resides to the subtree of node y, unless they are already part of the same subtree. To improve efficiency we track in O(V) extra space the rank of each subtree (its depth) and when merging two subtrees, we connect the one with minimum depth to the other, so the overall height of the resulting tree is kept as flat as possible.

It uses O(V) extra space, to track for each node who is the representative of its subset and O(V) to track the rank of the subtree rooted at each node.

It runs in O(V Ackermann(V)) time since we run 2 find operation for each edge (pair of nodes) we unite and use the union by rank with path compression method.

You can check my implementation of unionFind on my Gist along with some tests in UnionFindJTests.

[Java] Kerberos login and retrieve GSSCredentials from KerberosTicket

A scenario that popped up recently was to login a user via Java code to Kerberos and retrieve a GSSCredential object containing the Kerberos ticket. I used Java 8, but this works since Java 7 onwards.

Java offers a Krb5LoginModule class which can be used in conjuction with a LoginContext to achieve this.

The flow is quite simple (once you have read all the Kerberos documentation):

• on the machine where the code runs, place a correct krb5.conf file in the default location for your OS (Windows uses krb5.ini) OR set the java.security.krb5.conf system property pointing to the file
• define a PasswordCallback handler class
  
• create a LoginContext with a configuration using Krb5LoginModule and provide the password callback handler. The configuration must force the login to request a user input, which will then be routed to the callback handler. It is possible to use a keytab or cache credentials, but it's not shown here
  
• login the user and get its KerberosTicket
• create a GSSCredentials object using the ticket

This procedure allows handling multiple login mechanisms in the application and even multiple Kerberos realms.

[Java] Calculate the angle between clock hands

return null;

Unless it's an analog clock, in which case:

The hour hand makes a 360 degree turn every 12 hours or 12*60 = 720 minutes, therefore each minute the hand moves 360/720 = 0.5 degrees

The minute hand makes a 360 degree turn every hour or 60 minutes, therefore each minute the hand moves 360/60 = 6 degrees

Setting 12 as the 0 position, to calculate the angle of each hand we can:

•     hours = 0.5 * current minutes for that hour (60 * hours + minutes)
•     minutes = 6 * minutes

We now have the position of both hand with respect to the 12 o'clock, the angle between them will simply be the difference, between the two positions (absolute value!)

If the difference is more than 180 degrees, the angle is a reflex angle and since we want the smallest angle between the hands, we take its complement by subtracting it from 360 (again, absolute value unless we did a modulo before to account for 24 hour format)

You can check my implementation of clockAngle on my Gist along with some tests in ClockAngleJTests.

[Java] Number of trailing zeroes in factorial

Given a number N, return the amount of trailing zeroes in its factorial.

Example:

4! = 24, no trailing zeroes

10! = 3628800, two trailing zeroes

100! = something big with 24 trailing zeroes

We could compute the factorial then count the zeroes, which is O(N) time and might work for small values of N, however multiplication can be indeed expensive.

[Java] Generate the K-th number made only of primes 3, 5, 7

Generate the K-th number made only of primes 3, 5, 7.

Expected results up to K = 15: 1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81

This exercise is one of those that once the solution is known it's extremely easy but getting to the optimal solution requires work.

An initial suboptimal idea could be to start with a queue and placing only 1 in it.

Then execute some iterations where the top of the queue is polled, multiplied by 3,5,7 and then all results are added back to the queue, including the polled value.

We need to track generated values to avoid duplicating them. After some iterations, sort the queue, then poll until the k-th value is reached.

However the numbers generated this way quickly stray from the natural ordering so we end up generating more numbers that we need to get the actual solution.

After a long examination and paper examples (try drawing a matrix that expands with each new generated value and keep generating until the solution is reached), we notice that the emerging pattern is:

• use a queue for 3s, 5s, 7s 
• take the smallest top from all queues
• multiply this value by 3,5,7 UNLESS it is bigger that the top of a queue, in which case we skip that queue, then push it back to the corresponding 3,5 or 7 queue
• stop at k-th iteration, the min value generated at that step is the answer

This uses O(N) time and space and most importantly stops as soon as a result is reached.

You can check my implementation of generateKth357 on my Gist along with some tests in GenerateKth357JTests.

[Java] Partition array in K subsets of equal sum

Given an array of positive integers and a target K, determine whether it's possible to partition the array in K subsets of equal sum.

Example:

1,1,1,1 k = 2

it's possible to have two sets, each with a total sum of 2

1,1,1,1 k = 3

it's not possible to have 3 sets of equal sum

We first determine if this is generally feasible by looking at the total sum of elements in our array and comparing with K. If possible, each set should sum up to total / K, which means K must be a divisor of our total sum.

We then need to explore all possibilities to generate each subset, this is evident in this sample:

1,1,1,2,2,2 k = 3

The only solution is to pair each 1 with a 2, we cannot apply a greedy approach as we might miss this solution.

A bit similar to the house painting problem, we need to recursively explore our options keeping track of:

• number of "full" subsets, that is subsets we created so far that reached our target sum
• available elements, as we can only place each element in a single subset
• current sum of each subset

We start with no subset existing and all elements available and try an add each available element to a set until we reach the target sum. Everytime we use an element, we mark it as unavailable.

When a set reaches the target sum, we increase the number of "full" subsets and start creating a new subset repeating this logic.

When we have no more available elements, if the amount of "full" subsets is reached, we have our answer, otherwise we need to backtrack and explore a different configuration.

When we backtrack we simply mark the current element as available again, remove it from the current subset sum and proceed on the next element.

This approach gives us a (N * 2^N) time complexity as for each element we explore the option of choosing it or not for the current subset and worst case we repeat this process for each element in our array before we realize no solution exists. Not sure whether sorting the array would have a significant impact on the runtime since there can exist a configuration where the total sum is divisible by K but no arrangement of elements is possible, maybe sorting descending can on average be faster but not in worst case.

We use O(N) space instead for the recursion stack (can't have more than N calls as we pick each element once in a branch) and the array tracking the available elements.

You can check my implementation of canPartitionInKSubsetsOfEqualSum on my Gist along with some tests in CanPartitionInKSubsetsOfEqualSumJTests.

[Java] Group anagrams

Given a list of strings, group all anagrams together.

Example:

asd, lol, dsa

return:

[lol], [asd,dsa]

Anagrams are words of the exact same length with the exact same characters, potentially in different places.

We can use this to our advantage to easily determine whether two strings are anagrams of each other using an idea similar to a basic string compression algorithm. We create a fixed size array with a slot for each character in the alphabet (26 total, 0 = 'a' and 25 = 'z') and we process each string counting how many times each character appears in it.

We then create a string from that array using a fixed format: Xchar1...YcharN

We can now use this string as key for a map, which will quickly determine whether two strings are anagrams of not. All strings that are anagrams are added as values to the same map bucket, we then simply collect all values in an output list.

This uses O(N) time as we process all strings once and do constant work for each (alphabet size is fixed at 26) and O(N) space as we store all strings in our map.

You can check my implementation of groupAnagrams on my Gist along with some tests in GroupAnagramsJTests.

[Java] Verify is string can be rotated to match target

Given two strings, check whether the first can be rotated any number of times to match the second.

Example:

asd, lol: not possible

asd, sda: yes with one rotation

The key insight to solve this problem is to realize that a string concatenated with itself will contain all possible strings resulting from all its rotations:

asd becomes asdasd

All rotations of asd are: asd, sda, das and we can see that asdasd contains all of them.

Then the problem becomes a search for substring, after having checked that both strings have same length.

We can use KMP algorithm to do a N+N search using N space, stopping as soon as we find the first match, if there is none, then the string can't be rotated in the other one.

You can check my implementation of isRotation on my Gist along with some tests in IsRotationJTests.

[Java] Make biggest number from list of numbers

Given a list of integers, combine them to form the biggest number possible using all given numbers. Example:

500,60 return 60500

1,2,3 return 321

We can cheat a bit and get the input as array of strings, but the approach is the same. The idea is we need to sort this input in a way that provides us with the highest numbers first.

However, it is not enough to simply compare numbers since the example shows that approach would lead to the wrong result: 500,60 the biggest number is 60500 and not 50060 even though 500 is bigger than 60.

This example does show the solution though: given two numbers we want to order them based on the resulting number, since 60500 is bigger than 50060, the order is then 60,500

To solve our problem in O(N logN) time and O(logN) space (use Arrays.sort()) we simply need to provide a comparator that does what we want, then take each number and combine it in the result.

You can check my implementation of makeBiggestNumber on my Gist along with some tests in MakeBiggestNumberJTests.

[Java] Array of doubled pairs

Given an array of integers return true if it is possible to reorder its elements in pairs so that arr[2 * i + 1] = 2 * arr[2 * i] for all i up to length/2

In other words, given an array of integers allowing negatives and duplicates, find if it is possible to use each element in a pair where the first element in the pair is half the value of the second element of that pair. Elements cannot be reused among different pairs.

[Java] Satisfiability of equations

Given a series of equality and inequality equations, determine whether they can be satisfied.

Equations are in the form:

a==b

a!=b

where a,b are the two variables involved.

Example:

a==b, b==c, c==a: OK

a==b, b==c, c!=a: KO

Similar to the graph coloring we saw before, we can apply the same method here but expand it to more colors.

We create an adjacency list from all equality equations, the linked variables (connected components) must all have the same color, we proceed by starting with a color and then assigning it to all variables connected to each other, we repeat this process for all variables without color, each time using a different color.

Then we parse all inequality equations and verify if any conflict arises.

This algorithm runs in O(V) space and O(E) time as we explore all edges (equations) once. We use V space for the stack when coloring as at most we can add each vertex only once (we only add if vertex has no color).

You can check my implementation of equationsPossible on my Gist along with some tests in EquationsPossibleJTests.

[Java] Graph bipartition (2 coloring)

Given a graph, return a possible 2 coloring of it.

The algorithm is simple, for each node in the graph, if it doesn't yet have a color, run a DFS from it.

The DFS will assign a default color (eg; 1) to the node, if it doesn't already have one, then for each neighbor:

• if it already has a color which is NOT different from the current node color, break and fail
• if it doesn't have a color, assign the OPPOSITE of the current node color (eg use formula 1 - node color to invert between 0 and 1), then run a DFS from that node

In the end, if we stopped early it means the graph can't be colored with only 2 colors (there is no possible bipartition), otherwise we will have a possible 2 coloring or our graph as output.

This algorithm runs in O(V) space and O(E) time as for each node we explore all its neighbors once (we don't invoke DFS again unless neighbor had no color) and at most we can put V nodes on the callstack for recursion.

You can check my implementation of twoColor on my Gist along with some tests in TwoColorBipartitionJTests.

[Java] Reverse integer

Given a 32 bit integer, reverse it.

Example:

123 becomes 321

The initial thought was to treat the integer as a bit array, swapping each from left to right.

This would have some tricks in the implementation, especially since Java uses 2's complement for negative representation, but could be done and has a complexity of O(32) at most as we consider each bit in the number.

However, turns out there is a much better approach that uses divide and conquer logic to achieve the same result:

 public static int reverseBits(int n){  
     //take half of the bits from MSB to mid portion  
     //take half of the bits from mid to LSB portion  
     //swap them  
     //repeat the process with always smaller masks and portions  
     //mask is always 32 bit in size  
   
     //initial swap, throw away 16 LSB and 16 MSB, combine them together  
     //now we have the two halves reversed  
     n = n >>> 16 | n << 16;  
   
     //mask for left portion: 1111 1111 0000 0000 1111 1111 0000 0000  
     //mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111  
     //then shift by half of previous size (8 bit)  
     n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;  
   
     //mask for left portion: 1111 0000 1111 0000 1111 0000 1111 0000  
     //mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111  
     //then shift by half of previous size (4 bit)  
     n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;  
   
     //mask for left portion: 1100 1100 1100 1100 1100 1100 1100 1100  
     //mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011  
     //then shift by half of previous size (2 bit)  
     n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;  
   
     //mask for left portion: 1010 1010 1010 1010 1010 1010 1010 1010  
     //mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101  
     //then shift by half of previous size (1 bit)  
     n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;  
   
     //now all the bits have been moved around in the reverse place  
     return n;  
   }  

The idea is to split the integer in two halves, shift them by half the size of the integer, and combine them back.

Repeating this process on each half will in the end give the desired result.

[Java] Find missing integer in array of unique elements

Given an array of length N of unique positive integers in range 0..N both inclusive, find the missing one.

We have two linear approaches, one uses a mathematical formula, the other some bit magic.

Math:

all numbers in range 0..N summed up can be calculated with the formula:

N * (N + 1) / 2

If we sum up all elements in the array, our missing number is the expected sum minus the actual sum

Bit:

if the array was of size N + 1 and all integers in range 0 .. N were present and sorted, each would sit at the index same as the number itself, for example:

idx: 0 1 2

num: 0 1 2

Since we know only one number is missing, there must be some index where the value doesn't match the index.

Since N + 1 is NOT a valid index in the array, we can initialize a variable to that, then XOR that variable with all values and indices in the array.

All repeated elements (index and value) would cancel out, leaving only the missing one as result.

You can check my implementation of findMissingNumber on my Gist (math) and Gist (bit) along with some tests in FindMissingNumberJTests (math) and FindMissingNumberJTests (bit).

[Java] Count number of bits set to 1

Given a positive integer N, find for each integer in range 0..N inclusive, how many bits are set to 1.

We could for each integer in range 0..N consider its binary representation and pick off all bits set to 1 counting them.
This would make us do at most 32 operations for each number, being 32 a constant we'd have linear time but performance is still impacted.

We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
Drawing the binary sequence for 0..8 gives us:

• 0: 0000
• 1: 0001
• 2: 0010
• 3: 0011
• 4: 0100
• 5: 0101
• 6: 0110
• 7: 0111
• 8: 1000

And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example:

• 3 and 6
• 2, 4 and 8

What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the previous number, example:

• 5 = 4 + 1
• 7 = 6 + 1

so to create an odd N, we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number.
 

If we know how many bits are set in N/2, we skip all of this process and just reuse that value adding one to it if the lsb should be 1. We know if it should be 1 by checking N & 1.

This is also equal to saying number of bits set in N is N/2 + N mod 2 as anything modulo 2 will always be either 0 or 1, specifically 0 if N is even and 1 if N is odd.

We repeat this process for all numbers in our range and we have the solution.

Since the output is part of the solution, our space complexity is O(1) and our time is O(N).

All operations we use are division by 2 and modulo by 2, which are a right bit shift and a bitwise AND.

You can check my implementation of countOnes on my Gist along with some tests in CountOnesJTests.

[Java] Sum two integers without sum operator

Given two integers, return a + b without using sum operator.

Seems like it's time for more bit magic. 

We process our numbers bit by bit starting from LSB, we track a carry, a position in the result sum, and the result sum.

Getting the LSB can be done by:

n & 1

If 1 the bit was set to 1

Then we can calculate the result of the sum:

it will be a 1 only if there is an odd number of ones between lsbA, lsbB and carry:

• 1 + 1 = 0, unless carry was 1
• 1 + 0 = 0, unless carry was 1
• 0 + 0 = 0, unless carry was 1

res = lsbA ^ lsbB ^ carry

Then we can push that bit in the correct place in the final result:

res = res << position

And set it in the final sum:

sum |= res

Also we need to increase position for the next iteration, but we can't use sum operator:

position = -(~position)

We can then calculate the carry for the next iteration:

it will be a 1 if there were at least two ones between lsbA, lsbB, carry:

• 0 + 1 + 0 = 1 no carry
• 1 + 1 + 0 = 0 with carry
• 0 + 0 + 1 = 1 no carry
  
• 1 + 1 + 1 = 1 with carry 

carry = (lsbA & lsbB) | (lsbA & carry) | (lsbB & carry)

we then drop the lsb from both a and b WITHOUT preserving sign (we need it come to us for processing, we can't leave it set in MSB):

a = a >>> 1

b = b >>> 1

and repeat this process until both a and b are 0

One last thing to do after all of this, if there was still a carry left AND we are not trying to set it in position 32 (MSB), set it in the final sum.

You can check my implementation of sum on my Gist along with some tests in SumJTests.

[Java] Increment number without using sum operator

Here's another piece of bit magic that works on those systems where numbers are stored using 2's complement.

Since a negative number is stored using that form, and that form is obtainable by inverting all the bits then adding one, we can get the number + 1 by inverting all bits first and then flipping its sign:

n = -(~n)

This works for both negatives and positives.

[Java] Find all paths from source to dest in a directed acyclic graph

Given a DAG, find all paths from source to target.

Since it is a DAG, there are no cycles, therefore we can't go back to an already visited vertex during a visit.

We can therefore add the source to a stack, then use recursion to find all paths from source to target.

In the recursive function, we look at the current node (top of stack) and for each one of its edges, we add the destination to the stack and call recursion on that destination.

When the top of stack is the target, we scan the scan and track all elements as a solution, they will be in inverted order from last vertex to first. However, a foreach loop on a Stack (in Java) gives element in order from bottom to top, so there is no need to invert them in our result.

When we get back from a recursive call, we remove ourselves from the stack as we have fully explored our subgraph.

This code works in O(V) space as that's how deep the recursion could go, and our stack also matches the recursion in size.

For time complexity, I assumed we would get a O((V+E)^2) upper bound as without cycles we cannot go back to previously visited vertices but some paths might overlap and we would walk down the same edge multiple times.

This might not be the case if we look for ALL paths from ALL vertices, however we only consider ONE start vertex in this case.

I think it made sense as a similar problem which is topological sorting is linear and in this case we're looking at all paths between the two farthest nodes.

Turns out it's exponential in reality:  If all vertices are connected (without cycles) for each new node excluding start and end, we have a choice of either including it in a path or not, which would give a O(2^V) upper bound.

You can check my implementation of findAllPathsFromSourceToDestInDAG on my Gist along with some tests in FindAllPathsFromSourceToDestInDAGJTests.