The other day I have received an email from the Let’s Encrypt Expiry Bot stating that my SSL certificate for the domain name lucaslouca.com is about to expire.

In this post I have extensively described how to setup a WordPress blog on an EC2 instance along with a Let’s Encrypt SSL certificate.

Since I don’t want my visitors to encounter any errors when visiting my site I had to renew my SSL certificate. Here are the commands I used to renew my certificate:

Before I run letsencrypt, I temporarily disabled /var/www/html/.htaccess:

Run the letsencrypt command:

with output:

Enabled /var/www/html/.htaccess again:

Problem statement
Given an array of distinct elements find all triplets in array whose sum is equal to $0$.

Sample input

Sample output

Solution
We will solve this algorithm in $\mathcal{O}(n^2)$ time using hashing. The first iteration will be over all elements of our array. Let that elements be $a[i]$. Then we sum each $a[i]$ with a second element $a[j]$ (nested loop) and check whether we have a third element $x$ that is equal to $-(a[i] + a[j])$ in our HashSet because $x + a[i] + a[j]$ would then be equal to $0$. If no such element exists we add the current $a[j]$ to the HashSet for future lookups and continue. For each iteration for elements $a[i]$, we generate a new lookup HashSet.

Full Code

Problem statement
Given a string, find the length of the longest substring without repeating characters.

Examples

Example 1
Given abcabcbb, the answer is abc, which the length is $3$.

Example 2
Given bbbbb, the answer is b, with the length of $1$.

Example 3
Given pwwkew, the answer is wke, with the length of $3$. Note that the answer must be a substring, pwke is a subsequence and not a substring.

Solution

Problem statement
Marc loves cupcakes, but he also likes to stay fit. He eats $n$ cupcakes in one sitting, and each cupcake $i$ has a calorie count, $c_i$. After eating a cupcake with $c$ calories, he must walk at least $2^j \times c$ (where $c$ is the number cupcakes he has already eaten) miles to maintain his weight.

Given the individual calorie counts for each of the cupcakes, find and print a long integer denoting the minimum number of miles Marc must walk to maintain his weight. Note that he can eat the cupcakes in any order.

Input Format
The first line contains an integer, $n$, denoting the number of cupcakes.
The second line contains $n$ space-separated integers describing the respective calorie counts of each cupcake, $c_0, c_1, \dots, c_{n-1}$.

Constraints
$1 \le n \le 40$
$1 \le c_i \le 1000$

Output Format
Print a long integer denoting the minimum number of miles Marc must walk to maintain his weight.

Sample Input 0

Sample Output 0

Explanation 0
Let’s say the number of miles Marc must walk to maintain his weight is $miles$. He can minimize $miles$ by eating the $n=3$ cupcakes in the following order:

1. Eat the cupcake with $c_1 = 3$ calories, so $miles = 0 + (3 \times 2^0) = 3$.
2. Eat the cupcake with $c_2 = 2$ calories, so $miles = 3 + (2 \times 2^1) = 7$.
3. Eat the cupcake with $c_3 = 1$ calories, so $miles = 7 + (1 \times 2^2) = 11$.

We then print the final value of $miles$, which is $11$, as our answer.

Solution

Problem statement
A numeric string, $s$, is beautiful if it can be split into a sequence of two or more positive integers, $1_1, a_2, \dots, a_n$, satisfying the following conditions:

1. $a_i - a_{i-1} = 1$ for any $1 \textless i \le n$ (i.e., each element in the sequence is $1$ more than the previous element).
2. No $a_i$ contains a leading zero. For example, we can split $s=10203$ into the sequence $\left[1, 02, 03\right]$, but it is not beautiful because $02$ and $03$ have leading zeroes.
3. The contents of the sequence cannot be rearranged. For example, we can split $s=312$ into the sequence $\left[3, 1, 2\right]$, but it is not beautiful because it breaks our first constraint (i.e., $1 - 3 \ne 1$).

The diagram below depicts some beautiful strings:

