月度归档： 2019年3月

y some backoffice tech jobs=more stressful than FO

发表于 作者 BinTAN

Paradox. Here are some answers from colleagues

  • Reason: a front office system can be very stable and mature
  • Reason: a front office system’s business logic can be fairly simple. An outsider would think business functions A/B/C/D should be part of this FO system, but in reality, they are are offloaded to other (FO or MO) systems.
  • Reason: a FO team manager can have good control on the requirements given by business and external teams.
  • Reason: even though front office users can be demanding and want immediate answers, good localSys knowledge can help you find those immediate answers. Back office users can also be demanding.

 

[16] Fwd: techies’ common complaints about jobs

发表于 作者 BinTAN

We complain about high churn, but why the hell none of us go teach math?

We complain low $ROTI but how many percent of techies get any $ROTI from personal investment or self-learning?

We complain about low (if any) lasting social value in our work, but why the hell none of us chooses an RnD career?

Hi friends,

Most techies (including developers) probably feel undervalued, and have a lot of potential not utilized on the current job.

We blame our company or our team or our job. Maybe it’s not challenging enough; maybe too repetitive; maybe too niche.

We look up at some high flyer and ask “what if I’m given that role… I may not do better than that person, but surely I will be competent and up to the job.  It may be boring and stressful but Hey I will earn so much more!”

In many over-staffed IT departments, about 20% of the roles are critical and some 20% of the roles are dedicated to “peripheral”systems that no business users care about. Perhaps that system is lightly used, and users don’t trust the output anyway.……

Well, my current (devops) job gives me a lot of opportunities to push myself higher. It’s not too niche (like Quartz/Athena/SecDB). It offers complexity and depth. Not mindless and repetitive. Not something I feel already too familiar with (and jaded). I can see the impact quickly. The impact is on many people. The impact is on front office.

Still I’m not fired-up. I guess there are always better roles out there.

We had better condition our mind not to think that way. Instead make the best use of the current role. “When life gives you lemons, make lemonade”

3Hr@knapsack problem..overspent@@

发表于 作者 BinTAN

I spent 2-4 hours implementing/refining my own knapsack DP solution — https://github.com/tiger40490/repo1/blob/py1/py/algo_combo_perm/knapsack.py

Many “peers” would consider it overspent. This kind of “conventional” view tend to destroy the precious satisfaction, the wellspring of positive energy.

Some peers complete it in a hurry and move on.

They may not compare it against the comboSum problem … x-ref is crucial to pattern recognition

They may not learn a lot by doing it quickly. I wouldn’t learn much of anything if I do that .. 囫囵吞枣

## sg19: risks@tsn

发表于 作者 BinTAN

This time my TSN attitude is not driven by fear of stagnation, but a free-spirited, fun-seeking desire to explore.

My past TSN failures (and some successes) are the best guide. Given the multiple TSN failures, my expectation is rather low. However, the pain of stigma , confidence loss, impact on family can still be very real. That’s why I wrote in my blog that the safest job is back office java+SQL+scripting with low-calibre colleagues.

StampedLock.java: lowLevel

发表于 作者 BinTAN
  • main advantage over RWlock — optimisticRead, which can reduce writer starvation by readers
  • main drawback — non-reentrant and prone to self-deadlock
  • StampedLocks were introduced in java8 only for internal/low-level utilities in the development of thread-safe “components”, with low level but complex and demanding features.

— optimistic reading using a StampedLock object
A thread can hold this object in optRead mode. This mode can be thought of as an extremely weak version of a readLock, that can be broken by a writer at any time.

Your thread would first tryOptimisticRead() to get a temporary stamp. Then validate(theStamp) would pass iFF still “free”.

After first successful validation, you should quickly read just a few data items, and validate() again to confirm availability.

Remember that, with zero notice a writeLock can be created from this object, invalidating your optRead lock.

OptRead lock is designed for quick small reads, like stealing…

This class offers too many API methods. I wonder which ones are most often used. I hope the javadoc example helps.

— stamps are long integers

https://dzone.com/articles/a-look-at-stampedlock explains the stamps superficially.

Most if not all grab attempts return a stamp that is needed for unlocking or lock level upgrade/downgrade.

— why did they design this lock as non-reentrant? Must be some performance reason.

This construct is definitely designed for experts not the casual programmer.

— relation to the (interview-wise) hotter AtomicStampedReference

I don’t see any relation.

fellow experts siz`up each other≈QQ IV

发表于 作者 BinTAN
  • Scenario — Female engineer at an electronics exhibition booth, in the 70’s.
  • Scenario — a passenger falls sick on a flight and two doctors (different countries) came to the rescue. They size up each other to decide who to take the lead.
  • Scenario — two musicians across genres play together impromptu for the first time. Musicians usually are cooperative not competitive though.
  • Scenario — a comp science student visits another campus and logs in on the local network and start exploring (not “hacking”) and encounters local students on the network.
  • Scenario — provincial basketball player coming to a new town and plays a first one-on-one game with a top local player.
  • Scenario — an interesting algo challenge is openly discussed, among programmers from different countries and across industries. A problem to be solved in any language without external tools.

These scenarios are similar to QQ interviews. (Algo interviews are subtly different but mostly similar.) Venkat of OC impressed me with his c++ and c# QQ knowledge.

When fellow experts size up each other … what acid tests can they use? Algo, QQ topics or ZZ topics (I tend to read in my spare time)?

To really size up each other, we need to discuss common topics, not Your or My localsys.

.. but many people only talk about, in vague or high-level terms, how some localSystems were supposed to work, often based on hearsay. They leave out the important details. It’s impossible to verify any of those claims.

When we watch a movie from Europe, India, Korea … we can tell whether it has any international appeal or only limited local audience.  Similarly localSys knowledge has value only within a single company. The expertise I demonstrate in job interviews are relevant across many sites.

If I were a 5Y VP (or ED) I would have self-doubt — am I just a localSys expert or an accredited expert as proven on benchmarks/interviews? Look at Shubin/Steve, the Sprite expert in London, Richard of Quoine ..
Their expertise and value-add can be marginalized in the context of the current mainstream technologies.

BFT phrasebook

发表于 作者 BinTAN

BFT is one of the top 10 heavily used constructs in coding tests.

recursion-free — BFS feels like the most intuitive algo, recursion-free.

two hits — each node is accessed twice — appended to the FIFO and then popped from the FIFO. We need to be careful what to do at first vs 2nd visits. You can get confused if not unaware this subtlety.

graph — BFT is defined on graph, not only trees

tree — BFT produces a tree … the BFT tree.

mailer — Example: send a mailer to all linkedin contacts:

# send to each direct contact
# send to each second-degree contacts …

 

[19]c++guys becom`very unlucky cf java

发表于 作者 BinTAN

See also c++developer=strongest due2hard language@@

On 22 Apr 2019 I told Greg that c++ developers like me, Deepak, CSY.. are just so unlucky — most of the WallSt c++ job interviews are too demanding in terms of latency engineering, either on buy-side or sell-side. Greg agreed that java interviews are much easier to pass. Greg said if you have reasonable java (interview) skills, then you can get a job in a week. I told Greg that the only way Deepak or CSY could get an offer is through one of the few easy-entry c++jobs, but there are relatively few such jobs i.e. without a deep moat.

  • Out of 100 java guys trying WallSt jobs, 90 are disqualified in tech screening, often in early rounds, or in “basics screening”. Too many weak candidates without depth.
  • Out of 100 c++ guys trying WallSt jobs, perhaps 70 are disqualified for the same reason. This does NOT mean your chance is higher. The remaining 30 get filtered out in later rounds, for reasons like “well-qualified but not a good match, not exactly what we want”

The expertise entry-barrier is higher in C++, partly due to wider range of essential knowledge. Java is considered more of a commodity skill, so expertise is less a requirement.

Therefore, it’s easier for me to ace the java QQ interview than c++ QQ interview.

