FIX^tibrv: order flow

Background — In a typical sell-side an buy/sell order goes through multiple nodes of a flow chain before it goes out to the trading venue. The order message is payload in a messaging platform.

FIX and Tibrv (and derivatives) are established default choices for messaging platform. Both are highly adaptable to complex combinations of requirements.

FIX tibRV
TCP UDP transport
unicast multicast pub/sub fan-out
designed for low-latency eq trading popular for bond trading latency
order msg gets modified along the flow chain ? editable payload
Advertisements

missing q(return): non-void function #Josh

I told Josh about this real Scenario: my non-void function has 3 control paths, one of them without a return statement.

g++ usually give a warning under “-Wall”. Flowing off the end of a function is equivalent to a return with no value — undefined behavior in non-void function.

If you print the function return value and the 3rd control path executes, you get undefined behavior.

https://stackoverflow.com/questions/3402178/omitting-return-statement-in-c

C#job #eg: Ashish

See also enough c# mileage accummulated@@ and exposure: semi-automatic(shallow)Accu #$valuable contexx

As I told XR, a C# job offers opportunity for steeper growth curve, and higher chance of learning something useful [1]. It could provide another boost to my c++/java zbs.

As I told XR, some c++ shops are on VC++, and I am rather weak on windows and MSVS.

[1] In contrast, a regular c++ (and esp. java) job might hit a plateau of slow growth and diminishing return.

Therefore, c# job sounds more “strategic”. Strategic is not about long-term career development, but about engaging. With something “strategic” I might be more engaged, but I might lose the interest in X months too.

–Ashish’s team specifically

  • 🙂 Good chance of appreciation. Ashish isn’t as strong as Kevin.
  • 🙂 smaller codebase
  • 🙂 bitcoin trec (+shallow dnlg) will be a new addition to my /repertoire/ on my profile
  • 🙂 no risk of reputation damage at a big bank

hardware mutex, based@XCHG instruction

[[OS by William Stallings]] P216 is concise.

The atomic XCHG instruction on Intel processors can swap a local variable with a main memory location visible to all threads.

This instruction alone can implement a simple mutex usable by multiple threads on multiple processors sharing the same main memory. Limitations are severe:

  • even with a single mutex, deadlock is possible at the hardware level — ThrA in critical section can get interrupted and preempted (normal) and consequently put in a low-priority queue. ThrA would have to wait for the high-priority ThrB to complete, but ThrB is busy waiting to enter the same critical section.
    • Note in this example there’s no “lock object” per-se !
  • by default, unsuccessful threads are stuck in busy-wait — wasting CPU

 

components@kernel beside deviceDrivers #signals,interrupts

Q: exactly what constitute the linux kernel?

[[OpSys by William Stallings]] P99 has a nice diagram showing most of the components in linux kernel are device drivers and similar software

  • NIC driver
  • char device driver — for keyboard
  • block device driver — for disk
  • physical memory interface
  • device interrupt handlers

What are the other components of kernel?

1. system calls — the highest level in the kernel
1. Signals — the Signal definition and handlers are at the same level as syscalls, but at a higher level than the device interrupt module.
2. TCP/IP module —-  is a level between syscalls .. and .. NIC driver
2. virtual memory —– is a level between syscalls .. and .. physical memory interface
2. filesystem module – is a level between syscalls .. and .. block device driver

Lastly, scheduler — is a highly visible component of kernel. Scheduler relies critically on the device interrupt module.

It pays to limit tcost@SG job hunt #XR

XR said a few times that it is too time consuming each time to prepare for job interviews. The 3 or 4 months he spent has no long-term value. I immediately voiced my disagreement because I took IV fitness training as a lifelong mission, just like jogging or yoga or chin-up.

This view remains as my fundamental perspective, but my disposable time is limited. If I can save the time and spend in on some meaningful endeavors  [1] then it’s better to have a shorter job hunt.

[1] Q: what endeavors?

category: jobHunt

c++IV tougher than java #finance#XR

XR is first to point this out.

Q1: for candidates with 5+ years of experience, is the passing rate really worse in c++ IV than java IV? Let’s limit ourselves to sell-side.

%%A: indeed slightly lower.

Q2: is c++ paying slightly higher? I don’t think so.

Both java and c++ (c# too but not python) interviews go to crazy low levels details. Most tough questions in java/c#/python are low-level. Many tough c++ecosystem questions are C questions. C/C++ is a low-level language.

C++ interviewers may demand c++ecosystem knowledge but java also has its own ecosystem like add-on packages.

Perhaps the most important reason for my Q1 answer is selectivity. A java hiring team can be highly selective but on average, c++ hiring teams have higher selectivity:

  • higher bar
  • more time allocated to selecting the right candidate
  • less interested in commodity skills and more demanding on in-depth knowledge
  • less likely to settle for second best talent

What does it mean for Shanyou and Deepak? They are unlucky to hit a rising bar in a shrinking domain… increasingly competitive.

c++(!!Java)ecosystem questions are tough #Deepak

As I told my friend Deepak,

  1. c++ecosystem questions can be tougher than core c++ questions
  2. java ecosystem questions are easier than core java questions
    1. java ecosystem questions are often come-n-go, high-churn

Low level topics are tough

  1. c++ ecosystem questions are mostly in C and very low-level
  2. java ecosystem questions are usually high-level
    1. JVM internals, GC … are low-level and core java

 

represent graph: matrix ^ edgeSset

Josh’s book [[data structures and other objects using c++]] has 5 pages devoted to 3 common data structures representing a genric node graph. (I think my [[discrete math] also covers the same topic.)

  1. boolean adjacency matrix — amat
  2. edge set — eset
  3. edge list — marginally better than set… not discussed here
  • iterating all edges connected to a node — eset wins
  • sparse graph — amat wastes memory
  • test linkage between 2 nodes — amat wins
  • ease of implementation — amat wins

ABA problem #DeepakCM

  • breaks basic CAS assumptions, but I’m yet to understand the illustration program
  • most common solution is [1]
  • affects c++ CAS only, probably not java CAS

[1] https://lumian2015.github.io/lockFreeProgramming/aba-problem.html and http://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists explain the “tagged state reference”  aka “tagged pointer”

This topic was asked briefly in Deepak’s MS c++ interview in 2019.

 

c++dtor^py finalizer^java finalizer

This blog has enough posts on c# finalizers. See also AutoCloseable^Closeable #java

python finalizer is a special class method object.__del__(self), invoked when reference count drops to zero, and garbage-collected. As such, it’s not useful for resource management, which is better done with context manager, a popular python idiom and the best-known “protocol” in python.

— Java finalizer is an important QQ topic

https://stackoverflow.com/questions/2506488/when-is-the-finalize-method-called-in-java has some highly voted summaries.

The finalize() method can be at any time after it has become eligible for garbage collection, possibly never.

The finalize() method should only be written for cleanup of (usually non-Java) resources like closing files. [[effJava]] says avoid it.

https://www.infoq.com/articles/Finalize-Exiting-Java compares

  1. c++RAII
  2. java finalize()
  3. java 7 try-with-resources

c++QQ/zbs Expertise: I got some

As stated repeatedly, c++ is the most complicated and biggest language used i industry, at least in terms of syntax. Well, I have impressed many expert interviewers on my c++ language insight.

That means I must have some expertise in c++ QQ topics. For my c++ zbs growth, see separate blog posts.

Note socket, shared mem … are outside c++ language. More like OS libraries.

Deepak, Shanyou, Dilip .. are not really stronger. The know some sub-domains well, and I know some c++ sub-domains better, in both QQ and zbs.

–Now some of the topics of expertise to motivate myself to study

  • malloc and relatives … internals
  • enable_if
  • email discussion with CSY on temp obj

contents to keep in .C not .H file

1) Opening example — Suppose a constant SSN=123456789 is used in a1.cpp only. It is therefore a “local constant” and should be kept in a1.cpp not some .H file.  Reason?

The .H file may get included in some new .cpp file in the future. So we end up with multiple .cpp files dependent (at compile-time) on this .H file. Any change to the value or name of this SSN constant would require recompilation to not only a1.cpp but unnecessarily to other .cpp files 😦

2) #define and #include directives — should be kept in a1.cpp as much as possible, not .H files. This way, any change to  the directives would only require recompiling a1.cpp.

3) documentation comments — some of these documentations are subject to frequent change. If put in .H then any comment change would trigger recompilation of multiple .cpp files

##4+2 “games”I excelled,Visibly #MSFM

Most visible and most profitable game in this list is tech IV, including

  • 1a) branching out to c++
  • 1b) quant self-study to impress many technology interviewers

This topic already has many many posts in this blog. Below are other games I excelled in:

  1. excellent grades up to college Year 1
  2. paid off multiple rental properties + my own home, by age 43. All in good locations with reliable rental demand.
  3. Earned MSFM with flying colors at age 42 — sustained focus, self mastery

Some domains are not really competitive “games” but still I excelled visibly:

  1. no belly (as Nick pointed out); weight loss in late 2018, along with pull-up.
  2. keeping burn rate very low, and achieving some form of ffree around age 30 and again at 45

It’s instructive to recognize the pattern. I think in each game, I had some talent, and a lot of consistent effort. External positive feedback is far from powerful , immediate or frequent, so internal motivation is crucial. All individual games, not team games.

avoid if()assert

avoid:

if (…) assert(…)

Instead, put the if-condition into the assertion, which is

  1. more readable since the if-condition is clearly part of an assertion so other people tracing code don’t have one more IF block to check!
  2. more efficient compilation since preprocessor would strip the if-condition in release build

ibank: trade book`against exch and against client

In an ibank equity trading system, every (partial or full) fill seems to be booked twice

  1. as a trade against a client
  2. as a trade against an exchange

I think this is because the ibank, not the client, is a member of the exchange, even though the client is typically a big buy-side like a hedge fund or asset manager.

The booking system must be reconciled with the exchange. The exchange’s booking only shows the ibank as the counterparty (the opposite counterparty is the exchange itself.) Therefore the ibank must record one trade as “ibank vs exchange”

That means the “ibank vs client” trade has to be booked separately.

Q: how about bonds?
A: I believe the ibank is a dealer rather than a broker. Using internal inventory, the ibank can execute a trade against client, without a corresponding trade on ECN.

Q: how about forex?
A: I think there’s less standardization here. No forex ECN “takes the opposite side of every single trade” as exchanges do. Forex is typically a dealer’s market, similar to bonds. However for spot FX, dealers usually maintain low inventory and executes an ECN trade for every client trade. Biggest FX dealers are banks with huge inventory, but still relative small compared to the daily trade volume.

Most c++guys have no insight in STL

When I recall my STL interviews on Wall St, it’s clear that majority of c++ app developers use STL almost like a black box, every year for 5-10 years. Only 1% has the level of insight as Henry Wu.

Reason? such insight is never needed on the job. This factor also explains my advantage in QQ interviews.

  • Analogy — Most of us live in a house without civil engineering insight.

STL uses many TMP and memory techniques. Some may say STL is simple but I doubt they have even scratched surface on any of the advanced topics.

  • Analogy — some may say VWAP execution algo is simple.

Many interview questions drill in on one or two essential STL functionality (which everyone would have used), just below the surface. These questions filter out majority[1] of candidates. Therein I see an opportunity — You can pick one or two topics you like, and grow an edge and a halo, just as Henry did. Intellectual curiosity vs intellectual laziness. 不求甚解,不加咀嚼,囫囵吞枣 — I see it in many self-taught developers. That’s exactly what these Wall St interview questions are designed to identify and screen out.

How about west coast and other high-end tech interviews? I’m not sure.

[1] sometimes 90%, sometimes 60%.

 

##order states open2cancel/replace

Each OMS (order management system) in an OMS chain [2] remembers the state of each order [1]. Let’s focus on OMS4. When OMS4 receives an order-cancel/replace request message from upstream, will OMS4 accept the request and send the message downstream? Depends on the order state (of the order8) in question.

I believe if the order has been already rejected or fully filled or cancelled then not possible. OMS4 would reject the request.

What if order8 is in New state? That means acknowledged by liquidity venue but no fill received yet. Yes request is acceptable.

What if order8 is in PendingNew? That means OMS4 has not received the acknowledgement from downstream. meaning the liquidity venue has yet to enqueue the order. Well, in this case cancel (or replace) request will be forwarded to liquidity venue. OMS4 can optionally send back a PendingCancel or PendingReplace to indicate the current order status. In time, liquidity venue will either accept the request, or reject it because “already filled”, and send this response to OMS4.

[1] in non-volatile memory, and can respond to status queries and can often broadcast the order status to subscribers.

[2] A large trading platform often has a chain consisting of multiple OMS nodes, such as clientConnectivity, smartOrderRouter, AlgoEngine. I feel should not be more than 5 nodes, unless some aggregation is required.

## nothing to be proud of ] %% life@@

See also [2] ##4 qualities I admire in%%peers #!!status and
[1] ##envy Them constantly; !!celebrat`family,achievements..

Once a while in a young person’s life she(he) find herself (rather than her life) despicable in every way —

  • studies
  • dating
  • body image
  • fitness
  • team sports, not part of any “gang”
  • ….When we grow older we have some of these same “whips” + some new whips, which we use to beat ourselves up:
  • profession
  • home location, home size, school district
  • personal investments including properties
  • monthly saving rate

I think in such a situation we desperately need concrete, tangible evidence of personal achievement (not necessarily visible to other people). Here are some evidence to congratulate myself and defend myself against the whipping:

  • wife and kids — see [1]
  • SGP citizenship — see [1]
  • education credentials — see [1]
  • personal finance — see [1]
  • profession — see the first list in [1]
  • knowledge + experience about diet and wellness — see [2]
  • introspective or expressive writing and blogging — as a versatile coping, self-improvement, self-discovery device
    • English proficiency — I struggled for years and now I’m able to use English for expressive writing — something unimaginable in my teenage years.

## time-honored textual data file formats

[[art of Unix programming]] has insights on it… Note Windows tend to use binary file formats, whereas the Unix tradition favors textual.

Standard cvs format is not well designed. Its use of double-quote is criticized.

The /etc/passwd format supports metachar embedding better than standard csv.

The “record-jar” format combines cookie-jar with RFC-822 format and is more human-friendly than xml, ini, and cvs. It has field names. Its values can be unstructured text. It also supports “stanza” records.

xml can be checked for well-formed even without a DTD or schema.

I don’t have2aim@optimal solution

My friend Shanyou consistently holds a position like “I don’t need to find the better solutions (forget the “optimal”). If my solution is brute force or non-optimal, at least it works, so it will be good enough for many interviews and good enough for my coding drill. Many candidates can’t find even a brute force solution in the given time, so if I strengthen my capabilities to this level it’s valuable.

That’s inner strength — 定力
That’s much-needed focus
That’s undervalued realism
That’s celebration of every progress
That’s a pat on our own back

It’s a common and fatal de-motivation to tell ourselves (XR … ) “There’s no value in pursuing non-optimal solution.” Well there ARE a few:

  1. pride and achievement from completion of a tough challenge
  2. ECT, speed
  3. syntax idioms
  4. self-mastery, internal locus of control, similar to my yoga practice
  5. absorbency — demonstrate to myself; self confidence in absorbency
  6. joy, self-satisfaction — see exactly what I want{cod`drill beside immediate IV #Rahul
  7. … Other blogs provide other perspectives

!! Many published solutions are non-optimal in O()
!! Most solutions out there are non-optimal in terms of concise implementation, even if matching the best solutions in big-O.

Some interviewers only care about big-O and don’t care about too many loops; Other interviews want an elegant, simple solution; The most extreme interviews (FB?) score candidates on syntax and code quality too. Which one do you target? Realistically, I would take Shanyou’s target.

2 nodes] binTree-with-cycle: locate common ancestor

Q (Leetcode #236): given 2 valid nodes (and root) of a binary tree, find the lowest common ancestor. A node can be a (direct/indirect) descendant of itself. All values distinct. No uplink.

classic problem:)

Q2 (my own requirement): what if cycle is possible?

My idea — Just run a lazy-dft to find the two paths-from-root. On each path, if we detect a cycle we terminate that path. Before terminating any path, need to check if we hit both nodes, so after finding one node we must go all the way to the leaf node or the one of the 2 given node.

As soon as we find the 2 paths we terminate DFT.

IIF two CPUs are given, my dft will use two threads — one left to right; the other right to left. This will more quickly locate the 2 target nodes if they appear near extremities.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/binTree/commonAncestor_Cycle.cpp is my self-tested code, not tested on Leetcode

what I want{cod`drill beside tech muscle-build`#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.

This colleague always focus on passing Leetcode tests.

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 to him 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 about myself …
  • A2: I want some sense of achievement — when you read posted solutions you probably feel you learned something and achieved something. I feel more achievement when I come up with my own solutions, even if not optimal nor elegant.
  • A3: I want visible progress— When you read posted solutions to three common questions, clearly you feel progress. That’s why you aim to study 800 questions. I’m different. I don’t feel significant progress reading posted solutions.
  • A4: I want self-mastery — overcoming many obstacles, similar to yoga. I want to regain control of my spare time and follow some self-directed course.
  • A9: I want to build my mileage — as in driving. Mileage means how many productive hours I have spent on coding problems since age 20. A1/A2/A3 above all help keep me focused on doing more problems. Even with all the joy, achievement and progress, it’s still very easy to give up or lose steam.

rangeAND: bitwise AND of all ints in range

Q: Given a continuous range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

  • the lowest bit will most likely see 0 and 1 so … becomes zero
  • (turns out to be a minor tip) if the range has size > 8 then lowest 3 bits all zeroed out
  • imagine the bit array object incrementing from m to n. We want to find out if there’s a stable higher portion
  • Key technique — look at some examples. We can convert m and n to two bit images. we can look at some examples below.
  • we can compare the two bit images left to right to find the “higher portion”. All lower bits are probably zeroed out in the result

10110101
10110100
10110011
10110010
10110001
—–
10110000

–my solution not tested on Leetcode: https://github.com/tiger40490/repo1/blob/cpp1/cpp/rangeAnd.cpp
* compare m and n left to right. If m is shorter, then return 0.
* if same length, then compare left to right until a difference is found. Until that bit, all left-end bits are “retained”.

 

[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.

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”.

##[18] 4 qualities I admire ] peers #!!status

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

  1. personal wellness
  2. parenting
  3. personal finance, not only investment and burn rate
  4. mellowness to cope with the multitude of demands, setbacks, disappointments, difficulties, realities about the self and the competition
  5. … to be Compared to
    • zbs, portable GTD, not localSys
    • how to navigate and cope with office politics and big-company idiosyncrasies.

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

[1] Many people crossing my path 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 — lots of details as Shanyou and I agreed
  2. template meta-programming — deep topic but never quizzed in-depth beyond “tricks”
  3. move-semantics

— Themes are less visible 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 also 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 97th 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.

3personal survival capabilities #IV,health

Out of the subconscious realm, I hand-picked a couple of personal “qualities” [2] as the (three or five) 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.”

  • AA) my IV prowess — since Chartered. Compare 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
  • [T5] my rather healthy lifestyle 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 dedication to my kids, not only their studies
  • my bold investment style [2]
  • my education including English skills
  • [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.

[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 assets since I want to focus on personal qualities

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.

##[18]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

## 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

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

std::defer_lock #kill1@4deadlock factors

Only in the lock() call does the thread grabs both locks together. This breaks “incremental acquisition” , one of the four deadlock conditions.

  std::unique_lock<std::mutex> ulock1(mutex1,std::defer_lock);
  std::unique_lock<std::mutex> ulock2(mutex2,std::defer_lock);

  // now grab both locks
  std::lock(ulock1,ulock2); 

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
  • enable_if_t evaluates to either a valid type or nothing. You can use enable_if_t as a function return type. See [4]. This is the simplest way usage of enable_if to make the target function eligible for overload resolution. You can also use enable_if_t as a function parameter type but too complicated for me. [3]
  • 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!
    • Deepak’s demo in [4] uses bool as enable_if_t
  • static_assert — is not necessary for enable_if 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. An error would break the compilation.
    • static assert is always in definitions, not declarations. static asserts generate compiler errors.
    • Note the difference between failure vs error
    • I think template instantiation (including overload resolution) happens first and static_assert happens later. If static_assert fails, it’s too late. SFINAE game is over. Compilation has failed irrecoverably.
    • 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

[4] https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/SFINAE_Deepak.cpp

[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]%%competitive strengths as professional techie

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 new shared_ptr objects from “this”
    • Note if you only need to access “this” you won’t need the complexity here.

Pimco asked me in 2017!

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.

kernThr ] linux^Unix

Here are a few things I can recall, from [[UnderstandingLinuxKernel]].

P 104 lists some minor Linux kernel threads, but here are the important ones:

  • process 0 (swapper) is a kernel thread. This process gets scheduled when there’s no other process to run
  • process 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 kernThr is completely unrelated concept to traditional unix kernThr. More difference than similarities (zero?)

  • Unix kernel threads aka “native threads” 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

Linux kernel threads are less fundamental than kernel routines including sysCall handlers + interrupt handlers.

  1. every Linux user process enter kernel mode via kernel routines
  2. not every user process interacts with kernel threads

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.