You must perform $q$ queries, where each query consists of some string $s$. For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print YES x, where $x$ is the first number of the increasing sequence (if there are multiple such values of $x$, choose the smallest); otherwise, print NO instead.

Input Format
The first line contains an integer denoting (the number of strings to evaluate).
Each of the subsequent lines contains some string for a query.

Constraints
$1 \le q \le 10$
$1 \le |s| \le 32$
Each character in $s$ is a decimal digit from $0$ to $9$ (inclusive).

Output Format
For each query, print its answer on a new line (i.e., either YES x where $x$ is the smallest first number of the increasing sequence, or NO).

Sample Input 0

Sample Output 0

Explanation 0
The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For $s = 101103$, all possible splits violate the first and/or second conditions.
For $s = 010203$, it starts with a zero so all possible splits violate the second condition.
For $s = 13$, the only possible split is $\left[1,3\right]$, which violates the first condition.
For $s = 1$, there are no possible splits because $s$ only has one digit.

Solution

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, $A$, of $n$ distinct integers. The rules are as follows:

• Bob always plays first and the two players move in alternating turns.
• In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if $A = \left[2,3,5,4,1\right]$, then it becomes $A = \left[2,3\right]$ after the first move because we remove the maximum element (i.e., $5$) and all elements to its right (i.e., $4$ and $1$).
• The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play $g$ games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting $g$ (the number of games). The $2\times g$ subsequent lines describe each game array over two lines:

1. The first line contains a single integer, $n$, denoting the number of elements in $A$.
2. The second line contains $n$ distinct space-separated integers describing the respective values of $a_0, a_1, \dots, a_{n-1}$ for array $A$.

Constraints
Array contains $n$ distinct integers.
$1 \le g \le 100$
$1 \le n \le 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all games does not exceed $10^5$.

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

Sample Output 0

Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes $6$ and all the elements to its right, resulting in $A = \left[5,2\right]$:

In the second move, Andy removes $5$ and all the elements to its right, resulting in $A = \left[\right]$:

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes $3$ and all the elements to its right, resulting in $A = \left[\right]$. As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

When interested in buying bonds a term that often comes up is the definition of Yield To Maturity (YTM):

Yield to maturity (YTM) is the total return anticipated on a bond if the bond is held until the end of its lifetime. Yield to maturity is considered a long-term bond yield, but is expressed as an annual rate. In other words, it is the internal rate of return of an investment in a bond if the investor holds the bond until maturity and if all payments are made as scheduled. – Investopedia

Let us consider a bond with a par value of $\100$ and a coupon rate of $3\%$ with the bond maturing in $29$ years time. The current bond price is $\89$. We are interested in the bond’s YTM.

Knowing that we get $\3$ annual cashflow ($coupon\ rate \times par\ value = 0.03 \times \100 = \3$) we will have the following cashflow for the next $29$ years. Notice in the last year we will receive an additional $\100$ which is the bond’s principle:

Let us assume that we want to value these future cashflows and determine how much they are worth today. What we need to do, is to present value all of these future cashflows back to today and add up those present values $pv_i$. This sum would be the price of the bond.

A present value is the amount of money $pv$ one would need to invest today in order to have $c$ amount of money in $n$ years if he is earning $r%$ (annual)interest on his investment:

$pv = \frac{c}{(1 + r)^n}$

For example, if Bob wants to have $\100$ one year from now at a rate of $5\%$, he needs to invest $\95.24$ today ($\frac{100}{(1 + 0.05)} = 95.24$).

Back to our bond’s present value of future cashflows the resulting formula would look as follows:
$bond\ price = \frac{future\ cashflow\ 1}{(1 + ytm)^1} + \frac{future\ cashflow\ 2}{(1 + ytm)^2} + \frac{future\ cashflow\ 3}{(1 + ytm)^3} + \dots + \frac{future\ cashflow\ 29}{(1 + ytm)^{29}}$

with $ytm$ being the yield to maturity we are looking for.

For our particular bond the formula will look like this:
$bond\ price = \frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}}$

