The Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Check LeetCode link for more details and example input & output.

A Dynamic Programming Solution

Use the bottom up approach.

dp[i] = max(nums[i] + dp[i-2], dp[i-1])

dp[i] is the answer of the sub problem “i”, whose input array is a sub-array of the orginal input nums. The sub-array starts at index 0 and ends at index i.

Base cases:

• dp[0] is nums[0].
• dp[-1] is 0. (It’s used to calculate dp[1].)

Java Code

  public int rob(int[] nums) {
      int dp1 = nums[0]; // dp[i-1]
      int dp2 = 0; // dp[i-2]
      for (int i = 1; i < nums.length; i++) {
          int tmp = dp1;
          dp1 = Math.max(nums[i] + dp2, dp1);
          dp2 = tmp;
      }
      return dp1;
  }

The time complexity is O(n).

TreeMap

A Red-Black tree based NavigableMap implementation.

For the containsKey, get, put and remove operations, TreeMap guarantees log(n) time cost. While HashMap implements these four operation with O(1) time complexity. So when acting as a traditional hash table, TreeMap is slower than HashMap.

However, TreeMap has its own advantages. It’s not just a simple Map, but a SortedMap. It provides methods to get lowest and greatest key/entry more efficient than HashMap.

• firstEntry() / firstKey() / pollFirstEntry(), to return/remove lowest key or entry.
• lastKey() / lastEntry() / pollLastEntry(), for greatest key or entry.

To get the lowest or greatest, HashMap does it in O(n) time cost, while TreeMap only needs O(logn). (TreeMap keeps going left or right to retrieve the lowest or greatest.)

  // TreeMap source code
  final Entry<K,V> getFirstEntry() {
      Entry<K,V> p = root;
      if (p != null)
          while (p.left != null)
              p = p.left;
      return p;
  }

Check TreeMap Javadoc for more details.

PriorityQueue

An unbounded priority queue based on a priority heap.

The head of this queue is the least element with respect to the specified ordering.

So, for retrieving the lowest, PriorityQueue is faster than TreeMap. PriorityQueue provides O(1) time cost, while TreeMap provides log(n).

  // PriorityQueue source code
  public E peek() {
      return (E) queue[0];
  }

For removing the lowest in a PriorityQueue, it’s an O(logn) operation, which is same as doing it a TreeMap.

As its name indicates, PriorityQueue is a better choice when it’s used as a priority queue, that is, letting the lowest one be in the front of the queue. Retrieving the lowest, removing it and letting the next lowest value be in the front of the queue are fast, which are O(logn) operations.

However, if sometimes we need to remove an arbitrary entry, not the lowest entry, and want to retrieve the lowest fast, in this case, TreeMap provides a better overall performance than PriorityQueue. For example, we have a composite operation which has the following operations.

1. Add a new entry.
2. Remove some existed entry, not the lowest.
3. Retrieve the lowest entry.

For PriorityQueue, the second step is the slowest operation, which is O(n). So, the overall time cost of the composite operation using PriorityQueue is O(n). While using TreeMap, all three steps cost O(logn), so the overall time cost is O(logn).

Check PriorityQueue Javadoc for more details.

When I tried to do docker login -u username, I got below error.

  Error saving credentials: error storing credentials - err: exit status 1, out: 
  `Post "https://hub.docker.com/v2/users/login?refresh_token=true": EOF`

My environment:

• macOS 13.4 (22F66)
• Docker Desktop 4.20.1 (110738)

I got the same error popped up even when I tried to sign in in the Docker Desktop app.

The Fix

After googled for a while, I found this Stack Overflow answer helpful. As per the answer, removing the ~/.docker/config.json file fixes the problem. (For safety, you can rename it instead of removing it.)

Docker will create a new config.json file once you delete it.

The content of the old one I removed.

    $ cat ~/.docker/config.json-bak
    {
        "auths": {},
        "credsStore": "desktop",
        "currentContext": "desktop-linux"
    }

The one created by docker, which doesn’t block docker login.

    $ cat ~/.docker/config.json
    {
        "auths": {
            "https://index.docker.io/v1/": {}
        },
        "credsStore": "osxkeychain"
    }

Change the credsStore property from the value "desktop" to "osxkeychain" is the key of the fix. This property is to specify an external binary to serve as the default credential store. Setting to "osxkeychain" means using the docker-credential-osxkeychain helper.

There are different credentials helpers. For example, after installed the Docker Desktop in my Mac, I have below helpers installed.

$ docker-credential-[TAB]
docker-credential-desktop      docker-credential-ecr-login    docker-credential-osxkeychain

It’s said the docker-credential-desktop is just a wrapper of the docker-credential-osxkeychain on macOS. If it’s so, "credsStore": "desktop" was supposed to work. Maybe there is some bug in the -desktop helper.

Note that, removing the credsStore property in the config.json file also fixes the problem. Docker will fallback to the default behavior if the property is absent:

By default, Docker looks for the native binary on each of the platforms, i.e. “osxkeychain” on macOS, “wincred” on windows

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.

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

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
{
  // See https://go.microsoft.com/fwlink/?LinkId=827846 to learn about workspace recommendations.
  // 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.

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

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.

Fix the “requested access to the resource is denied” issue

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.

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': 
denied: requested access to the resource is denied

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.

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