local jargon, local sys architecture

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

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

Interviewers can only ask portable domain knowledge.. Local dnlg include things like

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

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 a newspaper? I do allow myself but in hind sight I often feel bad.

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

top3 personal survival capabilities #IV,burnRate#reflect

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

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

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

  • AA) my tech IV prowess. Look at CSY’s experience.
    • absorbency; continuous plow-back
    • self-renewal, staying relevant? Am rather successful so far
    • my reflective blogging is actually part of the my way-finding, motivation…
  • BB) my capacity to keep a well-paying dev job. 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
    • camp-out, extra hours
    • attention to details
  • [T3] personal burn-rate — important to my feeling of long term security
  • — The following factors are less “unique” but I want to give credit to
  • my education, English skills
  • my dedication to my kids, not only their studies
  • [T3 = a top-3 factor]

! benchmarking — AA is single-winner, 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.

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

I always enjoyed analysis@failing tech brands

I tend to learn something (very indirectly) about competition, churn, focus, …

  • Nokia — refocused on its traditional strength in telecom infrastructure
  • Erickson
  • RIM
  • Yahoo
  • Novell

I feel my choice of java and c++ have been good, but regret my investment in dotnet, pthreads

I feel any dominant technology can get displaced. A few examples (not intended to be complete) — C/C++ (by java), RDBMS, Solaris (by Linux)

My tech bets for 2019-2020:

  1. system knowledge #CSY
  2. socket
  3. c++ TMP — a pure QQ domain for IV muscle-building
  4. c++ threading

op=()will call implicit cvctor if RHS is!! same 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();
}

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.

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

phone pad: generate all combos #40%

Modified from Leetcode problem 17. Suppose there is nothing but one red button. and there are C (like 7) letters on it.

Q: With 4 (=N) draws from 3 (=C) letters (same phone pad button), how many permutations? C^N.

Q: With 4 (=N) draws from 3 (=C) letters, how many combinations?

For N=1, Ans=3
For N=2, Ans=6
For N=3, Ans=? Not obvious

–sol1:

Key: Each combo is represented as a sorted vector (ascending). There’s one-to-one mapping between such a vector and a combo.

let’s say C=3 and N grows from 1 to 3 .. For N=2, I put all combos on 3 rows (3 vectors or lists)

  • aa ab ac #all that starts with a
  • bb bc #all that start with b
  • cc # lone wolf

For N=3,

  • first container is populated by prepending ‘a’ to all 3 “old” containers of items
  • 2nd container is populated by prepending ‘b’ to 2nd-and-lower old containers
  • 3rd container is always a lone wolf

–sol-i: incremental solution — for N=3, given one combo, find the “next” combo. For example after bbc, we should get bcc.

