Skip to content

《背包问题九讲》2.0 alpha1

四年前,我曾经有过一个写一系列DP相关文章的宏伟计划,但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了。

现在,我打算将这个暂命名为“动态规划的思考艺术”的文章系列重新启动。其第一步便是用LaTeX重新修订那部广为传播并被做成过各种格式各种版本的“背包九讲”。

现在我已经完成了用LyX将九讲的原始文本输入并略加修饰的第一步,于是发布一个 alpha1 版本。下载地址在: http://love-oriented.com/pack/pack2alpha1.pdf

欢迎阅读并帮忙指正错漏之处,捉到的bugs较多或较大的同学有机会提前预览本系列将来的文章。

《把时间当作朋友》旁注/短摘

“管理时间”是谬误的,管理的焦点应是自己。

“既懒惰又勤奋”的矛盾,“时间没有了”的恐惧。

“不知道学习有什么用”的两种结果,心智力量的不同导致同样的论据得出两种论点。

不喜欢做某种事情的原因是否因为是没有做好,并非“有兴趣才能做好”,而是“做好了才有兴趣”。

“所以,所有学习上的成功,都只靠两件事:策略和坚持,而坚持本身就应该是最重要的策略之一。坚持,其实就是重复,而重复,说到底就是时间的投入,我是说,大量的时间投入。”“与其不停地找更好的方法,还不如马上开始行动,省得虚度更多的时间。”

(暂不打断阅读做笔记)

《数学分析原理》旁注(中)

第7章 (2008.11.28)

7.1:看来这章的主要问题是在数列与级数中引入变量x,研究极限确定的函数f(x)的性质。

7.2-7.6:举例逐条说明了:调换两个极限的先后会导致收敛到不同的值,连续函数的收敛级数可以有不连续的和,连续函数的极限函数可以处处间断(Dirichlet函数的解析表示),连续函数的微分与积分的极限与其极限函数的微分和积分可能不同。

7.7:“连续”“收敛”等概念都是由极限定义的,在前面加修饰“一致”的意思就是说,ε-N定义中的N不依赖于自变量x。

7.11:如果函数列是一致收敛的,两个极限就可调换。推论是,连续函数的序列,若一致收敛到f,则f是连续的。

7.16:如果函数列是一致收敛的,极限与积分号就可调换。推论是,一致收敛的函数列级数可逐项积分。

7.17:在闭区间上,极限与微分号可调换,不仅需要函数列一致收敛,还需在此闭区间上有某点x_0使{f_n(x_0)}收敛。

7.19以下的都没看下去。

《简明数论》的简明笔记(下)

  • x²≡d (mod p)的问题。
    • ax²+bx+c≡0 (mod p)可通过配方转化。
      • (2ax+b)²≡b²-4ac(mod p)
    • d是p的二次剩余当且仅当方程有解,否则为二次非剩余。
      • 既约剩余系中恰有(p-1)/2个二次剩余和(p-1)/2二次非剩余。
    • d是二次剩余当且仅当d(p-1)/2≡1 (mod p),否则模为-1。
      • 于是两二次剩余或两二次非剩余的积为二次剩余,二次剩余与非剩余的积为二次非剩余。
  • Legendre符号\left(\frac{d}{p}\right)当d是p的二次剩余、非剩余及p|d时分别取值1、-1、0。
    • Gauss二次互反律\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}的主要应用似乎是用来简化及计算Legendre符号的值,以求解二次同余方程。
      • 但在编程中可直接利用\left(\frac{d}{p}\right)=(-1)^{\frac{p-1}{2}}来计算,复杂度是相同的。
    • Jacobi符号具有与Legendre符号相同的互反律,但似乎就与二次同余方程没什么关系了,目前还没看到应用。
  • 关于同余方程的Lagrange定理的内容是同余方程的解数不超过它的次数。
    • 可用归纳法证明,很优雅。
    • n次同余方程f(x)=x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod{p}有n个解,当且仅当f(x)的次数小于等于p,且f(x)除xp-x所得的余式模p恒等于0。
    • 对于次数大于p的高次同余方程,总存在一个次数不大于p、首项系数为1的等价同余方程,即是xp-x除f(x)所得的余式(再将首项系数化为1)。
      • 例外是余式模p恒等于0,不妨认为此时的等价同余方程就是xp-x。
    • 事实上,简化高次同余方程也可避免做多项式除法,可用Fermat小定理xp≡x (mod p)直接降低次数。
  • 模为素数幂的同余方程的解法看上去很强大,但是前提是需要先解出模为素数的同余方程啊!难道除了直接验证没什么通用的解法?26节先放下。

MSRA实习纪(一):面试篇

(我目前正在面试 Facebook 的 winter intern,所以还是先赶快把这段欠了很久的面经写出来以攒人品吧。)

我面试的是 MSRA 的 Innovation Engineering Group (创新工程组),面试官是一位 RSDE II。他在面试之前跟我用电话和邮件确定了电面的时间,而后我的电话就非常准时的如约而至了。(题外话:Facebook 的电话就似乎没有那么准时。)

面试时不仅需要接电话,还需要进入一个网页版的聊天系统,这个系统可以即时对话,还有虚拟的白板可以用文本或图像写写画画,之后的写代码环节就是在这个白板上进行的。

接了电话,寒暄过后就进入聊项目阶段。首先是对我简历上列出的项目经历做了些蜻蜓点水式的随机提问,应该是为了确认基本的真实性。而后,面试官问我这些项目经历中最大、最复杂的是哪个,我回答说是大一至大二暑假时跟着翁凯老师做的那个嵌入式Linux的项目。于是就开始深入地聊这个项目,比如说,为什么会选择AT91RM9200做CPU。这个问题我之前从来没想过,因为芯片选型这些重要决策当时都是翁凯老师确定的啊。于是便磕磕绊绊地说了些计算能力和外设接口满足需求、性价比高、省电、CPU频率可调之类的。

聊过简历上的项目后,又问了和编程语言相关的问题,既有客观题又有主观题。我记得的有C#里面的Property是干什么用的,动态语言和静态语言的区别,C#属于动态语言还是静态语言——最后这个问题比较tricky,传统上来说C#是根正苗红的静态的面向对象语言,但C# 3.5和4.0增加了一些比较“动态”的特性,但我在面试当时其实只知道这些动态特性的存在,并不了解具体有哪些。(应该还有别的很简单的客观题我记不起来了。)

下一个阶段是时间最长的,基于一个假想的项目来提问各种问题。大概是说有一个唱片公司在全国各地开了很多家买唱片的连锁店,连锁店内用电脑展示歌手、唱片、歌曲等信息,顾客可以用店内的电脑完成浏览、查询、试听等操作。首先问的是这样一个系统的架构,我答就是有一个中央服务器,店内的电脑连接服务器获取信息什么的。(不详细写了我当时的答案了,时间久了也不可能记那么清楚。)然后问到说现在这样一个系统性能很差,应该怎么办。我答性能问题首先一定要profiling,看到底哪里是性能瓶颈才能对症处理,比如说服务器性能差、网络性能差、客户端性能差需要优化的东西就完全不一样。面试官补充说道是网络带宽的问题,店里面都只有拨号网络,问我应该怎样优化。我回答了几方面:一是可以削减传输的内容,例如音视频功能在带宽不够的前提下可以考虑不予提供;二是可以对传输的内容进行压缩,压缩有有损和无损两种,分别可以应用于图像、音频、视频内容及文本内容;三是可以在客户端做缓存,下载过的东西就不要重复下载;四是网络实在很差的情况下可以考虑不用网络,假设信息更新频率不是那么快,可以考虑每周一次把数据更新刻成光盘快递给所有分店(这个有点是为了展示自己具有“think outside the box”的能力故意说的)。然后面试官就问,缓存的话可以怎么实现。我就答了算法可以用LRU、MRU什么的;数据结构根据储存在内存还是硬盘上可选用 hash table、B+ tree  等。然后面试官又非常详细地追问了一下只用内存的LRU具体怎么实现,我就详细地答道可以用一个 linked list 和一个 hash table 来做什么什么的,互相之间怎么着用指针指来指去怎么添加怎么删除什么的。

最后一个阶段是实际写代码,在那个可以实时看到对方打字过程的聊天工具里写,不要用IDE、编译器。先是让选语言,说我简历上列的那些个语言里除了Haskell 面试官不会其它可以任选。我考虑自己多年OI到ACM/ICPC的经验就选了C++。结果呢,要求实现一个排序。说起来比较囧,其实我最不会写排序了。高中的时候搞OI,其他用Pascal语言的同学都把快排背得滚瓜烂熟,而我则很轻松地用标准库里的qsort函数搞定(至今怨念OI比赛不准用STL);大学里搞ACM/ICPC更是有STL里好用的sort函数用啦。所以说虽然说要让我敲一个二分图匹配、平衡二叉树或者最小费用最大流什么的我都能基本做到随手就来,对于自己好多年都没有写过一次的排序我还是比较没信心。最终我选择了时间复杂度达到理论最优而又写起来相对不容易错的 merge sort 来写。由于第一次在这样的环境和场景下写程序,写的时候极其紧张(一紧张连new和delete都忘了怎么用了直接图省事写了句“int temp[n]; // C99”),代码写得磕磕绊绊,不过似乎最终还是一遍就写对了。还是感谢OI和ACM/ICPC为我打下的扎实的coding基础啊。

最后面试官问我还有没有什么问题要问他,我什么问题都想不到就说没有。不过我后来想到,也许应该最后问他一下他对我面试的表现总的评价怎么样,对我个人能否给出什么建议这样的问题。即便面试官回避问题或者干脆不答,也许也能有一点谨慎好学的印象分。如果面试官答了那就有可能是真知灼见的建议。

和预先通知的一样,这场面试总共耗时整整一个小时。

我后来意识到,我在面试中踏入的最大的误区是,在面试时被问到问题完全没必要等面试官话音刚落就回答。这是出于日常生活中两人交替说话时的行为习惯。但我现在觉得完全没必要在面试中也这样,对于比较复杂无法在一两句话内答完的问题,尤其是主观问题,完全没必要把自己第一感觉得到的答案直接说出来。可以直接跟面试官说我想一下,然后花个三十秒考虑一下各种可能性,分几点来回答,然后再有条理地说出来,这样可能会给人感觉更好。

悟到的另一条面试经验是,由于面试官问的很多问题都会直接基于你的简历中的内容。确认简历中内容的真实性也肯定是面试官的一项重要任务。所以有必要在面试前把自己的简历好好过一下,考虑一下每一项能力、经历等描述有哪些可以提问的角度,预先自我演练一下。比如说,把自己简历中从前做过的项目仔细过一下,不仅要想清楚自己在其中的作用和贡献应该怎样表述和展示,还有必要想一下整个项目在选型、架构等重大决策有哪些、为什么这么做,尽管那些决策自己可能并没有参与做出。

好了,这篇就是这样,敬请期待今后的“MSRA实习纪”系列。将来还可能会有Facebook面经以及我真心希望能有的Facebook实习纪哦!