电面1

阿里电面

如何判断一个链表是否有环？
从根节点开始遍历，记录遍历过的节点，如果有重复节点，那么就存在环。
1 这个可以用昨天提到的“快慢指针”来解决吧？设两个工作指针，一个快一个慢，如果有环的话，它们会必然在某点相遇。
2 
c++的虚函数和纯虚函数的区别？
virtual void test() = 0;
纯虚函数的类在其派生类中必须定义自己这个函数的版本，而且纯虚函数是没有实际意义的，他的目的告知编译器派生类将会定义自己的版本。

类中拥有纯虚函数表示这个类是抽象类，不存在此类的对象。

而虚函数仅表示派生类可以定义自己的版本，但是基类也可以有意义，若没有定义自己的版本，将使用基类的版本。


1000瓶药水，有1瓶有毒药，问几只小白鼠能够找出？

根据2^10=1024，所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
一位表示一个老鼠，0-7表示8个瓶子。也就是分别将1、3、5、7号瓶子的药混起来给老鼠1吃，2、3、6、7号瓶子的药混起来给老鼠2吃，4、5、6、7号瓶子的药混起来给老鼠3吃，哪个老鼠死了，相应的位标为1。如老鼠1死了、老鼠2没死、老鼠3死了，那么就是101=5号瓶子有毒。
同样道理10个老鼠可以确定1000个瓶子

如果1周内，小白鼠吃了有毒药的药水，会死亡。

给两周时间，问要几只小白鼠，log3 (1000)
如果你有两个星期的时间（换句话说你可以做两轮实验），为了从1000个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二轮实验了。提示：用三进制数表示即可。

如果有2瓶有毒药，问几只小白鼠能够找出？

1瓶的情况下，死掉的小白鼠和没死掉的小白鼠组成的二进制数，正好对应瓶子的编号。

2瓶的话，应该会需要更多的小白鼠吧。。
n只老鼠，在一周以后有活跟死两种状态，一共可以有2^n种不同的状态。
1000瓶水里有2瓶毒药一共是499500种状态，2^18=262 144，2^19=524 288，所以是19只吧。

如果16瓶水，1瓶有毒。问几只小白鼠能找出至少14瓶无毒的水。

> Written with [StackEdit](https://stackedit.io/).