word ladder: build graph +! test`every pair

发表于 作者 BinTAN

Leetcode Q 127: word ladder — Given two words (beginWord and endWord), and a word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

* Only one letter can be changed at a time.
* Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
* Return 0 if there is no such transformation sequence.
* All words have the same length.
* All words contain only lowercase alphabetic characters.
* You may assume no duplicates in the word list.

Example 1:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Example 2:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: 0

==== analysis:
First scan O(NN)to build the bidirectional edges of the graph. Given an existing graph of N words (N can be 1), a new word is compared against each to construct the edge list.

N(N+1)/2 comparisons. No need to be extra clever as this simple O(NN) algo is optimal for small N. No need to worry about the visualization of the graph either because the edge list is a proven representation

Aha — depending on the relative size of N and S (the standard length of every word), the optimal algo is different !

— Idea 2

Now I realize there’s a more efficient algo to build the graph, based on the neglected fact that all strings have equal length.

  • for a new word (always same length S), like abc, create S(=3) “patterns” — *bc, a*c, ab*.
  • each pattern will try to join an existing club or create a new club. Clubs are maintained in a hashtable of {pattern -> list of original words} In java or python, each word is basically a pointer to an an immutable global object.
  • If joining an existing club, then all existing club members are linked to the new word, so new word will now hold a reference to this club as an “edge list”
  • I think this algo is O(N*S). If S is small, then this algo is more efficient than O(NN)

At the end of this phase, if beginWord and endWord belong to disjoint sets then return 0. However I see no simple implementation of disjoint set. Therefore, I will run 2nd scan O(N+E) BFS. But there are many cycles, so we need a hashset “Seen”, or array of size N.

Insight — Array is more elegant than hash table in this case.

To compare two words, char-wise subtraction should give all zero except one char. This last routine can be extracted to a “simple routine to be implemented later”, so no need to worry about it in a white board session.

[17]predict 2-5Y job satisfaction #OC surprise

发表于 作者 BinTAN

Q: did the learning actually help with my job interviews (am not salary-focused like Mithun)? This is a key feedback.
A: Yes to some extent

The “table” is subject to frequent change, so I keep it in recoll (was a google sheet). Here some notes:

  • stigma/appreciation/respect(zbs) — turns to be the #1 key to job satisfaction, but appreciation is tricky. Bonus can break it, performance review can break it, other things can break it too. I often felt like “damaged goods”.
    • In Mac and Stirt (and OC too), managers considered me good enough for transfer to other teams.
    • retrospective can be more negative than dissatisfaction then-n-there, for Macq, Stirt
  • salary + other income — turns out to be insignificant when I have inner confidence and self-esteem. It is still one of the most important factors. When it’s very high, it overrides almost everything else.
  • distractions — do hurt my O2 for GTD, zbs development and self-learning
  • traction — positive feedback, includes zbs growth, instrumentation, self confidence, IV, catching up or surpassing peers
  • strategic orgro/stagnation — turns out to be a white elephant.
  • Many of the top factors are “perceptions” rather than “hardships”
    • perceptions — self-esteem@comp; strategic tsn; engaging… #best eg@perception — peer comparison
    • hardships — mkt depth (job pool size); workload; family time; commute; salary

! OC job was actually not bad if there were some appreciation from boss. However, the new, strategic specialization didn’t bring enough satisfaction.

! Verizon job experience was rather positive. I was on the rise, in my prime. It all ended when I moved to GS. I should have quit GS earlier. Citi was the start of another prime period. Prime mostly in terms of self-confidence, self-esteem …

My prediction — to have a satisfying (not necessarily strategic) job next time,

  • I need the #1 factor — appreciation.
  • A well-paid java job will mostly likely make me feel good.
  • LearningSomethingNew and engagement will NOT be a deciding factor (Recall c#/py experiences). I will still make time to learn something, just like in 95G

 

web2.0[def] IV need no j/c++insight..our t-investment lost#500w

发表于 作者 BinTAN

I attended a few technical interviews at web2.0 [1] type of companies over the years — google, amazon, VMWare … and recently Indeed, Facebook and some well-known Chinese tech shops.

These Interviewers never asked about java/c++ language details or data structures (as implemented in standard libraries), or Linux+compiler system knowledge. ( I know many of these shops do use java or c++ as firm-wide primary language.) They do require data structure knowledge in any language you choose.

My conclusion from these experiences — if we compete for these jobs, we can’t rely on the prior interview experiences gained from all the financial-domain tech interviews. Wall St vs West Coast are too different, so much so that Wall St essential tech knowledge is not useful for west coast interviews.. We have to leave that wealth of knowledge behind when we start on a new journey (to the West) of learning, trying (trying our luck at various interviews), failing and retrying.

Michael Jordan once quit NBA and tried his hand at professional baseball. I see ourselves as experienced basketball players trying baseball. Our interview skills, interview practice, in-depth knowledge of crucial interview topics have no value when we compete in west-coast interviews.

West cost shops mostly rely on algo interviews. You can use any (real) language. The most common are java/c++/python. You just need a tiny subset of the language knowledge to compete effectively in these coding tests. In contrast, financial firms quiz us on much wider and deeper knowledge of java/c++/c#/Linux etc.

Q: What if a west-coast candidate were to try the financial tech jobs like ibanks or hedge funds etc? I think they are likely to fail on those knowledge tests. I think it would take more than a year for them to acquire the obscure knowledge required at high-end financial tech jobs. In contrast, it takes months to practice a few hundreds leetcode problems. You can decide for yourself which side is more /impenetrable/ — Wall St or West Coast.

Ironically, neither the west-coast algo skill nor the financial tech obscure knowledge is needed in any real project. All of these high-end employers on both coasts invent artificial screening criteria to identify “cream of the crop”. What’s the correlation of on-the-job performance to a candidate’s algo skill and obscure knowledge? I would say zero correlation once we remove the intelligence/diligence factors. In other words, algo skill or obscure knowledge are poor predictors of job performance, but intelligence/diligence are good predictors.

In the bigger picture, these tech job markets are as f**ked up as decades ago, not improving, not worsening. As long as there are big salaries in these jobs, deep-pocketed employers will continue to use their artificial screening criteria. We have to play by their rules, or get out of the way.

— [1] web2.0 defined

I call them “web2.0” shops — second wave, second generation of Internet tech powerhouses.

Some of them are focused on cloud, AI, bigData, but usually with a deep integration, heavy reliance on the Internet ecosystem.

One day, I may apply to a new-age tech shop not related to the Internet, but the tech questions are the same. Therefore, I may have to keep my definition of web2.0 fluid and vague.

%% pure-algo/dStructure skill@recent CIV

发表于 作者 BinTAN

Hi Friends,

Over recent (about 12) months I have attempted several coding interviews

  • passed a Standard Chartered pure algo test over phone, short questions but non-trivial
  • probably passed a big weekend coding assignment given by an e-commerce start-up. I later found out my solution is similar to a published topological sorting algorithm so my algo is probably close to optimal.
  • passed another weekend big coding assignment given by Nasdaq
  • passed two separate paper+pencil coding tests at two reputable sell-side firms (i.e. banks or brokers)
  • passed a speed coding test at a reputable internet company headquartered in Texas.
  • probably passed a few bloomberg coding tests, both remote and onsite, on computers or whiteboard.
  • (All recent failed coding tests happened at High-frequency trading shops .. very picky.)

All of these positive experiences convinced me that my algo and esp. data structure skills are improving. So I gave myself a rating of “A-minus” among Wall Street candidates. I felt esp. confident with white-board coding — with a real compiler, my proficiency is lower than other candidates.

Then I failed, on technical ground, at two big internet companies (FB and … let’s say company XX). Ironically, these were white-board pure-algo problems involving non-trivial data structures — my traditional strengths. So what’s going on? Unexpected failures deserve analyses.

— First, I think I was still too slow by their standard. One interviewer (at XX) told me they wouldn’t reject candidates because of slow completion, but I believe that’s not what she actually meant to say (She is not native speaker). Suppose a candidate takes a long time to come up with a sub-optimal solution, I actually believe given more time he would find an optimal solution because I am that type of candidate. But interviewers would have to assume he is weaker than those who complete the optimal solution quickly.

Interviewers often say they look out for thought process, but that’s probably something they look out for in-addition-to finding decent solutions in time. I think I tend to show clear (not always correct) thought process but that’s not enough.

I think those interviewers really look for “near-optimal solutions but not because candidates memorized it before hand”, so candidate need to 1) find good solution 2) be able to explain when challenged.

— Second, I think the competitors are stronger (faster) than on Wall St. I call them “west-coast competitors” though they could be working in any country, all competing for west-coast tech jobs. I guess they practice hundreds of problems at Leetcode. Such heavy practice doesn’t guarantee success but increase their winning chance.

— Third, I think my big-O estimate needs improvement. I made multiple mistakes at XX coding rounds, and elsewhere.

Big-O has never been a show-stopper in my Wall St interviews so I didn’t pay close attention on details.

— Fourth, I think I have not tried often enough. If I keep trying similar internet companies I might get lucky and score a technical win.

—-

Given the stiff competition and high standard at west coast coding tests, I now feel it’s extremely important to set intermediate goals

  1. goal — pass some quick algo quizzes given by west coast interviewers over phone. I used to get those quizzes from Google phone round
  2. goal — pass some initial (simpler) coding round via webex/coderpad
  3. goal — impress at least one interviewer at one coding round. I can often sense that an interviewer is delighted to hear my idea
  4. goal — impress multiple interviewers, even if your solution is not optimal. I achieved this at Bloomberg
  5. goal — pass all coding rounds at a reputable west-coast tech shop — which is my original goal, never achieved
  6. goal — 100% technical win i.e. pass all technical rounds including system-design-interviews. Note you can still fail the soft skill test.
  7. goal — get an offer

With these intermediate goals, the picture is no longer black and white, but grayscale. We might have hit some of the intermediate goals already 🙂

##dry$valuable topics 4 high(absorbency)period #flight

发表于 作者 BinTAN

This ranking was originally compiled for “in-flight edutainment”. Warning — If high churn, low accu, low traction, or short shelf life then the precious absorbency effort is wasted

See also the pastTechBet.xlsx listing 20+ tech topics and comparing their mkt-depth, demand-trend, churn-resistance … My conclusion from that analysis is — any non-trivial effort is either on a niche or a non-growing tech skill, with notable exceptions of coreJava+threading. All mainstream and churn-resistant skills need only trivial effort.

  1. coding drill — esp. the hot picks. Look at tag “top50”. Practice solving them again quickly.
    • 😦 low accu?
  2. java concurrency book by Lea. More valuable than c++ concurrency because java threading is a industry standard reference implementation and widely used.
  3. java tuning, effJava,
  4. c++ TMP?
    • 😦 seldom asked but might be asked more in high-end interviews. TMP is heavily used in real world libraries.
    • 😦 low traction as seldom used
  5. effModernC++
  6. linux kernel as halo?
    • 🙂 often needed in high-end interviews
    • 😦 low traction since I’m a few layers removed from the kernel internals
    • 😦 no orgro
  7. c++11 concurrency features?
    • 😦 low traction since seldom asked in-depth

friend-circle #Union-Find#60%

发表于 作者 BinTAN

Q (Leetcode 547 union-find): There are N students in a class. Some of them are friends, while some are not. If A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

— analysis:
Rated “medium” on leetcode but my Design #1 is easier than many “easy” questions. Clearly this is a data-structure question … my traditional stronghold.

Challenge is merging.

— design 3: island count by BFS, but I think DFS might be easier

— design 1:
lookup map{studentId -> circleId}
Circle class{ circleId, presized vector of studentId}

When we merge two circles, the smaller circle’s students would /each/ update their circleId. This merge process has modest performance but simple.

In reality, students outnumber circles, so here’s an alternative ..

— design 2:
map remains same (Not optional!) .
Circle class is now {circleId, parentCircleId (default -1)}

The swallowed circle will have this->parentCircleId set to a top-level circleId… Path-compression as described in disjoint set.
The merge would only update this one field in one or more Circles. O(H) i.e. height of tree. H is usually very small because at any time, each circle’s parentCircleId is either -1 or a top-level circle — I hope to maintain this invariant.

Scenario:

  1. circles AA, BB, CC created
  2. circle a2 acquired by AA
  3. circle a3 acquired by a2 ultimately “branded” by AA
  4. circle b2 and b3 acquired by BB
  5. a2 swallows b2 –> need to update BB as acquired. When we try to update b2.parentCircleId, we realize it’s already set, so we follow the uplink to trace to the top-level node BB, and update ALL nodes on the path, including b2 as b2 is on the “path” to BB, but do we have to update b3 which is off the path? Suppose I don’t. I think it’s safe.
  6. circle c2 acquired by CC
  7. c2 now swallowed by b3. Now c2 will get branded by AA, and so should the nodes on the path ( b3 -> BB -> AA) This chain-update would speed up future mergers. Should C2’s old parent (CC) also get branded by AA? I think so.

After the data structures are fully updated, we simply return the count of top-level circles. (Each time a top-level circle gets created or disappears, we update that count.)

Additional field in Circle: The vector of studentId is needed only if we need to output the individual students in a given circle.

competitive strengthS offer different$values #speedCod`/math

发表于 作者 BinTAN

— update:

if you are fast at coding, your skill is easily recognized and valued! Depth of market
if you are good at cooking, your skill is easily recognized. Depth of market
if you are good at stock or FX trading?
if you are good at gadgets? Better get hired at a profitable firm
if you are good at GUI design?
if you are great at sports? Very few can make it to the professional league
if you are great at writing (Bo Rong?)
if you are great at music instruments or Singing?
If you are great at drawing?
if you are great at public speaking? Very few can make a living
if you are great at teaching kids? Singapore private tution centers would be good

—-

  • competitive strength in speed coding contest — such contest are now more prevalent and the skills are more valued
  • competitive strength in dStruct/algo beyond the classics
  • competitive strength in core cpp QQ
  • competitive strength in core java QQ — bigger job market than cpp
  • competitive strength in socket QQ
  • competitive strength in SQL QQ (and perl GTD) — better than swing
  • competitive strength in math before college level — huge and long-term impact
  • competence in localSys — no long-term impacts, so Ashish’s t-investment is unwise
  • improvement in yoga and fitness

In each “competitive” case, you build up competitive strength over H years but may lose it in K (could be long) years. Each strength has very different long-term impacts and long-term value, not “zero” (transient) as we sometimes perceived them to be.

Any Valuable resources (including a lucrative job) are scarce and invites competition. A competitive strength (in any one of these domains) has long term impact on my health, mental aging, stress level, my job choices, my commute, amount of annual leave.

For a concrete comparison, let’s compare speed coding vs math. In school, math is far more valuable. It enhances your physics, chemistry, economics… There are many math competitions at various levels.  After we turn 30, math, in the form of logical and number-theory quizzes, still plays a small part in some job interviews. However, speed coding strength (am building) now has such an appreciating value on the high-end competitive interview scene.  Over the next 10Y, speed coding will have far more impact on those aspects listed earlier.

However, if you want to invest in building such a strength, beware of huge disappointments. You can say every woman’s natural beauty has imperfections when you see that woman everyday. This is because our idea of perfect beauty is based on paintings and photos, not live humans. Similarly, every endeavor’s ROTI has imperfections compared to our naive, idealized concepts.

If you look for imperfections you will always find some, but such fixation on imperfections is cynical, demoralizing and unproductive research.

We need to zoom into our own strategic strengths + long term interests such as low-level, theoretical stuff, pure algo, dstruct, and avoid our weaknesses.

  • low level or theoretical QQ — my strength
  • low level investigation using tools + codebase — my weakness
  • picking up new GTD challenges — my relative weakness but I did well before joining Wall St.
  • picking up new IV topic — my relative strength

balloon burst #DP optimization #50%

发表于 作者 BinTAN

Q [ Leetcode 312]: not really classic : Given n (up to 500) balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array “nums”. You are asked to burst all the balloons one by one. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. Find the maximum coins you can collect by bursting the balloons wisely.

If you burst a leftmost balloon, you collect 1*it*rightNeighbor coins. In other words, when multiplying 3 numbers, any absentee is a one.

0 ≤ nums[i] ≤ 100

Example: Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
==analysis:
int-array optimization problem.
Might be related to some classic problem.

Let’s define a generic math-function of 3 balloon IDs score(myle, me, myri). In this problem, score() is simply “return myle*me*myri “, but in the next problem, score() could be any math function of the three inputs.

