Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 947

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /home/samsongli/meirendaddy.com/blog/wp-includes/kses.php on line 948
December 22, 2009

是王建硕提出的。他用英文写的,我用英文和他探讨了一下,觉得还是很有意思的一个题目。我这里用中文总结一下,免得忘记了。

有一个数据库的表T,表里面有多个列Ci,每个列的值域是实数。在这个表上可以定义查询。一个查询Q是一个表达式树,这个表达式树的非叶子结点,都是布尔表达式;而叶子结点,都是比较表达式。比较表达式的意思,就是一个列的名字Ci,一个比较运算符(<,<=,>,>=,<>)这些,然后一个实数值。

一个查询的例子:NOT (AND ((C1>5), OR ((C2<6),(C3<>9))))

问题是:给出两个这样的查询Q1和Q2,如何确定Q1的结果是否是Q2结果的子集?

这个的确是一个比较难的题目,因为比较的是两个查询,而不是两个结果集合。建硕也指出,这里最麻烦的,是那些比较表达式,因为它们是多个列上面的比较。

我给出了一个解法,是这样的:

  1. 对比较表达式进行改造,变为值域。比如:C1>=3变为:C1:[3,+∞);C2<>9变为:C2:(-∞,9) OR C2:(9,+∞)
  2. 对布尔表达式进行计算,最终的目的,是把表达式树变成一组item的OR的运算;而每个item,是一组factor之间的AND运算;每个factor,是一个值域。每个item里面,一个列名Ci最多只能出现一次。
  3. 对于每一个item,找出里面没有出现的列名Ci,增加相应的值域Ci(-∞,+∞)。
  4. 剩下的事情就简单了。对于Q2里面所有的item,看Q1里面是否存在一个item可以把它覆盖。如果是,那么Q2的结果,一定是Q1的子集。

这个是代数的解法,对应的几何映射,就是一个N维空间,其中N是表T的列的数目。每个列,都是空间里面的一维。每个item,都是空间里面的一个区域。每个查询,就是空间里面的一组这样的区域。表格T里面的任何一个可能的列,都是空间里面的一个点。查询的结果,就是落在这组空间里面的点的集合。

那么计算Q2是否是Q1的子集,就是计算Q2定义的空间区域集合,是否能被Q1定义的空间区域集合所容纳。

December 27, 2008

微软的题目:假设某门户网站有20亿注册用户,那么怎么存储这些用户,才能让用户快速的登录呢?普通的数据库肯定太慢了。

我靠,这20亿比中国人口还多啊,这就是照着网络身份证的方向去的。好题目。要我说,

  1. 要用分布式数据库,把用户名按照unicode(因为肯定各国人都有)的数字hash到不同的机器上去。
  2. 最好是in memory DB,所有数据存在内存里,因为后面需要。
  3. 用户登录以后,老办法,浏览器那边放个cookie,然后服务器这边操作的时候,要查cookie状态,照样是hash到某台机器上去,用in memory DB来查cookie是否合法,这台机器就负责这个用户的会话。
  4. 不同的阶段hash的方法不同,登录的时候可以内部hash一下,但是登录前找login server和登录后找特定机器来给用户服务,都可以跟DNS合作,从url上来hash到不同的机器。

另外一个好玩的题目:

词的变化:PAN -> PEN -> MEN -> MET 这中间所有的词都是正确的词,每次变化都只修改一个字母。设计一个算法,给出初始词(PAN)和目标词(MET),还有一个词典(用来查找正确的词),算法要给出词变化的最短路径。

基本上是个无向图图的搜索算法了。假设词的长度是n,那么每个n长度的字符串都是一个节点。两个字符串只差一个字母的,彼此之间有边。只有在词典里有的词才是合法的节点,其他节点都去掉。然后从初始词到目标词找最短路径。

December 21, 2008

前一段时间组里在中国那边招了个lead (lead 中文我不知道怎么翻译,好像大家也都这么叫,如果真要硬翻译,估计“工头”比较合适 ) :P  跑题了跑题了,这里要说的,是面试过程中发现的一些问题。

我以前在国内的时候也招过人,曾经有过一天面试14个小时,中间只有半个小时吃饭的事情。拿当时的总结和现在找工作的同学们比起来,大家的面试水平,还真是没什么进步。

从我们招人的角度看,招来的人有两个目的:一个是干活,另外一个,是跟同事一起和睦的干活。第二点其实更重要,现在没有哪个人可以自己独立完成一个大的软件项目了,在一个成熟的软件公司里面,所有的工作,都是要和他人合作完成的,无论是从内部客户那里来的需求,还是自己组内和同事的合作,交流与合作的能力,都影响到你是否能够拿到这个职位。