I guess this design is actually fairly simple and efficient, probably similar to  https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/nextCombo/iterative.cpp

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). 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% (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

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 illustration above is rather unlucky since histogram is right-heavy. So 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.

6 clusters@HFT c++IV questions

Every single HFT interview question is about low-latency.

Furthermore, the ibank algo-trading interviews revolve around the same clusters.

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

  1. socket
  2. template meta-programming — deep topic but never quizzed in-depth
  3. pthreads and c++ threading but I seldom get c++11 question here
  4. — less strong themes in these small clusters:
  5. STL container internals, mostly raw array, vector and hashmap
  6. memory optimization techniques using allocators, cache-optimization, malloc(), placement-new
  7. move-semantics
  8. — other topics are dispersed not showing any strong shared theme
  9. shared memory
  10. linux system calls
  11. compiler details
  12. some boost

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

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

See also post on CivilEngineers.

C is the first language I studied in-depth, in 1994. C was also the first professional programming language in my very first job

I’m proud of my association with C because

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

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

Hi XR,

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

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

You asked me this question —

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

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

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

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

A2: I want some sense of achievement

sequence@{max within sliding window} O(N) no dequeue #40%

Q (leetcode hard problem 239): Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the max item in it. Total run time should be O(N) but I think within each window we may not always get O(1).

https://www.interviewbit.com/problems/sliding-window-maximum/ is the same problem stated more clearly.

No need to produce a new value whenever the window slides. Just produce the final list in O(N). It may take much longer than O(1) to have the first output element!

====analysis====

Since there exists a O(N) solution i’m confident I can figure out a O(N) solution

idea — first scan to identify all the troughs. Items around trough to be removed

–latest idea, not using dequeue therefore likely original —

Update — consider a rising sequence before going any further

in my showman-stack, every element {idx,height} will show up on stage at least one episode. I would say each showman goes on stage either when it first enters the sliding window, or before leaves the sliding window. If that’s the case at each slide i only need to consider the head and tail.

first forward scan populates this deque and ensures only showmen are included. Let’s work out some examples. First part of first scan would simply find the max among first K items. 2nd scan might be combined with first scan, but for now, my goal is clear and focused — produce a clean stack of showmen-only

  • degenerate case — monotonic sequence requires virtually all elements be included
  • if a low point is “close to” a high point already in the stack, then skip it.
  • rules on the forward scan —
    • every new item needs to be pushed to the stack as it could be higher than all followers. The logic is “what before the push”
    • before pushing a new item, top of the stack is always the immediate predecessor. Need to add assert.

pseudo code:

O(N) pre-scan to find all troughs. For each of N items, record the preceding trough.

check if the most recent trough is within range. If not then nothing to pop. Assuming it is.

while new item >= top of stack __&&__ the 2nd top is within range (distance <=K):

keep pop

while new item >= top of stack && distance between is below K && there would still exist an earlier higher item within range:
//at end of the while loop, we could actually produce some output, but I would postpone it to 2nd scan

For the last K items in array, we need some O(K) special handling.

I think both conditions are necessary for popping the stack. Are these two conditions alone sufficient justification to remove the top?

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

How is debugger breakpoint implemented@@ brief notes #CSY

This is a once-only obscure interview question. I said up-front that CPU interrupts were needed. I still think so.

I believe CPU support is needed to debug assembly programs, where kernel may not exist.

For regular C program I still believe special CPU instructions are needed.

https://eli.thegreenplace.net/2011/01/27/how-debuggers-work-part-2-breakpoints seems to agree.

It says Interrupt #3 is designed for debugging. It also says SIGTRAP is used in linux, but windows supports no signals.

 

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

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

Hi XR,

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

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

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

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

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

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

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

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

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

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

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

A 2010 interviewer asked

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

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

relocate q[#include] to implementation file: j4

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

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

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

## most strategic TSN among%%abandoned

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

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

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

dlopen^LoadLibrary # plugin

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

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

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

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

Machine Learning #notes

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

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

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

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

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

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

placement new: pearls to impress IV

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

container{string}: j^cpp

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

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

In cpp,

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

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

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

 

##advanced python topics #!! IV

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

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

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

RTS domain knowledge IV questions, by an MD interviewer

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

 

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

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

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

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

c++TMP: 9 fundamental features + little tricks

ranked:

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

Tricks:

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

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

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

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

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

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

[12] closure in java^c#

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

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

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

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

t-investment: QQ^coding^localSys

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

  • coding drill
  • local sys knowledge

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

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

## template type constraint+validation @compile time

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

covariant return type: java=cpp

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

— ditto c++

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

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

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

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

python Protocols #phrasebook

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

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

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

numpy,scipy,pandas #cheatsheet

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

concurrent python..#my take

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

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

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

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

 

I created a shared_ptr with a local object address..

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

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

The proven solution — make_shared()

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

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

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

— c++

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

–java: let’s focus on ctor

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

std::weak_ptr phrasebook

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

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

#1 feature — detect dangle

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

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

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

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

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

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

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

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

— Some update based on Wallace chat.

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

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

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

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

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

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

 

enable_shared_from_this #CRTP

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

both base classes”export”conflicting typedef #MI

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

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

Solution — inside Der, declare

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

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

passive income ⇒ reduce GTD pressure#positive stress

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

Q: Anything more effective more practical?

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

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

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

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

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

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

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

## y they ask QQ questions #revisit

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

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

rvr^rvalue-object, again

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

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

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

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

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

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

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

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

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

unique_ptr implicit copy : only for rvr #auto_ptr

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

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

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

max all-black submatrix O(LN)#ZR

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

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

—Analysis:

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

— sol5:

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

— sol4 unfinished

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

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

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

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

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

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

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

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

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

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

SCB-FM algo Q2a 2 slists

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

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

====analysis====

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

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

–SolR: reverse one list … how?

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

–Sol2: 2 iterators, read-only lists.

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

IFF the end nodes match, then 2nd scan:

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

SCB-FM algo Q2b stack-based queue

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

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

====analysis====

service dequeue from a hidden stack.

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

isEmpty() must add up two sizes.

SCB-FM IV by architect #shared_ptr upcast

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

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

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

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

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

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

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

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

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

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

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

kernel threads ] linux^Unix

Here are a few things I can recall

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

your brain power^brain power invested ] localSys

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

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

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

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

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