I see each possible snapshot (having K balloons, i.e. at level K) as a graph node. Exactly 2^N nodes in the grid, i.e. 2^N possible snapshots i.e. 2^N combinations of these N balloons.

Every edge has a score. To compute the score, we only need the two nodes (snapshots) of the edge to identify the 3 balloons for score().

Pyramid — Let’s assume at bottom is “origin” i.e. snapshot of the original array ..Level 500; on top is “phi” i.e. snapshot of the empty array .. Level 0.

The problem transforms into a max path sum problem between these 2 nodes.

–solution-1 DP
From origin to any given node, there are many distinct paths each with a total score up to that node. If a node has 55 paths to it, the max sum among the 55 paths would be the uprank (upward rank) of the node.

If the node also has 44 paths from phi, the max sum among the 44 paths would be the downrank (downwrd rank) of the node. This is an interesting observation, but not needed in this solution since every edge is evaluated exactly once.

To our delight, uprank of a node AA at Level-5 depends only on the six Level-6 parent node upranks, so we don’t need to remember all the distinct paths to AA:). Our space complexity is the size of previous level + current level.

We just need to compute the uprank of every node at Level 6, then use those numbers to work out Level 5…. the Level 4 … all the way to phi.

If there are x nodes at Level 6 and y nodes at level 5, then there are 6x==5y edges linking the two levels.

Time complexity is O(V+E) i.e. visit every edge.

Level n: 1 node
Level n-1: n nodes
Level n-2: nc2 nodes
…
Level 2: nc2 nodes
Level 1: n nodes
Level 0: 1 node

Each node at level K has K child nodes above. This graph now suggests the max-path-sum algo (with edge scores), but it might be the only way to solve the problem, like the bbg odometer.

consider a DP algo to update the score at each node at level K, ie the max sum from root till here, via one of the K-1 nodes at level K-1

But Level 2 has too many (N-choose-2) nodes. Can We prune the tree, from either origin or phi?

competitors to x86 instruction set

发表于 作者 BinTAN

Interviewers often focus on x86 instruction sets, but I could point out competing instruction sets.

  • IBM’s PowerPC and Oracle’s Sparc — were a pair of once-popular instruction sets in HighPerformanceComputing. Even if they are less popular now, the still have a presence.
  • AMD64 — instruction set (i.e. x86-64) was created at AMD, as an extension on x86
  • IA-64 — instruction set was created at HP then Intel, widely deployed in data centers.
  • ARM — If interview is not 100% focused on server-side, then I would point out ARM instruction set is dominant in handheld.

if external lib return object by pointer #Rahul

发表于 作者 BinTAN

My colleague Rahul used some external library util and found out it returns a pointer. We briefly discussed the implications. Here are some afterthoughts.

  • Pattern — if I pass in an original object by reference, the lib util may return a wrapper object by pointer.  In such a context, is this wrapper object on heap? Always?

I would say usually on heap. But since the lib implementation is invisible, it may do other things.

In an alternative design, the library could update an object pre-existing in a ring buffer (or 3D matrix) and make it a wrapper. There’s no heap allocation in this round trip. The ring buffer itself could be previously allocated on heap or data segment, not as a local object in main() function. Reason — main() can end before other threads 😦

  • Pattern — if I pass in some parameters, the lib util could create a brand new object, based on my parameters. So in this context is this new-born on heap? Always?

I would say usually on heap. But since the lib implementation is invisible, it may use non-heap.

In a specialized design, the library could return singletons held in a lookup table. The singletons are usually pre-existing in heap or data-segment.

Q: Now suppose the library does return a new heap object, who would be responsible to release the memory?
A: One common design (Sutter) requires the library factory to own it. Reference counted smart pointers are useful, as the factory knows the reference count of the new heap object.

Q: Now suppose the library factory returns a new heap object by raw pointer, who would be responsible to release the memory?

late fill: fills after order is closed

发表于 作者 BinTAN

In FIX protocol, the concept of “closed order” is not so well defined IMO — I would say an order is closed after it is cancelled, expired, fully filled, rejected, replaced, DFD (closed for current day), , ,

Broker can send exec report on a closed order, known as a late fill, usually as a protocol violation.

As a buy-side, is it OK to ignore the late fill? Is it OK to pass on the late fill to other systems?

## sg19 java QQ to brush up

发表于 作者 BinTAN
  • — jxee
  • [10=10 min ]
  • [20] Containers
  • Cloud native? LG
  • JPA? LG
  • — other ecosystem items
  • containers, cgroups
  • jdk tools for heap analysis
  • tuning best practices
  • GC in general? bookish ok
  • Ajax integration? no one asked
  • — coreJava
  • java8/9 fundamentals?
  • high-level concurrency tools — how they are related to the low-level. Lower mkt value than low-level tools
  • serialization? not popular in IV
  • advanced generics like wildcard? not popular in IV
  • reflection? not popular in IV

c++factory usually heapy

发表于 作者 BinTAN

Java factory has little (any?) choice, but focus here is c++ factory techniques. I think it usually has to manufacture on heap.

In specialized cases, my factory can maintain a private pre-allocated object pool, carved out from heap, so the factory returns objects from this pool, without calling new().

To my surprise, some c++ factories actually return by value, as illustrated in both [[c++cookbook]] and https://herbsutter.com/2013/05/30/gotw-90-solution-factories/ RVO and move-sematics would likely kick in.

longer u stay,more localSys nlg≠⇒safer #SXA

发表于 作者 BinTAN

As I said in this blog, FTE-dev is often worse off than contractors.

I think if you stay for many years without moving up while some of your colleagues move up, you may or may not get a stigma.  Some of the newer members may become your manager:) But this is not the main focus here.

The longer you stay, the more knowledgeable about local system. Hopefully more relaxed and less stress? Partly true but very dangerous slippery slope. You hope that you can live comfortably under 80% of the earlier /intensity/, but I think it won’t happen in most ibanks [1].

In my observation, most VP-level old timers operate under /unrelenting/ pressure (“threat”) to maintain high productivity. They are expected to be more proficient and more productive than earlier, not allowed to slow down and take it easy … No semi-retirement here. Otherwise, they would fail the peer benchmark against other VPs.

When I posed this question to XiaoAn, who stayed in one Oracle post-sales field support job for 11 years, he agreed that the expectation indeed grows higher. I said these old-timers often look tired and /stressed out/ by the responsibilities, but now I think many managers have a zen attitude — Larry, Josh

Another Part of the threat comes from hungrier, younger colleagues able to reach (and then surpass) half your speed within a year or two, driven by /formidable/ brain-power (energy, intelligence, ..)

[1] There are exceptions but I only know a few so I don’t want to spend too much analyzing. Exception — if you were the original architect and you keep an eye on the evolution of your brainchild, and remain knowledgeable about it, but this scenario requires some brain-power.

That’s the harsh competitive reality even if you don’t seek increasing responsibilities. A small percentage of the people are ambitious ladder climbers. (Am clearly not, because at my current level I already feel the heavy workload.) Other people (the majority) I talk to want an “easy life”, not increasing responsibilities. However, If you don’t take up increasing responsibilities, you may become too expensive [2]. You may get a token bonus. I think you may even get a humiliating bonus.

Overall, in “peacetime” long service without moving up can feel embarrassing and uncomfortable for some individuals. (It’s more noticeable if most of the peers at your level are much younger, as in Macq and OC.) Some corporate cultures may tolerate but stigmatize that.

Employer claim they prefer employees staying longer rather than shorter. That’s blatant propaganda. In reality, some employers wish some old timers to leave on their own, to make way for younger, cheaper fresh blood [2]. GS annual 5% cull in peacetime is widely-reported in WSJ, Independent... A few common motivations:

  1. Old timers are sometimes perceived as obstacles to change, to be removed.
  2. some employers believe younger, newer workers are cheaper and more motivated on average
  3. Whenever a new manager comes in he would bring in his old friends, otherwise he is seen as weak.

Down turn? All hell breaks loose. Rather than protecting you, your long service track record may make you vulnerable[2]. You may be seen as an opportunity to “replenish fresh blood”. In contrast, the less-productive but newer colleagues may show potential, and the hiring manager don’t want to look bad — hiring then firing new guys. In other words, it’s sometimes safer for the manager to sacrifice an old timer than a recent new hire — consider my GS experience. This is different from my Stirt experience.

[2] Overall, old timers are not really safe, despite localSys advantage. Consider Jack Zhang, Arif (6Y veteran)

My personal biased conclusions —

  • no such thing as long service recognition. No such thing as two-way commitment.
  • If you can be replaced cheaper, you are at risk. The more you earn, the more risky
  • If you are earning above the market rate then you need enough value-add, regardless how long you have served.

brank ≈ luxury car #white elephant

发表于 作者 BinTAN

What’s in common between a luxury car and a brank like “Director”?

  • enviable, glamorous, glorifying
  • high maintenance, high visibility
  • you need some minimum personal capacity (“performance“) to maintain it over a long time
  • can wear out quickly, esp. when you age
  • Not a passive income generator,
  • perhaps not a reliable cash-cow asset,

My contractor job is like a mid-range reliable Japanese car.

prevalence@speed coding among coding-IV

发表于 作者 BinTAN

25-33% of my past coding IV (counted by hour) were tough Speed-coding. The remaining hours were

  • Easy speed-coding problems, easy to me
  • no-coding Pure-algo quizzes, often telephonic
  • Take-home assignments
  • Threading
  • latency engineering
  • test of language knowledge
  • SDI without implementation

— west-coast coding IV≅speed-coding contest

The skillset is unneeded on any job. For GTD or PKI, this skillset is not in top 10

You need everything fast. Many students practice heavily to gain speed.

 

float/int 1:1 mapping#java support

发表于 作者 BinTAN

See last paragraph of https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/package-summary.html …

you can use an AtomicInteger to hold byte values, and cast appropriately. You can also hold doubles using Double.doubleToRawLongBits(double) and Double.longBitsToDouble(long) conversions… because there’s a valuable 1:1 mapping between a 64-bit number and a 64-bit float number.

  • Useful if you need to precisely compare a 64-bit float value. For example, you can check if a value has changed at all. The value could be user-supplied or shared mutable.
  • Useful if you need to store float values in a hashtable, though I’m not sure about performance.
  • Useful if you need radix sort on floats

##any domain fac`same IV quizzes 20Y on #socket !! c++11

发表于 作者 BinTAN

(tagline: the most churn-resistant specializations.)

Socket IV questions have remained unchanged for 20Y — Unmatched stability and churn-resistance, but not necessarily accumulating

  • Preservation of t-investment
  • Preservation of accumulation
  • Preservation of deep learning? Socket programming has modest depth.

Q: Beside the specialization of socket programming, are there other specializations that are dominated by the same old QQ questions 20 years on?

  • [S] classic data structures
  • [S] classic sort/search algorithms on int-array, char-array, list ..
  • [S] classic traversal algorithms on trees, general graphs
  • [s] classic recursive, DP, greedy algorithms beyond graphs
  • [S] pre-c++0x core-C++ (a specialization!) questions are largely unchanged. C++11 questions are rooted in the old knowledge base.. BUT most of the c++11 QQ topics will likely fall out of interview fashion
  • [s] cross-language concurrency primitives.
  • unix file/process/string/signal manipulation
  • unix shell scripting — low market value
  • [S] SQL — including join, index design … but seldom quizzed in depth nowadays
  • [S] regex — seldom quizzed, but often needed in coding
  • [S=classic, well-defined specialization]
  • [s=slightly less well-defined specialization]

Now the disqualified skills

  1. JGC + jvm tuning — high churn over 20Y
  2. TMP — new features introduced in c++11

## strategic TSN among%%abandoned

发表于 作者 BinTAN

Q: name the most strategic trySomethingNew domains that I have since abandoned, given up, quit. How about the new plan to take on coding drills as a lifelong hobby?

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

  1. — ranked by surprise
  2. algo trading? actually very few roles spread across a number of firms
  3. c#
  4. drv pricing quant
  5. real time risk as in GS, Qz and Athena
  6. RDBMS tuning
  7. MOM, async, message-driven design knowhow
  8. distributed cache like Coherence and Gemfire
  9. Solaris sys admin and DBA
  10. perl, SQL, Unix/Linux power-user knowledge? No longer a top 10 focus

