Understanding mathematical notation for coding problems.

Question

The majority of my questions revolve around code (thus my activity on stackoverflow), but I've been going over interview question that assume a good understanding of mathematical notation. I don't have a great mathematical background, so I am having trouble understanding what the question is actually asking.

I am trying to decipher the following question (image because I couldn't figure out formatting):

I believe I understand every sentence except the last. Could someone help work through this? I believe with this example decoded, I can work through the majority of the others with some help from here.

Answer 1

Actually, I think there is a problem with the notation, because the final sentence seems to intend to define $v_i$, but $v_i$ was already used as part of the definition of the sequence $A$. The only way for all statements in the problem to be true is if the volume increases as time increases. But the wording of the problem implies that you should describe an algorithm to compute a value assuming the data in $A$ are arbitrary (aside from the requirement that the timestamps are increasing).

To make sense of the problem, we can change one letter, so that you are to compute $u_i = \max\{v_j \mid (t_i - t_j) \leq w, j \leq i\}$ for $0 \leq i \leq n - 1$. I think this is the problem you were intended to solve.

As an example, let $n=7$, $w = 3$, and let $A$ contain the following pairs:

\begin{align} A[0] &= (2,4) \\ A[1] &= (3,3) \\ A[2] &= (5,2) \\ A[3] &= (5.5,6) \\ A[4] &= (6,5) \\ A[5] &= (7,7) \\ A[6] &= (9,8) \\ \end{align}

Then $u_2 = 4$, because $t_2 = 5$ and so the only values of $j$ for which $t_2 - t_j \leq w$ and $j \leq i$ are $j = 0$ (because $t_2 - t_0 = 5 - 2 \leq 3$), $j = 1$ (because $t_2 - t_1 = 5 - 3 \leq 3$), and $j = 2$ (because $t_2 - t_2 = 0 \leq 3$). Of these three possible values of $j$, the one for which $v_j$ is the largest is $j=0$, that is, $v_j = v_0 = 4$; therefore we set $u_2 = v_0 = 4$.

(Now it should be clear how nonsensical the last equation of the problem statement actually was: that equation would have us set $v_2 = \max\{v_0,v_1,v_2\} = 4$, when clearly the data say that $v_2 = 2$.)

On the other hand, $u_4 = 6$; in that case the possible values of $j$ are $1, 2, 3, 4$, and $v_j$ is maximized when $j = 3$, so $u_4 = v_3 = 6$.

In plainer language, a "window" contains a subsequence of the entries of $A$. The "window" from which you will compute $v_i$ ends with the pair $(t_i, v_i)$, but it also may include earlier pairs; the qualifications that allow $(t_j, v_j)$ to be in the "window" are that $t_i - w \leq t_j \leq t_i$. (The condition $j \leq i$ is equivalent to $t_j \leq t_i$ since the timestamps are in increasing order.) The value you are looking for is the largest $v_j$ found in the "window".

Frankly, I think the way the last expression is written is rather backassward; it seems much more natural to me to express the volume as a function of time, that is, $v(t_j)$ instead of $v_j$, and express the "window" using the earliest and latest possible timestamps in it, so you would be looking for $\max\{v(t_j) \mid t_i - w \leq t_j \leq t_i\}$. (In that case it would even be OK to give that expression as the definition of $v_i$, since $v_i$ would not yet have been defined.) But that's just my opinion.

Answer 2

It's asking for a maximum of $v_j=A[j,2]$ where you also have side conditions.

When the conditions (to the right of $|$) are separated by a comma, it means an "and", i.e., all conditions must hold for a $v_j$ to be considered when computing the max.

So $v_i$ is a maximum of all the $v_i$'s for $i=j,j+1,\ldots,n-1,$ where you only consider those $v_j$'s for which $t_i-t_j=A[i,1]-A[j,1]\leq w$ for some given parameter $w$.

You can do this maximization in a loop for each i, by initializing an empty list for each $i$ and a while looping test for the conditions and add the v_j into a list when the conditions hold and then take max of that list.

Warning The question as stated seems to update $v_i's$ based on the $v_j$'s that come before them so a temp list of new v_i's may be necessary, though not so efficient.