13/10/2021

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

11/10/2021

[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] Distribute items in K buckets

Something simple which comes up often when problems require some sort of item distribution.

Given an amount of items N and K buckets, distribute the items in the buckets as uniformly as possible.

Amount of items each bucket would hold in perfect distribution: N/K (integer division)

Amount of remaining items which could make some buckets hold extra items compared to others: N%K

Therefore simply place N/K items in each bucket, then calculate the remainder N%K and place 1 item in each bucket until remainder is 0.

Of course if K is bigger than N, some buckets will be empty.

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

02/10/2021

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