现在的位置: 首页 > 综合 > 正文

大众点评实习生面试题(1)

2018年04月22日 ⁄ 综合 ⁄ 共 1345字 ⁄ 字号 评论关闭

下面是大众点评网技术部测试开发实习生的几道面试题

1,要求实现库函数strcpy,
原型声明:extern char *strcpy(char *dest,char *src);
功能:把src所指由NULL结束的字符串复制到dest所指的数组中。
说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。 返回指向dest的指针。
解析:这是我们常用的一个库函数,虽然只是一个简单的库函数,但是要注意细节的把握。例如对条件的判断等等。

char * strcpy( char *strDest, const char *strSrc )  //将源字符串加const,表明其为输入参数
{ 
    if(strDest == strSrc)   //考虑到源目所指区域有重叠的情况
    {  
        return strDest;
    } 
    
    assert( (strDest != NULL) && (strSrc != NULL) );  //对源地址和目的地址加非0断言
    char *address = strDest; 
    
    while( (*strDest++ = * strSrc++) != '\0'); 
    return address;     //为了实现链式操作,将目的地址返回
} 

2,有16个一模一样的瓶子,其中有15瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有4只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?
这个问题的答案也堪称经典:把瓶子从 0 到 15 依次编号,然后全部转换为 4 位二进制数。让第一只老鼠喝掉所有二进制数右起第一位是 1 的瓶子,让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子,等等。一星期后,如果第一只老鼠死了,就知道毒药瓶子的二进制编号中,右起第一位是 1 ;如果第二只老鼠没死,就知道毒药瓶子的二进制编号中,右起第二位是 0,等等。每只老鼠的死活都能确定出10位二进制数的其中一位,由此便可知道毒药瓶子的编号了。
由于2^4=16,所以我们只需要4只老鼠就能检查16瓶水,同理,我们只需要10老鼠就能检查1024瓶水。即 n 只老鼠能检查出 2^n 瓶水。

拓展一下:
如果你有两个星期的时间(换句话说你可以做两轮实验),为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。

答案:7 只老鼠就足够了。事实上,7 只老鼠足以从 3^7 = 2187 个瓶子中找出毒药来。首先,把所有瓶子从 0 到 2186 编号,然后全部转换为 7 位三进制数。现在,让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子,让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子,等等。一星期之后,如果第一只老鼠死了,就知道毒药瓶子的三进制编号中,右起第一位是 2 ;如果第二只老鼠没死,就知道毒药瓶子的三进制编号中,右起第二位不是 2,只可能是 0 或者1。 也就是说,每只死掉的老鼠都用自己的生命确定出了,三进制编号中自己负责的那一位是
2 ;但每只活着的老鼠都只能确定,它所负责的那一位不是 2 。于是,问题就归约到了只剩一个星期时的情况。在第二轮实验里,让每只活着的老鼠继续自己未完成的任务,喝掉它负责的那一位是 1 的所有瓶子。再过一星期,毒药瓶子的三进制编号便能全部揭晓了。
类似地,我们可以证明, n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。

抱歉!评论已关闭.