Generate parentheses challenge

Problem statement
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

Solution

 

Longest palindromic substring challenge

Problem statement
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Sample input 1

Output 1

Sample input 1

Output 1

Solution
We are going to iterate over each character in the input string and assume that each character we iterate over is the middle of a new potential palindromic substring.

For instance, if are currently at index i we will assume that s[i] is the middle of palindromic substring. Obviously s[i] is a palindrome of length 1. We will then try to extend this palindrome to the left and to the right as long as the left and right edges have the same character.
If we s[left] and s[right] are not equal anymore we have a palindrome s[left + 1 ... r - 1]:

Since s can have even or odd number of characters we have to consider both cases when starting to extend our initial palindrome:

since in case of even our middle will consist of two characters (at indices i and i+1) and not just one.

Full code

 

Group anagrams challenge

Problem statement
Given an array of strings, group anagrams together.

Sample input

Sample output

Note: All inputs will be in lower-case.

Full code

 

Build power set of set

Problem statement
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

Sample input

Sample output

Full code

 

Swap list nodes in pairs challenge

Problem statement
Given a linked list, swap every two adjacent nodes and return its head.

For example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Full code

 

Container with most water challenge

Problem statement

Given n non-negative integers a_1, a_2, \dots, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution
We are going to solve this problem using two pointers l and r. Pointer l starts from the left-most side and r starts from the right-most side. We then keep track of our maximum container:

and then move one of the pointers based on the following conditions:

Let us explain the logic behind this algorithm using the illustration below.

For wall A we want to use wall D as its counterpart since D is taller than A and as far on the right as possible. Any wall to the left of D can be ignored because it will only make our container smaller as D is already taller than A. That is why it doesn’t make any sense to decrease our index r. With A and D we have a container size of 3.

We then increment our index ‘l’ because A is shorter than D. That is, move it to wall B in hopes that we can find a taller counterpart for our tall wall D. Now, wall B is taller than its predecessor and actually increases our container size to 4. We can see that since we previously increased the index pointing to the shorter of the two walls (A vs D) we were able to find a counterpart (B) for wall D that increased our container size.

Finally we again increase our index pointing to the shortest wall in hopes that we may find an even taller counterpart for D. Moving l to C we see that this does not increase our container size. Also since l and r meet, we stop the search and return 4.

The full code is listed below.

Full code

 

Merge overlapping intervals challenge

Problem statement
Given a set of intervals in any order merge the overlapping intervals and return the list of merged intervals.

Sample input

Sample output

Solution
The first step we are going to take is sort the intervals in ascending order based on their ending time.

Next, we are going to traverse over the sorted list and as long as two adjacent intervals interval_1 and interval_2 overlap (interval_2.start \le interval_1.end) we keep merging them by taking min(interval_1.start, interval_2.start) as the new start and interval_2.end as the new end for our new interval.

Once no more adjacent intervals are merging we add the newly created interval to our new list and resume the traversal until we have visited all intervals in the original list.

Full code

 

KnightL on a chessboard challenge

Problem statement
KnightL is a chess piece that moves in an L shape. We define the possible moves of KnightL(a,b) as any movement from some position (x_1, y_1) to some (x_2, y_2) satisfying either of the following:

x_2 = x_1 \pm a and y_2 = y_1 \pm b, or
x_2 = x_1 \pm b and y_2 = y_1 \pm a

Note that (a, b) and (b, a) allow for the same exact set of movements. For example, the diagram below depicts the possible locations that KnightL(1,2) or KnightL(2,1) can move to from its current location at the center of a 5 \times 5 chessboard:

Observe that for each possible movement, the Knight moves 2 units in one direction (i.e., horizontal or vertical) and 1 unit in the perpendicular direction.

Given the value of n for an n \times n chessboard, answer the following question for each pair where 1 \le a,b \textless n:

  • What is the minimum number of moves it takes for KnightL(a,b) to get from position (0,0) to position (n - 1, n - 1)? If it’s not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each KnightL(a,b) according to the Output Format specified below.

Input Format
A single integer denoting n.

Constraints
5 \le n \le 25

Output Format
Print exactly n - 1 lines of output in which each line i (where 1 \le i \textless n) contains n - 1 space-separated integers describing the minimum number of moves KnightL(i,j) must make for each respective j (where 1 \le j \textless n). If some KnightL(i,j) cannot reach position (n - 1, n - 1), print -1 instead.

For example, if n = 3, we organize the answers for all the (i, j) pairs in our output like this:

Sample Input 0

Sample Output 0

Explanation 0

The diagram below depicts possible minimal paths for KnightL(1,1), KnightL(1,2), and KnightL(1,3):

One minimal path for KnightL(1,4) is:

(0,0) \rightarrow (1,4) \rightarrow (2,0) \rightarrow (3,4) \rightarrow (4,0) \rightarrow (0,1) \rightarrow (4,2) \rightarrow (0,3) \rightarrow (4,4)

We then print 4 4 2 8 as our first line of output because KnightL(1,1) took 4 moves, KnightL(1,2) took 4 moves, KnightL(1,3) took 2 moves, and KnightL(1,4) took 8 moves.

In some of the later rows of output, it’s impossible for KnightL(i,j) to reach position (4,4). For example, KnightL(3,3) can only move back and forth between (0,0) and (3,3) so it will never reach (4,4).

Solution
We are going to solve this problem by searching for a solution recursively for every (i,j). From each current position (r,c) we know which new position (newRow, newCol) we can reach. The possible values of (newRow, newCol) given a current position (r,c) and a pair (i,j) can be easily computed as follows:

We then have 8 (not necessarily valid) new positions we can reach from (r,c). Example: for a given newRow = rows[1] the corresponding newCol will be cols[1]. That is, an entry at index idx in rows corresponds to an entry at cols[idx].

We then call our search function recursively for every pair (newRow, newCol) we can reach from a given current position (r,c).

For our recursive algorithm to work we need to have a terminating condition:

where count is the current number of steps it took us to reach this far for a given function call.

Obviously thats not all. In order to avoid jumping between two positions indefinitely we need to store some sort of state so our algorithm will stop in case we can never reach (n - 1, n - 1). That is, we are only going to jump to a new state if we haven’t visited that state already or if we may have found a shorter path to that state in case the state has been visited before.

Our state is a combination of row, column and number of steps it took us to get there. We are going to jump to (newRow, newCol) only when:
– we haven’t visited (newRow, newCol) before, or,
– we have visited (newRow, newCol) before but the number of steps it took us to get there is larger than count + 1

Finally we need to keep track of our minimum number of steps for every (i,j).

Full code

 

Longest contiguous increasing subarray

Problem statement
Given an array A with N numbers print a longest increasing subarray in A.

Sample Input

Sample Output

Solution
We want to solve this problem in \mathcal{O}(n) time complexity. The easiest approach is to to start iterating over our array and increase our sequence length as long as A[i] \textgreater A[i-1]. If we reach a point where A[i] \not\textgreater A[i-1] we start a new sequence from index i. Along the way we somehow keep track of the largest sequence sequence found so far.

We can optimise our algorithm using an heuristic approach. If we reach an index i where a new subsequence might start (because A[i] \not\textgreater A[i-1]), instead of looping forwards from index i we can work our selfs backwards starting from index i + max till i and check if A[i] \textgreater A[i-1]. If A[j] \not\textgreater A[j-1] for some j \in \left[i, i + max\right] then we can skip and start searching for a new potential subsequence directly from index j. max is the length of a previous contiguous increasing subarray found.

The full code is listed below.

Code

 

Renewing Let’s Encrypt SSL certificate

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: