2018-12 在职刷题保持状态， 每天1题+ML insights

EE PhD今年5月毕业，在职湾区某养老院。为了phd 3年半毕业， 目前的职位是在phd老板压迫下毫无找工时间被迫从了。与其一直拿着那点stipend被压着当paper machine，不如主动跳出来，一边挣钱养家一边继续刷题找工作。BS,MS都是EE背景，phd做了statistics machine learning，cs背景比较弱，刷题时间之前几乎没有，这三个月集中刷300多，但是还是底子太虚。

16年狗家实习面，算法懂，code没写过多少，硬着头皮面， 被一波带走。
17年狗家全职，lc没怎么刷，只有时间看题想思路，最终跪在用stack写post-order binary tree traversal上....
18年毕业入职，准备奋发图强把coding和cs背景好好补补。

PhD老板至今还时不时地拉着我写paper，眼看着citation越来越高，但是自己却开始困惑迷茫了....写这么多paper的意义究竟是什么....
==========更新的分割线==============================================================
LC刷上700题， 总算对算法有了一定的自信。onsite拿了几个，L家刚刚面完，感觉还可以。ML系统性复习了一遍，把KDD近几年的几个大厂的paper都跟了跟。每天挑traffic最差的时候下班，堵车的时候用来听各种seminar，各种课程，各种talk。忙碌但是收获不小，哪怕最近这些全挂，也算是填充了不少经验。继续sys design， ML design以及参加几个kaggle的contest。加油加油！
==========再次更新的分割线==============================================================

收到L家HR的邮件，HC 准备move forward. 下一步估计是team matching，我也做好了准备随时上岸的准备。从开始认真准备到今天，一共5个月，感觉坚持和勤奋是拿到offer的唯一途径。希望后续一切顺利。
==========最终分割线==============================================================
Team matched. offer accepted. Let us call it a day.

==========重开分割线==============================================================
虽然已经上岸，但是不刷题的日子感觉略枯燥，不如每日一刷保持状态兼当娱乐啦~

Day1:
Recover from the phone interview and proceed to prepare for OA next week.
Solved 819，675,  380, 206.Learned to filter words in python with re.findall('\w+', string).
Many pending items at work and one paper revision pending...
Target 5 tomorrow.

Day4
Planned paper revision to Nature communication.
Prepared the response letter to reviewer 1 and 3. Need to work on the manuscript to reflect these responses.

Solved 793 before sleep. Notice that # of trailing zeros of x! is the min(k,t) if you can represent x! = (5^{k}*2^{t})*(rest). Since t >=k holds for all x!. Only need to count 5's as factor to x!.
class Solution:
    def preimageSizeFZF(self, K):
        """
        :type K: int
        :rtype: int
        # of zeros of x! is sum_i x//5^{i}
        """

        def numOfTrailingZ(x):
            ans  = 0
            base = 5
            while x  >= base:
                ans += x//base
                base *=5
            return ans
        #5*(K+1)! is a number that has K+1 trailing zeros
        #Search the smallest y such that numOfTrailingZ(y) == K+1
        l, r = 0, 5*(K+1)+1
        while l < r:
            mid = (l+r)//2
            count = numOfTrailingZ(mid)
            if count  > K:
                r = mid
            else:
                l = mid + 1
        y = l
        l, r = 0, 5*(K+1)+1
        #Search the smallest x such that numOfTrailingZ(y) == K
        while l < r:
            mid = (l+r)//2
            count = numOfTrailingZ(mid)
            if count  >= K:
                r = mid
            else:
                l = mid + 1
        x = l
        return y-x

Day53

Solved 265. To achieve O(nk), the key idea is to keep record of min and second min costs and asscoiated colors of painting i-1 houses. For i-th house and j-th color, if min color for i-1 not equal to j, then use min otherwise use second min.
Solved 323. Union find.

Solved 636. Very confusing start and end time that have differernt meanings.

ML reviewed:


Model-based Bayesian inference. (Model is P(y|theta))

Conjugacy:

Conjugate priors of a likelihood function is the prior distribution that, once times with that likelihood function, resulting in a posterior distribution of same family as the prior

—>The beauty is, you can start with a conjugate prior, incorporate new data, update it to a posterior and then use it as the new prior.

—>This process can continue without introducing new difficulties.

Hierarchical Bayes:

Instead of assuming the prior, you can estimated them by introducing hyper priors of hyper parameter phi on these priors. Choosing hyperprior to be proper, nearly flat.


Predictive posterior:

One cool thing you can do with a full bayesian inference is to do prediction of  P (y_new|y) by integrating out the theta:

P(y_new|y) = inte P(y_new, theta|y) d(theta) = inte  P(y_new|theta)P(y|theta) d(theta)

First term is the model and second term is the product of  Beyesian inference (the posterior).

Bayesian vs Frequentist inference:

1.Bayesian believes data is fixed and our belief on the parameters to be random
2.Frequentist believes the data is random (and repeatedly sampling produce the same data as those observed) and parameter is fixed (i.e., there is one true parameter). No uncertainty on the parameter (confidence interval just gives an uncertainty about the “true” value not the parameter itself)

Day2:
Early wake-up in the morning and start solving problem before breakfast.
Solved 295.
Head to work to fix a haunting bug for weeks.
Found the bug related to a stage not relevant to my CL. Push it to next week for more update.
Solved 322, 160 before getting off work early today.Need to revise the submitted paper on Sunday.

Solved 653, 695, 692.

Day3
Birthday of my wife and spend time only with her today.
Solved 396 before sleep.

Day5
Early wakeup in the morning as usual. No update from G.
Solved 387. Have a dp idea to solve 909. Need to try after heading to work.thought snake only goes from smaller indexed cell to bigger ones whereas it is not true. Not sure if it is ill posed description (as the pic shows so).
Solved 909 with BFS. Need to differentiate the state to visit a cell (Jump to a cell from a ladder/snake or move to a cell )

Solved 234.  Fast/slow pointer + reverse half of the linkedlist to achieve O(1) space.

Solved 694. DFS + affine transformation of island. use the coordinate of first top left 1 as offset to shift the coordinates of land in the island. Construct string as dfs-visit and put it into a set. Count the size of the set.

赞楼主坚持， 一定会成功

老哥这背景跳槽稳得很啊，刷到500基本妥妥的

fymaterials 发表于 2018-12-11 10:46
赞楼主坚持， 一定会成功

Thx!

爱学习的鼠哥 发表于 2018-12-11 10:56
老哥这背景跳槽稳得很啊，刷到500基本妥妥的

谢谢~感觉还是不是很习惯coding under pressure. 一遇到店面，手底下就特别慌。结束静下心一想就又觉得没那么难...还是上手要熟悉才比较有信心