merge 2 sorted slists #2try

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

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

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

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

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

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

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

LFU cache #cf.LRU #untested

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

====Analysis

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

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

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

localSys learning: get over the hump

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

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

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

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

[1] I WILL reward my son for that.

replacing auto_ptr with unique_ptr #IViewer’s focus

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

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

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

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

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

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

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

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

localSys insight: Self-learning

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

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

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

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

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

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

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

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

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

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

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

risk-neutral means..illustrated by CIP

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

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

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

 

max-profit # easy SCB-FM

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

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

====my answer (without hindsight)

If price keeps dropping, then no trade possible

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

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

 

SCB-FM design IV #UDP synch

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

  • out of sequence packets
  • duplicate packets

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

====My solution

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

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

 

SCB-FM eTrading IV#1

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

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

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

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

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

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

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

visible progress: Unreasonable expectations

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

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

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

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

It can be a punishment, like a flogging whip.

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

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

our coding drills r different: fundamental reason #le2XR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— cross rate calculator

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

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

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

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

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

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

mgr position risk: age-unfriendly

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

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

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

## CRTP usages #template Method

This write-up describes two usages of CRTP

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

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

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

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

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

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

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

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

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

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

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

Key points to remember about the code sample:

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

 

longest consecutive ints ] matrix 70% done

View story at Medium.com

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

Example:

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

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

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

self-hate due to hearsay 300k salary #XR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

No O() requirement.

====analysis=====

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

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

–solution 2 (only works for K=2)

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

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

can we use a matrix?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## eg@portableGTD skills: valuable but never quizzed

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

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

defer-send MSOutlook rule #3spaces

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

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

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

remove subsequent duplicates in slist #SocGen

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

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

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

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

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

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

why I said you looked too dissatisfied #XR

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

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

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

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

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

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

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

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

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

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

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

get ideas@top100 common Q #XR

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

  • real coding
  • reading the key ideas

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

Hi XR,

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

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

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

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

edit distance

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

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

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

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

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

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

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

—-
None of these ideas has proven effective.

x-ccy eq swap: my intuition

At Time 1, CK (a hedge fund based in Japan) buys IBM priced at USD 10, paying JPY 1000. 11 months later, IBM is still at USD 10 which is now JPY 990. CK faces a paper loss due to FX. I will treat USD as asset currency. CK bought 10 USD at 100 yen and now each USD is worth 99 yen only.

Now consider a comparable swap trade.

At Time 1, the dealer (say GS) buys and holds IBM on client’s behalf. How did GS pay for the shares? GS received JPY 1000 from CK and used it to get [1] 10 dollars to pay for the stock.

