[17]%%agile advantages: b aggressive

  • healthy job market
  • advantage: short commute. Job not too demanding. Plenty of time available for self-study
  • advantage: I can work day and night to get things done
  • advantage: I’m not aiming for a promotion, so I can try many interviews
  • advantage: my quant credentials and zbs is probably top tier among techies
  • advantage: domain nlg
  • advantage: health and stamina
  • advantage? data analysis aptitude
  • advantage: I have Singapore + java as safety net –> risk capacity.
  • advantage: am open to relocation
  • advantage: am open to short term contracts
  • advantage: am open to pay cuts
  • advantage: no family.
  • advantage: c++/c# in addition to java
  • advantage: above-average SQL, Unix, python/perl/bash

If I hit $220k as a contractor, my self-image and self-esteem would improve. I would feel confident, no longer inferior. In fact, I would feel better than the managers since I don’t rely on that one employer.

Advertisements

low-latency jobs; learning python#CSY

I believe my current trading system is latency-sensitive (as a large-scale [1] order management engine), but on this job I don’t do anything about latency — this is just another equity trading system job. I feel you don’t need to aim for low latency. Just aim for any c++ job that’s not off-putting to you.

[1] I consider it large scale because it has probably 10-20 developers working on it, for at least 5 years.

Low-latency jobs are harder to get, and they usually prefer developers in their 30’s or younger.

I don’t exactly avoid such jobs, but I don’t hold up any serious expectation of an offer by those teams. The main barrier of entry is technical capabilities, either coding test or obscure c++/linux questions. Even if I’m lucky to hit familiar, well-prepared tech questions, they may still find reasons to take a pass, as I experienced in my technical wins at SIG, Bloomberg etc.

Java and python are never show-stoppers for these jobs, so
* if you only aim for low-latency jobs, then don’t worry about python or java
* if you widen your search scope, then I suggest you pick up python, not java

Taking a step back to get a perspective, I think job seekers are like smartphone makers — we need to adjust our “product” for the changing customer taste. The “product” in this case is our testable tech skills. Domain knowledge is losing importance; Python is now in-demand; coding tests are growing harder; Linux/compiler system knowledge has always been important to low-latency interviews .. so we need to decide how to adjust our “product” to attract our customers.

—- Earlier email —-

How is your python practice?

This is a personal journey. Therefore some people don’t like to discuss in details how they are learning something new. So feel free to disclose any amount of information you feel comfortable with.

I advocated solving coding problems in python. I now realize both you and me don’t want to solve every problem. Out of 10 problems, we might solve 1 or 2 in real code. So in the past 4 weeks, perhaps you didn’t look at 10 problems so the number of problems you could solve in python might be very low. Therefore, my suggestion may not work for you.

In that case, I wonder what python coding experiments you prefer.

I once said python is easier to learn, but like learning any new language, it still demands a huge commitment, sustained focus, and personal sacrifice. Therefore, it helps greatly if there’s a python project on a day job. Without it, we need self-discipline, determination, and clear targets to sustain the focus and energy. None of these is really “easy”.

Talking about clear targets, one example is “solve one coding problem of medium complexity each week, in python”.

## emulators of secDB #GregR

— secDB derivatives/cousins/emulators:

  • Pimco and Macquarie licensed Beacon
  • CS hired two secDB veterans to build a similar system on java
  • MS has a RCE (risk calc engine) project, based on scala and java
  • UBS tried it too. I applied for this job in 2011 or 2012
  • Athena and Quartz
  • BlackRock Aladdin (1988), written in java, for risk management across portfolios. All other functionalities are secondary.

I feel you need such a system only if your books have many derivative contracts that needs constant “revaluation”. This is a core feature of derivative risk systems.

Q: beyond risk systems, why is Quartz also supporting trade booking and execution?

I think secrete key is in the data store, which is central to those systems. SecDB systems feature a specially designed in-memory and replicated data store, which can be the basis of those systems.

A special data store is live and reference market data.

##4 items I admire in%%peers #!!status

I ought to admire my peers’ [1] efforts and knowledge (but not their Status) on :

  • personal wellness
  • personal finance, not only investment and burn rate
  • zbs, portable GTD, not localSys
  • parenting
  • mellowness to cope with the multitude of demands, setbacks, disappointments, difficulties,

Even though some of my peers are not the most /accomplished/ , they make a commendable effort. That is admirable.

[1] Many people crossing my mind everyday are … not really my peers, esp. those managers in China. Critical thinking required.

I don’t have a more descriptive title..

windows registry: criticized

[[art of unix programming]] points out that Windows registry are sometimes corrupted. Remember the standard advice to always back up the registry before editing it?

When corrupted, the registry “frequently” breaks the entire system and requires a completely reinstall.

weakness — the registry is a centralized hierarchical config data store shared in RW mode by all (dozens of) applications.

weakness — single point of failure

In contrast, Unix config data is decentralized, but I won’t elaborate. Centralized hierarchy sounds plausible but doesn’t work well in practice.

Hadoop apps: Is java preferred@@

I didn’t hear about any negative experience with any other languages, I would assume yes java is preferred, and the most proven choice. If you go with the most popular “combination” then you can find the most resources online and the widest support tools.

–According to one website:

Hadoop itself is written in Java, with some C-written components. The Big Data solutions are scalable and can be created in any language that you prefer. Depending on your preferences, advantages, and disadvantages presented above, you can use any language you want.

bigData: java’s strengths #python

Although a lot of specialists argue in favor of Python, Java is also required for data analytics. I-banks prefer java for building enterprise systems. Many Big Data systems is developed in Java or created to run on JVM. The stack may include the following tools:

  1. Spark is used to stream data and distribute batch.
  2. Kafka – to queue huge volumes of information.
  3. Spring Boot – to provide system’s options to the customers via REST API.

I feel for high volume low-level “data” handling, java (and C++) are more suitable. For the high-level
“information” analysis, python and R are more suitable. However, in reality i might be wrong. Python might have big frameworks comparable to java’s.

git | understanding parent node

Suppose your git branch brA has a commit hash1 at its tip. Then you merge brA into master at merge commit hashM. Then you commit on brA again at hash2.

Q: What’s the parent node of hash2?
A: I think git actually shows hash1 as the parent, not hashM !

Q: is hashM on brA at all?
A: i don’t think so but some tools would show it as a commit on brA.

I guess that if after the merge, you immediately re-create (or reset) brA from masgter, then hash2’s parent would be hashM.

top-of-book imbalance: predictive power

At any time, for a given order book there’s an observable ticking ratio I name as “top-of-book-imbalance” or TOBI := b/(b+a) where

b is total volume at best bid level and
a is total volume at best ask level

For a given stock, whenever TOBI was high, statistically we had seen more market-buy orders in the preceding time period; and conversely when TOBI was low, we had seen more market-sell orders.

Therefore, TOBI has proven predictive power.

7 clusters@HFT-c++IV questions

Every single HFT interview question is about low-latency. Furthermore, the ibank algo-trading interviews revolve around the same clusters.

Even though I’m not aiming for HFT jobs, these topics are still very relevant to ibank and the “3rd type” of c++ shops.

  1. socket
  2. template meta-programming — deep topic but never quizzed in-depth beyond “tricks”
  3. move-semantics

— less visible themes in these clusters:

  1. pthreads and c++ threading but I seldom get c++11 question here
  2. STL container internals, mostly shared_ptr, raw array, vector, RBTree, and hashmap
  3. (back of tricks) memory optimization techniques using allocators, cache-optimization, malloc(), placement-new, object-pool, memset,
  4. miscellaneous core OO features like big4, virtual, MI, pbref/pbval

— other HFT topics are dispersed/scattered, not showing any strong central theme

  1. shared memory
  2. linux system calls
  3. compiler details
  4. selected boost libraries

4 components@latency

  1. Propagation delay — Amount of time required for a message to travel from the sender to receiver, which is a function of distance.
  2. Transmission delay — Amount of time required to push all the packet’s bits into the link, which is a function of the packet’s length and data rate of the link, and has nothing to do with distance
  3. Processing delay — Amount of time required to process the packet header, check for bit-level errors, and determine the packet’s destination. Personally, I would think application logic also introduces processing delay.
  4. Queuing delay —  Amount of time the packet is waiting in the queue until it can be processed. Personally, I would guess that a larger buffer tends to exacerbate queuing delay. I would say there are often multiple queuing points along the critical path, like an airport.

From https://hpbn.co/primer-on-latency-and-bandwidth/.

 

spare time utilization: %%strength

Very few peers are so conscious of burn^rot. Higher utilization of spare time is a key strength during my US peak + my dotcom peak + also my high school. We could analyze what’s common and what’s different between these peaks…

Outside those peaks, I also used this strength to complete my UChicago program, but the tangible benefit is smaller.

(This is different from efficiency on the job. Many efficient colleagues spend less time in office but get more done.  My style involves sacrificing personal spare time and family time.)

Looking forward, I guess this strength could be strategic for research-related domains, including any job involving some elements of research and accumulation.

A repeated manager praise for me is “broad-based”, related to this strength.

What if I hadn’t worked this hard # kids

Over my 20Y career, I showed _some_ talent professionally.

In contrast, I showed significantly more talent in school. My massive study effort increased my abilities [1] to the extent that people don’t notice the difference between my talent vs abilities. Even my IQ score improved due to my intellectual curiosity and absorbency. If these efforts are considered a talent, then yes I have the talent of diligence.

[1] eg — Chinese composition, English grammar/vocabulary, many knowledge-intensive subjects

Q1: what if I had put in just an average amount of effort in school and at work? Some people (mostly guys I really don’t know well) seem to put in sporadic efforts that average out to be "just average" but still got into similar professional level like I did, or higher.
A: For my academic excellence, persistent effort was necessary.

A: I guess sporadic effort could be enough to reach my level of professional "success" for very bright and lucky people. I doubt any professional programmer got higher than mine without consistent effort for many years.

Professional success depends on opportunity, on positioning and timing, on inter-personal skills and relationship skills, on judgment 判断力. None of these depends directly on consistent effort.

An example of positioning — my break into Wall St java market vs my peers who didn’t.

To analyze this question, I need to single out an under-appreciated talent — absorbency capacity i.e. 耐得住寂寞, where I score in the 95th percentile.

Q2: if my son only puts in sporadic and average efforts, could he end up losing the competitions?

versioned-queue problem

I think this problem is mostly about data structure, not algorithm.

Q: Design and implement a Version-Queue. A Version-Queue maintains a version number along with normal Queue functionality. Every version is a snapshot of the entire queue. Every operation[Enqueue/Dequeue] on the Queue increments its version.

Implement the following functions:

1. Enqueue – appends an element at the end of the queue.
2. Dequeue – returns the top element of the queue.
3. Print – it takes a version number as input and prints the elements of the queue of the given version. The version number input can also be an old/historical version number.

E.g. if the current version number of the queue is 7 and the input to this function is 5, then it should print the elements of the queue
when its version number was 5.

For simplicity, assume the elements are integers.

We expect you to write a helper program to test the above data structure which will read input from stdin and prints output to
stdout.

Input format:
First line should have an integer n (number of operations). This should be followed by n number of lines, each denoting one operation.
e.g.
6
e 1
e 4
d
e 5
p 2
p 4

‘e’ stands for enqueue

— My design —
In addition to the regular queue data structure, we need a few helper data structures.

All current + historical queue elements are saved as individual elements in a “Snapshot” vector, in arrival order. This vector never decreases in size even during dequeue. Two pointers represent the trailing edge (dequeue) and leading edge (enqueue).

(minor implementation detail — Since it’s a vector, the pointers can be implemented as 2 integer index variables. Pointers and iterators get invalidated by automatic resizing.)

Every enqueue operation increments the right pointer to the right;
Every dequeue operation Increments the left pointer to the Right;
(No decrement on the pointers.)

With this vector, I think we can reconstruct each snapshot in history.

Every pointer increment is recorded in a Version table, which is a vector of Version objects {Left pointer, Right pointer}. For example, if Version 782 has {L=22, R=55} then the snapshot #782 is the sub-array from Index 22 to 55.

Additional space costs:
O(K) where K = number of operations

Additional time costs:
Enqueue operation — O(1). Insert at end of the Snapshot vector and Version vector
Dequeue operation — O(1). Move a pointer + insert into Version vector Print operation — O(M) where M = maximum queue capacity

Minor point — To avoid vector automatic resize, we need to estimate in advance the limit on K i.e. number of operations. If you tell me you get millions of operations a microsecond, then over a day there
could be trillions of “versions” so the Versions vector and the Snapshot vector need sufficient initial capacity.

Note we could get 9000 enqueue operations in a row.

continuous coding drill #Shi

For years I practiced continuous self-learning on

  • java, c++, SQL — IV and GTD growth
  • Unix, python — mostly GTD
  • quant

I consider my continuous self-learning a key competitive advantage, and an important part of my absorbency capacity.

I asked a bright young Chinese grad. He practiced real coding for months in college. I said “fast and accurate” is the goal and he agreed. A few years into his full time job, he stopped practicing the same. Result? He said for the same coding problem he was able to make it work in 10 min then, but now probably 20 minutes.

I asked “Do you know anyone who keeps up the coding drill?” He gave a few points

  • he didn’t tell me any individual
  • he believed the only reason for coding drill is job hunting
  • when I said continuous practice all year round will make a big difference compared to practice only when job hunting, he agreed wholeheartedly and reiterated the same observation/belief, but he disagrees that continuous coding drill would lead to significant professional growth as a programmer. I think he has other ideas of significant growth. At my age, I don’t foresee any “significant growth”.

visible-progress n time utilization

I have an uncommon and unreasonable view that most of my waking hours should produce tangible “return” like learning, self-improvement, fitness or help kids learn.

Q: how about reading about parenting or just newspaper? I do allow myself but in hind sight I often feel bad. I feel worse if the reading is not so mainstream, like …

! Though I don’t have many examples, now I think most individuals who make more money don’t view their personal time as raw materials for a manufacturing process.

I now feel personal growth doesn’t have to produce self-glorification. How about cooking, kite-flying, dancing, sight seeing … without any talent whatsoever.

top3 personal survival capabilities #IV,burnRate#reflect

Out of the subconscious realm, I hand-picked a couple of personal “qualities” [2] as the (three or 5) pillars of my life [1] since 2007, the /watershed year/.

These are the pillars for my past, present and my future, immigration plan, family housing, retirement plan, … There’s possibly nothing new here, but this blog post provides another perspective into the “making” of my career and the foundation of my entire life. As such, this is not a worthless reflection.

I think everyone can consider answering this question — “Using specific and hopefully unique words, name 2 or more personal survival capabilities.”

[1] to some extent, my family’s life also rests on these same pillars, but I tend to under-estimate the capabilities of my family members and over-estimate my earning power.
[2] in this post I don’t want to include my financial asset since I want to focus on personal strengths

  • AA) my tech IV prowess. Look at CSY’s experience.
    • absorbency — of dry, theoretical domains. /continuous/ plow-back without exhaustion
    • self-renewal to stay relevant — lifelong learning. Am rather successful so far
    • my reflective blogging is actually part of the my career way-finding, motivation…
  • BB) my capacity to keep a well-paying dev job (not as “unique” as the other 2 capabilities). Even in the three Singapore cases, I was able to hold it for about 2 years, or receive a transfer or severance.
    • figure-things-out speed?  Not really my strength but my competence
    • camp-out, extra hours
    • attention to details
    • getting the big picture?
  • [T3] personal burn-rate — important to my feeling of long term security
  • — The following factors are less “unique” but I want to give credit to
  • my health (and bread-earning longevity) — in the long run this factor would prove increasingly important. It enables me to keep working long past retirement age.
  • my education including English skills
  • my dedication to my kids, not only their studies
  • [T3 = a top-3 factor]

! benchmarking — AA is a single-winner competition, whereas BB is about staying above minimum standard in the team.

! strengthening — I continue to plow back and build my AA/BB 内力, focusing on localSys + coding drill. A huge amount of energy, absorbency, continuous effort and dedication needed (cf. XR,YH, CSY…), though since 2018 I have noticed the ROTI is not as high as before 2012.

effectively ignore whitespace-only change in code review

$ perl -pe ‘s/\s//g’ tcm_creator.py> new
$ git checkout some-commit tcm_creator.py
$ perl -pe ‘s/\s//g’ tcm_creator.py> old
$ diff old new # should show no discrepancy

This worked for me. Entire file is flattened to a single long string.

IIF the whitespace change is only and always confined with a line i.e. no line splitting/joining , then perl  -l -pe is more useful.

 

async messaging-driven #FIX

A few distinct architectures:

  • architecture based on UDP multicast. Most of the other architectures are based on TCP.
  • architecture based on FIX messaging, modeled after the exchange-bank messaging, using multiple request/response messages to manage one stateful order
  • architecture based on pub-sub topics, much more reliable than multicast
  • architecture based on one-to-one message queue

op=() will call implicit cvctor if RHS is!!correct type

Below is an online c++ question, to predict the output (12310). The assignment “i=10” looks like a call to the synthesized assignment operator, but I overlooked the fact that RHS is a primitive int but LHS is Integer class, but assignment operator requires both sides to be Integer class type!

So an implicit conversion-ctor is required before the assignment operator is picked by the compiler.

A second knowledge gap — the synthesized assignment operator performs a bit-wise copy including the “num” field.

class Integer{
  int num;
public:
  Integer(){
    num=0;
    cout<<"1";
  }
  //explicit //would break the assignment
  Integer(int arg){
    cout<<"2";
    num=arg;
  }
  int getValue(){
    cout<<"3";
    return num;
  }
};
int main(){
  Integer i;
  i = 10;
  cout<<i.getValue();
}

keep central data structure+loop in cache

[[art of unix programming]] P290/291 advocates (presumably based on experience) to bend over backward and ensure the central data structure + time-critical loop NEVER fall out of cache.

I think this is vague but a useful sound byte to impress interviewers.

Developers need to know the size of L1 cache, L2 cache, L3 cache in our hardware. Then target the central data structure to one of them. Say L2 cache. We want to size our data structure to fit in there and never break the boundary.

An interesting illustration given on the same page — pre-computing of a data table was designed to save cpu time but could backfire if the increased data footprint leads to cache miss. Therefore it may be faster to recompute each time.

The same page also touches on loop-unrolling, designed to speed up execution, but may backfire due to increased code size breaking instruction cache.

semaphore: often !! ] thread library

lock and condVar are essential components of any thread library. Counting Semaphore is not.

  • In (C library) POSIX the semaphore functions do not start with pthread_ like locks and condVars are.
  • In (C library) SysV, the semaphore API is not part of any thread library whatsoever
  • In java, locks and condVars are integrated with every object, but Semaphore is a separate class
  • Windows is different

Important Note — both dotnet and java are a few abstraction levels higher than the thread or semaphore “libraries” provided on top of an operating system. These libraries [1]  are sometimes NOT part of kernel, even if the kernel provides basic thread support.

[1] ObjectSpace and RogueWave both provides thread libraries, not built into any operating system whatsoever.

binary semaphore^mutex #CSY

I usually trust official documentation by Microsoft, Oracle, Linux .. more than online forums, but I did find some worthwhile read in
https://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex . Multiple authors pointed out the notification feature of semaphore. I agree.

“Mutex can be released only by thread that had acquired it, while you can signal semaphore from any other thread (or process),” — This does NOT mean a non-owner thread can release a semaphore owned by another thread/process.

There are at least 4 different semaphore APIs
* java has Semaphore class
* dotnet has a Semaphore class based on Windows semaphore
* system-V semaphore API
* POSIX semaphore API

The windows (including dotnet) semaphore API is somewhat different from the rest. Notification feature is built into windows semaphore, but I don’t think the other 3 API documentations have any mentions of notification or signaling features.

I believe ownership is NOT the key point. By “ownership” the (Windows) semaphore discussions basically means “notification”. Non-owners of a semaphore can announce intention-to-acquire.

POSIX countingSemaphore ^ lock+condVar #Solaris docs

https://docs.oracle.com/cd/E19120-01/open.solaris/816-5137/sync-11157/index.html points out a lesser-known difference in the Solaris context:

Because semaphores need not be acquired and be released by the same thread, semaphores can be used for asynchronous event notification, such as in signal handlers. And, because semaphores contain state, semaphores can be used asynchronously without acquiring a mutex lock as is required by condition variables. However, semaphores are not as efficient as mutex locks.

The same page also shows POSIX countingSemaphore can be used IPC or between threads.

compare-up too much; too little compare-out

Comparison with “peers” is really hard to rationalize away.

Now my habit is 80% compare-up; and only 20% of the time we feel fortunate comparing to the wider population.

It’s better to become 20% compare-up.

Reason – Those up-comparisons are usually impractical, irrational and with wrong groups i.e. managers.

highest leverage: localSys^4beatFronts #short-term

Q: For the 2018 landscape, what t-investments promise the highest leverage and impact?

  1. delivery on projects
  2. local sys know-how
  3. portable GTD+zbs irrelevant for IV
  4. pure algo (no real coding) — probably has the highest leverage over the mid-term (like 1-5Y)
  5. QQ
  6. –LG2
  7. obscure QQ topics
  8. ECT+syntax — big room for improvement for timed IDE tests only
  9. Best practices — room for improvement for weekend IDE tests only

average O(): hashtable more imperfect than qsort

In these celebrated algorithms, we basically accept the average complexity as if they are very very likely in practice.

In comp science problems, hashtable’s usage and importance is about 10 times higher than qsort

  • I would say qsort is faster than many O(N logN) sorts. Qsort can use random pivot. It degrades only if extremely “lucky:)” like getting a 6 on every dice roll.
  • In contrast, hashtable performance depends mostly on programmer skill in designing the hash function, less on luck.

Performance compared to alternatives — qsort relative performance is usually as good as expected, but hashtable relative performance often falls short.

given unsorted ints, find median #O(N)

Classic problem — Q: Given an unsorted int array, find its median in O(N) time. For simplicity, we can first assume array size is odd.

I think we can use any data structure. We can scan the array multiple times.

—-simple partition algo

Pick a random item in the array as pivot value and partition the array. Let’s say we are unlucky and get 12% low vs 88% high. So we discard the 12% and repeat. Suppose then we get 66% vs 22% (within high section). We would then discard the 22%.

So we are likely to require 2N “visits”, I don’t think it would degrade to ((N logN).

—-fancy idea — weighted pivot

In one scan find the max and min. Calculate the mid value. Say this is 23.5, not even an integer. I will use this as a pivot value to partition the array into 2 segments.

Suppose N=101, so I’m looking for #51 item. Suppose left segment has 10 and right segment has 91, so I discard left segment. Now I’m looking for the #41 in the remaining array.

Now I find max and min again (if necessary). Now, Instead of getting the mid point between them, I will use a weighted pivot of (10*min+91*max)/101, so this pivot is shifted to the right, based on suspicion of a right-heavy histogram.

–complexity?

On average, I should get N+N/2+N/4 … <2N

Worst case? The earlier illustration is rather unlucky since that histogram happens to be right-heavy. In such a case, my “weighted pivot” idea should alleviate it.

[18]t-investment: c++now surpassing java

My learning journey has been more uphill in c++. Up to end of 2018, I probably have invested more effort in c++ than any language including java+swing.

I bought and read more c++ books than java+swing books.

If I include my 2Y in Chartered and 2Y in Macq, then my total c++ professional experience is comparable to java.

Q: why until recently I felt my GTD mileage was less than in java+swing?

  • A #1: c++ infrastructure is a /far cry/ from the clean-room java environment. More complicated compilation and more runtime problems.
  • A: I worked on mostly smaller systems… less familiar with the jargons and architecture patterns
  • A: not close to the heart of bigger c++ systems

Q: why until recently I didn’t feel as confident in c++ as java+swing?

  • A #1: interview experiences. About 30% of my c++ interviews were HFT. I always forgot I had technical wins at SIG and WorldQuant
  • A #2: GTD mileage, described above.

##tips: increase lazer@localSys #esp.SG

  • volunteer to take on more prod support, selectively.
  • accumulate some email threads and go through some relevant ones with a buddy once a week, but need to be strategic and get manager buy-in
  • reduce distraction — muscle-building. Tough but doable.
  • reduce distraction — FSM. Rationalize time spent on FSM, until I’m over the hump
  • reduce distraction — kids. Rationalize time spent on boy, since it didn’t work well. I think I can bring him out less often, since outing is way too costly in terms of my time.
  • camp out and focus on 1) project delivery 2) localSys
  • absorbency — when you are in the mood to learn local sys, increase your absorbency capacity with good food, exercise etc
  • sunshine — is needed on localSys tough effort. My son’s effort need the same sunshine

prefer ::at()over operator[]read`containers#UB

::at() throws exception … consistently 🙂

  • For (ordered or unordered) maps, I would prefer ::at() for reading, since operator[] silently inserts for lookup miss.
  • For vector, I would always favor vector::at() since operator[] has undefined behavior when index is beyond the end.
    1. worst outcome is getting trash without warning. I remember getting trash from an invalid STL iterator.
    2. better is consistent seg fault
    3. best is exception, since I can catch it

 

my “native”language=C #feel-good

See also post on CivilEngineers.

Context: speaking to interviewers, colleagues, I like to say my native programming language is … C

C is the first language I studied in-depth on my own, in 1994. C was also the first professional programming language in my very first job. I’m proud of my association with C because :

  • My dad is a specialist on 墨子. C is like 孔子. C never completely fell out of fashion for system programmers.
  • C is the most important language to Unix system programming (kernel, sockets, standard library…). As of 2019, system programing knowledge is growing progressively more important to my job interviews.
  • threading and data structure are among the top 5 most important and evergreen interview topics, both “born” in C.
    • Most thread implementations are related to system libraries.
    • all important data structures are low level and implemented in C more efficiently than other languages
  • In terms of depth — I think C, c++, java, c# have the most depth. I am slowly building my grasp of this depth. I think the accumulation is good.
  • In terms of of churn and accu — C is among the best. See [17] j^c++^c# churn/stability…
  • In terms of it’s relation to other languages — C is the #1 most important, as Confucius is in Chinese culture.
  • In terms of longevity — C is #1, the grand-daddy in the short history of programming languages. (C++ might come 2nd.) In contrast, all the popular languages will probably come and go — java, python, c#, javascript

exactly what I want{cod`drill beside immediate IV #Rahul

Hi XR,

I had a brief chat with my young, talented Indian colleague (not the talented intern). He pointed out that he is making progress with his Leetcode real-code drill better than 2 years ago in his Master’s program, because at that time he was in a (job-hunting) hurry and under real pressure. I can identify with him — at present, both he and I feel low or no pressure to improve coding skill so our brains work more efficiently. When I made this point he immediately agreed.

Over-stress inhibits brain capacity; Insufficient stress reduces energy level in the brain.

You asked me this question —

Q: so exactly what do you want from your coding drill? I won’t answer for my colleague, but my answer is related nevertheless.

Indeed if my goal was to pass coding interviews, then my real-code practice is not efficient and overkill. So why am I spending 20% to 33% of my coding drill effort on real-coding rather than reading key ideas… what’s the real reason?

I described a fundamental reason in
https://bintanvictor.wordpress.com/2018/08/04/why-our-coding-drills-are-different-fundamental-reason/ but today I will shift focus.

A1: I want enjoyment, positive feedback, self-esteem, feeling good,

A2: I want some sense of achievement

## portable skills like core c++j

I have found core java and core c++ outstanding domains for my personality. I feel there are not too many similar domains with

  1. feature: highly portable, standardized knowledge
  2. feature: requires more than such (simple) knowledge that anyone can pick up in a crash course
  3. feature: low churn high stability

… so we can hope to accumulate. Here are some comparable domains:

  • pure algo 🙂 yes standardized, non-trivial questions. I can accumulate. Better than brain teasers
  • socket and sys programming:) Yes standardized questions, including malloc, sharedMem
  • SQL 🙂 good despite shrinking demand.
    • Can we say the same about ANSI-C? Well, lots of c++ questions are C.
  • bond math 🙂 not so deep but good
  • python 😦 Deep questions are rare and non-standardized, like concurrency, meta-programming..
  • quant-dev domain 😦 questions are standard, but too few jobs
  • algo trading 😦 i don’t think they ask any standard question

longest substring+!repeating chars #untested

Q(leetcode Q3): Given a string, find the longest substring without repeating characters.

–Sol1 O(N):
keep a never-shrinking sliding window + a “hashmap” of chars in it. Actually the HM is a 26-element integer array of frequencies.

Every time the lagging edge of the windows moves by one, by definition one char drops out, so we remove that char from the HM, by decrementing its frequency. If hitting 0 then we also decrement a global var uniqCnt describing the HM.

IFF uniqCnt == windowSz then window is a clean.

Every time we see a clean window and it’s longer than the longest clean window, we update our record.

##Y c++IV improved much faster]U.S.than SG #insight{SCB breakthru

Hi XR,

I received 9 c++ offers since Mar 2017, mostly from U.S. In contrast, over the 4.5 years I spent in Singapore, I received only 3 c++ offers including a 90% offer from HFT firm WorldQuant (c++ job but not hardcore).

  1. Reason: buy-side employers — too picky. Most of the Singapore c++ jobs I tried are buy-side jobs. Many of the teams are not seriously hiring and only wanted rock stars.
    • In contrast, Since 2010 I tried about 6 Singapore ibank c++ jobs (Citi, Barclays, Macquarie, Standard Chartered Bank) and had much better technical wins than at buy-side interviews.
  2. Reason: Much fewer c++ jobs than in U.S.
  3. Reason: employee — I was always an employee while in Singapore and dare not attend frequent interviews.
  4. Reason: my c++ job in the U.S. are more mainstream so I had more opportunities to experiment on mainstream c++ interview topics. Experiments built up my confidence and depth.
  5. Reason: I had much more personal time to study and practice coding. This factor alone is not decisive. Without the real interviews, I would mostly waste my personal time.

Conclusion — availability of reasonable interview opportunities is a surprisingly oversize factor for my visible progress, 

By the way, Henry Wu (whom I told you about) had more successful c++ interviews. He joined WorldQuant and Bloomberg, two companies who didn’t take me up even after my technical wins.

key parts@move-semantics implementation: helicopter/historical view

Move semantics is 90% compile-time + 10% run-time programming. 95% in-the-fabric and invisible to us.

  • 90% TMP
    • 70% is about special casts — in the form of std::move and std::forward
    • std::swap
  • 10% traditional programming
    • RAII to destroy the “robbed” rvalue object
    • heap ptr assignment [1] to rob the resource

[1] This “stealing” is tip of the iceberg, the most visible part of move semantics. Bare-hand stealing was doable in c++03, but too dangerous. The rvr is a fundamental language feature to make the “steal” safer:

  • a safety device around the dangerous “steal”
  • a safety glove
  • a controlled destruction

The resource is typically a heapy thingy, common fixture in all STL containers and+ std::string + smart pointers. Therefore, move-semantics is widely used only in libraries, not in applications.

IV Q: can U implement op= using copier #swap+RAII

A 2010 interviewer asked

Q: do you know any technique to implement the assignment operator using an existing copy ctor?
A: Yes. See P100 [[c++codingStd]] There are multiple learning points:

  • RAII works with a class owning some heap resource.
  • RAII works with a local stack object owning a heapy thingy
  • RAII provides a much-needed exception safety. For the exception guarantee to hold, std::swap and operator delete should never throw, as echoed in my books.
  • I used to think only half the swap (i.e. transfer-in) is needed. Now I know the transfer-out on the old resource is more important. It guarantees the old resource is released even-if hitting exceptions, thanks to RAII.
  • The std::swap() trick needed here is powerful because there’s a heap pointer field. Without this field, I don’t think std::swap will be relevant.
  • self-assignment check — not required as it is rare and tolerable
  • Efficiency — considered highly efficient. The same swap-based op= is used extensively in the standard library.
  • idiomatic — this implementation of operator= for a resource-owning class is considered idiomatic, due to simplicity, safety and efficiency
C & operator=(C const & rhs){
  C localCopy(rhs); //not needed for move-assignment
  std::swap(rhs.heapResource, this->heapResource);
  return *this;
}
C & operator=(C const && rhs){ //move-assignment
  std::swap(rhs.heapResource, this->heapResource);
  return *this;
}

