The problem for September 9 is Compare Version Numbers. Given two
version numbers version1 and version2, represented as strings, you want to
return -1 if version1 is smaller than version2, 1 if version1 is larger
than version2, and 0 if they’re equal. Versions are strings consisting of one
or more revisions joined by a .. Each revision consists of digits only, but
may contain leading zeros. Every revision contains at least one character, so
it’s impossible for a substring of two . to exist. Comparing versions consists
in comparing the integer value of its revisions in left-to-right order. If a
version doesn’t specify a revision at a given index, then the revision should be
treated as 0.
A solution for this problem consists in splitting the two provided strings in
two sequences of numbers and do a pairwise comparison of them. Whenever a
version number is missing a revision, assume 0 as its value. The following is an
implementation of this strategy:
The problem for September 8 is Sum of Root to Leaf Binary Numbers.
You’re given a binary tree in which each node has value 0 or 1. In this case,
each path from the root to a leaf represents a binary number starting with the
most significant bit. For example, a path from root to leaf \(0 \rightarrow 1
\rightarrow 1 \rightarrow 0 \rightarrow 1\) represents the number \(01101\) in
binary, or \(13\) in decimal. We’re interested in the sum of numbers produced
from the paths from the root to every leaf in the tree.
We’re told that the number of nodes in the tree doesn’t exceed 1000 and that the
sum will not exceed \(2^{31} - 1\). Therefore, we can do a DFS on the
tree while keeping track of the number at each path, accumulating the current
number whenever we reach a leaf. Since the path follows the significance of the
bits in the resulting number, we can keep track of the current number while
traversing the tree by multiplying the current number by 2 whenever we go either
left or right, and sum the value at the node we’re visiting. The following is an
implementation of this idea:
The problem for September 7 is Word Pattern. You’re given two
strings. One of them consists of lowercase letters and the other consists of
lowercase letters separated by spaces. You want to find out if a
bijection exists between the characters of the first string and the
words in the second string. In other words, you want to return true if there
is a one-to-one correspondence between the characters of the first string and
the characters of the second string, and false otherwise.
If the number of words is different from the number of characters, then you can
be sure that no bijection exists. If the number of words is the same, we can go
word by word and check if a word happens to be mapped to different characters.
If it does, then no bijection exists. This is still not sufficient to determine
a bijection, since the same character can still be mapped to different words. In
order for a bijection to exist, the number of different words must be equal to
the number of different characters. Combining all those checks lets us determine
if there is a one-to-one correspondence between characters and words. The
following is an implementation of the previous idea:
The problem for September 6 is Image Overlap. You’re given two images
represented as binary, square matrices, of the same size. You want to translate
one of the images by sliding it left, right, up or down any number of units such
that, when placed on top of the other image, the number of 1s that overlap in
both images is maximized. The length of the side of the images is at most 30.
The length of the side of the images is small enough for us to try all possible
translations in \(\mathcal{O}(n^4)\). The following is an implementation of that
strategy:
The problem for September 5 is All Elements in Two Binary Search
Trees. We’re interested in, given two binary search trees of integers,
returning a sorted list of all the integers from both trees.
Since we’re dealing with binary search trees here, each node is
guaranteed to store a key greater than all the keys in the node’s left subtree
and less than those in its right subtree. As such, an in-order
traversal of the tree is guaranteed to produce a sorted list of its
elements. We can do an in-order traversal of a binary tree with \(n\) nodes in
\(\mathcal{O}(n)\). Having two sorted lists of size \(a\) and \(b\), we can
merge them in a new sorted list in \(\mathcal{O}(a + b)\). With these two
building blocks, we can produce an algorithm to return the sorted list of all
integers of both trees in \(\mathcal{O}(n + m)\), \(n\) being the number of
nodes in the first tree, and \(m\) being the number of nodes in the second tree.
The following is an implementation of that idea: