莫回首

2017-09-22 10:51 已编辑四川大学前端工程师

关注

百度校招三面面经-软件研发

一面(40min)

0. 自我介绍

1. 介绍ImageOCR的项目

2. 知道有哪些排序算法？

冒泡、插入、shell、归并、快排、堆排序、选择排序等等

有没有不会写的，排雷排掉了堆排序

3. 手写插入排序并解释

4. 上面的排序算法哪些是稳定的，哪些是不稳定的

还有一些忘了

二面(1.2h)

0. 介绍简历上的另外一个项目

1. PHP的基本数据类型以及基本数据类型内核如何实现?

基本数据类型

boolean(布尔型)    布尔型是最简单的数据类型，只有两个值 false(假) 和true(真)
string(字符串型)    字符串就是连续的字符序列，如 ehco "string";
integer(整型)        整型数据类型只能包含整数，这些数据类型可以是负数或者正数
folat(浮点型)    浮点型类型用于存储数字，和整型不同的是浮点型可以有小数点
array（数组）    一组相同类型的集合
object（对象）    对象是一个实力，使用new命令创建一个对象
resource（资源）    资源是一种特殊的变量，保存在外部资源的一个应用，资源是通过函数来进行建立的
null（ 空白）    特殊的值，表示变量没有值，任何变量的初始值都是null

变量的在内核当中的保存方式：

php5.3: http://blog.csdn.net/qq_28602957/article/details/52959132

typedef union _zvalue_value {
    long lval;                  /* long value */
    double dval;                /* double value */
    struct {
        char *val;
        int len;
    } str;
    HashTable *ht;              /* hash table value */
    zend_object_value obj;
    zend_ast *ast;
} zvalue_value;

struct _zval_struct {
    /* Variable information */
    zvalue_value value;     /* value */
    zend_uint refcount__gc;
    zend_uchar type;    /* active type */
    zend_uchar is_ref__gc;
};

PHP语言层类型	存在zvalue_value的成员变量
long,bool,resoure	lval
double	dval
string	str(len保存字符串的长度，val保存字符串的值)
array	ht（哈希表）
object	obj

php7: https://yq.aliyun.com/articles/27359

//存储变量的结构
struct _zval_struct {
    zend_value        value;            /* value */
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    type,         /* active type */
                zend_uchar    type_flags,
                zend_uchar    const_flags,
                zend_uchar    reserved)     /* call info for EX(This) */
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t     var_flags;
        uint32_t     next;                 /* hash collision chain */
        uint32_t     ***_slot;           /* literal *** slot */
        uint32_t     lineno;               /* line number (for ast nodes) */
        uint32_t     num_args;             /* arguments number for EX(This) */
        uint32_t     fe_pos;               /* foreach position */
        uint32_t     fe_iter_idx;          /* foreach iterator index */
    } u2;
};

//变量的值
//通过上面的代码我们可以看到。变量是通过一个_zval_struct结构体方式存储的。其中结构体中的value存储的是变量的值。这个成员是zend_value类型的。zend_value类型的定义如下：

typedef union _zend_value {
    zend_long         lval;             /* long value */
    double            dval;             /* double value */
    zend_refcounted  *counted;
    zend_string      *str;
    zend_array       *arr;
    zend_object      *obj;
    zend_resource    *res;
    zend_reference   *ref;
    zend_ast_ref     *ast;
    zval             *zv;
    void             *ptr;
    zend_class_entry *ce;
    zend_function    *func;
    struct {
        uint32_t w1;
        uint32_t w2;
    } ww;
} zend_value;

2. PHP如何与nginx通信，通信方式有什么异同

https://vsxen.github.io/2017/05/30/phpcgi-socks-vs-tcp/

CGI模式

