# New Year Chaos Solution - HackerRank

2023 Jun 13

### Problem

It is New Year’s Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from 1 to n. Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print `Too chaotic`.

See full description and example input & output in the HackerRank page.

### Solution

A person, wearing the number `q[i]`, was initally at position `q[i] - 1` (e.g. a person with number `3` was at the index `2` at first). The person can bribe others at most twice, so the person can move left at most 2 positions. When inspect the list, we compare each person’s original position, i.e. `q[i] - 1`, with the current position `i`, if `(q[i] - 1) - i` is greater than `2`, then this person bribes too many people. Our program prints `Too chaotic` in this case.

Next, we calculate how many bribes happen. Say, the initial list is:

``````  1 2 3 4 5
``````

And, its current state is:

``````  1 2 5 3 4
``````

For every person `X`, we check people in the left of this person, if any of them’s number is greater than `X`’s, then that person must bribe `X`.

Below is a Java version solution.

``````public static void minimumBribes(List<Integer> q) {
int bribes = 0;
for (int i = 0; i < q.size(); i++) {
if (q.get(i) - 1 - i > 2) { // this person has done too many bribes
System.out.println("Too chaotic");
return;
} else {
for (int j = 0; j < i; j++) {
// for every person in the left of "person q[i]",
// if that person's number is greater,
// than "person q[i]" got bribed by that person.
if (q.get(j) > q.get(i)) {
bribes++;
}
}
}
}
System.out.println(bribes);
}
``````

Time complexity is `O(n^2)`.

#### An Optimization

When calculate bribes, the above solution has done many unnecessary checks. A person `X`, wearing the number `q[i]`, was initally at position `q[i] - 1`. People, who were in the right of `X`, can do bribe to be positioned at `q[i] - 1` or `q[i] - 2`. The bribe limit is 2, it’s impossible for people who were in the right of `X` to be at index less than `q[i] - 2`. So we can improve the previous solution to let `j` start with `q[i] - 2`. The value `q[i] - 2` may be negative, to avoid the out-of-bound exception, let `j` start with `0` when `q[i] - 2` is negative.

``````public static void minimumBribes(List<Integer> q) {
int bribes = 0;
for (int i = 0; i < q.size(); i++) {
if (q.get(i) - 1 - i > 2) {
System.out.println("Too chaotic");
return;
} else {
int j = Math.max(0, q.get(i) - 2);
while (j < i) {
if (q.get(j) > q.get(i)) {
bribes++;
}
j++;
}
}
}
System.out.println(bribes);
}
``````

Note that, you can add another check, `q.get(i) - 1 == i`. In this case, the person hasn’t change the position, so no bribe happens on this person. We can skip bribe calculation in this case.

# Minimum Swaps 2 - HackerRank

2023 Jun 13

### Problem

You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. Find the minimum number of swaps required to sort the array in ascending order.

See full description and example input & output in the HackerRank page.

### Solution

Starting with `1`, try to put each number in correct position. If a number is not at the correct position, a swap is needed. For example, with the following input,

``````4 3 1 2
``````

`1` is not in correct position (correct position is index `0`). Therefore, swap `1` with the element at index `0`, which is `4`. After `1` is positioned correctly, check the next number, i.e. `2`.

We can use hash map for the lookup of current position of a number.

Below is a Java version solution.

``````    static int minimumSwaps(int[] arr) {
// the value space is [1, n], so we can use array to
// store the mapping between number and its position
int[] posMap = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
posMap[arr[i]] = i;
}

int swapCount = 0;
for (int num = 1; num <= arr.length; num++) {
int correctPos = num - 1;
int currentPos = posMap[num];
if (currentPos != correctPos) {
int tmp = arr[correctPos];
arr[correctPos] = num;
arr[currentPos] = tmp;

// update 'pos map'
posMap[num] = correctPos;
posMap[tmp] = currentPos;

swapCount++;
}
}
return swapCount;
}
``````

Time complexity is `O(n)`.

# Writing OpenAPI Specification

2022 Apr 26

### Visual Studio Code extension

I edit OpenAPI specification files in Visual Studio Code with extensions OpenAPI (Swagger) Editor and Swagger Viewer. With these extension, Visual Studio Code can edit, validate, preview OpenAPI specification files and try out API in the preview pages.

If you like these extensions, you can add them as workspace recommendations.

``````\$ tree .vscode/
.vscode/
└── extensions.json

\$ cat .vscode/extensions.json
{
// Extension identifier format: \${publisher}.\${name}. Example: vscode.csharp
// List of extensions which should be recommended for users of this workspace.
"recommendations": [
"Arjun.swagger-viewer",
"42Crunch.vscode-openapi"
],
// List of extensions recommended by VS Code that should not be recommended for users of this workspace.
"unwantedRecommendations": [

]
}
``````

The `.vscode` directory can be checked into the VCS to share with others.

### Using \$ref

The `\$ref` can be mixed with “in-place” definitions.

``````      parameters:
# Define a parameter in place
- in: path
name: id
required: true
description: The primary key.
schema:
type: integer
example: 21
# Local Reference, # means go to the root of the current document
- \$ref: '#/components/parameters/ParaFoo'
# Remote Reference
- \$ref: 'parameters.yaml#/components/parameters/ParaBar'
``````