Q: What (standard) solutions do GS have to eliminate its own FX risk and remain transparent to client? I think GS must pass on the FX risk to client.

[1] GS probably bought USDJPY on the street. Who GS bought from doesn’t matter, even if that’s another GS trader. For an illiquid currency, GS may not have sufficient inventory. Even if GS has inventory under trader Tom, Tom may not want to Sell the inventory at the market rate at this time. Client ought to get the market rate always.

GS own account is now long USDJPY at price 100 and GS want USD to strengthen. (If GS effectively passes on the FX risk, then CK would be long USDJPY. )

I believe GS need to Sell USDJPY to CK at price 100, to effectively and completely transfer the FX risk to client. After that,

  • GS is square USDJPY.
  • CK is Long USDJPY at price 100.

I believe the FX rate used in this trade must be communicated to CK.

11 months later, GS hedge account has $0 PnL since IBM hasn’t moved. GS FX account is square. In contrast, CK suffers a paper loss due to FX, since USD has weakened.

As a validation (as I instructed my son), notice that this outcome is identical to the traditional trade, where CK buys USDJPY at 100 to pay for the stock. Therefore, this deal is fair deal.

Q: Does GS make any money on the FX?
A: I don’t think so. If they do, it’s Not by design. By design, GS ought to Sell USDJPY to client at fair market price. “Fair” implies that GS could only earn bid/ask spread.

in size-N array find The duplicate int #1 to N+1 #pigeonhole Abhinav

https://leetcode.com/problems/find-the-duplicate-number/description/: Given an immutable int array nums containing n + 1 elements where each element is between 1 and n (inclusive), prove that at least one duplicate number must exist. You are guaranteed that there is only one duplicate number, find the duplicate value in O(1) space, below O(NN) time. The culprit may repeat many times.

I didn’t bother to write the code.

===== analaysis =====

contributed by a user and highly contrived:(
many likes:)

–bisection solution in O(N logN) time and O(1) space. I came up with this solution within a minute.

  1. Divide the full range [1 to n] into 2 almost-equal ranges (i.e. if n = 2K+1, then i use [1 to K] and [K+1 to n] as 2 ranges)
  2. Count how many nodes are in each range. Clearly one of the two ranges must have too many elements.
  3. Remember the boundary of that bad range so from now on we will ignore those nodes falling into the good range. We will use 2 variables to update/improve the boundary, until they coincide.
  4. within the bad range, repeat Step 1.

Key insight — progressive bisection.. non-recursive.

Key insight — applying pigeon-hold principle, we split the conceptual range. The more common (but ineffective) technique would split the physical array.

generate simple paths between 2 graph nodes

