# iterate K pre-sorted uneven immutable lists #FB

Interviewer (Richard) was kind enough to offer me a tip early enough. so we didn’t waste time (which could easily result in out-of-time)

Q: given K pre-sorted immutable lists, each up to N items, return an iterator that on demand yields each of the (up to K*N) items in sorted sequence.

Estimate time and space complexities.

====analysis

— I first proposed pair-wise merge. Since there are logK passes, Time complexity == O(NK logK)

Space complexity is tricky. Very first pass i have to create a single list up to NK items. Then I can reuse this list in each merge. so space complexity == NK [1], but I said NK*logK. Interviewer wasn’t familiar with this solution and didn’t correct me.

[1] See https://www.geeksforgeeks.org/sort-array-two-halves-sorted/. Suppose 8 lists to merge. I will merge A+B into first quarter of the big array (size NK), then C+D into 2nd quarter… In next pass, I will merge AB + CD in-place using the first half of my big array.

The advantage of this solution — once I create a single merged array, each iteration is O(1). This can be valuable if run-time iteration speed is crucial but initial warm-up speed is unimportant.

### bigO insight — merging N pre-sorted arrays is O(N logN), same as merge sort?

— Then interviewer suggested iterating over the K lists so I implemented the solution in https://github.com/tiger40490/repo1/blob/py1/py/88miscIVQ/itr_K_presortedLists_FB.py

• Space complexity = K
• Time complexity:
• next() O(logK) due to popping. I said Fib heap has O(1) insert
• init() O(K)
• hasNext() O(1)

How about a RBTree instead of heap? Space complexity is unchanged.  Time complexity:

• next() O(logK) for both remove and insert
• init()  O(K logK), worse than priorityQ
• hasNext() O(1)

— FB interviewer asked why I prefer to keep state in global var rather than a per-record field

%%A: Runtime heap allocation is slower if the record is bigger. In contrast, the global dictionary is tiny and likely lives in L1-cache

# GS CIV:highest point]%%visible python proficiency

One of the few real pieces of evidence of progress. Average 1-2 times each year.

I should really recognize (not dismiss) the fact that, the 3 questions together represent the toughest python speed coding test I have ever taken.

GS is selective and python is relatively unfamiliar to me. Before 2019, I would not have imagined I could pass this tough coding interview.

• extreme time pressure, comparable to Indeed and FB
• unfamiliar territory — linear probing, defaultdict etc
• completed without error
• many issues encountered and resolved on the spot
• bigO analysis performed. No performance bug
• high energy, high concentration
• highest GTD proficiency ever

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

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
• gave wife the SPR then Singapore citizenship
• gave me decent salary
• supported my property investments

# engagement+spare time utilization: %%strength

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

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

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

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

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

# visible-progress: national football team

A sensible national football team (say China) should not focus solely on the World Cup as the only measurement of visible progress.

There are many other indications of progress.

It’s completely counterproductive to always point a finger and sneer “this country has never made it to the world cup”.

# q[visible progress]=Unreasonable expectations

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

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

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

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

It can be a punishment, like a flogging whip.

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

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

# distract^susFocus^engage^absorbency^visPgress^traction #Clarified

I hope to differentiate these related terms, and reduce proliferation of tags

• traction — is kind of vague and high-level, so no “t_traction”
• traction — often describes learning curve breakthrough. Defined in [11]traction(def)^learning curve gradient #diminishing ROTI
• visPgress — is more concrete and well-defined than “traction”
• (dis)engaged — describes a mental state, like “absorbed”, “enchanted”
• (dis)engaged — can be felt only from inside
• t_distract — specific distractions, often short-term like kids, e-banking…
• sustainedFocus — is often required to overcome tough learning obstacles
• sustainedFocus — can be sustained by self-discipline (absorbency) whereas engaged is often due to luck and sustained interest.
• sustainedFocus — is more a specific form of being “engaged”
• sustainedFocus — is a longer phrase compared to the honeymoon of engagement
• absorbency — is most specific
• absorbency — describes the difficulty of staying engaged despite dry, repetitive, focused learning
• t_focus@GTD tag and gzGTD category are broadly similar

Grandpa is a model of

• engaged
• sustainedFocus — but without too much self-discipline needed
• absorbency

In comparison to grandpa,

• I want to have more sustained focus
• I want longer engagement, because I tend to lose interest too soon
• I know my engagement lasts only hours, so I frequently feel a bold justification to capture the moment, perhaps at a financial cost
• my absorbency capacity is not as good as I wish
• i feel a real need to capture commute time
• I need a job that gives me more personal time, even during work hours.
• … I think these factors have profound consequences, such as my career decisions