—-

  • python? Not yet abandoned
  • web dev for dotcom? I did this for years then abandoned it. Many of the tech skills are still relevant like sessions, java thread safety, long-running jobs

EnumSet^regular enum

发表于 作者 BinTAN

[category javaOrphan]
A java enum type usually represents .. (hold your breath) .. a radio-button-group. A variable of this type will bind to exactly one of the declared enum constants.

eg: Continent — there are only 7 declared constants. A Continent variable binds to Africa or Antarctic but not both.
eg: SolarPlanet — there are only 8 declared constants
eg: ChemicalElement — there are only 118 declared constants
eg: ChinaProvince — there are only 23 declared constants

In contrast, enum type has a very different meaning if used within an EnumSet. (I will name a meaning soon). Each enum constant is an independent boolean flag. You can mix and match these flags.

Eg: Given enum BaseColor { Red,Yellow,Blue} we can have only 2^3 = 8 distinct combinations. R+Y gives orange color. R+Y+B gives white color.

Therefore, the BaseColor enum represents the 3 dimensions of color composition.

EnumSet was created to replace bit vector. If your bit vector has a meaning (rare!) then the underlying enum type would have a meaning. Here’s an example from [[effJava]]

Eg: enum Style {Bold, Underline, Italic, Blink, StrikeThrough, Superscript, Subscript… } This enum represents the 7 dimensions of text styling.

[[effJava]] reveals the telltale sign — if the enum type has up to 64 declared constants (only three in BaseColor.java), then entire EnumSet is actually represented as a single 64-bit integer. This proves that our three enum constants are three boolean flags.

pre-allocate DTOs@SOD #HFT #ets

发表于 作者 BinTAN

example — etsflow framework pre-allocates object pool (presumably the flow elements) for the day, to avoid runtime call to malloc. Are these objects ever released to the pool? I doubt it since all of these objects are subject to query or bust.

example — RTS pre-allocates outgoing message objects from a ring buffer’s head, and “returns” to the ring buffer at the tail… See How RTS achieved 400-700 KMPS #epoll

example — Sell-side HFT OMS also uses pre-allocation. Suppose for every new order there are 3 new DataTransferObjects A/B/C to be instantiated on heap. Traditional approach would make 3 allocation requests in real time. I think the free-list manager becomes a hotspot, even if there’s a per-thread free list.

Basically HFT avoids new/malloc after market opens. RTS uses mostly arrays, and very few (rather small) STL containers. Those STL containers tend to be populated before market opens and remain static.

Pre-allocation is a popular technique. We compute at compile time the sizes of A/B/C based on their class declarations. For DTO class A, sizeof(A) just adds up the non-static data field sizes. Then we estimate how many orders we will get a day (say 7 million). Then we pre-allocate 7 million A objects in an array. The allocation happens at start-up, though the sizes are compile-time constants.

When an order comes in, the A/B/C DTO objects are already allocated but empty.

Byte-array is an alternative, but this smells like the raw free list to me…

java enum: elegant

发表于 作者 BinTAN

“Elegant” (and “clean”) is probably the best adjective. My comments below are mostly based on [[effJava]]

  • 🙂 immutable in the face of serialization
  • 🙂 strict singleton in the face of serialization .. P311
  • 🙂 simple enough to be easily embedded as a static nested class
  • 🙂 you can add behavior (and data) unique to Jupiter, using a constant-specific class body
  • 🙂 You can switch on enum values
  • compiler adds two implicit static methods values() and valueOf(), not listed on the official javadoc 😦
  • values() returns a fixed array of the predefined enum values
  • valueOf(planetNameStr) would return the matching enum instance
    • Note this method is unrelated to String.valueOf()
    • you can even add your own fromString(abbrevatedPlanetName) method. see [[effJava]]

EnumSet (see separate blogpost) and EnumMap built on the strength of enum feature

Q:are java primitive+reference on heap or stack #escape

发表于 作者 BinTAN

An old question but my answers are not really old 🙂

In Java, a so-called “referent” is a non-primitive thingy with a unique address on heap, accessed via heap pointers.

In java, a referent is always an Object, and an Object is always on heap therefore always a referent.

(Java language defines “reference types” in terms of primitive types, so we need a clear understanding of primitive types first.)

In java, a primitive thingy is either part of a (heapy) Object or a local thingy on stack

(In C++ lingo, object can be a new int(88)…)

A reference is, at run-time really a heap pointer. Assuming 32-bit machine, the pointer itself occupies 4 bytes and must be allocated somewhere. If the reference is local to a method, like a parameter or a local variable, then the 4 bytes are on stack like a 32-bit primitive local variable. If it’s part of an object then it’s on heap just like a 32-bit primitive field.

— advanced topic: escape

Escape analysis is enabled by default. EA can avoid construction an Object on heap, by using the individual fields as local variables.

— advanced topic: arrays

Arrays are special and rarely quizzed. My unverified hypothesis:

  • at run-time an array of 3 ints is allocated like an Object with 3 int-fields
  • at run-time an array of 3 Dogs is allocated like an Object with 3 Dog fields. This resembles std::vector<shared_ptr<Dog>>
  • Q: how about std::vector<Dog>?
  • %%A: I don’t think java supports it.
  • The array itself is an Object

c++QQ critical-mass[def2] has started growing!

发表于 作者 BinTAN

If I compare myself with young c++ developers or older guys (like CSY, Paul..) I can see clear patterns in QQ and GTD.

  1. QQ and (to a lesser extent) zbs — I’m clearly pulling ahead, sometimes heads and shoulders above them. Some of these guys have wider QQ knowledge but lacks depth. I wrote about “experts” sizing up each other..
  2. zbs: instrumentation — one of the key areas of improvement for me! However, I can see many of the older guys at RTS aren’t more knowledgeable.
  3. GTD: paradoxically, the younger guys are more productive than me or older guys.

— Now let’s retrace the gradual breakthrough

In May 2019, I felt I have achieved enough critical-mass on c++ QQ topics. Critical mass is defined by The two acid test questions.

Q1: without a full-time c++ job, but with enough interviews, will my c++ QQ insight/understanding show resilience against churn and memory fading, as in coreJava?
Q2: thick->thin achieved? Not yet, but cross-reference graph is now built up as a defense against fading memory

This java career review provides a valuable context.

What visible progress gave me this level confidence? Recent technical wins show my improved ranking among c++candidates.

  1. SCB-FM
  2. CVA
  3. SIG
  4. TradeWeb core team

Note I have invested more effort on c++ QQ than java… [18]t-investment: c++now surpassing java

  • — now a sample of critical-mass topics, roughly ranked by importance on high-end interviews, mostly at HFT and ibanks
  • coding tests
  • mv-semantics
  • containers
  • smart ptr
  • heap memory mgmt including new..
  • polymorphism including MI #44 posts in the category
  • TMP — important at high-end but not HFT
  • [e] pthreads + c++11 threads
  • [e] sockets
  • runtime costs of virtual and heap, as Stroustrup explained
  • [e] cache efficiency, compiler optimizations,
  • [e] linux
  • [e] new innovation directions
  • [e] benchmarks involving c++ as Stroustrup explained
  • build tools
  • [e=ecosystem topics]

##gains{Stirt job loss

发表于 作者 BinTAN

immediately after I joined Macq, I realized I have traded up for a better job, better in every way.

  • gain: self-confidence that I can comfortably handle the ensuing financial impact on family
  • gain: self-confidence that I have survived again, albeit with a scar
  • gain: a protective scar — as of 2019 I’m still traumatized but slowly I’m healing from inside
  • gain: lesson learned the hard way — avoid FTE
  • $gain: compensation package more than covered my bench time but still I prefer the … something else instead of the compensation

## Y most young developers shun contracts

发表于 作者 BinTAN

GregR convinced me that most young developers aren’t interested in Wall St contract jobs. I can’t remember the exact reasons but something like

  • no medical benefits
  • salary can drop; furlough
  • frequent job change required — often forced to change job.
  • no job security — Employers tend to cut contractors first.
  • no compensation package like golden handshake
  • no promotion no career growth
  • no bonus
  • lower chance to move away from hands-on dev and become project mgr etc
  • restricted to mostly ibanks — many young bright people are interested in buy-side or non-finance.
  • maintenance of existing codebase — Daniel Yang reportedly quit a 180k 缝缝补补 dev job
  • often requires domain knowledge that the younger developers don’t have.

In my experience the contractors I see are mostly above 40 or at least 35+. The younger guys (Nikhil..) tend to be part of a contract agency like Infosys.

https://www.channelnewsasia.com/news/commentary/covid-19-coronavirus-job-work-tip-skills-government-support-hire-12509712is a Singapore perspective: “many jobseekers turn away such contracts, choosing to hold out for something long-term that may or may not come”

The upshot — I have fewer strong competition from the young generation. Most of the older guys are not so competitive in either IV or GTD on a new job. In particular, their figure-things-out speed is on average slower than younger dev.

unnoticed gain{SG3jobs: 看破quantDev

发表于 作者 BinTAN

All three jobs were java-lite , with some quantDev exposure. Through these jobs, I gained the crucial clarity about the bleak reality of the quantDev career direction. The clarity enabled me to take the bold decision to stop the brave but costly TSN attempts to secure a foothold. Foothold is simply too tough and futile.

Traditional QuantDev in derivative pricing is a shrinking job pool. Poor portability of skills without any standard set of interview topics.

at same pay, now I would prefer eq than drv pricing domain, due to mkt depth and job pool.

QuantDev offers no contract roles !

Instead, I successfully established some c#/py/c++ trec. The c++ accu, though incomplete, was especially difficult and precious.

Without these progresses, I would be lacking the confidence in py/c#/c++ professional dev that enabled me to work towards and achieve multiple job offers. I would still be stuck in the quantDev direction.

initialize matrix with invalid value, not 0 #DP

发表于 作者 BinTAN

In simple bottom-up dynamic programming algos, we often need to build a matrix of previous results to derive later results.

In contrast, harder DP problems may need other tools, but often in addition to, not in place of, a matrix.

Q: (often neglected question): what initial value to put into matrix?

  • In some problems, the top-right triangular area is not used. So the dump() had better use some obviously invalid values to highlight the used cells. 999999 is often a reasonable choice, but then dump() would need alignment.
    • If you use the read_matrix technique discussed in another blogpost, then I think dump() should use read_matrix
  • Sometimes we can use an initial high value because the DP algo will use min() to compare. I think this is fine.
  • Zero is often a reasonable-looking initial value, but a lot of times zero is a legit vale in the algorithm ! Therefore, the initial value looks like a computed value and very confusing.

 

[19]if I had stayed ] java

发表于 作者 BinTAN

I think every tsn experience and proposal has some “buts”, so does it mean we should stop trying?

No. If I had stayed within java/sql/perl then I would have been worse off —

  • fewer job opportunities, less broadened technical base
  • slightly more worry about job security
  • more worry about churn
  • more worry about outsourcing
  • no differentiation from millions of java guys
  • left behind by some of the alpha geeks who branch out and establish new strongholds.
    • My technical mind is the BROAD-n-deep, curious explorer type so it is stifled if confined to java
  • sql and perl both falling out of fashion

But ….

  • possibly more competent in terms of figure-things-out relative to team peers
  • possibly fewer stigmas and more respect
  • ^^ These factors depend mostly on localSys knowledge
  • not so much stress, so much painful struggle in the beginning
  • possibly an architect role, provided I stay long and invest heavily in localSys

Was leverage good on my multiple tsn attempts after GS? reasonable leverage in some attempts.

checked STL^checked java Collections

发表于 作者 BinTAN

jdk checkedList, checkedMap etc are designed to check type errors — checking any newly added item has the correct type for the collection. See P 246 [[java generics]]

STL checked container checks very different coding errors. See http://www.informit.com/articles/article.aspx?p=373341, which is extracted from my book [[c++codingStd]]

biasedLocking^lockfree^ST-mode

发表于 作者 BinTAN

This is a pure QQ topic, but you can score a few points by mentioning it.