CGI CGI（common gateway interface）通常翻译为共同网关接口，是HTTP服务器与机器上的其他程序进行通信的一个接口，让Web服务器必要时启动额外的程序处理动态内容。CGI是一种协议，它定义了Webserver与CGI程序的通信方式。Webserver接受客户端的HTTP请求，然后建立进程执行CGI程序，客户端的请求被传递给CGI程序，CGI执行后结果再返回Webserver。 CGI的出现让WEB从静态变为为动态，随着Web的越来越普及，很多的网站的都需要有动态的页面，以便与浏览者互交。随着网络技术的发展，CGI方式的缺点也越来越突出。每次客户端请求都需要建立和销毁进程。因为HTTP要生成一个动态页面，系统就必须启动一个新的进程以运行CGI程序，不断地fork是一项很消耗时间和资源的工作。

FastCGI

众所周知，CGI解释器的反复加载是CGI性能低下的主要原因，如果CGI解释器保持在内存中并接受FastCGI进程管理器调度，则可以提供良好的性能、伸缩性、Fail-Over特性等等。

FastCGI是一个常驻型的CGI，可以一直执行，只要激活后，不会每次都花时间去fork一次，而且还支持分布式运算（使得php程序解释执行可以单独交给php服务器），即可以在网站服务器以外的主机上执行并且接受来自其它网站服务器来的请求。

1、Web Server 启动时载入FastCGI进程管理器（IIS ISAPI或Apache Module）;
2、FastCGI进程管理器自身初始化，启动多个CGI解释器进程 (在任务管理器中可见多个php-cgi.exe)并等待来自Web Server的连接。
3、当客户端请求到达Web Server时，FastCGI进程管理器选择并连接到一个CGI解释器。Web server将CGI环境变量和标准输入发送到FastCGI子进程php-cgi.exe。
4、FastCGI子进程完成处理后将标准输出和错误信息从同一连接返回Web Server。当FastCGI子进程关闭连接时，请求便告处理完成。FastCGI子进程接着等待并处理来自FastCGI进程管理器（运行在 WebServer中）的下一个连接。在正常的CGI模式中，php-cgi.exe在此便退出了

Apache 模块

MPM Multi Path Modules （多道处理模块）用于定义apache在响应多个用户请求时所工作的模型。有三种MPM模式：

prefork（一个请求一个进程响应）

worker（一个请求用一个线程响应，启动多个进程每个进程生成多个线程）

event（一个进程处理多个请求）

以模块安装的php没有独立的进程，是作为apache的模块和apache一起启动的。

以上三种MPM模式，worker模式会比prefork模式占据更少的内存，高并发下的表现更好。而且使用多进程和多线程混合模式，即使有一个线程挂了，也只影响和该线程同进程的其他线程，不会影响到其他的进程。但是如果有特别多的线程都使用keep-alive的长连接方式，则线程会一直被占据直到超时才释放，导致在高并发场景下无可用线程。而event模式使用了一个专门的线程来处理这些keep-alive类线程，较好的解决了这个问题。

Nginx

Nginx处理PHP文件只有FastCGI 一种
不过Nginx连接fastcgi的方式有2种：TCP和unix domain socket
Unix domain socket 或者 IPC socket是一种终端，可以使同一台操作系统上的两个或多个进程进行数据通信。与管道相比，Unix domain sockets 既可以使用字节流和数据队列，而管道通信则只能通过字节流。Unix domain sockets的接口和Internet socket很像，但它不使用网络底层协议来通信。Unix domain socket 的功能是POSIX操作系统里的一种组件。
Unix domain sockets 使用系统文件的地址来作为自己的身份。它可以被系统进程引用。所以两个进程可以同时打开一个Unix domain sockets来进行通信。不过这种通信方式是发生在系统内核里而不会在网络里传播。
TCP和unix domain socket方式对比
TCP是使用TCP端口连接127.0.0.1:9000
Socket是使用unix domain socket连接套接字/dev/shm/php-cgi.sock（很多教程使用路径/tmp，而路径/dev/shm是个tmpfs，速度比磁盘快得多）
测试机是个1核的centos5.4，2用户并发时系统资源消耗50%左右，10用户资源就跑得很满了

结论是在服务器压力不大的情况下，tcp和socket差别不大，但在压力比较满的时候，用套接字方式，效果确实比较好。
下面是php 5.3以上版本将TCP改成socket方式的配置方法：
修改php-fpm.conf（/usr/local/php/etc/php-fpm.conf）
;listen = 127.0.0.1:9000
listen = /dev/shm/php-cgi.sock
修改nginx配置文件server段的配置，将http的方式改为socket方式

从原理上来说，unix socket方式肯定要比tcp的方式快而且消耗资源少，因为socket之间在nginx和php-fpm的进程之间通信，而tcp需要经过本地回环驱动，还要申请临时端口和tcp相关资源。
当然还是从原理上来说，unix socket会显得不是那么稳定，当并发连接数爆发时，会产生大量的长时缓存，在没有面向连接协议支撑的情况下，大数据包很有可能就直接出错并不会返回异常。而TCP这样的面向连接的协议，多少可以保证通信的正确性和完整性。

3. PHP的执行模式有哪些

http://blog.csdn.net/xujingzhong0077/article/details/53316767

运行模式

关于PHP目前比较常见的五大运行模式：
1）CGI（通用网关接口/ Common Gateway Interface）
2）FastCGI（常驻型CGI / Long-Live CGI）
3）CLI（命令行运行 / Command Line Interface）
4）Web模块模式（Apache等Web服务器运行的模式）
5）ISAPI（Internet Server Application Program Interface）

备注：在PHP5.3以后，PHP不再有ISAPI模式，安装后也不再有php5isapi.dll这个文件。要在IIS6上使用高版本PHP，必须安装FastCGI 扩展，然后使IIS6支持FastCGI。

1.1、CGI模式

CGI即通用网关接口（Common Gateway Interface），它是一段程序，通俗的讲CGI就象是一座桥，把网页和Web服务器中的执行程序连接起来，它把HTML接收的指令传递给服务器的执行程序，再把服务器执行程序的结果返还给HTML页。CGI 的跨平台性能极佳，几乎可以在任何操作系统上实现。CGI已经是比较老的模式了，这几年都很少用了。

每有一个用户请求，都会先要创建CGI的子进程，然后处理请求，处理完后结束这个子进程，这就是Fork-And-Execute模式。当用户请求数量非常多时，会大量挤占系统的资源如内存，CPU时间等，造成效能低下。所以用CGI方式的服务器有多少连接请求就会有多少CGI子进程，子进程反复加载是CGI性能低下的主要原因。

如果不想把 PHP 嵌入到服务器端软件（如 Apache）作为一个模块安装的话，可以选择以 CGI 的模式安装。或者把 PHP 用于不同的 CGI 封装以便为代码创建安全的 chroot 和 setuid 环境。这样每个客户机请求一个PHP文件，Web服务器就调用php.exe（win下是php.exe,linux是php）去解释这个文件，然后再把解释的结果以网页的形式返回给客户机。这种安装方式通常会把 PHP 的可执行文件安装到 web 服务器的 cgi-bin 目录。CERT 建议书 CA-96.11 建议不要把任何的解释器放到 cgi-bin 目录。这种方式的好处是把Web Server和具体的程序处理独立开来，结构清晰，可控性强，同时缺点就是如果在高访问需求的情况下，CGI的进程Fork就会成为很大的服务器负担，想象一下数百个并发请求导致服务器Fork出数百个进程就明白了。这也是为什么CGI一直背负性能低下，高资源消耗的恶名的原因。

1.2、FastCGI模式

FastCGI是CGI的升级版本，FastCGI像是一个常驻 (long-live)型的 CGI，它可以一直执行着，只要激活后，不会每次都要花费时间去 Fork 一次（这是 CGI 最为人诟病的 fork-and-execute 模式）。
FastCGI是一个可伸缩地、高速地在HTTP server和动态脚本语言间通信的接口。多数流行的HTTP server都支持FastCGI，包括Apache、Nginx和lighttpd等，同时，FastCGI也被许多脚本语言所支持，其中就有PHP。
FastCGI接口方式采用C/S结构，可以将HTTP服务器和脚本解析服务器分开，同时在脚本解析服务器上启动一个或者多个脚本解析守护进程。当HTTP服务器每次遇到动态程序时，可以将其直接交付给FastCGI进程来执行，然后将得到的结果返回给浏览器。这种方式可以让HTTP服务器专一地处理静态请求或者将动态脚本服务器的结果返回给客户端，这在很大程度上提高了整个应用系统的性能。

【原理】
1）Web Server启动时载入FastCGI进程管理器（IIS ISAPI或Apache Module)；
2）FastCGI进程管理器自身初始化，启动多个CGI解释器进程 (可见多个php-cgi.exe或php-cig)并等待来自Web Server的连接；
3）当客户端请求到达Web Server时，FastCGI进程管理器选择并连接到一个CGI解释器。Web server将CGI环境变量和标准输入发送到FastCGI子进程php-cgi；
4）FastCGI子进程完成处理后将标准输出和错误信息从同一连接返回Web Server。当FastCGI子进程关闭连接时，请求便告处理完成。FastCGI子进程接着等待并处理来自FastCGI进程管理器（运行在 WebServer中）的下一个连接。在正常的CGI模式中，php-cgi.exe在此便退出了。
在CGI模式中，你可以想象 CGI通常有多慢。每一个Web请求PHP都必须重新解析php.ini、重新载入全部dll扩展并重初始化全部数据结构。使用FastCGI，所有这些都只在进程启动时发生一次。一个额外的好处是，持续数据库连接（Persistent database connection）可以工作。

备注：PHP的FastCGI进程管理器是PHP-FPM（PHP-FastCGI Process Manager）
【优点】
1）从稳定性上看，FastCGI是以独立的进程池来运行CGI，单独一个进程死掉，系统可以很轻易的丢弃，然后重新分配新的进程来运行逻辑；
2）从安全性上看，FastCGI支持分布式运算。FastCGI和宿主的Server完全独立，FastCGI怎么down也不会把Server搞垮；
3）从性能上看，FastCGI把动态逻辑的处理从Server中分离出来，大负荷的IO处理还是留给宿主Server，这样宿主Server可以一心一意作IO，对于一个普通的***页来说, 逻辑处理可能只有一小部分，大量的是图片等静态。

【缺点】
说完了好处，也来说说缺点。从我的实际使用来看，用FastCGI模式更适合生产环境的服务器。但对于开发用机器来说就不太合适。因为当使用 Zend Studio调试程序时，由于 FastCGI会认为 PHP进程超时，从而在页面返回 500错误。这一点让人非常恼火，所以我在开发机器上还是换回了 ISAPI模式。对某些服务器的新版本支持不好，对分布式负载均衡没要求的模块化安装是否是更好的选择。目前的FastCGI和Server沟通还不够智能，一个FastCGI进程如果执行时间过长会被当成是死进程杀掉重起，这样在处理长时间任务的时候很麻烦，这样做也使得FastCGI无法允许联机调试。因为是多进程，所以比CGI多线程消耗更多的服务器内存，PHP-CGI解释器每进程消耗7至25兆内存，将这个数字乘以50或100就是很大的内存数。

1.3 CLI模式