relocate q[#include] to implementation file: j4

If possible, I would move a #include from MyClass header to MyClass implementation.

This would reduce size of the MyClass header, and speeds up system recompile if it is included by many classes. The pimpl idiom and forward-declaration use similar techniques to speed up recompile.

However, in most cases, it’s easier to put all #include in MyClass header.

## most strategic TSN among%%abandoned

Q: name the most strategic trySomethingNew domains that I have since abandoned.

Don’t spend too much time, even though this is a decent question — the answers are nothing new.

  1. — ranked by surprise
  2. web dev for dotcom
  3. Unix sys admin and DBA
  4. algo trading? actually very few roles spread across a number of firms
  5. distributed cache like Coherence and Gemfire
  6. perl, SQL, Unix/Linux system knowledge? No longer a top 10 focus
  7. real time risk as in GS and Athena
  8. drv pricing quant
  9. c#
  • python? Not yet abandoned

dlopen^LoadLibrary # plugin

Windows doesn’t have the dlopen API, but many techniques are similar on Windows LoadLibrary API.

https://en.wikipedia.org/wiki/Dynamic_loading#In_C/C++

  • UNIX-like operating systems such as macOS, Linux … uses dlopen(), dlsym() etc
  • Windows uses LoadLibrary() and GetProcAddress() etc

I was never asked about this in interviews, and never needed this feature. Useful knowledge for a c++ veteran though.

Machine Learning #notes

Machine Learning — can be thought of as a method of data analysis, but a method that can automate analytical model building. As such, this method can find hidden insights unknown to the data scientist. I think the AlphaGo Zero is an example .. https://en.wikipedia.org/wiki/AlphaGo_Zero

Training artificial intelligence without datasets derived from human experts is… valuable in practice because expert data is “often expensive, unreliable or simply unavailable.”

AlphaGo Zero’s neural network was trained using TensorFlow. The robot engaged in reinforcement learning, playing against itself until it could anticipate its own moves and how those moves would affect the game’s outcome

So the robot’s training is by playing against itself, not studying past games by other players.

The robot discovered many playing strategies that human players never thought of. In the first three days AlphaGo Zero played 4.9 million games against itself and learned more strategies than any human can.

In the game of GO, world’s strongest players are no longer humans. Strongest players are all robots. The strongest strategies humans have developed are easily beaten by these robots. Human players can watch these top (robot) players fight against each other, and try to understand why their strategies work.

placement new: pearls to impress IV

  • #1 usage — needed in vector::push_back(). See [[c++cookbook]] and my SIG coding test in github
  • #2 usage — if you need to call MyClass ctor after malloc()
  • #3 usage — custom allocators
  • — more advanced
  • Explicit call of dtor — is not placement-delete but is related to placement-new. See https://isocpp.org/wiki/faq/dtors#placement-new
  • — even more advanced
  • placement-delete — is an internal mechanism (invisible) to ensure that placement-new failure doesn’t leak memory. See https://en.wikipedia.org/wiki/Placement_syntax#Placement_delete

container{string}: j^cpp

In java, any container (of string or int or anything) holds pointers only.

I think c# collections (i.e. containers) contain pointers if T is a reference type.

In cpp,

  • container of int always contains nonref, unlike java
  • container of container contains ptr, just like in java
  • but container of string is widely used, and invariably contains nonref std::string !

Q: is there any justification for container<(smart) ptr to string>? I found rather few online discussions.
A: See boost::ptr_container

Q: what if the strings are very large?
A: many std::string implementations use COW to speed up copying + assignment, however, string copy ctor has O(lengthOfString) per in the standard ! So in a standard-compliant implementation copy and assignment would be expensive, so I believe we must use container<(smart) ptr to string>

 

##advanced python topics #!! IV

I read a few books and sites listing “advanced python” topics, but they don’t agree on what features are important.

Anyone can list 20 (or 100) obscure and non-trivial python features and call it “list of advanced python features

  • Mixin/AbstractBaseClass, related to Protocols
  • Protocol, as an informally defined Interface
  • coroutines?
  • Futures for async? python3.2 😦
  • Properties? Similar to c# properties; provides better encapsulation than __myField3
  • q[yield] keyword

ECN domain knowledge IV questions, by an MD interviewer

  • Q: what kind of data are stored in your orderbook?
  • Q: what kind of data fields are sent by the matching engine in the order messages?
  • Q3: In an NYSE orderbook, typically do you see smaller or bigger order quantities at the next level below top of book?
  • Q3b: Suppose you, as a dealer on a private ECN, maintains a best offer and the 2nd best offer for IBM (or gold or whatever). Which of the two offer quantities would you make bigger and why?
  • Q: your server hardware capacity?
  • Q: how many threads in your parser process?
  • Q: name a few resiliency features in your parser
  • Q: what happens when a parser process is down?
  • Q: why do you consider Line A + Line B a resilience feature if the same thread consumes both? The entire parser can crash, right?
  • %%A3b: 2nd best. The average execution price would be better when some market-taker /lifts both offers/. When we put out our inventory at a discount we don’t want to give too much — we say first 100 customers only.
  • A3b: 2nd best. risk minimization… easier to hedge the ensuing exposure created when some market-taker /lifts both offers/.

 

##5 understandable-yet-useful type traits for TMP

type_traits.h defines too many constructs but only a few are easy to understand and unambiguous:

  1. enable_if
  2. is_same
  3. conditional — https://en.cppreference.com/w/cpp/types/conditional. Not necessarily widely used but my favorite
  4. is_base_of — https://en.cppreference.com/w/cpp/types/is_base_of
  5. is_polymorphic — https://en.cppreference.com/w/cpp/types/is_polymorphic about virtual function
  6. — not so understandable
  7. is_pointer — ambiguous. I think it only knows about regular ptr and function ptr
  8. is_class and is_scalar — possibly useful to check T is a class vs a “simple” type
  9. — understandable but not so valuable
  10. is_abstract — having pure virtual function
  11. — neither very understandable nor highly valuable

I guess all of these type traits are class templates. The way to access the result is the (boolean) ::value member typedef usually, though enable_if_t evaluates to a type.

c++TMP: 9 fundamental features + little tricks

ranked:

  1. SFINAE — fundamental compiler rule for overload resolution
  2. template specialization
  3. NDTTP — non-type template param, widely used, probably most of the standard TMP
  4. within a class template, define member function templates or nested class templates, with additional dummy types, probably required by SFINAE
  5. Even if an actual type (eg, Trade) behind a dummy type T doesn’t support an operation in vector<T>, compiler can still instantiate vector<Trade> if you don’t use that operation. [[c++Primer]] P329 has examples.
  6. default arguments — for type-param (or non-type-param), a small syntactical feature with BIG usages

Tricks:

  1. #include <type_traits>
  2. member typedefs — a regular class can define member typedefs. but this trick is used much more in class templates

enable_if{bool,T=void} #sfinae,static_assert

  • enable_if is a TMP technique that hides a function overload (or template specialization) — convenient way to leverage SFINAE to conditionally remove functions from overload resolution based on type traits and to provide separate function overloads for different type traits. [3]
    • I think static_assert doesn’t do the job.
  • typically used with std::is_* compile-time type checks provided in type_traits.h
  • There are hundreds of references to it in the C++11 standard template library [1]
  • type traits — often combined with enable_if [1]
  • sfinae — is closely related to enable_if [1]
  • by default (common usage), the enable_if_t evaluates to void if “enabled”. I have a github experiment specifically on enable_if_t. If you use enable_if_t as return type you had better put a q(*) after it!
  • static_assert — is not necessary for it but can be used for compile-time type validation. Note static_assert is unrelated to sfinae. https://stackoverflow.com/questions/16302977/static-assertions-and-sfinae explains that
    • sfinae checks declarations of overloads. sfinae = Substitution failure is not a (compiler) error
    • static assert is always in definitions, not declarations. static asserts generate compiler errors.
    • ! Aha moment on SFINAE !

[1] https://eli.thegreenplace.net/2014/sfinae-and-enable_if/

[2] https://stackoverflow.com/questions/30556176/template-detects-if-t-is-pointer-or-class

[3] https://en.cppreference.com/w/cpp/types/enable_if

[12] closure in java^c#

I feel c# Action<T1, T2 ..> and Func<T1,….> constructs are a good illustration of closure. The code block has access to local variables in the enclosing block. Static/non-static Fields are accessible too.

I feel the c# syntax is much simpler than java. http://stackoverflow.com/questions/5443510/closure-in-java-7  said “Since Java 1.1, anonymous inner class have provided this facility in a highly verbose manner. they also have a restriction of only being able to access final (and definitely assigned) variables.”

A practical scenario — When I extract common code into a static (sometimes non-static) utility function, I often end up passing in billions of local variables. It often pays to refactor the function into a closures. (More verbose in java but technically doable.) With closures you don’t need to pass those variables as they are implicitly passed into the closure (or needs no passing at all).

Obviously, if the common code is complicated (above 10 lines) the closure would look bulky. Solution?  Keep the static utility function as is when you refactor, and have the closure call it. Suppose the static function compute() takes 5 local variable arguments. Closure can be invoked with none but closure will invoke compute() with the 5 local variables “implicitly passed in”.

t-investment: QQ^coding^localSys

My investment in QQ category is more adequate than my investment in

  • coding drill
  • local sys knowledge

All 3 are important to family well-being, sense of security, progress, self-esteem..

However, localSys learning is obviously non-portable. Still at the current juncture localSys is the most important area lacking “sunshine”

## template type constraint+validation @compile time

  1. –Here are the compile-time validation/checks offered by c++:
  2. std::is_pointer and family — each function checks one type of pointer. Very specific and clean
  3. q[ = delete ]  — to eliminate specific concrete type args. Laser removal .. extremely clean. Scott Meyers pointed out this usage of =delete. Does this work with SFINAE ???????
  4. std::enable_if() — see separate blog post
  5. sfinae — probably the most versatile, flexible and powerful
  6. static_assert? Can be combined with other techniques to implement compile-time validation and constraints. See https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/SFINAE_ptrCheck.cpp

covariant return type: java=cpp

java “override” rule permits covariant return — a overriding function to return a type D that’s subtype of B which is the original return type of the overridden method.

— ditto c++

https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Covariant_Return_Types. Most common usage is a clone method that

  • returns ptr to Derived, in the Derived class
  • returns ptr to Base in the Base class

Covariant return types work with with multiple inheritance and with protected and private inheritance — these simply affect the access levels of the relevant functions.

I was wrong to say virtual mechanism requires exact match on return type.

python Protocols #phrasebook

  • interface — similar to java Interface
  • unenforced — unlike java Interface, python compiler doesn’t enforce anything about protocols
  • eg: ContextManager protocol defines __enter__() and __exit__() methods
  • eg: Sequence protocol defines __len__() and __getitem__() methods
  • partial — you can partially implement the required functions of a protocol
    • eg: your class can implement just the __getitem__() and still works as a Sequence

c++ lockfree data types: mostly bool/int/pointer

  • In generally, only atomic bool/int/pointer can be lock-free. Bigger types need special implementation techniques and I have read that lock-free is usually not possible.
  • Atomic flags are lock-free (this is the only type guaranteed to be lock-free on all library implementations)

numpy,scipy,pandas #cheatsheet

  • numpy provides efficient and large matrices
    • also linear algebra
  • scipy extends numpy
  • scipy compete against matlab and provides
    • mathematical optimizations including optimize.curve_fit()
    • stats
    • numerical integration
    • spline smoothing
  • pandas extends numpy
  • pandas provides key data structures like
    • time series
    • dataFrame i.e. spreadsheet

concurrent python..#my take

I’m biased against multi-threading towards multiprocessing because …

  1. threading is for high-performance, but java/c++ leaves python in the dust
  2. GIL in CPython, which is the default download version of python. The standard doc says “If you want your application to make better use of the computational resources of multi-core machines, you are advised to use multiprocessing

(For my academic curiosity ….) Python thread library offers common bells and whistles:

  • join()
  • timers
  • condVar
  • lock
  • counting semaphore
  • barrier
  • concurrent queue
  • isDaemon()
  • Futures? python3.2 😦

 

[19] self-review: competitive strengths

In my 30’s I would look at the managers sitting in their private offices, and tell myself “I’m not a manager type. I’m the technical type”. However, I have always failed to rise above the rest and reach tech leadership, like senior architect or tech fellow.

Eventually I concluded my strength was limited to theoretical interview topics in java and math.

After spending 2 years self-learning and 3 years in UChicago on quant, I still feel stronger in math than my fellow developers, but math is becoming less and less important to most developer jobs. I can’t afford to invest more time in math (like CSDoctor does), because jobs are scarce.

Now finally I can add “c++” after “java” in my profile.

Pure algorithm (without real-coding test) was my traditional strength, but now I know the west coast and HFT standard. I think it’s still my strength by ibank standard.

I was seldom very strong in GetThingsDone, but ironically the GTD guys seldom rise up. GTD productivity is a necessary but insufficient condition for promotion.

I created a shared_ptr with a local object address..

In my trade busting project, I once created a local object, and used its address to construct a shared_ptr (under an alias like TradePtr).

I hit consistent crashes. I think the reason is — shared_ptr likes heap objects. When my function returns, the shared_ptr tried to call delete on the raw ptr, which points at the local stack, leading to crash.

The proven solution — make_shared()

subclass ctor/dtor using virtual func: java^c++

See https://stackoverflow.com/questions/13440375/invoking-virtual-method-in-constructor-difference-between-java-and-c

Suppose both superclass and subclass defines a virtual cleanup() method.

— c++

… you lose the virtual i.e. “dynamic dispatch” feature. The subclass instance is not present so the only the base class implementation of cleanup() could run.

–java: let’s focus on ctor

… the subclass implementation of cleanup() would run, even though the subclass instance is not initialized — dangerous! See P70 [[elements of java style]]

std::weak_ptr phrasebook

ALWAYS need to compare with raw ptr and shared_ptr, to understand the usage context, motivations and justifications

Based on the chapter in [[effModernC++]]

#1 feature — detect dangle

  • use case — a subject that keeps track of its observers who might become dangling pointers
  • use case — objects A and B pointing to each other with ref count … leading to island. Raw ptr won’t work since dangle becomes undetectable.
  • Achilles’ heel of the #1 feature — manual “delete” on the raw ptr is beneath the radar of reference counting, and leads to chaos and subversion of ownership control, as illustrated —
#include <iostream>
#include <memory>
using namespace std;

void f1(){
  auto p = new int(55);
  shared_ptr<int> sp(p);
  weak_ptr<int> wp(sp);

  cout<<"expired()? "<<wp.expired()<<endl; // false
  cout<<"deleting from down below\n";
  delete p; // sp.reset();
  cout<<"expired()? "<<wp.expired()<<endl; // still false!
  // at end of this function, shared_ptr would double-delete as the manual delete 
// is beneath the radar of reference counting:(
}
int main(){
  f1();
}

##[18] y dotnet hasn’t caught on #enterprise-focus

Don’t spend too much time about this unless considering to take up c#.

In 2012/13 I invested my time into c# just in case c# would become more widespread and high-paying. However, after 2013, I have not noticed this trend strengthening. If I have to guess why, here some personal glimpses:

  • web-GUI — Rise of alternative user interfaces such as mobiles and javascript-based web UI, etching away the strongest stronghold of C#. Nowadays, which new build chooses a fat client built in swing, javaFX, winforms, WPF or Silverlight? Fewer and fewer, to my surprise.
  • Linux — Maturity and further performance improvement of Linux machines compared to windows machines. For large server side apps, or cloud apps, I see more and more adoption of Linux.
  • Java@server-side — (in financial sector) Strengthening of java as the technology of choice on the server side. c# made a valiant but unsuccessful attempt to dethrone java in this game. Java may have limitations (do we know any?), but somehow the decision makers are not worried about them.
  • Open source — there’s continuing community effort to improve the java ecosystem (+ python, javascript, c++ ecosystems). C# is losing out IMO.
  • C++@windows — (My personal speculation) I feel c# offers higher performance than java on windows machines, but vc++ is even faster.

Among ibanks, the main reasons for the current c# situation are 1) Linux 2) web-GUI

— Some update based on Wallace chat.

I think 1) microsoft stack, 2) jvm stack and 3) web 2.0 stack all have vast ecosystems, but at enterprise level, only microsoft^jvm

How about server side c++ or python? much smaller mind-share.

Wallace said on Wall St (where he worked for 5+ years) he knows no ibank using c# on the back-end. Wallace believed Unix/Linux is the main reason.

How about outside ibanks? Wallace said c# back-end is not so rare.

##all c++ explicit casts #std::move

  • — implicit casts
  • cvctor — is the most important implicit cast
  • conversion operator member-functions
  • numerical type conversions specified by C standard
  • — C:
  • parentheses cast
  • — C++03 added four casts
  • dynamic_cast — usable on references and pointers.
  • const_cast
  • reinterpret_cast — usually on pointers
  • static_cast
  • — c++11
  • std::move() — only for references, not pointers
  • std::forward()
  • numerous type conversions in type_traits.h
  • — boost:
  • boost::polymorphic_cast? is similar to dynamic_cast but much less popular and not essential knowledge expected of a c++ veteran

 

enable_shared_from_this #CRTP

  • std::enable_shared_from_this is a base class template
  • shared_from_this() is the member function provided
  • CRTP is needed when you derive from this base class.
  • underlying problem (target of this solution) — two separate “clubs” centered around the same raw ptr. Each club thinks it owns the raw ptr and would destroy it independently.
  • usage example —
    • your host class is already managed via a shared_ptr
    • your instance method need to create shared_ptr objects from “this”
    • Note if you only need to access “this” you won’t need the complexity here.

both base classes”export”conflicting typedef #MI

Consider class Der: public A, public B{};

If both A and B defines a typedef for Ptr, then C::Ptr will cause ambiguity error and compiler error will explicit list the A::Ptr and B::Ptr as “candidates”!

Solution — inside Der, declare

typedef B::Ptr Ptr; //to exclude the A::Ptr typedef
// This solution works even if B is a CRTP base class like

class Der: public A, public B<Der, P, Q>{
  typedef B<Der,P,Q>::Ptr Ptr; 
};

Q: passive income ⇒ reduce GTD pressure#positive stress

My (growing) Passive income does reduce cash flow pressure… but it has no effect so far on my work GTD pressure.

Q: Anything more effective more practical?

  1. take more frequent unpaid leaves, to exercise, blog or visit family
  2. expensive gym membership

How about a lower salary job (key: low caliber team)? No I still want some challenge some engagement, some uphill, some positive stress.

const vector{string} won’t let you modify strings

Point #1: a const vector only gives out const references. In this case, reference to const string objects.

My friend ChengShi said he has never seen const vector<const string>, because const vector<string> is good.

Point #2: In fact, my experiment of q[vector<const string>] can’t compile. Why?

https://stackoverflow.com/questions/17313062/vector-of-const-objects-giving-compile-error explains that in vector<T>, T must be assignable!

## y they ask QQ questions #revisit

Remember QQ means ‘tough topics not needed for GTD’. A QQ quiz (to some extent, algo quiz too)

  • measures your diligence, amount of learning effort you put in beyond your work projects.
  • measures your dedication and commitment to self-learning a dry, tough topic. Learning is not only a drudgery, but also a major challenge on a typical job. 90% of the day-to-day challenges involve learning, re-learning, connecting the dots..
  • checks for a self-starter vs a passive learner
  • measures your self-reliance at learning
  • measures how detail-oriented a candidate is
  • checks for intellectually laziness
  • measures soundness of fundamental concepts underlying your logical “framework”. In many large financial systems there are fundamental design principles and concepts that are .. fairly logical and consistent. Yang was good at grasping the logical, and questioning the illogical.
  • measures depth of curiosity and learning
  • measures technical communication bandwidth with another developer

rvr^rvalue-object, again

  • ALL objects by definition exist in runtime memory but references may not.
  • std::move() is about rvr variables not rvalue objects!
  • I now believe rvr is a compiler concept. Underlying is just an temporary address.
    • Further, the traditional lvr is probabably a compiler concept too. Underlying is a regular pointer variable.

rvalue object is an object that can ONLY appear on the RHS of assignment. A rather vague explanation!

rvalue object can be naturally occurring (usually anonymous), or “converted from a named object” by std::move(), but if some variable still references the object, then the object is actually not a rvalue object.

The SCB architect pointed that “some variable” can be a const ref bound to a naturally occurring rvalue! To my surprise the c++ syntax rule says the object is still a temp object i.e. rvalue object, so you can’t assign it to a lvr !

1)template code bloat 2)inline..hurt i-cache@@

Q: does template code bloat increase instruction cache pressure and increase risk of cache thrashing?
A: i have seen about 8 forums mention of template code bloat increasing i-cache pressure, but no clear evidence, no consensus among authorities. In fact, no known authority has confirmed this issue.

However, I would think having many similar functions in the executable will likely lead to unnecessary competition for i-cache.

In contrast, for inlining there is consensus. wikipedia states — excess inlining will hurt speed, due to inlined code consuming too much of the instruction cache .. Inlining imposes a cost on performance, due to the code expansion (due to duplication) hurting instruction cache performance.[5] This is most significant if, prior to expansion, the working set of the program (or a hot section of code) fit in one level of the memory hierarchy (e.g., L1 cache), but after expansion it no longer fits, resulting in frequent cache misses at that level.

See also inline: footprint+perf can Backfire ! #Google

unique_ptr implicit copy : only for rvr #auto_ptr

P 470-471 [[c++primer]] made it clear that

  • on a regular unique_ptr variable, explicit copy is a compilation error. Different from auto_ptr here.
  • However returning an unnamed temp unique_ptr (rvalue object) from a function is a standard idiom.
    • Factory returning a unique_ptr by value is the most standard idiom.
    • This is actually the scenario in my SCB-FM interview by the team architect

Underlying reason is what I have known for a long time — move-only. What I didn’t know (well enough to impress interviewer) — the implication for implicit copy. Implicit copy is the most common usage of unique_ptr.

max all-black submatrix O(LN)#ZR

Same problem as https://leetcode.com/problems/maximal-rectangle/description/

Q: Given a 2D binary matrix (L by N) filled with white(0) and black(1) cells, find the largest all-black rectangle. See raiserchu’s mail on 12 Sep 13. There is a clever DP solution, probably O(LN).

—Analysis:

Worst case — A standard chess board? We can’t do better than O(LN) since there are LN cells to read.

— sol5:

First scan O(LN) to record, in each cell {bar height; horizontalBarStart/End}.

— sol4 unfinished

Scan #1 O(LN): build a shadow matrix “histogram” where each integer in the cell is the height (possibly 0) of the bar anchored therein.

Scan #2 O(LN) for each cell, remember the currentRunStart column index i.e. from that column until current column, we have an all-black box of height == current bar height

— sol3 O(LNS) new idea based on max rectangle ] histogram treat top 2 (denote J:=2) rows as a histogram. Find the max rectangle therein. Then J:=3 …

  • Scan #1 O(LN): build a shadow matrix “histogram” where each integer in the cell is the height (possibly 0) of the bar anchored therein. In other words, if a cell value=5 then there are exactly 4 consecutive black cells above this (black) cell. Build it incrementally, level by level, top to bottom.
  • Scan #2a: for each row in the shadow matrix, we run the proven algo in O(NS), Note there’s no help from previous row:(
    • S:= #unique heights, N:= matrix width 
  • Scan #2 := the entire scan of L rows. so worst case we hit O(LNS)

Q: Can we do better by reducing scan #2a complexity to O(N), by making use of the previous row results?

— My brute force solution 1: Each rectangle is identified by 2 vertices, i.e 4 integers. Without loss of generality, We require the “high” corner to have higher x-coordinate and higher y-coordinate than the “low” corner. (We can assume y-axis run upward.) With this O(N^4) nested loop we can iterate over all possible rectangles:

Lock low corner
Move high corner in typewriter (zigzag) steps i.e.
  hold highY and move highX step by step
  process the (series of) resulting rectangles
  increment highY and repeat
Move the lower corner in typewriter steps and repeat

Key observation: any “bad pixel” disqualifies every rectangle containing it.

— Here’s my partial solution:
We can effectively ignore all the “good pixels”.

1) Look at the x coordinates of all bad pixels. Sort them into an array. Find the largest gap. Suppose it’s between x=22 and x=33. Our candidate rectangle extends horizontally from 23 to 32, exactly. Notice there’s no bad pixel within this vertical band [1].
2) Look at the y coordinates of all bad pixels. Sort them into an array. Find the largest gap. Suppose it’s between y=15 and y=18. Our candidate rectangle extends vertically from 16 to 17, exactly.
[1] This candidate rectangle can expand All the way vertically, though it may give a bigger rectangle
Ditto horizontally.

SCB-FM algo Q2a 2 slists

Q: Given two well-formed singly-linked lists (loop-free), that might be merged at some node, locate the merge point. If not merged, return null.

Note every node has exactly one child node, but may have two parent nodes.

====analysis====

Suppose list A has size P=55 and list B has size Q=32

–SolH: hashtable O(N+M) — optimal

–SolR: reverse one list … how?

–SolA: array-based.  construct a simple 55-array of A node pointers, and another 32-array of B node pointers. Then compare the last array elements, then binary search in B. O(N+M) + O(log M), actually faster than O(N+M) + O(M).

–Sol2: 2 iterators, read-only lists.

first scan to find the 2 end nodes and remember the sizes like 55 vs 32.

IFF the end nodes match, then 2nd scan:

skip first P-Q (23) nodes in the longer list and then increment 2 iterators. Compare the 2 iterators at each step.

SCB-FM algo Q2b stack-based queue

Q: given a hardware-based stack API consisting of 3 functions {pop/push/isEmpty}, please implement a queue api consisting of 3 functions {enqueue/dequeue/isEmpty}

https://leetcode.com/problems/implement-queue-using-stacks/description/ is similar

====analysis====

service dequeue from a hidden stack.

When hidden stack is empty, pop all nodes from visible stack to hidden stack

isEmpty() must add up two sizes.

SCB-FM IV by architect #shared_ptr upcast

Q: how does the compiler accept this code:
shared_ptr<C> aa = myDerSharedPtr; //myDerSharedPtr is a shared_ptr<D> object

%%Q: shared_ptr<C> has a copy ctor and also a conversion ctor accepting a C raw ptr, but here we are passing in a shared_ptr<D> instance. How does compiler handle it?
%%A: I guess shared_ptr<D> has a conversion operator returning a D raw ptr, but this is not used.
AA: there’s a conversion ctor template<class U> shared_ptr(shared_ptr<U>…) — a TMP trick. See https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/shPtrUpcastCopy.cpp .

The github experiment also reveals — If a function lvr param is shared_ptr<C> & and you pass in a shared_ptr<D>, compiler will complain about assigning an rvalue (i.e. anonymous temp) object to an lvalue reference — a key insight into rvr + rvalue objects.

Q3: just when is the memory freed for temp objects like q[ string1 + string2 ]
%%A: at an unspecified time. A custom string implementation could use COW, in a single-threaded project. This is a common practice in many pre-c++11 libraries
A(from architect): after the semicolon

Q3b: how can you extend the lifetime of those naturally occurring temp object?
A: assign the temp to a “const ref” variable.

Q: what are your favorite c++11/14 features? See ## c++11 features I understand as significant

Q: OK you briefly mentioned move semantic..what is it?

struct C{ //tested
  virtual void f(){/*..*/}
  ~C(){     cout<<"C dtor\n";  } //non-virtual
};
struct D: public C{
  string s;
  D(): s("def"){}
  ~D(){     cout<<"D dtor\n";  }
};
D createD(){return D();} //return by value! probably via RVO
int main(){
  C const & trade = createD();
}

Q: is string memory freed?
%%A: yes. Verified

Q: what if the string field is in D?
%%A: yes. Verified

I believe the temp D object is on stack and is guaranteed to be destructed. Since the D ctor called base ctor, the dtor sequence is guaranteed to be ~D then ~C.

kernel threads ] linux^Unix

Here are a few things I can recall

  • process 0 (swapper) is a kernel thread. This process gets scheduled when there’s no other process to run
  • peroces 1 (init) is a kernel thread. This process launches and monitors all other processes except process 0. It’s also the adopted parents of all orphaned zombies
  • both of them run forever. Most other linux kernel threads run for a short while and exit.
  • linux kernel threads are fundamentally different from Unix kernel threads, aka “native threads”. The “native thread” concept was first known to me in jvm.  kernel scheduler can see native threads but not java green threads.
  • native threads often run user mode but linux kernel threads only run in kernel mode and very limited in usage. I think they are mostly set up to access hardware

your brain power^brain power invested ] localSys

Background – “how fast you figure things out relative to your peers”.

For each team member AA, the struggle is the same — AA’s brain power vs the cumulative brain power that has gone into the local system which measures the complexity. If the local system complexity is too high then AA would struggle and take a long time (before he gives up).

The “local system” could include firmwide frameworks, or something open-source.

I prefer a local system created by low site-specific brain power, like one with standard SQL/stored-procs, standard noSQL, standard data encoding (FIX, Json..), standard java/c++ libraries, including OSS.

  • RTS and OC – relatively small amount of site-specific brain power in the system.
  • PWM comm – actually small amount of local system complexity but time given is too short
  • Barc – brand new codebase .. low site-specific brain power.
  • Quartz — the worst

merge 2 sorted slists #2try

Q: Merge two sorted linked lists and return it as a new (ascending) list. The new list should be made by splicing together the nodes of the first two lists.

====analysis
A test of implementation skill. A test of clear communication and clear thinking. My solution below is O(1) space and O(N) time without allocating any heap memory.

I would pick the list having the lowest value as the Yellow jersey (leading). The other list is the green. At any time there exist two head nodes for two slists.

I always keep a brown pointer to the last of the leading pack in the yellow’s list. The leading pack are the “retired” nodes.

Swap – In the event of a ‘swap’, the brown’s current child (current yellow jersey list head) gets detached and becomes the new green jersey, and the old green jersey moves into the leading pack. Then we increment the ptr — this old green jersey’s child becomes the yellow jersey.