所以在面试的时候,除了展示自己技术上的能力以外,更重要的,就是展示自己是一个好相处,容易合作,知道进退的人。

我见过的国内工程师来面试,大多数是只知道展示第一条,忘记了第二条;也有个别的,过分的展示了第二条。

展示第一条很容易,上来问问做过的项目,加上几条基本概念,就知道对方的底细了。不确定的话,再来一道编程题目,这个人的基本技能就都有了。但是第二条比较困难,不仅是对面试人困难,考官也不容易了解对方的性格脾气。这个时候,其实主动权在面试人一方,就是制造机会来展示自己的团队精神。

展示其实也是有技巧的。我曾经遇到过一位应聘人,上来就跟我握手,热情的好像我欠了他的钱,生怕我跑掉的那种。然后我很不合适宜的问了他关于团队精神的看法,他给我上了20分钟的课。这就属于火候过了的那种,毕竟我也是工程师,不会找一个人整天跟我握手谈理念。

我现在看下来,国内的软件工程师们,如果没有在职场上混够年头,经常是光顾着展示自己的技术能力了,对自己的团队精神没有好好的照顾到,很多时候导致公司里面对这方面有顾虑,从而影响到最终的招聘。

November 14, 2008

今天看到一个特别简单的题目,就是说有两个数组A和B,假设都是整数类型的,而且都是从小到大排好序的,A里面,从下标0开始,有X个数;B里面有Y个数,A的长度是X+Y,B的长度是Y,就是说A里面能放下所有A和B的数。目标是设计一个算法,把所有这些数字都放到A里面去,当然结果要是排序的。

这个题目再简单不过了,就是倒着做merge sort。具体说就是用两个下标,分别从A和B的数据尾巴开始,做合并。合并的结果从A的最后一个位置开始放,最后A里面就是A和B的合并的并且排序的结果了。

说到这个题目,想起另外一个比较难的题目来。不过还是用一个简单的题目开始吧:假如有一个很长的整数数组,要求用这个数组实现两个堆栈。

这个题目很简单,就是用两个栈指针,然后分别从数组的两头开始,向中间生长。具体写程序的时候,检查一下两个指针是否相遇就可以了。

然后题目就难了一点:如何用一个数组实现三个堆栈?

答案其实是上面那个题目的一个挺巧妙的扩展:三个堆栈里面的两个,还是按照上面的办法做;然后第三个堆栈,从数组三分之一的地方开始,向三分之二的方向生长。具体说来:

假设数组是A,长度是L,那么三个堆栈分别从下标0,L,和1/3L的地方开始生长。假设三个堆栈的栈顶指针分别是x,y和z,那么当栈生长到一定时间的时候,空间会不够用,可能会有以下情况:

  1. x生长到了1/3L
  2. y和z相遇

这两种情况下,数组都会有一段空间空闲(如果三个栈一样长,那就结束了),或者是A[x,1/3L],或者是A[y,z]。那么把这个空间继续按照上面的办法分割,直到空间用完为止。

November 10, 2008

经典的面试题目,通常假设是连通图。

首先要明确的,是这个图是有向图,还是无向图。

无向图比较简单,就用染色法好了。对每个访问过的结点进行标记,遇到标记过的结点,就说明图里有圈。

有向图稍微复杂一点,先找出所有没有进入边的结点,把它们作为起点集合,从他们中间选一个出发。如果这个集合是空,那么有圈。

然后的方法,就是每个结点有两个标志位:一个用来标志是否访问过,另外一个用来标志是否当前“活跃”。从出发点集合选 一个没有被访问过的结点,开始进行深度优先搜索。遇到的没有访问过的结点,标记访问过,并且活跃;回退的时候,清除活跃标志。

如果遇到的结点是访问过的,但是不活跃,那么不访问这个结点。

如果遇到的结点是活跃的,那么有圈。

直到找到圈,或者所有出发集合里的结点都被访问过为止。

November 8, 2008

题目:写一个函数,给一个C的字符串S,返回一个字符串,其内容是S的反向。比如,S是“abc”,返回“cba”

参考代码:

char* reverse(const char* s) {

if (!s) return s;  //check if s is NULL (1)

size_t size = strlen(s);

if (! size || size == 1) return s; // check for empty string or single char string (1)

char* r = new char[size + 1];  // (2)

for (size_t i = 0; i < size; ++i) {

r[i] = s[size - i - 1];  // reverse (3)

}

r[size] = ‘\0′;  // (4)

return r;  // caller should delete r after use (5)

}

点评:

本题的考点有以下几点:

  1. 边界条件的检查
  2. C字符串的结构
  3. C字符串的寻址方式
  4. C字符串的结尾方式
  5. 内存管理