柳传志,倪光南,联想,柳青,滴滴出行

我面了滴滴出行,印象最深的是最后一个面试官问我的问题是在USACO training page上的一个问题,那就是,给个自然数n,有多少不同的\{1,2,\ldots,n\}的和同等的二分拆,用更数学的语言,就是

\left|\{I, J : I \cap J = \emptyset, I \cup J = \{1,2,\ldots,n\}, \sum_{i \in I} i = \sum_{j \in J} j\}\right|.

这个问题我在美国高二时做的,我的一位同学,俄罗斯人,父母都是程序员(而我父母都不是),虽然他对真正的编程懂一些而当然的我对计算机和软件开发没任何概念,只不过数学能力在那儿,但这个问题他却一周都没想通。而我基本没多久就发觉到可以以动态规划的方式计算出

\prod_{i=1}^n (1+x^i)

的系数,下标为n(n+1)/4的系数就是我们要计算的值,不久就把这个动态规划写出来并成功提交了。

说实话,动态规划的概念真的挺trivial的,连计算Fibonacci数用的方法都能算动态规划。动态规划对有数学思维的人都是感觉挺自然地。

上面那问题没啥好说的啦,我更想说的是当时我还不知道滴滴出行公司的背景,尤其其高层。 Continue reading “柳传志,倪光南,联想,柳青,滴滴出行”

Advertisements