Every time after we increment the pointer, we compare its child node vs the green jersey.

I won’t bother with std::list::splice() and will use python or my own c++ linked list.

LFU cache #cf.LRU #untested

Q LFU (Least-Frequently-Used) cache to support the following operations: get and put in O(1)
* get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
* put(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

====Analysis

  1. dstruc — centry i.e. CacheEntry node {key, value, hitCount, lastHit (timestamp), pointers to prev/next centries, (optional)ptr to host LinkNode}, to be used in an inner link list.
    • invariant: hitCount can only increase
  2. dstruct — inner list of centry nodes
    • invariant: list always sorted by lastHit. We can remove any intermediate node, but incoming node is always added to the Tail
  3. dstruct — fixed-sized (rehash-free) hashtable {key -> ptr to centry}
  4. dstruct — LinkNode {level, inner list-of-centry, prev/next pointers } where all centry objects share the same hitCount denoted “level”.
  5. dstruct — outer list of LinkNodes, always sorted by level

“bubble-up” operation — Whenever a centry gets a cache-hit, its hitCount increments. It immediately and unconditionally bubbles up to the LinkNode one level higher (to be created in O(1) if necessary) ((
* [o1] query the hashtable and follow ptr to remove the centry from old linkNode
* [o1] append the centry to new linkNode, at Tail of inner list. The new LinkNode could be non-existent but Never empty!
* [o1] optionally, new host linkNode’s address is saved in the centry;
))

  • Get() hit — relatively easy. Update the hitCount and bubble up
  • Get() miss — trivial
  • Put() Update — similar to get-hit
  • Insertion (possibly after deletion) — [o1] append to Tail of the Level-1 LinkNode (to be created if necessary) and add to hashtable
  • Deletion — always from list to hashtable, never the converse
    • [o1] identify lowest level in existence, then delete the head (i.e. eviction target) of inner list
    • when a linkNode becomes empty, it must disappear from the outer list, to prevent build-up of consecutive empty LinkNodes leading to linear search for eviction target. Imagine aaaaa bbbbb c[Now need to evict an “a”]. Therefore, array of LinkNode is unacceptable.

localSys learning: get over the hump

  • eg: nyse xtap
  • eg: OC Quest ownership handover
  • eg: Same with my son’s piano … Same with my son’s math problem solving ..

Once I get over the hump … relief ! and then I tend to keep going for a few hours and gain more local system insight.

There are various signs of the hump…. It’s nice to notice “Hey, we might be at the hump”, so we could turn on “supportive self-coach”

  • block out distractions/interruptions … put on earphone
  • ask for help rather than pushing too hard on our own
  • take frequent breaks with food or mini-workout
  • recognize that even 30 minutes of immersion is tough, valuable and an achievement to be celebrated [1], with or without visible progress.

[1] I WILL reward my son for that.

replacing auto_ptr with unique_ptr #IViewer’s focus

I spent lots of time cleaning up hundreds of auto_ptr usages but interviewers were more interested in the theoretical differences between the two.

  • On the job, it’s an operational challenge. You don’t need the knowledge.
  • On the interview, it’s a knowledge challenge… theoretical, bookish. You don’t need the GTD capacities.

##af 70 ..spend%%spare time meaningfully

Holy grail — Long-term sustainable (hopefully intrinsic) motivation + modest level of expertise, with reliable (albeit low) income and (a bit of) social value.

I need a purpose, a goal to work towards… Without it, the absence of a … job would create a void. Depression, lack of purpose, loss of energy. None of the below is easily achievable or easily available. Whichever I choose, need to work towards it.

  • Research would be ideal. I have proven aptitude in theoretical domains ..
  • xp: I think the RTS/NYSE work has more meaning as it impacts more users.
  • xp: devops effort has proven value to the local team
  • I might consider joining a start-up, which provides employment and learning opportunity for younger workers (perhaps in their 50’s?)
  • Teach (online) — Chinese/English, with emphasis on writing and vocab
  • Teach (online) — programming? threading, data struct, algo
  • Teach — statistical data analysis, If not outdated..
  • Teach — enterprise app design, If not outdated? Too competitive. They may not take in an old programmer.
  • Teach — financial math? After 70?
    • ▼this domain is too competitive and entry barrier too high. A lot of effort to cross it but demand is low.
    • ▼Limited practical value. more specialized, but growing demand.
    • ▼I feel I need interaction with people.
  • Two-way translation service, but I prefer interactions.
  • Chinese medicine?

Tim (RTS), a friend in his 50’s gave 3 points

  1. earn a salary to help kids pay student loan
  2. sight seeing world wide — costs a lot
  3. volunteering

localSys insight: Self-learning

Q: by correlating the logs, config, source code, queries … on your own [3] in your spare time [2], do you think you can gain insight into local system?

This question is at the heart of my GTD challenges, including code-reading weakness.

I don’t need to be super-fast to make progress.

[2] I often have some spare time, not a lot but a few hours a week. Sometimes my work hour is exactly allocated to this. In 2018, I have plenty of weekend hours 🙂

[3] self-learning — There’s a balance to strike between asking and self-learning. I’m pretty good at guessing :).

I guess some developers rely on asking others and then making rapid progress. It has not been very successful for me, and I have not tried it many times. For me, it’s almost always a personal journey.

new orderId is generated for order-replace, !! order-modify

https://www.nyse.com/publicdocs/nyse/data/XDP_Integrated_Feed_Client_Specification_v2.1g.pdf

shows that NYSE matching engine has specific business logic for order-repace vs order-modify

  • order-modify reuses existing orderId
  • order-replace would create a new orderId — The “sitting” order must be removed from the book and replaced with the new order.

My friend Ashish said in more than one forex ECN’s,  order update always generates new orderId. He actually implemented the order update business logic in FIX clients that connect to the ECN’s.

risk-neutral means..illustrated by CIP

Background — all of my valuation procedures are subjective, like valuing a property, an oil field, a commodity …

Risk-Neutral has always been confusing, vague, abstract to me. CIP ^ UIP, based on Mark Hendricks notes has an illustration —

  • RN means .. regardless of individuals’ risk profiles … therefore objective
  • RN means .. partially [1] backed by arbitrage arguments, but often theoretical
    • [1] partially can mean 30% or 80%
    • If it’s well supported by arbitrage argument, then replication becomes theoretical foundation of RN pricing

 

max-profit # easy SCB-FM

Q: maximize profit on a given a price series … you can buy, sell, buy, sell any number of times, each time one share. No buy-buy-sell-sell allowed, i.e. at the time of buying, you must have no holding.

Q: ok you said it’s O(N), can you do it in one scan?

====my answer (without hindsight)

If price keeps dropping, then no trade possible

If price keeps rising steadily, then only one buy-sell pair

if i get peak-trough-peak-trough… then i must discard the first peak since I can’t do anything with it.

 

SCB-FM design IV #UDP synch

Q: In your parser class, onData(seq, packet) gets called by the UDP framework with

  • out of sequence packets
  • duplicate packets

Inside your onData(), you need to invoke client callback function like callback(packet) but in sequence and without duplicates. How do you achieve it?

====My solution

  • keep the packets in a circular buffer or a deque in the parser. Save each packet in a slot keyed by the seq number of the packet. Remember the nextSeqToSend. If we get a higher sequence, just warehouse it in the buffer.
  • (Interviewer didn’t ask) How do you reuse space in the circular buffer? when I’m warehousing packet #109999 in slot #9999, then logically the packet in the first slot was already sent out, so I can safely “wrap around” to save next packet in there. I can implement my system to ensure it is actually safe.

Q: if you use a deque, how do you allocate slot for packet #5 while waiting for #4?
%%A: i would allocate for both, but keep #4 slot vacant. Not sure if std::deque has this API

 

SCB-FM eTrading IV#1

Q: tell me more about your pricing projects
Q: is your project management style agile?

Q: what’s const correctness and “mutable”
Q: cpu cache optimization

(open) Q: forward vs backward iteration of array
%%A: i don’t know any perf difference

Q: make_shared advantage over calling ctor of shared_ptr?
%%A: memory leak… Correct. See http://www.enseignement.polytechnique.fr/informatique/INF478/docs/Cpp/en/cpp/memory/shared_ptr/make_shared.html
%%A: one allocation only
%%A: perfect forwarding

Q: is shared_ptr thread safe?
%%A: yes only for the increment of reference count
%%A: if concurrent with a copying operation on inst3, inst3 is reset on another thread, then I don’t know if it’s thread safe. See thread-unsafe shared_ptr: tiny examples

Q5: any experience with c++11?
Q5a: what are the c++11 code modernization changes you did. Examples?

Q: auto_ptr vs unique_ptr
%%A: unique_ptr can be moved (explicitly), not copied. auto_ptr can be copied and moved??
%%A: unique_ptr can go into containers. Yes see unique^shared^auto_ptr #container

visible progress: Unreasonable expectations

See also my sample list in the sms twister blog visible progress # very rare therefore to be celebrated

Contrast with the views in [[reconciliation]]. Beware empty [g=] glorifications that don’t mean much when I look back 20Y later.

Every week, I actually make more progress than my fellow daddies with kids and commute etc. However, Once a while, in retrospect I would fall apart and cast serious doubt on (and belittle) my progress and point out the unfortunately invisible long-term effect.

I think many people implicitly follow a harsh and simplistic criteria like earning capacity, kids’ grades or absolute return, to dismiss and discredit all the “progresses”. This can become irrational, counterproductive, and /demotivating/ — engine loss of power. Such criteria are unfair to the self. If you are a teacher or coach, would you be so harsh on your student?

It can be a punishment, like a flogging whip.

Putting on a critical thinker’s hat, I feel that for most guys in my situation, it’s no mean achievements to maintain current condition and make small progress, with invisible long-term effect. Anything more is asking too much, and requires luck, talent, determination, contexx etc.

  • –ranked by …? I want to highlight the unsung heroes…
  • cholesterol, dental, belly and weight? maintaining is no mean achievement
  • loving relationship with wife? maintained, even strengthened
  • knowledge (and first hand experience) with diet, fitness, aging? building up slowly
  • more blood donation, done for my kids.
  • semi-retirement planning? improving through 5 discussions/year
  • more familiar with Bayonne residential market
  • relationship with in-laws? improved, as visible long term progress. More important — relationship with my own parents maintained
  • boy’s renzi and Chinese reading? improved slightly. Not really long term visible progress but at least he maintained
  • physical flexibility? maintained .. yes! Improvement? yes a bit of visible progress, with huge effortstamina? maintained … no mean achievement
  • [g] financial domain knowledge? I expanded to FX; market data; low-latency equity; FIX exchange trading…. Visible progress but shallow.
  • algo and coding test performance? I tend to belittle the improvement
  • bonding with kids? constantly building, deepening… Not by default, but by effort.
  • c++/c# conquered as a visible long term progress. Rather hard and long mileage, which probably means high entry barrier for the new entrants.
    • Probably more important — java skill level maintained.
  • credit score
  • financial assets (mostly holding well against inflation)? yes visible progress but I tend to belittle it. Building this portfolio actually required persistent effort, years of analysis, experiments, ..

our coding drills r different: fundamental reason #le2XR

Fundamentally, one chooses how to practice based on past interview experience of his own, not hearsays.

Question for you — how many times in the last 18 months did you get a coding interview that required 30+ minutes per question?

A: about 20 out of 25 positions in my recent experience, not including a BGC-partners onsite when they gave me 4 different questions but each 20 minutes only.

Most of my coding rounds are hackerrank/codility or over weekend.

  • Now I think for you the answer is 10% (but did you include those hacker rank tests?)
  • Now I think for you, mostly you don’t need to compile ! That’s why you call them “algorithm questions” rather than coding questions.

Even if I persuade you on the importance of edit-compile-test speed, or the value of python, sooner or later you would doubt “Really? How come I seldom need to write real code so fast in an interview?”. You would eventually stop practicing with real-code and refocus on pure algorithms, by reading key ideas behind common questions.

If you spend hours of focused energy writing real code as practice, and feel worn out, your own, personal experience would eventually kick in and remind you that it’s not worth it.

Conversely, if I were to follow your method to memorize key ideas only, my personal experience would soon shout out — “Take a step back and look again, you are already pretty fast coming up with data structure and algorithm ideas, but your REAL weakness is implementing them — too slow !”

I listed all recent interview episodes in tabular format — https://bintanvictor.wordpress.com/2018/04/28/some-worthwhile-coding-iv-experiences/.

  • 100% of big tech companies require at least one coding question lasting more than 30 minutes.
  • 100% of big buy-side shops require at least one coding question lasting more than 30 minutes.
  • More than 50% of investment bank jobs also require it.
  • For the other c++ financial companies (the so-called “third party” players) like Bloomberg, exchanges, brokers, market data providers, about 80% of the jobs require it.

local jargon, local sys architecture #WFH

Background:  3 types: Portable dnlg ] finance IT listed 3 portable types of dnlg (i.e. domain knowledge), but now I feel the local (i.e. non-portable) dnlg is more relevant to

  • your remote work
  • GTD productivity,
  • your survival,
  • your overall value-add to the team,
  • assessment by manager

Interviewers can only ask portable dnlg, Local dnlg include things like

  1. local jargon
  2. local system architecture, local “data flow”

##FX/eq projects ] PWM, for SG IV

—-fx or eq
* Swing app to monitor multiple live database tables and auto-refresh upon new quotes/trades and position updates.
* Post-trade Affirmation for complex derivative deals. A workflow application. Operations verify deal attributes by phone and Affirm on the deal to send out trade confirm.
* Statistical feed “blender” (with multiple purposes), needed to remove outliers among diverse indicative eFX forward quotes. Outliers tend to mess up our auto pricers, tiered pricers and cross rate pricers.
* (Ledger balance?) PnL report. Nightly batch to apply marks on option positions and compute PnL. Reports both clients and firm accounts.
* Volatility surface fitter for FX (& equity index/single-names). Volatility smile curve fitter. Quote inversion. Option position mark-to-market, driven by live quotes from multiple live eFX markets.
* Workflow engine for Error trade reconciliation/chargeback. A single error ticket can compute PnL and chargeback across multiple (up to 100) error trades and cover trades. Every quarter, this engine reconciles hundreds of error trade whose total values add up to millions of dollars.

* Deal entry screen for trade booking after a retail dealer executes over phone. If trade validation fails, we notify the dealer to amend and resubmit. Same swing app is also used by spot/swap/options dealers to book voice trades.
—-eq
system? data normalization to take care of splits and dividends
system? basic back testing of simple strategies
system? re-sampling

* (EOS) web-based trade/order entry, with multiple validations. Used primarily by investment advisers across Americas, Europe and Asia. Thousands (up to 5-figure) of orders received daily.
** showing real time bid/ask from GS + bid/ask from trading venues
** supports most order types — limit/market/FOK/IOC/SL

* swing-based real time order book display. Updates to displayed order books come from the backend OMS via real time messaging.
* Also contributed to the OMS backend. Orders originate exclusively from private bank clients. We then monitor their cancels/amends and execution reports (via firm-wide messaging hub) from exchanges, ECN and GS private liquidity pool. Total message volume up to 6 figures.

—-fx
We are the interface to multiple ECNs to 1) receive quotes, enrich and publish to PWM clients 2) forward client orders to ECN in 2-leg spread trades 3) execute trades received from ECN 4) generate and validate (against tri-arb) cross rates using ECN quotes. Also contributed to auto quoters and RFQ engine. Supervised and monitored the progress of high-frequency eFX applications. Performed eFX development activities such as requirement gathering, design, testing and deployment. Personal contributions included
* Tiered quote pricer. Each FX customer falls into one of the tiers. When a currency pair updates in our pricer, all registered clients would get a new quote (??delivered to their Financial Advisors??). Silver tier clients receive a better bid/ask spread than regular clients; Gold tier gets the best quote.
* eFX rate update/distribution engine to downstream real time risk, PnL, position marking systems
* eFX option real time risk report (unfinished). Option position risk calc is rather slow, so each user selects a limited number of positions into his watch-list. Watched positions get periodically updated based on live ECN rates to show real-time risk.
* (questionable project) Compute cross rates for PWM trades that are large, recurring and involving illiquid currencies. Cross rates computation from daily close USD buy/sell rates.
————
— blender
http://www.olsendata.com/fileadmin/Publications/Tech_Papers/FXBlenderDoc_01.pdf (C:\0x\xz_ref)
outliers are particularly damaging to market making systems.
input – transaction prices and indicative quotes
output – only indicative quotes

— cross rate calculator

What we compute are backdated cross rates. PWM (non-trading) client agrees on a currency conversion AAA/BBB. She agrees on AAA amount, and wait for a few hours/days to get the actual BBB amount, just like cross currency credit card payment —

MasterCard exchange rates are based on multiple market sources (such as Bloomberg, Reuters, Central Banks, and others). These rates are collected during our daily rate setting process. The exchange rates displayed on the web site are derived from the buy and sell rates included in the MasterCard daily T057 Currency Conversion Rate File.

MasterCard applies the USD as unique reconciliation currency to manage all currency conversions globally. Due to possible rounding differences, the published calculated cross-rates may not precisely reflect the actual rate applied to the transaction amount when converting to the cardholder billing amount. The calculated cross-rates will be loaded onto the MasterCard web site on a daily basis.

MasterCard applies the exchange rate to transactions at the time of settlement, not at the point of authorization of the sale.

–ECN interface
(my code doesn’t use FIX. Our volume is lower. conversion from FIX to xml is encapsulated in a library)

FXAall, Currenex, Hotspot, TradeWeb , Bloomberg. Example applications:
* auto quoters
* price feeds
* market data feeds
* post trade feeds
* execution gateways

mgr position risk: age-unfriendly

Statistically, very few IT managers can maintain the income level beyond age 55.

I believe those managers in 30’s and 40’s are often more capable, more competitive and more ambitious.

Even if you are above average as a manager, the chance of rising up is statistically slim and you end up contending against the younger, hungrier, /up-and-coming/ rising stars.

## CRTP usages #template Method

This write-up describes two usages of CRTP

I briefly read the excellent blog https://www.fluentcpp.com/2017/05/16/what-the-crtp-brings-to-code/. I feel CRTP is advanced for almost all the contexts I can think of. (In contrast,  I can see some “necessary” usages of SFINAE, such as the one in my little AddOrder.h)

https://stackoverflow.com/questions/262254/crtp-to-avoid-dynamic-polymorphism shows a simple [1] example of CRTP to replace virtual functions. How much efficiency improvement does it make? Questionable. I always say that if you want the lowest latency, then write selected modules in assembly language, and store it in hardware like FPGA.

[1] if there is anything simple in template meta-programming.

I have heard of several techniques to avoid virtual functions, but I believe the actual evidence (in terms of measured improvement in latency) is likely unconvincing or insignificant. Therefore, if CRTP is used to eliminate virtual function latency, then I am not sure how much value it adds.

There are other techniques to avoid “virtual”. I feel they are easier to understand than CRTP.

Q: for a virtual method v1(), the derived class is not yet written when the base class is compiled. Later, Only at run time can the “system” pick the right implementation of v1(). How about CRTP?
A: base class is not compiled ahead of the derived class. Each derived class includes the base class as a template in header.

Beside this “virtual-elimination” use case, CRTP has other applications (am still unfamiliar with), but if I’m asked in interviews I will only mention this one use case. One of the common “other usages” is TemplateMethod with compile time (not runtime) resolution, the 1st usage in the excellent blog . In the classic template method pattern, the “procedure” is published and finalized in the base class. Individual steps of the procedure are virtual methods, resolved at runtime. In the CRTP version, superclass methods call subclass methods, safely and cleanly. Superclass using subclass is a taboo in most contexts, but both traditional TemplateMethod and CRTP are notable exceptions.

The article didn’t clearly highlight a key point about this usage — The base class NumericalFunctions is general purpose, designed to be subclassed by anyone.  I could write a Temperature class to subclass NumericalFunctions too. This way, the code in NumericalFunctions is available for reuse.

template <typename Sub> struct NumericalFunctions { //templateMethod demo
    void square(){ //a reusable code to be "inherited" by any subclass
        Sub& underlying = static_cast<Sub&>(*this);
        // cast to Sub* is probably more common and I tested too.

        //Now we can Access subclass instance without using virtual function!
        underlying.setValue(underlying.getValue() * underlying.getValue());

        cout<<"from inside superclass square(), you can even access subclass field: "
            <<underlying._value<<endl;
    }
};
struct Sensitivity : public NumericalFunctions<Sensitivity> {
    double _value;
    double getValue() const{ return _value; }
    void setValue(double value){ _value = value; }
};
int main(){
  Sensitivity * inst = new Sensitivity;
  inst->setValue(17);
  inst->square();
  cout<<inst->getValue();
}

Key points to remember about the code sample:

  • base-class — is a template with a dummy type “Sub”
  • derived classes — have the form “class Sub1 public Base<Sub1>”
  • the static dispatch (non-virtual) function in Base always static_cast “this” to *Sub.

 

longest consecutive ints ] matrix 70% done

View story at Medium.com

Q: Given a n*n square matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1. We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.

Example:

Input: mat[][] = {
{1, 2, 9}
{5, 3, 8}
{4, 6, 7}}
Output: 4
The longest path is 6-7-8-9.

–sol1, probably O(NN) since each node is checked no more than 5 times.

1) typewriter search for the first unvisited node. Exit if all visited. Once a node is found, designate it as cur.
2) down-search .. explore cur’s four neighbors to see if any == cur-1.
3) if found, then desingate that node as cur and continue the down-search.
4) At end of down-search, Go back to #2) and start up-search.
5) At end of up-search we have a linked list. IFF list size > 1, then all nodes on it are marked as visited.
7) go back to #1.

self-hate due to hearsay 300k salary #XR

.. You seem to feel the (hearsay) income level of 300k is the minimum you need to feel good about yourself. In that case, your worry and negative self-assessment about income is misaligned with reality.

A bit of real statistics to chew on – rank all countries by GDP per-capita. Most of the top 10 richest countries have population below 9 million including Switzerland and most of the Northern Europe countries.

Q: How many countries are richer than U.S. *and* with a population above 20 million?
Answer: zero. Japan, Germany, UK, France,  … are all less rich than the U.S. Now, I believe you don’t want to compare with developing countries like China, Korean, Taiwan, India, let’s first focus on rich countries —

  • I believe half the American families earn less than 60k combined income, so do you think half the American families are struggling to survive every day?
  • I would estimate (based on my knowledge) more than half the *families* across the rich countries earn less than USD 60k, but you are implying that a single income of 300k is the minimum you need?
  • USD 300k single income would put you in the top 2% in any rich country, but you feel that’s the minimum you need?
  • USD 300k is higher than at least half the doctors’ and lawyers’ income across the rich countries, so you seem to say most doctors and lawyers are struggling to survive based on their income
  • My wife’s income is about SGD 30k. A regular teacher’s salary in Singapore is about SGD 50k. Singapore is, by most rankings, more affluent than the U.S. and teachers are a large, white-collar workforce. By your standard, even a 500% increase in a Singapore teacher’s income would still be too low for you.
  • In one of the most expensive cities of our world – London, a USD 300k salary would be top 2%. I know from many sources that London finance IT salary is lower than New York. A 700-pound daily contract rate is “extremely rare” (unheard of to many people) but it works to be only USD 230k, but you would think that’s not enough to survive. Mind you, London is more expensive than New York.
  • Some would say London is still cheaper than … Hongkong. A UBS VP position I tried was at HKD 1.2 million, about half your minimum standard.
  • I have friends in Shanghai and Beijing – the most expensive Chinese cities (along with Shenzhen). A 300k USD salary would be one in 500 jobs over there, but you think it’s barely enough for you. They would guess you live in a city where home price is 10 times higher than Shanghai/Beijing but in reality, your home is more affordable — A comparable apartment (not a 2-storey house with backyard) in Beijing/Shanghai would cost at least USD 1.5 million.

You are living in an ivory tower (and refusing to step out to the real world) if you hold on to that irrational and negative view. You sound like a guy complaining about his 10-room, 3-story mansion. It’s not depression but hallucination.

If you carry this habit into parenting, then beware — your kids could be top of their class but you may still feel they are not good enough because they didn’t win a gold medal. Would be tragic. I think Chinese parents are demanding but most are not at that level. We love our kids and accept them. We ought to love and accept ourselves.

I recommend [[compassion and self-hate]] by Theodore Issac Rubin, my favorite American self-help writer. His books changed my life. I feel good to know he is now 95. I’m grateful to Dr Rubin; I’m grateful to my dad; I’m grateful to Buddhism teachings; and I’m grateful when I answer your questions — I often get a chance to look into myself. I thank our creator to give me the analytical powers (though not as powerful as Dr Rubin) to dissect the layers and uncover the core issues in my psyche. As I endeavor to answer your questions I often reach a deeper understanding of my own pains, stupidity, irrationality and unfairness to myself and love ones.

%% absorbency isn’t highest #don’t scold kids

Obviously 99% of us have limited technical talent like learning capacity, memory, problem solving speed .. but today I will focus on another factor “absorbency 耐得住寂寞” – the capacity to endure repetitive practice, sustained focus, and build the /mileage/ required for mastery. No one has unlimited absorbency. Sooner or later we all reach saturation point, or “breaking point” (Liu Shuo).

Opening example — I often tell my friends “Study is not hard work for me.”

example — When I was trying rock climbing, my finger and forearm would get too tired for me to continue. On the other hand, as a teenager, I could do 600 sit-up in 10 minutes non-stop.

Absorbency is one of the top 5 most important technical talents, esp. in the long run. Some fellow parents said the vast majority of primary school pupils are not very different in IQ. I would add that differences in absorbency is big. I often feel my son is weaker on absorbency when practicing piano, Chinese handwriting and math. I think he is improving. His swimming practice has always been good.

Some individuals are not the brightest/fastest but can tolerate high amounts of practice and can become formidable like 郭靖

Let’s shift focus to my own technical absorbency. I want to say I’m not the strongest so I should not blame my son.

  1. Coding drill – I can do more than most peers, but then some grads can solve more than 5 problems a day, and pass all Leetcode tests.
  2. Quant study – I did more than half my homework on my own. Some classmates were able to practice and study more.
  3. Getting a grasp on a big codebase – absorbency required, beside learning speed + memory.
  • eg flight — how much technical learning you get on a 15H long flight is a measure of your technical absorbency.
  • eg coding drill — Rahul, me and Abhinav each find joy in coding drill but many of my friends seem to focus on reading the ideas rather than practicing and solving problems independently. Focusing on the end result rather than the journey is no fun. The joy increases your absorbency
  • Positive feedback — is a key factor affecting absorbency. Coding practice and software programming offers immediate feedback.
  • self-doubt — I frequently (once a month?) question my endeavor (and the elusive strategic value) .. detrimental to absorbency. It’s already hard to absorb the practice even without these self-doubts.
    * yoga
    * risk analytics
    * socket

max-profit@most 2K trades #proven but untested

Q(Leetcode): Say you have a price history as array. Design an algorithm to find the maximum profit. You may complete at most 2K transactions, consisting of exactly K (eg 2) buys and K sells. You may not engage in multiple transactions at the same time (i.e. you must sell the stock before you buy again). No short sell please.

No O() requirement.

====analysis=====

I feel first challenge is to list all (not more than 10) scenarios. This step has taken me a few days, even though I drew many examples.

–solution 1 (brute force): construct all possible pairs, rank them and pick top 2.

–solution 2 (only works for K=2)

  1. Identify all the turning points so we end up with HLHLHL… We can eliminate or ignore the other points.
  2. * identify the best pair using the max-profit algo. denote them as L1/Hj
  3. * In the subarray before L1, find the best pair
  4. * in the subarray after Hj, find the best pair
  5. pick the best among the two an denote it as p2
  6. Now look into the subarray L1 to Hj. If there’s no enclosed pairs within then we have a simple case — use L1/Hj and p2. But let’s assume there are at least 2 nodes enclosed. I will denote entire subarray as L1 H1 L2 H2 … Lj Hj (where L1-Hj is the max-profit)
  7. * use max-profit algo to find the worst loss from H1 to Lj. Suppose it’s H3 to L5.
  8. If this loss exceeds p2, then the we will return L1/H3 and l5/Hj. Otherwise, return L1/Hj and p2

This solution uses the watermark algo 4 times (*).

can we use a matrix?

We can keep track of all profitable pairs i.e. le/ri indices, and also a pointer to the current best pair that’s not overlapping with “me”.

After creating 2nd pair, IFF no overlap, then we update the pointers in both instances.

After creating 7th pair, if it doesn’t overlap with the #3 highest pair, then check-update the pointer in #3.

I think if we can efficiently keep track of these then it should work.

I feel basic decision is to break the best pair or keep it

case: need to break the highest pair into 2 pairs,
case: best pair + another pair outside. I think this is easy..
case: 1,18,2,19,15,16. Perhaps the hardest case to solve.

minimum hardware requirement to run linux #historical observation

  1. Bell labs Unix, in its early days, were able to run on hardware considered “underpowered” even by the standard of that day — P33 [[art of unix programming]]. I believe contemporary kernels were unable to run on those low-end machines.
  2. Linux (P77) has a similar characteristic. In the 1990’s the big commercial Unixes targeted enterprise-class hardware but Linux emphasized doing more with less. Today, Linux powers 99% of the world’s most powerful supercomputers but Linux also runs on low-end or obsolete hardware.

In both cases, I feel that an OS designed with very low minimum hardware requirement turned out to be actually more efficient, more adaptable, more versatile, more powerful than their conventional competitors.

peek@solution,get hint,then solve the problem yourself

I have found it rather important to follow this routine — Suppose a given easy or hard leetcode problem is too unfamiliar to me (might be familiar to you) so I have very few ideas, all on the wrong track. I would peek at the discussions to get some useful hint. I stop reading right there and go back to my drawing board and spend the next hour (or day) conceiving my own solution.

This has worked more than half the times. Benefit? I get to implement and remember my own solution.

There is a more important but subtle benefit — that hint is often related to a Reusable problem-solving technique, the holy grail of coding drill.

The way I see it, there are only a dozen or so (below 20) reusable techniques. Even if I were to memorize all of them, they would be useless to me because the real challenge is how to Apply a technique to a given problem. The way I learn to apply a technique is

* make sure I feel the hint i.e. it connects some dots in my mind
* experiment with various ways to use the hint to tackle the problem
* some experiments show progress; some become dead-end because they are the wrong ways to apply the technique
* keep sharpening "pattern recognition" until the key characteristics of the problem becomes clear in my mind.

The more I experiment with the hint, the more familiar I get… familiar with the problem, the hint, and the hitherto hidden gem behind the hint. That gem is often (not always) a reusable technique.

I won’t learn how to apply a Reusable technique if I don’t experiment, if I read a solution directly. The dots won’t connect. Pattern-recognition will still develop but slowly. Worse still, I may completely miss the hidden Reusable technique in the solution.

I always believe the real value in doing a Leetcode problem is the technique, reusable or not.

The solution I conceive will Not be as optimal as the one in the discussion … but it is easier to digest. The optimal solution in the discussion is usually rather concise (since the authors want to look cool) and elegant, but I don’t need to learn an elegant solution. I need to learn a Reusable technique. For that purpose, my own solution is easier to digest because it uses only a bit of the new technique + many familiar techniques.

## eg@portableGTD skills: valuable but never quizzed

Background — survival skills not tested in IV are usually [1] localSys and [2] portable GTD

  • — dev-tool knowledge
  • my posts on c++ build errors
  • Many posts on gdb
  • most posts on eclipse and MSVS
  • posts on git/cvs
  • posts on bash
  • posts on vi, less, find
  • — beyond tool knowledge
  • correlate logs, config, source code, data store…
  • script automation and shell customization skills
  • techniques and familiarity with jira

defer-send MSOutlook rule #3spaces

I have used this type of rules in many companies. My current set-up is —

Apply this rule after I submit a msg marked as Normal importance: defer delivery by 1 minute.

I wish there’s a “importance = A or B” condition.

remove subsequent duplicates in slist #SocGen

Q (SocGen hackerrank): given the head node of a linked list that might have duplicate values,  return the head node of a sanitized linked list without duplicates.

eg: Node@0x7089 (value=3) ->Node@0x6481 (value=2) ->Node@0x7921 (value=3) ->Node@0x6308 (value=7) ->null

would become Node@0x7089 (value=3) ->Node@0x6481 (value=2) ->Node@0x6308 (value=7) ->null

Note the first node (value=3) is still in the list, but all subsequent nodes with (value=3) are discarded.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/linkedList/removeDupNodes_SocGen.cpp is my tested solution

  • The two-pointer solution sounds simple but is over-complicated and error-prone during implementation.
  • fake-link-head technique is again useful

y I said you looked too dissatisfied #XR

聊天每 10次 觉得你有5 次(太多 🙂 流露对自己的处境严重不满。这方面我们俩类似, 所以我也有同感。正因如此, 我觉得你没必要这么不满意, 更不必苦闷。

从没听你提到你父亲。我父亲这方面给我宝贵的指点. 更重要是, 反复指点 — 我的思维习惯好难改变, 我一直有独立思考的性格和信心, 真固执 , 甚至顽固不化。我感激他不厌其烦指出我的愚人自扰.

光感激没啥用. 更重要的是 我被他的智慧和耐心逐渐地感化, 认识到自己并非顽固不化。

你我对很多问题的看法差异都与我父亲相关。比如学区;比如名校招生偏向弱族;比如各国教育系统哪个更成功; 比如对孩子评估过早…

还是说个人事业吧. 我深感自己 IQ/EQ 有限, 实在没必要和高薪的技术人员比.(更不要去比管理型人才). 所以我说目前处境不错, 偷笑还来不及.

刷题并不一定要有经济效益 — 比如拿个硅谷 或是高频 顶级公司聘约. 我比较重视能力提高,技能积累. 几年候 就算积累效果不佳, 我也希望能做到心安理得.

我的 UChicago 硕士读下来这个状况, 心安理得 着实不容易 . 我的总结 — 金融数学职位太少而且要求比我能力高, 薪水不一定比程序员高多少, 也没有 Contract 可言. 没法发挥我 (和 CSDoctor) coding 方面的特长和经验. 所以说 2013 年选择这个硕士课程, 实情了解得不够. 上了船才知道。

这次惨痛的经历决定了我对各种新技术新领域的谨慎, 徘徊, 举足不前.

既然我不看好这些领域的”钱”途, 我也没你那么不满现状. 话说回来,

* i’m good at scripting/SQL/data-processing compared to other developers I know;
* I like analyzing complex data, with attention to details;
* I have formal math training including statistics

So IF there’s some high-paying domain for me, I am open to it. That’s a big IF. The way I see it, most of those data analyst jobs are not paying well. If it pays well, it would be too hard to get in.

get ideas@top100 common Q #XR

Update — Now I realize my energy is limited so I need to allocate my spare time between

  • real coding
  • reading the key ideas

Also, I feel no positive feedback when reading the key ideas. I hit de-motivation.

Hi XR,

I now agree with your analysis — if I understand and memorize 1 key point about each problem, by reading leetcode, those points will help me significantly in a coding interview. This is one of the 4 benefits of coding practice #syntax,ECT,BP

  • If the problem is easy, then those key points will save me from running out of time.
  • If the problem is hard for everyone, then interviewer would have a lower expectation i.e. no need to complete it 100%. If I am on the right track (while other candidates are not) then i have an edge.
    1. case in point —- Last Friday I told you about shortest-path problems. I learned the technique from past interviews.
    2. case in point —- remember I told you about my own facebook question (3-way sorter/classifier #FB) Your swap technique is a valuable key point, even though it won’t help me finish the solution within 30 minutes
    3. case in point —- In 2018 I encountered comparable int array shuffling problems within 2 months at MS and LiquidNet. Key points are relevant.
    4. case in point —- In a 2018 interview, I learned to use N-by-N matrix to represent a N-node graph, then I used this key idea in another coding interview.

I wonder if I could get myself to follow a plan similar to yours:

  • every weekend (+ weekday evenings) spend 30 – 120 minutes.
  • First select some interesting” and popular question. If no idea, put it on back-burner
  • after a while, give up and read the solution to get the ideas
  • eg: edit distance
  • eg: punctuating continuous sentence
  • eg: regex
  • eg: maximum all-black sub-matrix

edit distance

The DP idea — compare matrix-path-counter, which is less obvious and easier than This one.

Q72 on Leetcode: Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Comment — Top 100, naturally occurring. I won’t bother to pass all Leetcode tests esp. the load tests. If I pass all non-load tests I would consider my solution decent.

https://github.com/tiger40490/repo1/tree/py1/py/str has my implementation based on a DP idea online, and a spreadsheet illustration. The idea is elegant once you wrap your mind around it.

===analysis===
Starting with the small string (length S), The challenge is to project as many of the S chars to the large string (length L). If we can project 5 chars at most, then … (wrong — the remaining S-5 chars need replacement, and the other L-S chars need insertion.)

–idea2: draw all the projection arrows from S to L. In a good-projection, every arrow on the right should be more slanted than every arrow on the left. We want the largest good-projection. In the opening example, the largest would have 5 arrows, …

—-
None of these ideas has proven effective.