URL Reference is also supported. See more at the Using \$ref documentation.

# only() vs. times(1) in Mockito

2021 Dec 13

Use `times(1)` to verify a method is called exactly once.

``````  verify(orderService, times(1)).getOrder(anyLong());
verify(orderService, times(1)).createOrder(any(CreateOrderRequest.class));
``````

The above code verifies that both `getOrder` and `createOrder` are called exactly once on `orderService`.

If the `times(1)` in above example is replaced by `only()`, the test would fail.

As per Mockito Javadoc of `only()`,

Allows checking if given method was the only one invoked

`verify(mock, only()).someMethod();` is same as

``````  verify(mock).someMethod();
verifyNoMoreInteractions(mock);
``````

i.e.

``````  verify(mock, times(1)).someMethod();
verifyNoMoreInteractions(mock);
``````

Therefore,

``````  verify(orderService, only()).getOrder(anyLong());
verify(orderService, only()).createOrder(any(CreateOrderRequest.class));
``````

is equivalent to

``````  verify(orderService, times(1)).getOrder(anyLong()); // L1
verifyNoMoreInteractions(orderService); // L2
verify(orderService, times(1)).createOrder(any(CreateOrderRequest.class)); // L3
verifyNoMoreInteractions(orderService); // L4
``````

It would fail at line “L2”.

# Run GitLab CI Pipeline on Protected Branches by a Member of Developer Role

2021 Aug 24

To let project members of the “Developer” role be able to run GitLab CI pipeline on protected branches, go to “Settings -> Repository -> Protected branches”, in “Allowed to merge” dropbox, add “Developers + Maintainers”.

See discussion on this GitLab issue for details.

If the CI job needs to pull Docker images from registry of a GitLab project, the user who run the CI pipeline must have necessary permission to this GitLab project.

As per this GitLab document, the user should at least have the “Developer” role to pull Docker images from GitLab projects.

Action Guest, Reporter Developer
Pull container images from current projects
Pull container images from public projects
Pull container images from internal projects

If the user has a “Guest” or “Reporter” role in a project X, the CI job of project Y needs to pull images from the registry of project X, when that user run the CI job of project Y, the job would fail. Error message in the failed CI job would be like

``````pull access denied for registry.gitlab.example.com/group/project-x,
repository does not exist or may require 'docker login':
``````

# Why @Mock Annotated Object Is Null

2021 May 19

Mockito provides annotations like `@Mock`, `@Spy`, `@Captor` to make code simpler. Since most of our code is just copied from Google search and Stack Overflow, we may use these Mockito annotations like below, after quick reading of Google search results like this article.