[[javaPerf2014]] P268 says biased locking is enabled by default but can be disabled to improve performance in app servers using a thread pool and contended locks. It explains the reason i.e. biased locking comes with a price — a runtime overhead.

https://stackoverflow.com/questions/9439602/biased-locking-in-java is very concise — un-contended locking may incur zero cost, as claimed in the accepted answer

  • .. incurs no synchronization cost. I suppose this is typically geared towards overly conservative code that performs locks on objects without ever exposing them to another thread. The actual synchronization overhead will only kick in once another thread tries to obtain a lock on the object.
  • Biased locking is the default in java6 ====> -XX:+UseBiasedLocking improving the performance of uncontended synchronization. An object is “biased” toward the thread which first acquires its monitor; subsequent monitor-related operations are relatively faster. Some applications with significant amounts of uncontended synchronization may attain significant speedups

Is this technique considered lockfree? No, but some may speculate that it might be even faster than lockfree. So if you suspect most of the time there’s only one thread accessing a critical section, you could choose to rely on the (java6 default) biased locking rather than lockfree solution. Most of the time this mutex-based design would challenge (if not beat) a lockfree performance.

However, I believe single-threaded mode is still faster, where a thread isn’t aware of other threads, as if it is the only thread access those objects i.e. no shared-mutable. There would be no lock grab, no memory fencing at all. [[javaPerf2014]] P375 agrees.

Q: which linux c++thread is stuck #CSY

发表于 作者 BinTAN

This is a typical “c++ecosystem question”. It’s not about c++ or C; it’s about linux instrumentation tools.

Q1: Given a multi-threaded server, you see some telltale signs that process is stuck and you suspect only one of the threads is stuck while the other threads are fine. How do you verify?

Q2: What if it’s a production environment?
A: I guess all my solution should be usable on production, since the entire machine is non-functioning. We can’t make it any worse.  If the machine is still doing useful work, then we should probably wait till end of day to investigate.

–Method: thread dump? Not popular for c++ processes. I have reason to believe it’s a JVM feature, since java threads are always jvm constructs, usually based on operating system threads [1]. JVM has full visibility into all threads and provides comprehensive instrumentation interface.

https://www.thoughtspot.com/codex/threadstacks-library-inspect-stacktraces-live-c-processes shows a custom c++ thread dumper but you need custom hooks in your c++ source code.

[1] Note “kernel-thread” has an unrelated meaning in the linux context

–Method: gdb

thread apply all bt – prints a stack trace of every thread, allowing you to somewhat easily find the stuck one

I think in gdb you can release each thread one by one and suspend only one suspect thread, allowing the good threads to continue

–Method: /proc — the dynamic pseudo file system

For each process, a lot of information is available in /proc/12345 . Information on each thread is available in /proc/12345/task/67890 where 67890 is the kernel thread ID. This is where ps, top and other tools get thread information.

 

closestMatch in sorted-collection: j^c++^python

发表于 作者 BinTAN

Both of the above operate on sorted arrays. C++ also has

— java has the cleanest yet rich interface. P236 (P183 for Set) [[java generics]] lists four methods belonging to the NavigableMap interface

  • ceilingEntry(key) — closest entry higher or equal
  • higherEntry(key) — closest entry strictly higher than key
  • lowerEntry
  • floorEntry

2 threads taking turn #std::ref #CSY

发表于 作者 BinTAN

Vanguard Q: write a program containing exactly 3 threads printing 1/3/5/7/… 2/4/6/8… respectively, but in lock steps, as if passing a token between them.

https://github.com/tiger40490/repo1/blob/cpp1/cpp/thr/takeTurn.cpp is my solution.

I managed to avoid sleep() and condVar. The idea — all thread run the same function which

  1. check the shared mutable variable Next. If it’s “my” turn then
  2. grab lock, print my next number, update Next, release lock
  3. end-if
  4. yield and exit

I used an atomic<char> “Next” set to lastOutput%something, that’s visible to all threads, even if not holding a lock.

 

contains(): Set^SortedSet

发表于 作者 BinTAN

–in java # See P247/32 [[java generics]]

  • Set<Acct> contains() uses Acct.equals()
  • SortedSet<Acct> contains() uses Comparable<Acct> or a custom comparitor class, and ignores Acct.equals()

–In STL

The tree-based containers use “equivalence” to determine containment, basically same as the java  comparator.

The hash-based containers use hashCode + a equality predicate. The implementation details are slightly complicated since both the hash function and the predicate function are template params. Upon template instantiation, the two concrete types become “member types” of the host class. If host class is undered_set<string>, then we get two concrete member types:

unordered_set<string>::hasher and unordered_set<string>::key_equal

These member types can be implemented as typedefs or nested classes. See ARM.

%%AuxDS strength ] coding test #algoQQ

发表于 作者 BinTAN

Update — Indeed experience..

  1. when a tough problem requires us to construct an explicit and non-trivial auxiliary data structures (AuxDS), i often have an intuitive feel for the data structures needed, not always the optimal.
  2. when a tough problem requires a simpler AuxDS + unusual algo, I don’t have an edge.
  3. When a tough problem requires only an unusual algo, I don’t have an edge.
    * eg: edit distance
    * eg: sliding window max
    * eg: maximal sub-matrix

    • Suggestion: invest in algoQQ. I feel they will stick with me.

Can C implement basic containers@@

发表于 作者 BinTAN

Templates — I think template is unavailable in C, and I don’t know how C could emulate it, except using macros.

C doesn’t support exceptions but luckily very few exceptions in STL.

Most STL container classes have relative few member functions. I think C can implement free functions with “this” as an additional parameter.

Bulk of the basic operations on container are global functions in the form of STL algorithms. I think C can implement them.

Iterators are tricky. In STL I think they are usually nested classes. I think I would just give up. C supports no operator overloading so there’s no point providing an iterator.

##STL iterator is implemented as ..

发表于 作者 BinTAN
  • implemented as raw ptr — if your data is held in an array
  • implemented as member class (sugarcoated as member typedef) — most common
  • implemented as friend class
  • implemented as wrapper over internal container’s iterator — (cheat) if your custom container is kind of wrapper over an STL container, then just use the internal container’s iterator as your iterator.

Remember an iterator class is a form of smart pointer by definition, since it implements operator->() and operator*()

##java8 features #MethodRef

发表于 作者 BinTAN
  • lambda
  • default methods
  • streaming
  • method references? Supposed to be an important feature in the core language/syntax. related to lambda syntax, presumably a syntactic sugar coating.
  • java.util.Optional<T> introduced to reduce NPE. Compare boost::optional
  • CompletableFuture<T> to promote async, event-driven programming
  • PermGen disappears in java8
  • –not really java8 features:
  • java7 introduced G1 garbage collector though default GC remains ParallelGC, for both java8 and java7

pureDev beats techLead: paycut is OK #CYW

发表于 作者 BinTAN

My hypothesis based on discussions with CYW:

Bottom line –YW said if the pure tech salary is only 20k lower, then he may prefer the workload. The work-life balance, the freedom-from-care and simplicity .. are often highlighted by my tech-lead friends (like Su form GS?), though I suspect most of them still take tech lead roles (or higher).

A techLead has (usually difficult) deliverables for multiple business groups pushing for conflicting priorities. The techLead also need to enlist support from external teams. As such, he as nontrivial additional workload including supervising his own team members, managing users, liaising with other teams … all in addition to he development workload.

  • 😦 吃力不讨好
  • 😦 It’s not easy to mobilize other people to work for your deliverables.
  • 😦 The extra workload often requires overtime. RTS’s Venkat might be an example when he claimed he works 7 days a week.

The power dynamics is based on loyalty. Some big boss might value your loyalty more than your GTD capacity. Loyalty is tricky investment. If you invest in loyalty to big boss A, but A gets replaced by big boss B (as often happens), and B invariably brings in his own loyal lieutenants, then you have a problem. I think Jerry Zhang (Citi) faced this situation when Srini took over.

Unlikely the tech lead, the typical pure-tech contributor doesn’t need to demonstrate loyalty.

I think some senior developer roles are pure-tech-contributors.

both DEPTH+breadth expected of%%age: selective dig

发表于 作者 BinTAN

Given my age, many interviewers expect me to demonstrate insight into many essential (not-obscure) topics such as lockfree (Ilya),

Interviewers expect a tough combination of breadth + some depth in a subset of those topics.

To my advantage I’m a low-level digger, and also a broad-based avid reader. The cross-reference in blog is esp. valuable.

Challenge for me — identify which subtopic to dig deeper, among the breadth of topics, given my limited absorbency and the distractions.

##java heap allocation+!explicit q[new]

发表于 作者 BinTAN

Most of these are java compiler tricks. Here are a few java heap allocations without explicit q[new]

  • (pre-runtime) enum instance instantiation — probably at class-loading time
    • P62 [[java precisely]]
  • String myStr = “string1”; // see string pool blogpost
    • P11 [[java precisely]]
    • NOT anonymous temp object like in c++
  • “string1” + “str2” — is same as myStr.concat(..). So a method can often new up an object like this.
    • P10/11 [[java precisely]]
  • boxing
  • (most tricky) array initialization
    • int[] days ={31,28,31/* instantiates the array on heap */};
    • most tricky
    • P17 [[java precisely]] has examples
    • P16 [[java precisely]] also shows an alternative syntax “new int[]”

crypto exchange revenue #hearsay

发表于 作者 BinTAN

–Jasper wrote “Trading Fees: When it comes to crypto-to-fiat trading pairs, there are no fees. As for crypto-to-crypto pairs, 0.15% of transaction value for market takers and -0.075% of transaction value (a rebate) for market makers is the rule.”

$100M daily trading volume is a figure I heard. $150k of fee income, assuming 15 bps fee.

I guess the rebate is like a income tax rebate. Market makers still pay a fee but a lower fee than market-takers.

–one-time listing fee

I was told that some creator of new crypotocurrency pay $5mil to a popular exchange for a listing. It’s a one-time listing fee.

 

market-depth^elite domains #jxee

发表于 作者 BinTAN

I used to dismiss “commodity” skills like market data, risk system, JXEE… I used to prefer high-end specializations like algo-trading, quant-dev, derivative pricers. In reality, average salary is only slightly different and a commodity job can often outpay a specialist job.

As I get older, it makes sense to prefer market depth rather than “elite”(high-end niche) domains. A job market with depth (eg jxee, market-data, risk systems) offers a large number of positions. The typical salary of top 10% vs the median are not very different — small gaps. In contrast, the elite domains feature bigger gaps. As I grow older, I may need to reconsider the specialist vs generalist-manager choices.

Reminders about this preference (See also the spreadsheet):

  1. stagnation in my orgradient
  2. may or may not use my specialist skills in math, concurrency, algorithms, or SQL …
  3. robust demand
  4. low churn — a critical criteria whenever I mention “market depth”. I don’t like the market depth of javascript and web java.
  5. salary probabilities(distro): mgr^NBA#marketDepth etc

–case study: Algo trading domain

The skillset overlap between HFT vs other algo systems (sell-side, OTC, RFQ, automated pricing/execution..) is questionable. So is “accumulation” across the boundary.  There seems to be a formidable “dragon gate” — 鲤鱼跳龙门.

Within c++ based HFT, accumulation is conceivable. Job pool is so small that I worry about market depth. My friend Shanyou agreed that most of the technical requirement is latency. C/C++ latency techniques are different from java.

However, HFT developers seldom need to optimize latency

Outside HFT, the level of sophistication and latency-sensitivity varies. Given the vague definition, there are many (mostly java) jobs related to algo trading i.e. better market depth. Demand is more robust. Less elitist.

jvm footprint: classes can dominate objects

发表于 作者 BinTAN

P56 of The official [[java platform performance]], written by SUN java dev team, has pie charts showing that

  • a typical Large server app can have about 20% of heap usage taken up by classes, rather than objects.
  • a typical small or medium client app usually have more RAM used by classes than data, up to 66% of heap usage take up by classes.

On the same page also says it’s possible to reduce class footprint.

mgr|risk| promotion=hazard #AlexV@MS

发表于 作者 BinTAN

My reflections after a discussion with Alex Vinokur. “mgr” in this context means any lead role.

When I feel left behind on the slow track, it’s usually in comparison to the manager peers. Alex knows some Morgan Stanley developer. The guy rose to ED but after a while, he wanted hands-on development so he stopped managing teams and became a very senior developer. But his performance/value-add was bench-marked against those hands-off manager EDs. After a while, presumably he was seen as too expensive as a developer and got the golden handshake in Mar 2019.

When Alex told me this story, I gave this illustration — Suppose with hard work I am competent at Level 5 (mid-level VP) and very comfortably at Level 4 (junior VP) but struggle a bit at Level 6 (ED) when bench-marked to Level 6 peers. In such a case, for job safety I may want to remain at Level 5 rather than moving up. For an easy life, I may even prefer Level 4. If I get promoted to Level 6 I face stiff peer competition, from guys competent at Level 6. The benchmark-risk can be real. 高处不胜寒

When you get promoted to Level 6, you can’t avoid the peer bench-marking. You will get bench-marked, like it or not. I find this peer bench-marking unhealthy and hazardous, but Alex is very explicit when describing the benchmark/calibration system in many firms. GS 360-degree review system explicitly asked reviewer not to give the same score to 3 reviewees if there are 3 at that level. Basically, the system wants to identify the bottom 5% performers, even if all of them are doing a good job.

Promoted to a lead role, your chance of survival can drop, unless you decide to give up the leadership role and return to a non-leader role.

Conclusion — Better remain at a level you can perform well relative to peers.

## Grandpa+AshS: 随遇而安@PIP #GS

发表于 作者 BinTAN

grandpa’s advice is 随遇而安 — “Do your best. If they decide it’s a role mismatch then look for another job”. I will expand on his advice and add relevant tips and observations

  • academic self-image .. fragile — Ashish pointed out I was academically too successful and unable to cope with put-downs
  • best effort — I don’t need to bend over backward and sacrifice family
  • no shame
  • no fear of stigma — sounds impossible but it is possible !
  • no regret
  • guilt — the guilt should be on employer for making a wrong hire and creating hardship in my life.
  • stay positive — there’s a chance I can survive for 1-2 years
  • peer caliber — Ashish said those guys aren’t rock stars
  • Saurabh attitude — I believe at a high salary or as the first technology hire for Julian, expectation would be rather high. Can I withstand the pressure as Saurabh did?
  • GS pressure cooker — I survived there, so I should be able to survive anywhere else.
  • learning to cope — At GS/Qz/Macq, did I learn coping strategies to manage the pressure? I hope so.

The pressure to perform would likely create real stress in the family, as i’m not as ‘carefree’ as in Bayonne. I feel some of the past stigmas would come back to haunt me.

See also choose job for respect,stigma,benchmark

 

try{}must be completed by ..#j^c++^c#

发表于 作者 BinTAN

— Java before 7 and c#
try{} should be completed by at least a catch or finally. Lone wolf try{} block won’t compile. See https://www.c-sharpcorner.com/UploadFile/skumaar_mca/exception-handling-in-C-Sharp/

In particular, try/finally without catch is a standard idiom.

— java 7:
try{} should be completed by a catch, a finally, both or none .. four configurations 🙂

The try/finally configuration now has an important special case i.e. try-with-resources, where the finally is implicit so you won’t see it in anywhere.

— c++ as of 2019
C++ has no finally.

try{} must be followed by catch.

rvr(+lvr)usually shows up as function param ONLY

发表于 作者 BinTAN

r-value reference is a type, and therefore a compile-time thing, not a runtime thing as far as I know. At runtime, there’s no r-value reference variable,

only addresses and 32-bit pointer objects.

(I believe at runtime there is probably no lvr reference variable either.)

Compiler recognizes the RHS’s type and decides how to bind the RHS object to a variable, be it an rvr-variable, lvr-variable, nonref-variable, or const-lvr-variable.

About the only place I would use a “&&” variable is a function parameter. I don’t think I would ever need to declare a local variable or a field with “&&”.

Do I ever assign an rvr variable as a RHS to something else? Only in one case, as described in [[effModernC++]] P162 and possibly Item 25. This kind of usage is only needed for QQ interviews and never in any job…. never. It’s too tricky and doesn’t buy us anything significant.

RTS feed for Internet clients #Mark #50%

发表于 作者 BinTAN

Q: Based on the RTS market data dissemination system, what if some clients subscribe by a slow Internet connection and your orderbook (TCP) feed need to provide delta updates each time a client reconnects?

Default solution: similar to FIX/TCP .. sender to maintain per-client state. Kenny of Trecquant said his trading app can be extremely simple if exchange maintains state. I won’t elaborate. Here is my own Solution.

Note on terminology — in multicast there’s no TCP-style “server” . Instead, there’s a sender engine for many receiver clients.

Suppose we have too many clients. To minimize per-client state management, my engine would simply multicast to all clients real time updates + periodic snapshots.

A client AA can request a snapshot on any symbol group, and I will immediately multicast the snapshots on a refresh channel. If client BB never requests anything, BB can ignore the refresh multicast channel.

Request quota — each client like AA can request X free snapshots a day. Beyond that, AA’s requests would be regulated like

  • levied a fee
  • queued with lower priority

It’s feasible to replace the refresh multicast group with an unicast UDP channel per client, but to me the multicast-refresh solution offers clear advantages without major drawbacks.

  1. if there is an outage affecting two clients, each would request the same snapshots, creating unnecessary work on the engine. The request quota would incentivize each client to monitor the refresh group and avoid sending the same request as someone else
  2. multicast can be valuable to clients who like more frequent snapshots than the periodic.
  3. My operations team can also utilize this refresh channel to broadcast unsolicited (FreeOfCharge) snapshots. For this task, I would avoid using the publisher channel as it can be busy sending real time updates. We don’t want to interleave real time and snapshot messages.