So how can we go about finding $ytm$? Well, above we have learned that sum of present values of all future cash flows is our bond price. Since we already know the today’s bond price which is $\89$, the formula becomes like this:
$\frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}} = 89$

All we need to do now is to solve the above equation for $ytm$ so that it holds true. We will do this through trial-and-error.

Solving the equation by hand requires an understanding of the relationship between a bond’s price and its yield, as well as of the different types of bond pricings. Bonds can be priced at a discount, at par and at a premium. When the bond is priced at par, the bond’s interest rate is equal to its coupon rate. A bond priced above par (called a premium bond) has a coupon rate higher than the interest rate, and a bond priced below par (called a discount bond) has a coupon rate lower than the interest rate. So if an investor were calculating YTM on a bond priced below par, he or she would solve the equation by plugging in various annual interest rates that were higher than the coupon rate until finding a bond price close to the price of the bond in question (quote from: Investopedia).

You can verify this quickly with a simple example. Assume a bond with current price $b$ and a par value of $100$ that matures in $1$ year. The coupon rate is $c$ and interest rate is $ytm$:

$b = \frac{100 + c \times 100}{(1 + ytm)}$
==>
$b \times (1 + ytm) = 100 + c \times 100 = 100 \times (1 + c)$
==>
$\frac{b}{100} = \frac{(1 + c)}{(1 + ytm)}$

If $\frac{b}{100} \textless 1$ then $(1 + ytm) \textgreater (1 + c)$. Similarly for the other cases.

Back to our bond. We had the following equation:
$\frac{3}{(1 + ytm)^1} + \frac{3}{(1 + ytm)^2} + \frac{3}{(1 + ytm)^3} + \dots + \frac{3 + 100}{(1 + ytm)^{29}} = 89$

Now we must solve for the interest rate $ytm$ which is where things start to get difficult. Yet, we do not have to start simply guessing random numbers if we stop for a moment to consider the relationship between bond price and yield. As was mentioned above, when a bond is priced at a discount from par, its interest rate will be greater than the coupon rate. In this example, the par value of the bond is $\100$, but it is priced below the par value at $\89$, meaning that the bond is priced at a discount. As such, the annual interest rate we are seeking must necessarily be greater than the coupon rate of $3\%$.

With this information we can now calculate and test a number of bond prices by plugging various annual interest rates that are higher than $3\%$ into the formula above. Using a few different interest rates above $3\%$, one would come up with the following bond prices:

I have used $0.00001$ increments and as we can see with an interest rate of $3.62\%$ we can approximate our current price of $\89$ quite good enough. So $3.62\%$ would be our Yield To Maturity.

Full code

References
Yield To Maturity (YTM) – Investopedia

Problem statement
The Tower of Hanoi is a famous game consisting of $3$ rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game’s objective is to move the entire stack to another rod, obeying the following rules:

1. Only one disc can be moved at a time.
2. Each move consists of taking the topmost disc from a stack and moving it to the top of another stack.
3. No disc may be placed on top of a smaller disc.

Gena has a modified version of the Tower of Hanoi. His Hanoi has $4$ rods and $N$ discs ordered by ascending size. He made a few moves (following the rules above), but stopped and lost his place. He wants to restore the tower to its original state by making valid moves. Given the state of Gena’s Hanoi, help him calculate the minimum number of moves needed to restore the tower to its original state.

Note: Gena’s rods are numbered from $1$ to $4$. All discs are initially located on rod $1$.

Input Format
The first line contains a single integer, $N$, denoting the number of discs.
The second line contains $N$ space-separated integers, where the $i^{th}$ integer is the index of the rod where the disk with diameter $i$ is located.

Constraints
$1 \le N \le 10$

Output Format
Print the minimum number of moves Gena must make to restore the tower to its initial, ordered state on the first rod.

Sample Input

Sample Output

Explanation
$3$ moves are enough to build the tower. Here is one possible solution:

Solution
We will use BFS to solve this challenge. We will use a helper array minForTower with minForTower[i] holding the size of the smallest disc located at tower i. The validMovesFromState() method will compute and return a Set<Integer[]> of all valid directly subsequent moves that can be made from a given tower-disc allocation. We will store visited states in an array int[] visited = new int[(int) Math.pow(4, n)] using a key. The array length is $4^N$ since we can have a maximum of $4^N$ possible tower-disc allocations/states. Each state has an integer key. For example, given a state $\left[1, 4, 1\right]$, a key is an integer representing that allocation. Bits $2i$ and $2i+1$ of the key represent the tower (Tower $0$ = $00_b$, Tower $1$ = $01_b$, Tower $2$ = $10_b$, Tower $3$ = $11_b$). For $\left[1, 4, 1\right]$ the key is $12 = 001100_b$.

We then do a BFS putting the states in a queue along with the depth of the given state. The depth or number of steps it took us to get to that state is stored at index $0$ of the state array. Each time we reach our goal state we check we update our minimum if necessary.

The full code is listed below.

Full code

Find the number of ways that a given integer, $X$, can be expressed as the sum of the $N^{th}$ power of unique, natural numbers.

Input Format
The first line contains an integer $X$.
The second line contains an integer $N$.

Constraints
$1 \le X \le 1000$
$2 \le N \le 10$

Output Format
Output a single integer, the answer to the problem explained above.

Sample Input 0

Sample Output 0

Explanation 0
If $X = 10$ and $N=2$, we need to find the number of ways that $10$ can be represented as the sum of squares of unique numbers.

$10 = 1^2 + 3^2$

This is the only way in which $10$ can be expressed as the sum of unique squares.

Sample Input 1

Sample Output 1

Explanation 1
$100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2$

Sample Input 2

Sample Output 2

Solution

Problem statement
Lauren has a chart of distinct projected prices for a house over the next $n$ years, where the price of the house in the $i^{th}$ year is $p_i$. She wants to purchase and resell the house at a minimal loss according to the following rules:

The house cannot be sold at a price greater than or equal to the price it was purchased at (i.e., it must be resold at a loss). The house cannot be resold within the same year it was purchased. Find and print the minimum amount of money Lauren must lose if she buys the house and resells it within the next years.

Note: It’s guaranteed that a valid answer exists.

Input Format
The first line contains an integer, $n$, denoting the number of years of house data. The second line contains space-separated long integers describing the respective values of $p_1, p_2,\dots, p_n$.

Constraints
$2\le n \le 2 \times 10^5$ $1 \le p_i \le 10^{16}$ All the prices are distinct. It’s guaranteed that a valid answer exists.

Output Format
Print a single integer denoting the minimum amount of money Lauren must lose if she buys and resells the house within the next $n$ years.

Sample Input 0

Sample Output 0

Explanation 0
Lauren buys the house in year $1$ at price $p_1 = 5$ and sells it in year $3$ at $p_3 = 3$ for a minimal loss of $5 - 3 = 2$.

Sample Input 1

Sample Output 1

Explanation 1
Lauren buys the house in year $2$ at price $p_2 = 7$ and sells it in year $5$ at $p_5 = 5$ for a minimal loss of $7 - 5 = 2$.

Sample Input & Output 3
minimum-loss-input
minimum-loss-output

Solution
Naive approach
The naive approach is to iterate over each price $p_i$ and compare it with all the subsequent prices, storing any new found minimum loss based on the two rules stated in the problem statement. This obviously has a running time of $\mathcal{O}(n^2)$.

Binary Search Tree (BST) approach
We can construct a BST from the prices array. The construction has a running time of $\mathcal{O}(nlogn)$. We then go through all the nodes. Starting at node x we traverse up (go to its parent) the BST as long as the current node is not a left child of its parent (or no parent is available). If the current node is a left child then we return the value of its parent. This value is the smallest value that is greater than the value of the original/starting node x. Searching the BST for every node has a total worst case running time of $\mathcal{O}(nlogn)$.

Full code