%%strength: GTD with non-trivial research/innovation

If the research is too easy, then other developers can also do it, often faster.

If the research takes years, then it’s really for a researcher. I’m not a researcher (yet)

The project could have high value!

eg: Barcap proj
eg: b2bTradingEngine
eg: bloomberg adapter in GMDS
eg: home-made web server using WCF

Advertisements

retreat to raw ptr from smart ptr ASAP

Raw ptr is in the fabric of C. Raw pointers interact/integrate with countless parts of the language in complex ways. Smart pointers are advertised as drop-in replacements but that advertisement may not cover all of those “interactions”:

  • double ptr
  • new/delete/free
  • ptr/ref layering
  • ptr to function
  • ptr to field
  • 2D array
  • array of ptr
  • ptr arithmetics
  • compare to NULL
  • ptr to const — smart ptr to const should be fine
  • “this” ptr
  • factory returning ptr — can it return a smart ptr?
  • address of ptr object

Personal suggestion (unconventional) — stick to the known best practices of smart ptr (such as storing them in containers). In all other situations, do not treat them as drop-in replacements but retrieve and use the raw ptr.

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.

unsolved! [12]locate]long sentence a permutation of 3 words

Q: you are given a list of words denoted L, that are all the same length + a string denoted S. Find a substring of S that is a concatenation of each word in the list exactly once and without any intervening characters. This substring is guaranteed to occur exactly once in S.

Example:.
L: “fooo”, “barr”, “wing”, “ding”, “wing”.
S: “lingmindraboofooowingdingbarrwingmonkeypoundcake”.
Answer — fooowingdingbarrwing.

My solutions below ignore the “same-length” helpful constraint.

Solution-B (Brute force) — For each permutation, scan by indexOf() or strstr() or string::find(). Guaranteed to find a solution in finite time. Inefficient if list is large.

Solution-C — a potentially faster solution.

Phase 1: For each word in the list, i’d count how many times it occurs. The word with lowest occurrence would be a “candidate”. If every word occurs 2+, then I may resort to Solution-B.

I’d start with the longest word (skipping those non-unique words) in L — assumed to be the most likely candidate. As soon as I find a word with occurrence=1 exactly, I exit Phase 1 with a super candidate. For this discussion, I assume we have a super candidate.

Phase 2a: remove the super candidate from the list. Find the shortest word’s length in the list. Say it’s 4. Blindly read the next 4 character in S after our super candidate. See if any word starts with that…..

Phase 2b: do the same leftward. Perhaps by reversing all the strings.

py class^module(singleton), briefly

Both modu5 and class2 are based on a dict. Both can contain “system-wide” variables, effectively singleton objects.

A module is like a singleton class, without constructor or inheritance. All methods are classmethods, so a module can be simpler to use if you want a singleton class.

Global variables and singletons — I figured these out because 2nd time you import a module, the module-level objects aren’t created again! You can safely construct objects at the module level and all of them become global variables.

Calling a method on a class goes through __getattr__ hook. Probably no such thing in a module.

Importing a regular module actually executes the *.py file – no such feature with a class.

Modules (not classes) are hooked into the (non-trivial) import mechanism.

Module functions and Methods have differences.

See also
https://learnpythonthehardway.org/book/ex40.html
http://stackoverflow.com/questions/600190/python-choosing-between-modules-and-classes