max product (j-i)*min(arr[i], arr[j]), streaming mode #Ashish

In the static, non-streaming context, the optimal solution is perhaps in my gmail. The brute force would evaluate roughly N*N/2 pairs. We can reduce that significantly.

Start with 1st/last, which is quite possibly the final winner. Save this as maxProductOfLoopA and evaluate a[0] vs a[9 i.e. last].

  • Suppose a[0] > a[9], then 1/9 , 2/9 , 3/9 etc are automatically eliminated.
  • Suppose a[0] < a[9], then 0/8, 0/7, 0/6 etc are automatically eliminated.
  • if a[0] == a[9], then 0/8 etc are automatically eliminated

You can visualize it as removing an outer layer from a NxN matrix. Note the matrix is triangular and has exactly one outer row and one outer column at any moment. In the first step, you either remove the outer row or outer column.

Supposed you removed */9 column. In 2nd step, we compute 2nd product at 0/8, and 2nd evaluation of a[0] vs a[8] and remove another outer layer.

In about N steps we should reduce the matrix to 1 remaining cell. This cell could be the final winner so we must evaluate it.

—-

Hi Ashish,

Let me change your question slightly. Input numbers come individually in a stream. Among all possible pairs of numbers, we want to compute and publish the latest maximum product:

    A(i, j) * B(i, j)

, where A(i, j) is the time lag j-i and B(i, j) is minimum(arr[i], arr[j])

NB: We will need to keep all numbers seen so far, since the the winning pair might include the first elements.

At any time there’s a current max. When we receive the 89th element, enter loop A:

compute the product for 1st/89th i.e. arr[0]/arr[88]
* If arr[0] > arr[88], then just exit the loop with this product as maxProductOfLoopA. No need to try 2nd/89th or 3rd/89th, as all those products are all smaller than 1st/89th. (This is the genius of the solution you told me.)
* otherwise, compute the product for 2nd/89th. If it exceeds maxProductOfLoopA, then update maxProductOfLoopA. Now check if arr[1] > arr[88]. If yes just exit loop A with maxProductOfLoopA
* otherwise compute the product for 3rd/89th….

Once we exit loopA, update the current max product using maxProductOfLoopA.

For streaming situation, I think this is one good solution, if not the optimal solution.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s