PHP-CLI是PHP Command Line Interface的简称，如同它名字的意思，就是PHP在命令行运行的接口，区别于在Web服务器上运行的PHP环境（PHP-CGI，ISAPI等）。也就是说，PHP不单可以写前台网页，它还可以用来写后台的程序。 PHP的CLI Shell脚本适用于所有的PHP优势，使创建要么支持脚本或系统甚至与GUI应用程序的服务端，在Windows和Linux下都是支持PHP-CLI模式的。
【优点】
1）使用多进程，子进程结束以后，内核会负责回收资源；
2）使用多进程，子进程异常退出不会导致整个进程Thread退出，父进程还有机会重建流程；
3）一个常驻主进程，只负责任务分发，逻辑更清楚。
我们在Linux下经常使用"php –m"查找PHP安装了那些扩展就是PHP命令行运行模式；有兴趣的同学可以输入"php –h"去深入研究该运行模式。

1.4 模块模式

模块模式是以mod_php5模块的形式集成，此时mod_php5模块的作用是接收Apache传递过来的PHP文件请求，并处理这些请求，然后将处理后的结果返回给Apache。如果我们在Apache启动前在其配置文件中配置好了PHP模块
（mod_php5）， PHP模块通过注册apache2的ap_hook_post_config挂钩，在Apache启动的时候启动此模块以接受PHP文件的请求。
除了这种启动时的加载方式，Apache的模块可以在运行的时候动态装载，这意味着对服务器可以进行功能扩展而不需要重新对源代码进行编译，甚至根本不需要停止服务器。我们所需要做的仅仅是给服务器发送信号HUP或者AP_SIG_GRACEFUL通知服务器重新载入模块。但是在动态加载之前，我们需要将模块编译成为动态链接库。此时的动态加载就是加载动态链接库。 Apache中对动态链接库的处理是通过模块mod_so来完成的，因此mod_so模块不能被动态加载，它只能被静态编译进Apache的核心。这意味着它是随着Apache一起启动的。
Apache是如何加载模块的呢？我们以前面提到的mod_php5模块为例。首先我们需要在Apache的配置文件httpd.conf中添加一行：
LoadModule php5_module modules/mod_php5.so

这里我们使用了LoadModule命令，该命令的第一个参数是模块的名称，名称可以在模块实现的源码中找到。第二个选项是该模块所处的路径。如果需要在服务器运行时加载模块，可以通过发送信号HUP或者AP_SIG_GRACEFUL给服务器，一旦接受到该信号，Apache将重新装载模块，而不需要重新启动服务器。
该运行模式是我们以前在windows环境下使用apache服务器经常使用的，而在模块化（DLL）中，PHP是与Web服务器一起启动并运行的。（它是apache在CGI的基础上进行的一种扩展，加快PHP的运行效率）。

1.5 ISAPI模式

ISAPI（Internet Server Application Program Interface）是微软提供的一套面向Internet服务的API接口，一个ISAPI的DLL，可以在被用户请求激活后长驻内存，等待用户的另一个请求，还可以在一个DLL里设置多个用户请求处理函数，此外，ISAPI的DLL应用程序和WWW服务器处于同一个进程中，效率要显著高于CGI。（由于微软的排他性，只能运行于windows环境）
PHP作为Apache模块，Apache服务器在系统启动后，预先生成多个进程副本驻留在内存中，一旦有请求出现，就立即使用这些空余的子进程进行处理，这样就不存在生成子进程造成的延迟了。这些服务器副本在处理完一次HTTP请求之后并不立即退出，而是停留在计算机中等待下次请求。对于客户浏览器的请求反应更快，性能较高。

4. PHP代码的执行流程

http://blog.csdn.net/a2534725767/article/details/55194582

1.Scanning(Lexing) ,将PHP代码转换为语言片段(Tokens)  
2.Parsing, 将Tokens转换成简单而有意义的表达式  
3.Compilation, 将表达式编译成Opocdes  
4.Execution, 顺次执行Opcodes，每次一条，从而实现PHP脚本的功能。

5. PHP与Golang的区别

参考博文

面试的时候基本上上面说到的都说到了一些但是面试的时候逻辑还是不够清晰

6. 深度优先遍历与广度优先遍历

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/18/2596983.html

a. DFS

（1）访问顶点v；
（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

b. BFS

（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。
直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。