Q1: given 2 nodes in a graph containing N (eg 121) nodes, potentially with cycles, generate all simple paths between the pair. A simple path has no cycle. (In other words, length + 1 ==  # unique nodes in a simple path)

  • I think there are classic math algorithms for it, because this is part of basic graph theory. Here are some applications of this type of algorithms —
  • Q1b (special case of Q1): given 2 nodes in a C by R matrix grid, where every node is connected to (up to) four neighbors, generate all cycle-free paths.
    • I can solve this problem in python
  • Q2 (easy one based on Q1): generate all simple paths between any node pair in a graph. The shortest simple path has length=0. Longest simple path can potentially visit every node exactly once.
  • A: first generate all 121-Choose-2 node pairs. For each pair, solve Q1. Lastly generate the 121 trivial paths of length=0.
  • Q2b (special case of Q2): given a C by R (eg 11×11) matrix grid, where every node is connected to (up to) four neighbors, generate all simple paths.
  • Q2c (easy one based on Q2): given a binary tree containing no cycles, generate all paths.

— my DFT implementation (probably not 100% correct) , where each “trail” either fails or becomes a path.

  1. from NodeA start a breadcrumb/trail. We can’t revisit any node already visited on current breadcrumb,
    1. if this is a matrix, then instead of a hashtable, we can also use a shadow matrix, but the breadcrumb is much smaller than a shadow matrix
  2. if we can reach a node surrounded by nodes on the same breadcrumb, then the trail fails
  3. else we will reach NodeB 🙂 Print the breadcrumb

By construction, we won’t see duplicate paths 🙂

https://github.com/tiger40490/repo1/blob/py1/py/grid/classic_count4waySimplePaths.py is the implemnetation

–BFT? I don’t think it can print each unique path

shortest path btw 2 graph nodes #binary matrix as illutration

Q: given 2 cells in a binary matrix (1=black, 0=white=blocked), check the pair are connected and if yes return the shortest path. There exists a path of length 1 between any 2 cells IFF both are side by side or stack atop.

count paths between 2 bTree nodes #PimcoQ9 Ashish is arguably harder than this problem, but this problem allows moving in four directions.

binary-matrix island count #DeepakM technique is more applicable. A BFT path should work.

  • every reachable node is painted Green (like 2)
  • we give up after our queue is empty

https://github.com/tiger40490/repo1/blob/py1/py/grid/classic_connectedPair.py is the implementation, briefly tested.

fewest jumps to reach right end #triple jump

Q(Leetcode): Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents the maximum permitted jump length from that position.

https://github.com/tiger40490/repo1/blob/py1/py/array/tripleJump.py is my solution, NOT tested on Leetcode.

==== analysis =====
Typical greedy algorithm. I will jump leftward [1].

Suppose there are N=99 nodes in the array. I will pre-scan the N nodes to build a shadow array of integer records, each a BestLefNode. (The first record is unused.)

Eg: If BestLefNode[44] == 33, it means that based on known data so far, the left-most (furthest) node we can jump to from Node #44 is Node #33.

When we visit Node #7 during the rightward scan, we will update 0 or more BestLefNode records from #8 onward.

As soon as we update BestLefNode[N-1] i.e. right-most record, we exit the initial scan since the optimal solution is now available. For example, if rightmost BestLefNode has value #88, that means the furthest node we can reach from the right end is Node #88, so we will jump to #88 and then check the best destination From #88.

[1] why not start from left end and jump rightward? No I think there’s no symmetry in this problem. From Node 1 the immediately-reachable nodes are a continuous region.

longest consecutive ints]O(N) #zebra

Popularity — 1000+ likes on Leetcode … possibly popular

Q(Leetcode): Given an unsorted array of integers, find the longest consecutive element sequence, in O(N) time. Eg: given [100, 4, 200, 1, 3, 2] return [1,2,3,4]

I call this the zebra problem because  every consecutive sequence of int is a black stripe and the gaps between them are white stripes. We want the widest black stripe. Obviously, each stripe has minimum size 1.

https://github.com/tiger40490/repo1/blob/py1/py/array/zebra.py is my O(N) solution, not tested on Leetcode.

========

What’s UnionFind? A reusable technique?

Like inserting interval #merging #80% done, I  feel this is a data structure problem,

To keep things simple, i will first run one iteration to remove all duplicate items.

I will use hashtable where key a known item. The value is a pointer to a “segment” object.

A segment stores the min and max values. All integers within [min, max] of the segment are always known-items during my scan of input array.

When a new item is either min-1 or max+1, we expand the segment by adjusting the extremes…

The trick is joining two segments, without link pointers. After joining, we don’t really adjust the min/max fields. We only update the max-length global variable if needed.

To keep the hashtable small, I can optionally delete from it but we don’t want to do a range delete within the loop — O(NN)

git | list all(and only)commit hashes from branching point to a descendant commit

Background — Suppose you made 3 commits on your feature branch name “parix”, but meanwhile, someone added 4 commits in master branch. Therefore there is now a divergence in the commit history graph.

Often times you need to visualize the divergence. You need to exactly what 3 commits are on your branch after the common ancestor.

git log master..pairx # listing the 3 additional commits in pairx branch, right after the common ancestor i.e. the branching point

git log pairx..master # to show those 4 commits.

generate combinationSum compositions #backtrack up] trie+tree

Q: https://leetcode.com/problems/combination-sum/description/

Given a set of unique candidate numbers and a target number, find all unique combinations of candidates, where each combination sums to target. Each candidate may be used repeatedly.

My solution is https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/comboSum.cpp , showing a reusable backtracking technique described below. However, the backtracking relies on a key insight. Suppose we have target = 7 and X=2,Y=3,Z=4 as the candidates.

  • when we try a Y, we don’t need to try any more Xs. For example, If we are trying XY, then all XX* solutions are already handled by earlier recursive calls.
  • each combo sequence is naturally pre-sorted. A blessing … but also a curse when X+X+Y anre Y+X+X are considered two distinct formulas. Latest code in github can support this requirement too.
                 root
          x        y     z
      /   |  \
     x    y   z       
    / \   | \  \
 xxx  xxy | xyz \ 
         xyy     xzz
void //can return something if needed

recurs( solutionsFound &, //growing
        curPartialSolution &, 
// above collections could be global variables, to simplify things

        remainingCandidates, /*probably an immutable global array. 
If we need the remaining array to shrink, we can still rely on startIndex to skip used candidates.*/

        gapFromTarget, 
        startIndex, //used to select from remaining candidates
) 

Inside this function, we scan remaining candidates starting from startIndex. Typically in one iteration

  1. we add a new candidate into curPartialSolution
  2. we call recurs
  3. we remove the last added candidate from curPartialSolution to restore the original curPartialSolution — backtracking up the tree.
  4. move on to the next candidate

irrational envy for all-round high flyer peers

When I first identify an acquaintance as an all-round high flyer, his (her) “note-worthy” achievements were invariablly rather few, thanks to my automatic filter on his other “success” stories … becasue those kinds of “successes” are, at a deep and personal level, unimportant to me. But then those things insidiously sneak past my defence into my inferiority complex and /infest/. Extremely irrational and 不值得.

I would rather feel inferior to someone (I know well) with many unrelated yet worthy achievements [3]. I doubt there’s any in my circle.

Incidentally, when a public speaker is introduced on stage, the audience often hear a list of “successes” which are mostly unimportant to me.

(Even though none of them is a friend I know well enough) Over the years there were a small number of acquaintances [1] I have singled out. Once I singe one out, I tend to lose my critical thinking and see many unimportant/insignificant/secondary “achievements” as enviable. Critical thinking is badly, badly needed at such a juncture!

Incidentally, one of the most effective ways to feel not-inferior is a lucrative job offer, even if I don’t take it.

The initial “enviable achievements” are usually one of these 5
1) income, almost always managerial [2]
2) investment, mostly property
3) beautiful wife
* fitness, flexibility and body shape
* short commute

The other factors are usually (as they should) in my “don’t-care/unimportant-to-me” list, but they sneak into my inferiority complex.

* (multiple) degreed from prestigous universities? Actually most of them are inferior to me!
* academic kids
* competitions and awards to himself or kids
* branded employers? many of them have fewer than mine
* running his own side business? I did while many of them didn’t
* wife professional career
* work-life balance… “easy job”? Questionable. Most high-paying jobs require effort
* writing and music skills? I achieved more than most of them!
* publications
* cars? is a liability not an asset!
* green card
* vacations to many places? Huge cost, no real gain for me
* magerial success at an erly age
* golf skills? i couldn’t care less when I’m not losing my critical thinking.
* networking skill, smooth personality? I’m not this type

[2] as soon as I hear the MD title of some ex-classmate, I lose my critical thinking defence.

