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

Advertisements

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
  • added additional tests. My implementation is basically flawless.
  • 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
  • made GC possible
  • gave wife the SPR then Singapore citizenship
  • gave me decent salary
  • supported my property investments

parent/child pairs→tree algos #Indeed

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

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.

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

coding drill≈yoga + weight loss

I had a brief discussion with my friend Ashish.. Coding test improvement is similar to weight or flexibility improvement. I also tell my son about diet control. You probably can think of many other examples.

  • we don’t notice any improvement for a long time. Still, I believe the practice makes me better than before.
    • In the absence of visible progress, Optimism and Faith is important. A pessimist tends to give up before seeing ROTI
  • when we stop the exercise, we are likely to lose part of the effort and continue the downward spiral, esp. with flexibility. See coding drill: LASTING value4family wellbeing for10Y 
  • as we grow older, we feel we tend to lose the competition, even though there’s not enough evidence.
  • it can feel boring and repetitive
  • pair exercise is easier
    • Otherwise, promise a friend

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