``````@RunWith(MockitoJUnitRunner.class)
class OrderTest {
@Captor
ArgumentCaptor<Offer> offerCaptor;

@Test
void test() {
// use the `offerCaptor` object ...
}
``````

However, when run, the test throws NullPointerException due to the `offerCaptor` is `null`, even though it’s annotated by `@Captor`.

(Spending hours of Googling and debugging.)

The root cause of NPE is that the test is using JUnit 5, but `@RunWith` is a JUnit 4 annotation.

@RunWith no longer exists; superseded by @ExtendWith.

Therefore, `@RunWith(MockitoJUnitRunner.class)` is totally ignored by JUnit 5, no setup happens for objects annotated by `@Captor`.

To support JUnit 5 `@ExtendWith`, Mockito provides a MockitoExtension class.

This extension is the JUnit Jupiter equivalent of our JUnit4 MockitoJUnitRunner.

Below code has no NPE, for test cases using JUnit 5 and Mockito annotations.

``````@ExtendWith(MockitoExtension.class)
class OrderTest {
@Captor
ArgumentCaptor<Offer> offerCaptor;
``````

### Some Thoughts

It would be better if JUnit 5 warns us if it finds the obsolete JUnit 4 `@RunWith`, instead of failing silently.

Another solution is that, if a project is going to use JUnit 5, just exclude the JUnit 4 from the dependencies of the project. So using `@RunWith` would be a compile error.

# Fix a Helm "Secret Too Long" Bug

2021 Mar 23

When try to upgrade a Helm chart, it fails with an error like below.

``````Error: UPGRADE FAILED: create: failed to create:
Secret "sh.helm.release..." is invalid:
data: Too long: must have at most 1048576 bytes
``````

Helm by default uses Kubernetes Secrets to store release information. For what is “release information”, basically it includes the source files of the chart.

The release information includes the contents of charts and values files

See Storage backends for more details.

In my case, certificates (after encryption) are stored in the chart files, each of which is like hundreds KB big. And what’s more, each certificates has several variants for each deployment environments, like alpha, beta and production. All these files are in one helm chart. When to bring in a new certificate into the chart, the chart becomes too big, so the above error happens.

To solve this error for my chart, a simple solution to create a script to dynamically “helm ignore” files which are not needed for a Helm release for a particular deployment environment. For example, before do Helm release for the alpha environment, (using CI scripts to) add files which are for production and beta into the `.helmignore` file to exclude these files from the Helm chart.

``````HELM_ENVS=(alpha beta prod)
for HELM_ENV in \${HELM_ENVS[@]}; do
if [ "\$HELM_ENV" != "\$DEPLOY_ENV" ]; then
echo "helm ignore this folder in chart: secrets/\$HELM_ENV/"
echo "secrets/\$APL_ENV/" >> .helmignore
fi
done
``````

Helm also has a beta feature called “SQL storage backend” to store release information in a database, for a big chart.

Using such a storage backend is particularly useful if your release information weighs more than 1MB

# CompletableFuture: join() vs. get()

2021 Mar 23

What’s the difference between `join()` and `get()` of the `CompletableFuture` class?

Both of them wait for the future completion. The only difference is what kind of exceptions these two methods throw. The `get()`, originated in the `Future` interface, throws “checked exceptions”. While `join()` throws “unchecked exceptions”.

In old days, like Java 1.5 era when `Future.get()` was designed, checked exceptions might be preferred. Nowadays, unchecked exceptions are more preferred, therefore `join()` is preferred.

To simplify usage in most contexts, this class also defines methods join() and getNow(T) that instead throw the CompletionException directly in these cases.

In other words, `join()` is simpler to use, in the sense of exception handling. It’s kind of an official recommendation.

# Reminder Operator Returns Negative Value in Java

2021 Mar 23

The `%` operator is the reminder operator in Java. In other languages, it may be called modulo operator.

”%”, which divides one operand by another and returns the remainder as its result.

It seems a simple operator, by looking at example code like this, `10 % 7 = 3`.

However, the `%` operator may return a negative value.

``````  assertEquals(-1, -9 % 2, "return negative value here");
assertEquals(1, 9 % -2, "return positive value here");
``````

It’s because Java’s reminder implementation uses “truncated division”. See details in this Wiki page. The “truncation (integer part)” of `-9 / 2`, i.e. `-4.5`, is `-4`. So,

``````  -9 % 2 = -9 - 2 * (-4) = -9 - (-8) = -1
``````

For the `9 % -2` case, the “truncation” is also `-4`. However,

``````  9 % -2 = 9 - (-2) * (-4) = 9 - 8 = 1
``````

### A Problem

Sometime, this `%` returning negative behavior may cause problems.

``````  var batches = 10;
// ... some RxJava code
.groupBy(input -> Objects.hash(input) % batches)
//...
``````

For example, in above code you may want to split your work into 10 batches. However, because the `Objects.hash()` may return negative hash code, `Objects.hash(input) % 10` has 19 possible values (integers), from -9 to 9. So unexpectedly, your work is split int 19 batches.

### A Rescue

Java 8 provides a Math.floorMod() method, which can be used in situations like above. According to its Javadoc,

If the signs of the arguments are the same, the results of floorMod and the % operator are the same.

If the signs of the arguments are different, the results differ from the % operator.

``````floorMod(+4, -3) == -2;   and (+4 % -3) == +1
floorMod(-4, +3) == +2;   and (-4 % +3) == -1
floorMod(-4, -3) == -1;   and (-4 % -3) == -1
``````

The `floorMod(x, y)` is calculated using below relationship.

``````floorDiv(x, y) * y + floorMod(x, y) == x
``````

And for the Math.floorDiv() method, its Javadoc says

Returns the largest (closest to positive infinity) int value that is less than or equal to the algebraic quotient.

For example, floorDiv(-4, 3) == -2, whereas (-4 / 3) == -1.

Given dividend is -4 and divisor is 3, its algebraic quotient is -1.333333. “The largest (closest to positive infinity) int value that is less than or equal to” -1.333333 is -2, not -1 which is larger than the quotient. Therefore, `floorDiv(-4, 3) == -2`.

``````  floorMod(-4, 3) = -4 - floorDiv(-4, 3) * 3 = -4 - (-2)*3 = 2
``````

# Compare Two OffsetDateTime of the Same Instant

2021 Mar 16

For two Java OffsetDateTime objects of the same instant, but with different timezone offset, to check whether they represent the same point in time, the `isEqual` method should be used.

``````var date1 = OffsetDateTime.parse("2008-12-03T11:00+01:00");
var date2 = OffsetDateTime.parse("2008-12-03T12:00+02:00");
date1.isEqual(date2); // the result is true
date1.equals(date2); // the result is false
date1.compareTo(date2); // the result < 0
``````

In the above code, both of the OffsetDateTime objects represent “2008-12-03T10:00Z”. However, the `equals` or the `compareTo` method will tell these two object are not “equal”.

The OffsetDateTime class uses a field of LocalDateTime and a field of ZoneOffset to represent an instant. Its `equals` method cares about whether all these field of two objects are same or not. Obviously, fields of `date1` are not equals with ones of `date2`.

The `compareTo` has same behavior as `equals`.

It is “consistent with equals”, as defined by Comparable.

As per Javadoc of OffsetDateTime, what `isEqual` does is `dateTime1.toInstant().equals(dateTime2.toInstant())`. That is OffsetDateTime object are convert to Instant object first, and use the `equals` of Instant for comparison.