why I said you looked too dissatisfied

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

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

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

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

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

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

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

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

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

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

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

Advertisements

staircase problem #CSY@Bbg

Q (bbg question posed to Shanyou): given a ladder of height N (eg 3), you can reach it by steps 1,1,1 or 1,2 or 2,1, or 3. Generate all paths.

Shanyou gave a recursive solution and interviewer asked “Can you find a non-recursive solution”?

I feel this is simpler than AQR factorization and the CombinationSum problems.

Is this same as N-boy-split? No. With the split, ABCB can be rearranged to ADCB

easy to test — https://github.com/tiger40490/repo1/blob/cpp1/cpp/combo_permu/staircase_CSY.cpp is my tested solution.

Open quesiton — why path count == 2N-1?

–jargon file:

a STEP from LEVEL 0 to 2 has LENGTH=2, and skips level 1; a PATH consists of 1 or more STEPS; a FORMULA is a complete PATH, and always starts at level 0 and may hit intermediate levels #2, #5, #6 …

–BFT solution. suppose N = 5. We model each path as a directory path from root. Each queue item is a path represented by a linked list or vector of capacity N.

I hope this solution avoids duplicates… Yes it does:)

  1. enqueue all “first levels” /1; /2; /3; /4; /5
  2. then dequeue and visit first path i.e. “1”. In this case, there are 4 levels remaining in the staircase, so enqueue /1/1;  /1/2;  /1/3;  /1/4
  3. then dequeue and visit 2nd path in the queue i.e. “/2”. enqueue /2/1; /2/2;  /2/3

Every time (after dequeue) we see a path has total length==N, we print it out as a formula.

–DP iterative solution

  1. build the formulas for a length-2 staircase: /1/1; /2
  2. then build the formulas for a length-3 staircase — for each of the previous formulas , prepend a step of length 1. For all but the first previous formulas, also append a step of length 1. Also add a new path of length 2.
    1. We end up with /1/1/1; 1/2; /2/1; /3
  3. for length-4 staircase, we need a SET to avoid duplicates 😦

get ideas@top100 common Q #XR

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

  • real coding
  • reading the key ideas

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

Hi XR,

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

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

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

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

max profit : at most 2H trades

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

No O() requirement.

====analysis=====

–my simple solution:

  1. Identify all the turning points so we end up with hlhlhl… We can eliminate or ignore the other points.
  2. count how many (say C) low-high couples. Ignore the first if it’s a high
  3. If C is higher than K then we just pick the biggest K couples. I think this can be done in …
  4. if C is lower than or equals K, then these C couples are the only trades to make

edit distance

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

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

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

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

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

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

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

—-
None of these ideas has proven effective.

MSOffice one-note

Confession — I’m not a laggard on adopting new applications.

😦 too bulky to back up
😦 hard to move to computers without MSOffice

Ascii text files are my default choice. I use spreadsheets when I must. I use MSWord only for equations.

I think it’s suitable for office use

🙂 save screenshots

🙂 add notes anywhere on the doc

don’t feel so bad about recursive solutions #CSY

If I only have a recursive solution and interviewer points out it could overflow the stack, then here’s my answer

"Indeed I wish there’s an iterative solution. It would be more efficient. However, if there are multiple threads available, then iterative solution might be less adaptable to use multiple threads.

As to stack overflow, I understand the run time stack space is much smaller than the heap space, so if I am given a large data set and I hit a million nested recursive calls, then I will follow standard procedure to convert my recursive solution to an iterative solution, and maintain my own stack in heap. This will relieve the pressure on stack space"

This answer applies to all your recursive solutions.