[19] body-build`does hit low visPgress#leverage,disengaged

发表于 作者 BinTAN

In Singapore (but very few NY 🙂 jobs, I noticed a pattern — the longer I stayed on a stable job, the lower I dropped in motivation, incentives and positive feedback/reinforcement for IV body-building including QQ, coding..

Every time I pass a non-trivial tech screening, I feel a real boost … Reinforcement of absorbency and reinforcement of a wellspring of energy lasting a few days to a few months … sometimes years thanks to my retrospective blogging. My Singapore experience is missing this crucial IV element. Without it, my absorbency of dry technical learning is hard to sustain. This also explains why my absorbency of localSys is hard to sustain.

(My son has never experienced such positive reinforcement.)

To gain perspective I find it necessary to compare with other endeavors. My conclusion — body-building has the highest leverage. See also meaningful endeavor(Now)4family: IV^zbs^gym..

Whenever I feel guilty/ashamed of my fixation on IV, and try to learn zbs, localSys, GTD etc,  eventually (often quickly) I hit a broken reinforcement loop and a weak or depleted “energy supply” and invariably give up, very rationally.

Q: is there any /endeavor/ with higher visPgress than IV body-building?

chores that require absorbency visPgress #immediate $ROTI leverage over long-term, on family well-being
body-building Yes in the form of blog+github… not $$ [1] reasonably high, given huge $gain and huge t-investment 😦 higher leverage than everything else combined [2], despite the churn
… cf localSys highly visible respect, not $$ ->necessary but insufficient condition for move-up
non-prop investment easily visible but small low given the small profit no leverage so far
yoga (+ fitness) some but hard to keep $zero high leverage, well-known
diet for BMI highest but hard to keep $zero 😦 low since it’s hard to keep up

[1] I think many of my peers can’t keep up the body-building effort precisely because there’s no $ROTI… personal projects: any ROI ] salary@@
[2] direct fruits of the endeavor:

  • made my nice TPY home possible
  • enabled me to move between countries
  • made GC possible
  • gave wife the SPR then Singapore citizenship
  • gave me decent salary
  • supported my property investments

mixing log4j logger.info + System.out.println

发表于 作者 BinTAN

log4j.rootCategory=INFO, sysout
log4j.category.package1=INFO, logfile

Given this log4j.cfg content,

  • package1 classes’s logger output would go to log file specified
  • other packages’s logger output would go to sysout
  • System.out and System.err would go to sysout
  • In my dev system, sysout messages are saved to a separate sysout log file.

I have seen that System.out is less likely buffered.

ibank c# shops moving to java #Ellen+Sunil

发表于 作者 BinTAN

Update — a c# veteran in OC said server-centric systems prefer java, while client-centric systems still prefer c#. The OC c# system was server-centric, so presumably he has witnessed the decline of c# in his own space.

I also confirmed with two Wall Street WPF veterans that browser GUI systems have grown in capabilities and can now emulate WPF. These systems leverage on west coast innovations with javascript.

—-

A Singapore banking recruiter shared with me her observation. I had earlier spoken to her a few times and she had earned my respect for her insight.

She said a few Singapore ibank departments were using c# before but now hiring java developers instead. I said c# is a newer language and I have never heard of such a migration. She didn’t address that but said java is apparently more open-source than c#.

I think this is a relatively isolated case. Some time in the past or future you may see java shops moving to c#.

She is very close to Standard Chartered bank (a c++ shop, as she acknowledged) and said SCB is hiring more java developers than before.

She said nowadays just about the only Singapore employers of c++ is HFT. I disagree. SCB, Macq and some ibanks still use some c++.

She said java is now the dominant language for internet companies, to my surprise. She said there’s now improving mobility between java developers in ibanks vs internet shops. I think she meant the big-data java roles, not core-java roles.

She said the SG banking job pool is dominated by java — out of 10 jobs, 9 are java jobs — “crazy” as she said. I guess less than half of those 9 jobs are coreJava.

hands-on dev beats mgr @same pay

发表于 作者 BinTAN

BA, project mgr, even mid-level managers in some companies can earn the same 160k salary of a typical “developer” role. For a manager in a finance IT, salary is often higher, but for a statistically meaningful comparison I will use a 160k benchmark. Note in finance IT or tech firms, 160k is not high but on main street many developer positions pay below 160k.

As stated in other blogposts, at the same salary, developers enjoy higher mobility, more choices, higher career security…

jvm heap histogram simple console tool

发表于 作者 BinTAN

The simplest among many similar tools. This type of analysis is easier in java than in c++ because jvm manages memory allocations. In fact, GC can even relocate objects.

~$jcmd test GC.class_histogram
58161:

num #instances #bytes class name
----------------------------------------------
 1: 1020 93864 [C
 2: 481 54856 java.lang.Class
 3: 526 26072 [Ljava.lang.Object;
 4: 13 25664 [B
 5: 1008 24192 java.lang.String
 6: 79 5688 java.lang.reflect.Field
 7: 256 4096 java.lang.Integer
 8: 94 3760 java.lang.ref.SoftReference
 9: 91 3712 [I
 10: 111 3552 java.util.Hashtable$Entry
 11: 8 3008 java.lang.Thread
...

REST^SOAP

发表于 作者 BinTAN

REST stands for Representational State Transfer … basically means that each unique URL is a representation of some object. You can get the contents of that object using an HTTP GET, use a POST, PUT, or DELETE to modify the object (in practice most of the services use a POST for this).

— soap vs REST (most interviewers probably focus here) —

  • REST has only GET POST PUT DELETE; soap uses custom methods “setAge()” etc
  • SOAP takes more dev effort, despite it’s name
  • SOAP used to dominate enterprise apps, though XR used REST in ibanks.

–real REST URLs

https://restfulapi.net/resource-naming/ shows some examples. It also says

URIs should not be used to indicate that a CRUD function is performed. URIs should be used to uniquely identify resources and not any action upon them. HTTP request methods should be used to indicate which CRUD function is performed.

HTTP GET http://api.example.com/device-management/managed-devices  //Get all devices
HTTP POST http://api.example.com/device-management/managed-devices  //Create new Device
HTTP GET http://api.example.com/device-management/managed-devices/{id}  //Get device for given Id
HTTP PUT http://api.example.com/device-management/managed-devices/{id}  //Update device for given Id
HTTP DELETE http://api.example.com/device-management/managed-devices/{id}  //Delete device for given Id

importance@formal edu4tech career

发表于 作者 BinTAN

I tend to dismiss the value of formal education (including degrees) and I tend to overvalue on-the-job quick-n-dirty learning. Compared to Asia, U.S. tech culture is less fixated on formal education.

  • Eg: Some inexperienced developer colleagues seem to have a good grasp of option math
  • Eg: my theoretical knowledge of comp science is completely self-taught, including concurrency, SQL, OO,..
  • eg: A more extreme example of such a domain is DynamicProgramming + Greedy algorithms. An intelligent programmer (regardless of age) can become highly competent without formal training.

Some theoretical domains are really based on field practice such as OO design.

Even if you have a solid education, either formally, or on the job over a few focused years, we all face the same challenge of continuing education —

  1. my web dev experience (self-education) is now outdated, according my interviews at Indeed , ByteDance ..
    • But luckily there are many interviews I can attend and learn from.
  2. data science, machine learning … is not so easy to self-learn
    • luckily there are many online learning resources.

 

parent/child pairs→tree algos #Indeed

发表于 作者 BinTAN

As a speed-coding test, this problem requires you to apply common computer science constructs to a realistic problem, and then challenges you

“How many seconds do you need to build a working directed graph from raw data, and run BFT/DFT on it?”

45 minutes given. Target is to complete first 2 questions with working code. Can some candidates complete all 3 questions? I guess so.

Q: You are given some raw data like

parent_child_pairs = [ (1, 3), (2, 3), (3, 6), (5, 6), (5, 7), (4, 5), (4, 8), (8, 10), (11,2) ]

Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.

For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:

  11
   \
1   2   4
 \ /   / \
  3   5   8
   \ / \   \
    6   7   10

Q1: write a function to output all individuals having no parents(like 1 and 4) in a list, and another list of individuals having a single parent (like 8 and 7)

Q2: write a bool function to determine if two named individuals have any common ancestor. 3 and 6 yes; 3 and 1 no!

I wrote a DFT solution .. https://github.com/tiger40490/repo1/blob/py1/py/tree/commonAncestor_Indeed.py Not very efficient but I really should care less about that since the real challenge is .. timely completion. I was not used to writing DFT on the spot within minutes but I hacked it together under ticking clock, first time in my career !

To find if two sets intersect, I was forced to make a quick judgment call to write my own loop.

  • I didn’t know if there’s a simple and reliable solution online
  • i didn’t know how much effort is required to search online and understand it
  • i didn’t know how much effort is required to adapt standard solution to suit my needs
  • My own loop gives more legwork but more control if requirements turns out to be non-standard.

Q3: (original wording) Write a function that, for a given individual in our dataset, returns their earliest known ancestor — the one at the farthest distance from the input individual. If there is more than one ancestor tied for “earliest”, return any one of them. If the input individual has no parents, the function should return null (or -1).

Sample input and output:

findEarliestAncestor(parentChildPairs, 8) => 4
findEarliestAncestor(parentChildPairs, 7) => 4
findEarliestAncestor(parentChildPairs, 6) => 11
findEarliestAncestor(parentChildPairs, 1) => null or -1

Docker containers

发表于 作者 BinTAN

Container is widely used in cloud computing; Docker is a “popular new kid” in jxee, probably not in coreJava.

https://jaxenter.com/nobody-puts-java-container-139373.html is not too shallow, and not too deep. Free of marketing propaganda.

  • containers are standard Linux processes running a shared kernel, not isolated kernels

https://www.redhat.com/en/topics/containers/what-is-docker addresses several confusions and then contrasts raw linux containers with docker containers.

— docker and container

The word “Docker” refers to several things, including

  • tools from an open source project;
  • additional tools from Docker Inc., the company that primarily supports that project

Here’s a brief explainer:

  • The software “Docker” (community or commercial) is containerization technology that enables the creation and use of Linux® containers.
  • The company, Docker Inc., builds on the work of the Docker community, makes it more secure, and shares those advancements back to the greater community. It then supports the improved and hardened technologies for enterprise customers.

I feel docker is a facade/wrapper over raw linux container features.

The tools built on top of Linux containers—what makes Docker user-friendly and unique—gives users unprecedented access to apps, the ability to rapidly deploy, and control over versions and version distribution.

Indeed: hearsay algo questions#speedPractice

发表于 作者 BinTAN

Q: The first interview consisted of interviews with two separate people. The first asked for a function that takes in a string of words separated by spaces and prints the first duplicate word. The second asked for a function that takes in two sorted unique int arrays and returns an array of the duplicates between the two arrays.

Q: Implementing an LRU = Least recently used cache. Question was I have a cached of storing just 50 objects now how do you make sure you have unique 50 elements in a cache adding 51 should kick out least recently used one from that 50 objects.

Q: Shunting Yard Algorithm

containers+MSA: cloud-affinity

发表于 作者 BinTAN

I feel both the MSA architecture and the low level container technology can have a long-term impact thanks to cloud.

The implementations might be replaced by newer implementations in a few years. but some of the ideas may evolve. Now is still the volatile early phase… ##[17] proliferation → consolidation.. beware of churn

Both of them are easy to launch on elastic cloud

Both of them can be started on multiple machines as a wolf pack to handle bigger workload.

11 notable features added to c++

发表于 作者 BinTAN

https://en.cppreference.com/w/cpp/language/history briefly mentions

  • [90] exception handling
  • [90] templates
  • [98] cast operators
  • [98] dynamic_cast and typeid()
  • [98] covariant return type
  • [07] boost ref wrapper .. see std::reference_wrapper
  • [11] GarbageCollector interface .. See c++ GC interface
  • [11] std::next(), prev(), std::begin(), std::end() .. see favor std::begin(arrayOrContainer)
  • [11] exception_ptr? not sure how useful
  • [14] shared_lock — a RW lock
  • [14] shared_timed_mutex .. see try_lock: since pthreads
  • [14] std::exchange — comparable to std::swap() but doesn’t offer the atomicity of std::atomic_exchange()

cpu sharing among Docker container for jvm

发表于 作者 BinTAN

Note cgroup is also usable beyond jvm and Docker, but i will just focus on jvm running in a Docker container..

Based on https://jaxenter.com/nobody-puts-java-container-139373.html

CPU shares are the default CPU isolation (or sharing??) and basically provide a priority weighting across all cpu time slots across all cores.

The default weight value of any process is 1024, so if you start a container as follows q[ docker run -it –rm -c 512 stress ] it will receive less CPU cycles than a default process/container.

But how many cycles exactly? That depends on the overall set of processes running at that node. Let us consider two cgroups A and B.

sudo cgcreate -g cpu:A
sudo cgcreate -g cpu:B
cgroup A: sudo cgset -r cpu.shares=768 A 75%
cgroup B: sudo cgset -r cpu.shares=256 B 25%

Cgroups A has CPU shares of 768 and the other has 256. That means that the CPU shares assume that if nothing else is running on the system, A is going to receive 75% of the CPU shares and B will receive the remaining 25%.

If we remove cgroup A, then cgroup B would end up receiving 100% of CPU shares.

https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/6/html/resource_management_guide/sec-cpu has more precise details.

https://scoutapp.com/blog/restricting-process-cpu-usage-using-nice-cpulimit-and-cgroups compares q(nice), cpulimit and cgroups. It provides more precise info on cpu.shares.

cpulimit can be used on an existing PID 1234:

cpulimit -l 50 -p 1234 # limit process 1234 to 50% of cpu timeslots. The remaining cpu timeslots can go to other processes or go to waste.

Leetcode speed-coding contest #Rahul

发表于 作者 BinTAN
  • don’t look at ranking
  • yoga — I CAN keep up this practice. This practice is good for my mental health and family well-being
  • yoga — I feel even if i don’t improve visbly, the fact that my participation count is increasing means I’m improving
  • if I don’t do the contest then I may not do any coding drill at all
  • What if I give up after one or a few episodes?
  • impact on family well-being?
  • leverage over long term?

In [[who moved my cheese]], we discover the world has changed. The harsh reality is, in this profession, your experience (like doctors) is heavily discounted. Your current runtime performance is easily benchmarked, just like a painter, or pianist, or chef.

G9 workhorse-algos ] speedCoding #XR

发表于 作者 BinTAN

XR said we should take speed coding contests to find out what basic algos are needed.

Opening example — parent/child pairs→tree algos #Indeed is one example of realistic problem that requires common comp-science constructs…

Need to memorize enough to implement on the spot, as these are basic “comp science constructs” needed for “realistic problems”

  • dft/bft, with levels
  • BST find predecessor
  • Binary search in array
  • Merge-sort/insertion-sort/partitioning
  • .. realistic string problems:
  • .. realistic int array problems:
  • max profit; max subarray sum
  • .. realistic matrix problems:

Below are basic algos for hackerrank/codility but NOT applicable to realistic problems typical of Indeed/FB

  • Linked list: remove dupes
  • string: collapse consecutive chars

##Java9 features #fewer than java8

发表于 作者 BinTAN
  1. #1 Most important – modular jars featuring declarative module-descriptors i.e. requires and exports
  2. #2 linux cgroup support.. For one example, see Docker/java9 cpu isolation/affinity
  3. #3 G1 becoming default JGC.. CMS JGC: deprecated in java9
  4. REPL JShell
  5. private interface methods, either static or non-static
  6. Minor: C++11 style collection factory methods like

List<String> strings = List.of(“first”, “second”);

It’s unbelievable but not uncommon in Java history —

  • Java9 release introduced significantly fewer and less impactful features than java8.
  • Similarly, java5 overshadows java6 and java7 combined

 

jvm spawns(approx)32 JGC threads on 32-core

发表于 作者 BinTAN

Based on https://jaxenter.com/nobody-puts-java-container-139373.html

jvm would spawn 32 GC threads on a 32-core box [1].  As of 2018, this is the default, but you can change it with jvm parameters like -XX:ParallelGCThreads and -XX:ConcGCThreads

Java 9 introduced automatic detection of cpu-set when jvm runs in a cgroup (such as a docker container) with a cpu-set. For example, JVM detects there are 3 cores in the cpu-set, and spawns 3 GC threads.

[1] presumably for the parallel GC or the CMS GC but i’m not sure. https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/parallel.html and https://blog.codecentric.de/en/2013/01/useful-jvm-flags-part-6-throughput-collector/ says for the parallelGC the default would be 5/8*32 + 3 = 23 threads.

wasm: a distant threat to javascript

发表于 作者 BinTAN

https://medium.com/javascript-scene/what-is-webassembly-the-dawn-of-a-new-era-61256ec5a8f6 is a good WebAssembly intro, by an author.

  • wsam is an in-browser language, like javascript
  • wsam offers low-level (web-ASSEMBLY) programming constructs to complement javascript
  • I feel wsam will only be considered by extreme-performance browser apps. It’s too low-level, too inconvenient to be popular.
  • How many percent market share will javascript lose to wsam? 0.1% to 0.5%
  • The fact that wsam is cited as the main challenger to javascript means javascript is unchallenged as the dominant choice on the browser

##[19] cited strengths@java

发表于 作者 BinTAN

In this post we compare c++, python, javascript, c#

  • [G3] Scalability and performance [1] – James Governor has a saying: “When web companies grow up, they become Java shops”.Java is built for scalability in mind, which is why it is so popular among enterprises and scaling startups. Twitter moved from Ruby to Java for scaling purposes.
  • [G9] community support [1] such as stackoverflow —
  • [G9] portability [1] — on Linux and Android.
  • [G9] versatile — For web, batch jobs, and server-side. MS is a java shop, using java for trading. but DDAM is not a typical MS app. DDAM has many batch jobs but the UI is all in web java.
    • python and c++ are also versatile
  • [G5] Java has high correlation with fashionable technologies — hadoop; cloud; big data; microservices… Python and javascript are also in the league.
  • [G3] proven —
    • web apps are the biggest market segment. Some (js/php/ruby) of the top 10 most popular languages are used exclusive for web. Java is more proven than c#, python, c++.
    • enterprise apps (complex business logic + DB) are my primary focus. java is more proven than python, javascript, php, c#
  • [G3=a top-3 strength]

[1] https://stackify.com/popular-programming-languages-2018/ explains Java’s popularity

 

real-world treeNode has uplink

发表于 作者 BinTAN

I think only in contrived interview questions do we find tree nodes without uplink.

Uplink basically, means every edge is bidirectional. With uplinks, from any node we can easily trace to the ancestor nodes.

In real world trees, uplink is cheap-yet-valuable most of the time. AVL tree node has uplink, but let’s look at RBTree:

  • RBTree needs uplink for tree rotation.
  • Also, I believe when you give an insertion hint, the “engine” needs to validate the hinted node, by checking parent + another ancestor.

scaffolding around try{}block #noexcept

发表于 作者 BinTAN

[[ARM]] P358 says that all local non-static objects on the current call stack fully constructed since start of the try-block are “registered” for stack unwinding. The registration is fine-grained in terms of partial destruction —

  • for any array with 3 out of 9 objects fully constructed, the stack unwinding would only destruct those 3
  • for a half constructed composite object with sub-objects, all constructed sub-objects will be destructed
  • Any half-constructed object is not registered since the dtor would be unsafe.

I guess this registration is an overhead at run time.

For the stack objects created in a noexcept function, this “registration” is not required, so compiler may or may not call their destructors.

— in http://www.stroustrup.com/C++11FAQ.html#noexcept Stroustrup hints at the  scaffolding

  • noexcept is a efficiency feature — widely ans systematically used in standard library to improve performance
  • noexcept is crude and “very efficient”
  • dtor may not be invoked upon stack unwinding
  • stack unwinding may not happen at all

 

 

long-term value: QQ imt ECT speed

发表于 作者 BinTAN

The alpha geeks — authors, experts, open source contributors … are they fast enough to win those coding contests?

The speed-coding contest winners … are they powerful, influential, innovative, creative, insightful? Their IQ? Not necessarily high, but they are nobody if not superfast.

The QQ knowledge is, by definition, not needed on projects, usually obscure, deep, theoretical or advanced technical knowledge. As such, QQ knowledge has some value, arguably more than the ECT speed.

Some say a self-respecting programmer need some of this QQ expertise.

RAII phrasebook

发表于 作者 BinTAN

See [[ARM]] P 358and [[Essential C++] P199.

  • local — local nonstatic object required. See [ARM]]
  • dtor — is required.
  • stack unwinding — either by exception or normal return. Note noexcept may skip stack unwinding.
  • partial destruction — see other blog posts
  • scaffolding — see other blog posts
  • exception guarantee — RAII is the only exception guarantee
  • exception strategy — RAII is the best exception strategy
  • double-exception — what if an unhandled exception triggers unwinding but en-route a new exception is born? No good strategy.
  • == for memory management .. RAII is the #1 most important memory management technique.
  • memory leak prevention
  • smart ptr — example of RAII for memory management.

##tech skill superficial exposure: 5 eg

发表于 作者 BinTAN

see also exposure: semi-automatic(shallow)Accu #$valuable contexx and low-complexity topics #JGC..

  • –(defining?) features (actually limitations) of superficial exposure
  • accu — (except bash, sql) I would say very few of the items below offer any accu comparable to my core-c++ and core-java accu
  • entry barrier — (except SQL) is not created since you didn’t gain some real edge
  • commodity skill —
  • traction — spinning the wheel
  1. JGC — i think most guys have only textbook knowledge, no GTD knowledge.
  2. lockfree — most guys have only textbook knowledge
  3. [e] spring, tibrv — xp: I used it many times and read many books but no breakthrough. In-depth knowledge is never quizzed
  4. bash scripting — xp: i read books for years but only gained some traction by writing many non-trivial bash scripts
  5. SQL — xp: 5 years typical experience is less than 1Y@PWM
  6. –other examples (beware oth)
  7. [e] EJB, JPA (hibernate), JMS, Hadoop(?)
  8. memory profilers; leak detectors
  9. design patterns — really just for show.
  10. Ajax
  11. [e] Gemfire
  12. java latency tuning — is an art not a science.
    • Poor portability. JVM tuning is mostly about .. GC but at application level, real problem is usually I/O like data store + serialization. Sometimes data structure + threading also matter receives disproportionate limelight.
    • conclusion — superficial, textbook knowledge in this skillset probably won’t help with latency tuning.
  13. [e=ecosystem like add-on packages outside the core language.] Ecosystem skills are hard to enable deep learning and traction as employers don’t need deep insight. GTD is all they need.

friend to a class template

发表于 作者 BinTAN

Similar to java reflection, void pointers, reinterpret_cast etc, friend is a powerful keyword in real projects, with GTD power. The rules are a bit tricky when you combine friend + template.

I think this is a relatively useful IV knowledge pearl as it demonstrates a fundamental concept — each template instantiation (“concretized template class”) is treated as a distinct class.

[[ARM]] P351 stipulates that

* A simple non-template friend introduced into a class template is a friend to ALL instances of the class template.

That’s the simple case.

* Now another common scenario — the class template C2 has a dummy type T, and the friend is another template F3 parameterized with the same type T. Now there’s a one-to-one friendship:

  • F3<float> is a trusted friend to C2<float>
  • F3<Acct> is a trusted friend to C2<Acct>
  • …

 

 

noexcept impact on RAII

发表于 作者 BinTAN

If a function (esp. dtor) is declared noexcept, compiler can choose to omit stack-unwinding “scaffolding” around it.  Among other things, there’s a runtime performance gain. This gain is a real advantage of using noexcept instead of empty throw() which is deprecated in c++0x.

Q: Is there any impact on RAII?
%%A: yes

Q: Can we even use RAII in such a context?
%%A: I think we can. If the function does throw, then std::terminate() runs, instead of the destructors

Note Best concise intro to noexcept is P780 [[c++primer]]

meaningful mv-ctor requires heap

发表于 作者 BinTAN

I think any data type with a meaningful mv operation (including move-assignment) must use heap storage, accessed via a heap ptr.

SSO (small-string-optimization) bypasses heap, so the mv-ctor isn’t meaningful. See Item 29 of [[effModernC++]]

Built-in primitives like bool, int, float does support rvr, but no efficient move-operation. In fact, they are not class types, so no mv-ctor or mv-assignment. The compiler probably treats their rvr variables as dummies.

move()doesn’t move..who does@@

发表于 作者 BinTAN

(Note in this blogpost, when I say mv-ctor i mean move-ctor and move-assignment.)

As explained in other posts in this blog, move() is a compile time cast, no performing a physical “steal” at runtime, so

Q: what c++11 constructs performs a physical steal?
%%A: mv-ctor

  • move() ⇏ steal — std::move() may not trigger a physical steal — If you call myContainer.insert(std::move(myString)) but your custom String class has no mv-ctor, then copy-ctor is picked by compiler .. see P21 [[Josuttis]].
  • steal ⇏ move() — a physical steal may not require std::move() — if you have a naturally occurring rvalue object.
  • steal => mv-ctor

##techies’workload stress when Not slower than teammates

发表于 作者 BinTAN

I won’t put on “t_gzPain” or t_stress as these factors are not stressors in my career! The opinions below are valid based on “their” personal experiences not my experience. As such, I should  NOT overthink about these.

  • Daniel Yan of RTS cited the effect of imposed deadline by exchange
  • Several IT friends cited the fire-fighting mode
  • CSDoctor said in some companies like Huawei, there was an unhealthy culture of long office hours, eroding family time, but i think this is rare nowadays.

2 heaviest work stressors  provides a incisive introduction to the same topic.

I tend to believe that “high performance” teams tend to emphasize GTD, intensity (“productivity” and “efficiency”) … remember Macq’s Kevin. He is highly efficient and he feels’ I’m not productive enough even though there’s no one else to compare.

However, my Barcap workload was not so heavy but high-impact 🙂

My conclusion at beginning and end of this analysis — figure-things-out faster than team colleagues is still the primary determinant of stress/respect/stigma.

success@concurrency features] java^c++^c#

发表于 作者 BinTAN

I’m biased towards java.

I feel c# concurrency is less impactful because most of the important concurrent systems use *nix servers not windows, and most concurrent programming jobs do not go to windows developers.

Outside windows, c++ concurrency is mostly based on the C library pthreads, non-OO and inconvenient compared to java/c#

The c++11 thread classes are the next generation following pthreads, but not widely used.

Java’s concurrency support is the most successful among languages, well-designed from the beginning and rather stable. It’s much simpler than c++11 thread classes, having only the Thread.java and Runnable.java data types. More than half the java interviews would ask threading, because java threading is understandable and usable by the average programmer, who can’t really understand c++ concurrency features.

starting thread in ctor #Lea

发表于 作者 BinTAN

Q: is it good practice to call new Thread(..).start() in MyClass ctor? This is common practice in my projects. I feel there are always alternatives.

I feel 30% confident this blog has another blogpost on this subject, to be combined.

[[DougLea]] points out the potential danger of starting thread in your ctor, esp. if subclasses are beyond your control.

The visibility effect is equivalent to parent thread releasing an implicit lock, and acquisition by run() on new thread.

Frequently, the constructed MyClass instance is used by the new thread, but is MyClass fully constructed? It is if the new Thread(..).start() is last line in ctor, but what if this ctor runs as part of a subclass ctor?

%%perfect hash: 1000 known string keys #MLP-sg %50

发表于 作者 BinTAN

See also string bucket-sort

Q: similar to FIX tags, you are given a published dictionary of 5000 short string keys, each up to 10-characters. Every message consists of about 100 key/payload pairs. Design a parser for these messages. Note every key would be in the dictionary.

Simple solution 1 BST like AVL or RBT to hold the pairs. O(log N=5000) … 5000 keys require about 12 levels. Possibly faster than hashtable.

Simple solution 2 standard hashtable to hold the pairs. The hashcode for string is usually fast enough, with minimal collision if load factor is set sufficiently low. Even if zero collision, this requires allocating 5000 linked nodes in memory.

In this case since the key strings are known in advance, I believe we can design a perfect hashing algorithm without collision. Interviewer said perfect hashing is hard in this case.

Solution 3: perfect hashing. Group the key strings by length, to 10 groups

  • If the number of distinct 8-char keys is small, for instance, we can use switch-case
  • for 1-char string keys, we maintain a dedicated bucket array (“table”) indexed by the ascii code
  • for 2-char string keys I can have a nested 2D array. Given key string “px”, “p” identifies the level2 array and within it, “x” identifies the bucket for the payload.
  • for 3-char keys, ditto

For those 10-char string keys, a 10-level nested array would be too large. Here’s my strategy. Assuming a lot of key strings (say, 3000 out of total population of 5000) are 4-char long, let’s tackle this sub-problem first:

  • for 4-char keys, I would designate an index range like 1 to 6000 (6000 buckets) to hold 3000 keys in this group. I would compute an initial hashcode := (char1*31+char2)*31+char3… % 6000 for this group of 3000 key strings and check for collision within this group. If there’s collision, then adjust some of the prime numbers and retry. Since load factor is 0.5 I hope we can avoid collision within this group. If it’s hard to avoid collision, I can reduce load factor, or introduce my collision resolver[2].
  • for 5-char keys, I would designate an index range like 6001 to 7800 (1800 buckets) to hold 900 keys in this group. I would compute initial hashcode := (char1*31+char2)*31+char3… %1800 for this group of keys and check for collision within this group.
  • So far, we have designed with a big combined bucket array. As an alternative, if there are only 7 key groups [4-char, 5-char, .. 10-char] then we can use seven dedicated bucket arrays, but what if 7000 groups? 7000 bucket arrays? I think so. Memory footprint is same as a combined bucket array.

[2] Here’s a simple collision resolver. Suppose Strings A and B(and C,D..) all hash to the same initial-hashcode of 55. I need to find another bucket for B. After I compute all the initial-hashcode values for each of 3000 key strings, I can easily find an unused bucket like 77. I will simply add an if-block to use bucket 77 for key B. Now this scheme is probably faster than open-addressing and separate chaining since the calc logic can be manually optimized , held in instruction-cache, or burned into FPGA. In contrast,

  • Separate chaining requires runtime memory access to follow the linked nodes. We can only hope the linked nodes are cached
  • open addressing requires runtime probing. Our load factor of 0.5 is not very good so open addressing can become slow.

http://www.dre.vanderbilt.edu/~schmidt/PDF/gperf.pdf is a published perfect hashing solution.