Coding Exercise 01: Is a character array a subset of another one?

I will occasionally create a problem that every basic programmer should be able to solve within thirty minutes.

Today's problem is checking whether a character array is a subset of another one (when viewed as sets of characters):

Write a function whose first and second inputs are arrays of characters and output is true if every element of the first input is an element of the second input and false otherwise.

For example,

(['t', 'e', 'n', 'n', 'e', 's', 's', 'e', 'e'], ['e', 'n', 's', 't'])

outputs true and

(['h', 'e', 'l', 'l', 'o'], ['a', 'h', 'l', 'e'])

outputs false.

The canonical naïve function runs in O(n * m) time, where n and m are the sizes of the first and second inputs, respectively. Can you write a function that runs in O(n + m) time?

Give the Same Name to Different Things!

Mathematics is the art of giving the same name to different things. Henri Poincaré, 1854 - 1912.
Henri Poincaré said that mathematics is the art of discovering that two seemingly different objects are intrinsically the same within some predefined context. Mathematicians empathize with him but everyone else normally does not. I will try to explain his sentiment.

The set of natural numbers $\mathbb N$ comprises the numbers $0$, $1$, $2$, etc. and the set of rational numbers $\mathbb Q$ comprises the numbers that can be written as the ratio $\pm n/m$ of two numbers $n$ and $m$ in $\mathbb N$, where $m$ is not allowed to be $0$, of course.

For example, $3/4=0.75$, $-1/2=-0.5$, and $3/1=3$ are numbers in $\mathbb Q$, and $3$ is the only number in this list that is also a number in $\mathbb N$.

Your intuition probably agrees with the claim that $\mathbb N$ is a "smaller" set than $\mathbb Q$: after all, $\mathbb Q$ contains $\mathbb N$ since every number $n$ in $\mathbb N$ can be written as $n/1$, which is a number in $\mathbb Q$ by definition. Moreover, $\mathbb Q$ contains the negative numbers $-1$, $-2$, $-3$, etc. to boot!

Nevertheless, it turns out that $\mathbb N$ and $\mathbb Q$ "have the same size" even though both contain an infinite amount of numbers. Explicitly, we can identify every number $n$ in $\mathbb N$ with a unique number $q$ in $\mathbb Q$ in such a way that every number $q$ in $\mathbb Q$ is identified with a number $n$ in $\mathbb N$.

The above definition of size is analogous to the claim that the sets $\left\{a,b,c\right\}$ and $\left\{0,1,2\right\}$ have the same size (in this case three) since the identification $a\leftrightarrow0$, $b\leftrightarrow1$, and $c\leftrightarrow2$ satisfies the above hypotheses.

Therefore, in the context of set theory, $\mathbb N$ and $\mathbb Q$ are the same set (i.e., they can be identified).

On a different note, the most well-known example in pop culture of Henri's quote is the claim that a doughnut and a coffee cup are homeomorphic, i.e., one can be reshaped into the other "in a nice way". This is analogous to the claim that a circle and a square are homeomorphic, and you can already imagine a way to reshape one into the other "in a nice way", e.g., by "smoothing out" the corners of the square.

Therefore, in the context of topology, a circle and a square are the same topological space (i.e., they can be identified) when viewed as topological subspaces of $\mathbb R^2$ together with the standard topology, whatever that means to you.

Such identifications are useful because they simplify the task of studying objects if we can discover that an enormous number of seemingly different ones are, in fact, intrinsically the same within some predefined context: whatever is topologically true about the circle is topologically true about the square, the triangle, the pentagon, the hexagon, etc. Thus we only need to study one: the mighty circle.

Since mathematics is not all blabber, I will give you an explicit homeomorphism between the circle and the square but will not prove that said map is indeed a homeomorphism; I will make use of the proverbial "it is left as an exercise for the reader".

Let
$$C=\left\{\left(x,y\right)\in\mathbb R^2:x^2+y^2=1\right\}$$be the circle, let
$$S=\left\{\left(x,y\right)\in\mathbb R^2:\max\left\{\left|x\right|,\left|y\right|\right\}=1\right\}$$be the square, and define $\varphi:C\to S$ by
$$\left(x,y\right)\mapsto\begin{cases}\left(x/y,1\right)&\text{if }\left|x\right|\leq\sqrt2/2\text{ and }y\geq\sqrt2/2,\\\left(x/y,-1\right)&\text{if }\left|x\right|\leq\sqrt2/2\text{ and }y\leq\sqrt2/2,\\\left(1,y/x\right)&\text{if }\left|y\right|<\sqrt2/2\text{ and }x>\sqrt2/2,\text{ and}\\\left(-1,y/x\right)&\text{if }\left|y\right|<\sqrt2/2\text{ and }x<\sqrt2/2.\end{cases}$$Then $\varphi$ is a homeomorphism between $C$ and $S$, where $C$ and $S$ inherit the subspace topology of $\mathbb R^2$ together with the standard topology.