Better consider [[compassion and self hate]] and Buddhist teaching

[1] Beside ML, Here are some questionable names. Many of them I barely know the name and job title, so my inferiority is fundamentally similar to my infatuation over the Indonesian girl Sandy, whom I spoke to fewer than 3 times.
* Lu Nuo — I only know he has a writing hobby …
* Cai Hongyu
* Tao YY — I don’t really know how he is doing
* Yang Yang
* Xie Xiaoli

[3] briefly on myself — math, piano, c#, swing, properties, blog, helping friends with job hunting

maximum path sum through binTree #untested 70%

Q: (Leetcode “hard” Q124) Given a non-empty binary tree of signed integers, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from any starting node to any node in the tree along the parent->child connections. The path must contain at least one node and does not need to go through the root. No uplink

====analysis====

optimal solution(?) — DFT. Along each root-to-leaf path, use the max-subarray (Kadane) algo and store maxSumEndingHere value in each node, for reuse.

prior knowledge can make you look brainy: algo IV

After solving the min-stack problem, I found something paradoxical , even nonsensical — Someone said this question is considered “easy”, but if you have not seen it before then you may find it extremely hard. I thought O(1) worst case was impossible. I have experienced many similar situations where prior knowledge can make you look very brainy.
  • example — detect loops in a singly linked list, where the loop could be far out.
  • example — reverse an extremely long singly linked list which breaks any recursive solution, so you must use non-recursion
  • example — in a regular unsorted binary tree (every node has up to 2 child nodes and no uplink to parent) how to print all nodes in-order but with O(1) additional space and O(N) time
I feel west coast (and Bloomberg) tend to ask this type of questions because they expect their candidates to study and acquire the knowledge before applying.
If you don’t study, and hope to come up with a reasonable solution on the spot, then you must be extremely intelligent or lucky. I think the math Olympiad gold medalists also need to study before their competitions.

tech design “debate” with mgr

Some pointers from Rahul and other colleagues

  • [GS] pick your battle
  • manager will be the one holding the baby after you leave the team.
  • I feel I need to pay attention to the para-linguistics, and not focus solely on the technical side
  • I tend to hold strong views on design question that aren’t really major. I tend to argue and hold my ground even when it’s really a minor design decision. I appear stubborn and argumentative when I suspect the decision makers have not fully understood my points. Once I see that manager completely understands my arguments, I would stop pushing.
  • I feel i should put a limit on how much time I’m “costing” my mgr. After mgr has spent, say, 10 minutes listening to my points, I should probably “give up”.
  • [MS] Mgr probably hopes that I accept the collective decision and be “happy”, not reluctantly ..
  • [MS] need to avoid giving the impression that I have made up my mind about which design is best and only here to persuade.
  • [MS] need to avoid giving the impression that I’m not really open to new input
  • [MS] try to show unbiased .. without a favorite, even though my proposal is clearly my favorite
  • I hope to strike a balance between striving for a better design, and minimizing conflict
  • Try to detach the egos from the competing designs

order partially filled then cancelled

Three scenarios: (Assuming a big order to sell 9M)

  1. client doesn’t like the partials so far, and cancels the rest of the order
  2. IOC limit order is partially filled because … at the requested price level there’s not enough quantity
  3. IOC market order is partially filled since there’s not enough quantity.
    • This is uncommon, but possible for an illiquid stock and big order.

order slice^execution: jargon

An execution is also known as a fill, often a partial fill.

  • A slice is part of a request; An execution is part of a response to some request

A slice can have many fills, but a fill is always for a single request.

  • An execution always comes from some exchange, back to buy-side clients, whereas
  • A request (including a slice) always comes from upstream (like clients) to downstream (like exchanges)
  • Slicing is controlled by OMS systems like HFT; Executions are controlled by exchanges.
  • Clients can send a cancel for a slice before it’s filled; Executions can be busted only by exchanges.