面试资料收集

###鉴别出那瓶水有毒

有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时后就会死亡，至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒
链接：https://www.nowcoder.com/questionTerminal/84726a200b4a4a0d95b9565b4c6eb216
来源：牛客网

每个老鼠只有死或活2种状态，因此每个老鼠可以看作一个bit，取0或1
N个老鼠可以看作N个bit，可以表达2^N种状态（其中第i个状态代表第i个瓶子有毒）
例如：当N＝2时，可以表达4种状态
0，0（ 一号老鼠活，二号老鼠活）
0，1（ 一号老鼠活，二号老鼠死）
1，0（ 一号老鼠死，二号老鼠活）
1，1（ 一号老鼠死，二号老鼠死）
具体来说，有A、B、C、D这4个瓶子，一号老鼠喝A和B， 二号老鼠喝B和C
如果 0，0 （ 一号老鼠活，二号老鼠活），说明是D有毒，第0个状态代表第4个瓶子有毒
如果 0，1 （ 一号老鼠活，二号老鼠死） ，说明是C有毒 ，第1个状态代表第3个瓶子有毒
如果 1，0 （ 一号老鼠死，二号老鼠活） ，说明是A有毒 ，第2个状态代表第1个瓶子有毒
如果 1，1 （ 一号老鼠死，二号老鼠死） ，说明是B有毒 ，第3个状态代表第2个瓶子有毒
可以想象成用2进制来表示1000个数最少需要多少位

你第一次访问网站时，
https://learnku.com/articles/25858 
服务端脚本中开启了Sessionsession_start();，

服务器会生成一个不重复的 SESSIONID 的文件session_id();，比如在/var/lib/php/session目录

并将返回(Response)如下的HTTP头 Set-Cookie:PHPSESSIONID=xxxxxxx

客户端接收到Set-Cookie的头，将PHPSESSIONID写入cookie

当你第二次访问页面时，所有Cookie会附带的请求头(Request)发送给服务器端

服务器识别PHPSESSIONID这个cookie，然后去session目录查找对应session文件，

找到这个session文件后，检查是否过期，如果没有过期，去读取Session文件中的配置；如果已经过期，清空其中的配置
如果一个Cookie都没接收到，基本上可以预判客户端禁用了Cookie，那将session_id附带在每个网址后面(包括POST)，
比如：

GET http://www.xx.com/index.php?session_id=xxxxx
POST http://www.xx.com/post.php?session_id=xxxxx
然后在每个页面的开头使用session_id($_GET['session_id'])，来强制指定当前session_id
所以Laravel等框架中，内部实现了Session的所有逻辑，并将PHPSESSIONID设置为httponly并加密，这样，前端JS就无法读取和修改这些敏感信息，降低了被盗用的风险。

如何进行防 SQL 注入

1 表单尽量用 post 提交,核心用户验证都走 post,避开 get容易暴露客户数据
2 使用HTTP_REFERER 检查源文件是否来自本系统
3 开启addslashes在特殊符号前加\
4 使用htmlspecialchars对字符串转实体
5 用户授权登录
6 使用PDO

大流量高并发量网站的解决方案

对比现实中饭店一下子同一个时间段来吃饭 比方中午https://learnku.com/articles/25886
1 把这个店面面积扩大点，增加同时吃饭人数
   服务器优化：我们把apache服务器只支持（3000并发）可以换成nginx服务器（3w并发）
2 多找点服务员和厨师嘛  
   服务器优化：修改apache，nginx的默认配置，把其中的并发数调到最高嘛
3 多开一些店 连锁店
   服务器优化：多增加几台服务器同时对客户提供网络服务 lvs nginx 做负载均衡
4 限时客户在我们店吃饭的时间 不能让他们吃完还打牌把
   服务器优化：减少客户在服务器上的连接断开时间 比方mysql 的连接断开时间 wait_timeout这个参数最多的连接时间 不能让客户恶意一直连着
5 给厨师培训 增加他的上菜时间
   那就要给php代码做优化
6 让厨师叫手下把菜提前做好 放到冰箱里面
   redis 缓存 文件缓存

sql分组

1) 算出每个班级中的学生，按照成绩降序排序;https://learnku.com/articles/25903#topnav
select name,class,score from student order by class,score desc;

2) 查出每个班的及格人数和不及格人数，格式为:class、及格人数、不及格人数;

SELECT class,
SUM(CASE WHEN score>=60 THEN 1 ELSE 0 END),
SUM(CASE WHEN score<60 THEN 1 ELSE 0 END)
FROM tb1 GROUP BY class
这边主要先分组 在聚合在加入判断条件

