Modulo operation and circular array – code

Modulo is the operation that returns the remainder of one number divided by another. It is a arithmetical operator, represented as % in Java. For example, 6 % 4 is 2. In this post we are not using it as math operator, instead focus on the use of modulo operation in circular array. By applying it to array index, an array can be turned into a circular array.

Here are two examples of using modulo operation in circular array . The first one is to check whether a char array has consecutive letters, such as ‘abcd’. The trick part of this question is that the letter at the end of the array circles back to the start. For example, ‘c’, ‘d’, ‘a’, b’ has consecutive letters. Because after letter ‘b’ at the index 3, will continue to index 0. The solution is to use mod operator – The index after 3 is 4, when 4 mod by array length 4, the index becomes 0.

A more complicated use is Round Robin Tournament Scheduler. The details about how it works can be found in wiki. The basis of the algorithm is using circle method. So we apply modulo operation to implement scheduling algorithm. Please note, If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a “bye”. 


I. Basic modulo operation in circular array

Question:
Write a method to test whether an array has four consecutive letters.
following examples are true:
{‘d’, ‘e’, ‘f’, ‘g’}
{‘z’, ‘a’, ‘b’, ‘c’} ‘z’ is followed by ‘a’
{‘x’, ‘y’, ‘z’, ‘a’}
following examples are false:
{‘a’, ‘b’, ‘k’, ‘d’}
{‘b’, ‘x’, ‘y’, ‘z’}

Java Code:

Output:
[a, x, y, z]
true
[z, a, b, c]
true

O Notation:
Time complexity: O(n*k) ~ O(n)
Space complexity: O(1)
n is array length, k is 4 (constant)


II. Round Robin Tournament

Question:
There are 10 soccer teams that will play in the league. Read the names of the teams and develop a round-robin schedule so that every team plays with every other team over the next 9 weeks.

Java Code:

Output:

O Notation:
Time complexity: O(n^2)
Space complexity: O(1)
n is number of teams

Actionable:
Download ModuloOperatonInCircularArray.zip
The complete list of coding interview questions
Round Robin Tournament at github

Comments are closed