3) 用 PHP 写入连接数据库("localhost","msuser","mspass")、执行以上 SQL、显示结果、 判断错误、关闭数据库的过程
$conn=mysql_connect(‘localhost’,'msuser ’,’mspass′);//链接数据库
Mysql_select_db(‘test’);
$sql=" SELECT class,
SUM(CASE WHEN score>=60 THEN 1 ELSE 0 END), SUM(CASE WHEN score<60 THEN 1 ELSE 0 END)
FROM tb1 GROUP BY class";
if($result=Mysql_query($sql)){
     while($row=mysql_fetch_assoc($result)){
     print_r($row);
} }
Mysql_close($conn);

GET 与 POST 的区别

GET在浏览器回退时是无害的，而POST会再次提交请求。
GET产生的URL地址可以被Bookmark，而POST不可以。
GET请求会被浏览器主动cache，而POST不会，除非手动设置。
GET请求只能进行url编码，而POST支持多种编码方式。
GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
GET请求在URL中传送的参数是有长度限制的，而POST么有。
对参数的数据类型，GET只接受ASCII字符，而POST没有限制。
GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。
GET参数通过URL传递，POST放在Request body中

GET产生一个TCP数据包；POST产生两个TCP数据包。https://learnku.com/articles/25881


对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；

而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

也就是说，GET只需要汽车跑一趟就把货送到了，而POST得跑两趟，第一趟，先去和服务器打个招呼“嗨，我等下要送一批货来，你们打开门迎接我”，然后再回头把货送过去。

因为POST需要两步，时间上消耗的要多一点，看起来GET比POST更有效。因此Yahoo团队有推荐用GET替换POST来优化网站性能。但这是一个坑！跳入需谨慎。为什么？

1. GET与POST都有自己的语义，不能随便混用。

2. 据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。

3. 并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。

浏览器有没有默认发送 Expect:100-continue 的请求头就不清楚, 但是 curl 是默认会发送的. 具体的解释可以看鸟哥的博客: http://www.laruence.com/2011/01/20/1840.html

摘抄一下重点:

在使用curl做POST的时候, 当要POST的数据大于1024字节的时候, curl并不会直接就发起POST请求, 而是会分为俩步,

 1. 发送一个请求, 包含一个Expect:100-continue, 询问Server使用愿意接受数据
 2. 接收到Server返回的100-continue应答以后, 才把数据POST给Server

并不是所有的Server都会正确应答100-continue, 比如lighttpd, 就会返回417 “Expectation Failed”, 则会造成逻辑出错.
因此, 在使用 curl 时可以考虑增加一步处理, 既在请求头中将 Expect 值置空. 鸟哥给出的 demo 是这样

curl_setopt($ch, CURLOPT_HTTPHEADER, array('Expect:'));
guzzle 的做法是:

// If the Expect header is not present, prevent curl from adding it
if (!$request->hasHeader('Expect')) {
    $conf[CURLOPT_HTTPHEADER][] = 'Expect:';
}

nginx 配置

server {
    # 监听 HTTP 协议默认的 [80] 端口。https://learnku.com/articles/25861
    listen 80;
    # 绑定主机名 [example.com]。
    server_name example.com;
    # 服务器站点根目录 [/example.com/public]。
    root /example.com/public;

    # 添加几条有关安全的响应头；与 Google+ 的配置类似，详情参见文末。
    add_header X-Frame-Options "SAMEORIGIN";
    add_header X-XSS-Protection "1; mode=block";
    add_header X-Content-Type-Options "nosniff";

    # 站点默认页面；可指定多个，将顺序查找。
    # 例如，访问 http://example.com/ Nginx 将首先尝试「站点根目录/index.html」是否存在，不存在则继续尝试「站点根目录/index.htm」，以此类推...
    index index.html index.htm index.php;

    # 指定字符集为 UTF-8
    charset utf-8;

    # Laravel 默认重写规则；删除将导致 Laravel 路由失效且 Nginx 响应 404。
    location / {
        try_files $uri $uri/ /index.php?$query_string;
    }

    # 关闭 [/favicon.ico] 和 [/robots.txt] 的访问日志。
    # 并且即使它们不存在，也不写入错误日志。
    location = /favicon.ico { access_log off; log_not_found off; }
    location = /robots.txt  { access_log off; log_not_found off; }

    # 将 [404] 错误交给 [/index.php] 处理，表示由 Laravel 渲染美观的错误页面。
    error_page 404 /index.php;

    # URI 符合正则表达式 [\.php$] 的请求将进入此段配置
    location ~ \.php$ {
        # 配置 FastCGI 服务地址，可以为 IP:端口，也可以为 Unix socket。
        fastcgi_pass unix:/var/run/php/php7.2-fpm.sock;
        # 配置 FastCGI 的主页为 index.php。
        fastcgi_index index.php;
        # 配置 FastCGI 参数 SCRIPT_FILENAME 为 $realpath_root$fastcgi_script_name。
        fastcgi_param SCRIPT_FILENAME $realpath_root$fastcgi_script_name;
        # 引用更多默认的 FastCGI 参数。
        include fastcgi_params;
    }
    # 通俗地说，以上配置将所有 URI 以 .php 结尾的请求，全部交给 PHP-FPM 处理。

    # 除符合正则表达式 [/\.(?!well-known).*] 之外的 URI，全部拒绝访问
    # 也就是说，拒绝公开以 [.] 开头的目录，[.well-known] 除外
    location ~ /\.(?!well-known).* {
        deny all;
    }
}

###判断两个有序数组是否有公共元素

// https://github.com/chunlintang/interview/blob/master/src/algorithms/common.php
function common($arr1, $arr2)
{
	$len1 = count($arr1);
	$len2 = count($arr2);
	$common = [];
	$i = $j = 0;
	while ($i < $len1 && $j < $len2) {
		if ($arr1[$i] > $arr2[$j]) {
			$j++;
		} elseif ($arr1[$i] < $arr2[$j]) {
			$i++;
		} else {
			array_push($common, $arr1[$i]);
			$i++;
			$j++;
		}
	}
	return $common;
}

猴子选大王，约瑟夫环

// 
function monkeyKing($n, $m)
{
	$arr = [1, $n];
	$i = 0;
	while (count($arr) > 1) {
		$i++;
		$survice = array_shift($arr);
		if ($i % $m != 0) {
			array_push($arr, $survice);
		}
	}
	return $arr[0];
}

质数

// 质数
function prime($n)
{
	$prime = [2];
	for ($i = 3; $i < $n; $i += 2) {
		$sqrt = intval(sqrt($i));
		for ($j = 3; $j <= $sqrt; $j += 2) {
			if ($i % $j == 0) {
				break;
			}
		}
		if ($i > $sqrt) {
			array_push($prime, $i);
		}
	}
	return $prime;
}

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / 2); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / 2) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出，$i不会继续+1，即最后$i <= floor($value / 2)
        if ($value != 1 && $i > floor($value / 2)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 质数数组
    $primeArr = [];
    // 循环所有备选数
    foreach ($arr as $value) {
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，退出循环
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除数$j比备选数的中间数大的则为质数
        // 这样判断的依据：
        // 假如备选数为质数，则内层的for循环不会break退出，则执行完毕，$i会继续+1，即最后$i = floor($value / $i) + 1
        // 假如备选数不为质数，则内层的for循环遇到整除就会break退出且$i不会继续+1，即最后$i <= floor($value / $i)
        if ($value != 1 && $i > floor($value / $i)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}
/**
 * 获取所有的质数
 * @param array $arr
 * @return array
 */
function get_prime_number_three($arr = []) {
    // 质数数组
    $primeArr = $arr;
    // 循环所有备选数
    foreach ($primeArr as $key => $value) {
        if ($value == 1) {
            unset($primeArr[$key]);
            continue;
        }
        // 备选数和备选数的中间数以下的数字整除比较
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能够整除，则不是质数，从数组中删除且退出循环
            if ($value % $i == 0) {
                unset($primeArr[$key]);
                break;
            }
        }
    }
    // 重置数组索引返回
    return array_values($primeArr);
}
// 所有备选数数组
$numberArr = range(1, 100, 1);
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印
print_r($primeNumberArr);
// 所有备选数数组
$numberArr = [11, 22, 33, 66, 77, 3, 8, 10, 99];
// 获取备选数中的所有质数
$primeNumberArr = get_prime_number($numberArr);
// 输出打印http://blog.y0701.com/2018/09/18/PHP%E7%AE%97%E6%B3%95%E4%B9%8B%E5%88%A4%E6%96%AD%E6%98%AF%E5%90%A6%E6%98%AF%E8%B4%A8%E6%95%B0/
print_r($primeNumberArr);

PHP算法之二分查找

/**
 * 二分查找算法
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @return int        返回找到的键
 */
function binary_search($arr, $number) {
    // 非数组或者数组为空，直接返回-1
    if (!is_array($arr) || empty($arr)) {
        return -1;
    }
    // 初始变量值
    $len = count($arr);
    $lower = 0;
    $high = $len - 1;
    // 最低点比最高点大就退出
    while ($lower <= $high) {
        // 以中间点作为参照点比较
        $middle = intval(($lower + $high) / 2);
        if ($arr[$middle] > $number) {
            // 查找数比参照点小，舍去右边
            $high = $middle - 1;
        } else if ($arr[$middle] < $number) {
            // 查找数比参照点大，舍去左边
            $lower = $middle + 1;
        } else {
            // 查找数与参照点相等，则找到返回
            return $middle;
        }
    }
    // 未找到，返回-1
    return -1;
}
/**
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @param int $lower 区间最低点
 * @param int $high 区间最高点
 * @return int
 */
function binary_search_recursion(&$arr, $number, $lower, $high) {
    // 以区间的中间点作为参照点比较
    $middle = intval(($lower + $high) / 2);
    // 最低点比最高点大就退出
    if ($lower > $high) {
        return -1;
    }
    if ($number > $arr[$middle]) {
        // 查找数比参照点大，舍去左边继续查找
        return binary_search_recursion($arr, $number, $middle + 1, $high);
    } elseif ($number < $arr[$middle]) {
        // 查找数比参照点小，舍去右边继续查找
        return binary_search_recursion($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}
// 待查找区间
$arr = [1, 3, 7, 9, 11, 57, 63, 99];
// 非递归查找66所在的位置
$find_key = binary_search($arr, 57);
// 递归查找66所在的位置
$find_key_r = binary_search_recursion($arr, 57, 0, count($arr));
// 输出打印
print_r($find_key);
print_r($find_key_r);http://blog.y0701.com/2018/09/20/PHP%E7%AE%97%E6%B3%95%E4%B9%8B%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/

UTF-8编码


Unicode只是一个符号集，它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储。

汉字”严”的unicode是十六进制数4E25，转换成二进制数足足有15位（100111000100101），也就是说这个符号的表示至少需要2个字节。表示其他更大的符号，可能需要3个字节或者4个字节，甚至更多。

UTF-8就是在互联网上使用最广的一种Unicode的实现方式。其他实现方式还包括UTF-16（字符用两个字节或四个字节表示）和UTF-32（字符用四个字节表示），不过在互联网上基本不用。重复一遍，这里的关系是，UTF-8是Unicode的实现方式之一。

UTF-8最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度。
Unicode转义字符让我们可以通过Unicode码点输入特殊的字符。 有两种形式：\uhhhh对应16bit的码点值， \Uhhhhhhhh对应32bit的码点值， 其中h是一个十六进制数字；一般很少需要使用32bit的形式。 每一个对应码点的UTF8编码。 例如：下面的字母串面值都表示相同的值：
 
"世界"
"\xe4\xb8\x96\xe7\x95\x8c"
"\u4e16\u754c"
"\U00004e16\U0000754c"
上面三个转义序列都为第一个字符串提供替代写法， 但是它们的值都是相同的。
打开”记事本”程序Notepad.exe，新建一个文本文件，内容就是一个”严”字，依次采用ANSI，Unicode，Unicode big endian 和 UTF-8编码方式保存。
然后，用文本编辑软件UltraEdit中的”十六进制功能”，观察该文件的内部编码方式。

ANSI：文件的编码就是两个字节”D1 CF”，这正是”严”的GB2312编码，这也暗示GB2312是采用大头方式存储的。
Unicode：编码是四个字节”FF FE 25 4E”，其中”FF FE”表明是小头方式存储，真正的编码是4E25。
Unicode big endian：编码是四个字节”FE FF 4E 25″，其中”FE FF”表明是大头方式存储。
UTF-8：编码是六个字节”EF BB BF E4 B8 A5″，前三个字节”EF BB BF”表示这是UTF-8编码，后三个”E4B8A5″就是”严”的具体编码，它的存储顺序与编码顺序是一致的。
注意，windows下通过记事本保存的utf8默认是带BOM的utf，而一般建议都是使用不带BOM的utf8编码https://xin053.github.io/2016/09/07/UTF-8%E7%BC%96%E7%A0%81/

缓存穿透缓存击穿缓存雪崩

1
2
3

缓存穿透 ： DB 承受了没有必要的查询流量，意思就是查到空值的时候没有做缓存处理，再次查询的时候继续读库了
缓存击穿：热点 Key，大量并发读请求引起的小雪崩， 就是缓存在某个时间点过期的时候，恰好在这个时间点对这个 Key 有大量的并发请求过来，这些请求发现缓存过期一般都会从后端 DB 加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端 DB 压垮
缓存雪崩：缓存设置同一过期时间，引发的大量的读取数据库操作