2016年2月萌生了从体制内跳出来的想法，3月中下旬开始陆续面了几家，主要是PHP开发岗，简单记录一下碰到的笔试、面试题目。
发现问题，期待提高。
算法数据结构
基础排序算法（快排、冒泡、选择、插入）
两个有序数组归并
时间长不手写了，还是写在纸上，感觉生疏了很多，需要加强复习、练习。
发现自己对php语法其实并不熟悉，以后应该多用面试相关语言练习试试
给定入栈序列、出栈序列，问是否合法
维护一个栈，出栈序列视为队列，每次入栈后检查栈顶元素是否与出栈队列队头相同，若相同则出栈&出队直至不同，最后检查栈是否为空。
给一棵多叉树（父节点存子节点），将存储结构改为子节点存父节点，返回叶子节点队列
反过来，将子节点存父节点的改为父节点存子节点
简单的数据结构题，第二问的时候用map存新的节点，方便查找是否已经建立该节点。
发现自己对C++的vector、map已经不太熟悉了，还得多练习。
给一个NxN的方阵，从（0,0）开始顺时针转圈填写1-NxN
dx={1,0,-1,0},dy = {0,1,0,-1},表示顺时针右、下、左、上四个方向坐标变换，判断是否已填写&是否是边界
给一个运算式字符串，写个计算器
先读取数字/符号，维护一个数字栈，一个符号栈，括号优先级最高，然后是乘除，然后加减
写循环缓冲区（循环链表）的push和get操作
这个没写好，其实是很简单，但是好久不写了，思路有点混乱，判断空和满的状态直接迷糊了，太不应该了。
给定一个只有正整数的数组，表示一个容器底部形状每个格子的高度，
从上往下注水，问最后这个容器能容纳的水量（一个格子表示1）
每个位置所能容纳的最大水量=min(该位置左边的最大格子高度，该位置右边的最大格子高度)-该位置高度【若为负则该位置容水量为0】
维护一个数组，从左向右扫一遍原始数组，记录当前位置左边的最大值；再从右往左扫一遍，记录当前位置右边的最大值，若小于从左往右的则更新。然后计算差值累和。
设计一个字符串随机池数据结构，包含三个操作：
void add(string str)->向随机池里加入一个字符串
void del(string str)->从随机池里删除对应串
string get()->等概论随机取出一个字符串
要求三种操作的时间复杂度都是O(1)
add操作使用链表hash，同时将插入字符串压入一个vector，hash表内记录string和他对应放入vector的位置；
del操作hash找到，用vector里末尾位替换当前删除值，删除末尾位；
get操作用vector长度取随机数，取出对应位置串。
给定一个字符串，只能在后面添加字符，要求添加最少字符使得字符串变成回文串
思路比较简单，就是找到最右边的最长回文串的回文中心，然后补充完整。
卡在了偶回文的处理方法上，面试官说是Manacher（马拉车）算法的改写，以前没用过，学习一下。
地图上有10^8个饭店，现在有10^6个查询，要求查出对应位置周围2km内的所有饭店（约10^4个）
如果每次都在线查询，就是1014复杂度。所以考虑分块，按照1km划分方格，预处理每个格子内饭店数量，对应每次查询，找出对应位置所在方格&周边一圈方格内饭店（104量级），从中查出，则总体复杂度降为10^10
长度为n的数组，查询最大值和最小值，要求比较次数最少。
直接扫一遍的话比较次数是2n次
每次从数组中取出两个元素，判断其大小，然后再分别判断其是否是最大或最小值，这样一次处理两个元素，每一次比较3次，最终的比较次数就是n/2*3=1.5n
一百个灯泡排成一排，第一轮将所有灯泡打开；
第二轮每隔一个灯泡关掉一个；
即排在偶数的灯泡被关掉，第三轮每隔两个灯泡；
依次类推，第100轮结束的时候，还有几盏灯泡亮着
1．对于每盏灯，拉动的次数是奇数时，灯就是亮着的，拉动的次数是偶数时，灯就是关着的。
2．每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。
3．1—100这100个数中有哪几个数，约数的个数是奇数。
**我们知道：一个数的约数都是成对出现的，只有完全平方数约数的个数才是奇数个。 **
所以这100盏灯中有10盏灯是亮着的，它们的编号分别是：1、4、9、16、25、36、49、64、81、100
PHP相关
SESSION和COOKIES的区别
1、cookie数据存放在客户的浏览器上，session数据放在服务器上。
2、cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗 考虑到安全应当使用session。
3、session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能 考虑到减轻服务器性能方面，应当使用COOKIE。
4、单个cookie保存的数据不能超过4K，很多浏览器都限制一个站点最多保存20个cookie。
isset()和empty()的区别
empty
如果 变量 是非空或非零的值，则 empty() 返回 FALSE。换句话说，”"、0、”0″、NULL、FALSE、array()、var $var、未定义;以及没有任何属性的对象都将被认为是空的，如果 var 为空，则返回 TRUE。
isset
如果 变量 存在(非NULL)则返回 TRUE，否则返回 FALSE(包括未定义）。变量值设置为：null，返回也是false;unset一个变量后，变量被取消了。注意，isset对于NULL值变量，特殊处理。
php设计模式
这个以前真没接触过，感觉需要恶补
用单例模式设计一个php计时器类，包含
start();//分配计时器id
stop($id);//暂停对应id计时器，并返回时长
restart($id);//唤起
这个题让我理解了单例模式的作用，以前一直都觉得只有数据库连接会用到。
基本思路是每个计时器包含id、start_time、status、time_all，分别表示计时器id、开始时间、计时器开关状态、总时长。计时器类包含计时器数组、个数。
start()分配新的计时器，start_time设为当前时间，time_all为0；
stop($id)先判断计时器状态，若已经暂停，直接返回time_all,否则先暂停，time_all += 当前时间-start_time；
restart($id)改状态为开始，start_time改为当前时间。
正则表达式相关
以前都是现用现查，而且也用的少，要加强学习
在看这本书正则表达式必知必会（修订版）
Linux命令&shell相关
之前一直在用windows系统，很少用linux，所以命令什么的会的也少也不熟悉，这个对专职很有影响。
现在一来自己换了macbook，二来新换的工作应该常用linux，在实践中学习积累吧。
前端相关
js里数组的原生方法
==和===的区别（null和undefined区别）
这些都是很基础的js相关问题，然而我就是不知道，被问了除了一脸萌比没有别的反应。清楚的意识到，自己所掌握的只是皮毛的皮毛，并不了解真正的前端，需要学习的东西很多。
面试官非常nice的指出了我的问题，并给我提了学习方法，包括去研究原生js、了解框架的内部机制。推荐了两本书：
最近的几次面试结果都不好，但是让我确定了一些事：
- 及时地从事业单位跳出来是正确的职业规划
- 用人单位需要的是能干活的人而不是能学习的，需要抓紧时间追赶这一年半时间落下的技术技能
- 我真挺喜欢前端这个方向的
JQuery基本操作
这个是第一家的笔试题，当时比较傻，也没带本代码库也不敢查，有些地方想不起来函数了。其实应该是可以查的，毕竟实际环境中都是要查的。
HTTP状态码
网站首页加载速度慢如何优化
之前没有太多的关注过页面优化的问题，能想到的只有
- 压缩代码
- 压缩图片等文件
- js放在后面
浏览器渲染原理
d3.js和echarts实现上的区别
d3绘图使用svg，echarts使用canvas
实现 js 的 indexof() 函数，并出测试数据验证
这个比较简单，主要注意边界数据的处理，包括空串、子串长于模式串等
实现网页loading加载动画
之前写过loading，但用的很笨的方法，就是用一个gif图，但是这样也会占用加载时间。还是需要考虑用CSS去实现。
数据库相关
mysql有哪些索引，都有什么用
之前完全没接触过索引，需要认真学习实践
设计一个用户金币系统数据库，用户每天登陆获得2个金币，立即激活。
每次消费获得20枚金币，冻结1个月，若消费退款则收回，否则一个月后激活。
要求用户可以查看自己的金币总数&可用金币数。
要求写出数据库表设计&维护逻辑。
用户金币表-coin_user
| ID | TPYE | INFO |
|---|---|---|
| user_id | varchar(36) | 用户id |
| coin_active | int | 激活金币数 |
| coin_freeze | int | 冻结金币数 |
金币流水表-coin_serial
| ID | TPYE | INFO |
|---|---|---|
| serial_id | varchar(36) | 流水号 |
| user_id | varchar(36) | 用户id |
| occurrence_time | datetime | 发生时间 |
| coin_num | int | 金币数 |
| get_type | int | 获取类型（0-登录，1-消费） |
| status | int | 状态（0-激活，1-冻结，2-收回） |
逻辑
- 登录：查看coin_serial里当天是否有该用户登录金币记录，若没有，coin_serial里增加用户登录流水记录&&coin_user对应用户coin_active+1
- 消费：coin_serial里加一条消费金币流水（status为1），coin_user对应用户coin_freeze+20
- 回收：coin_serial对应消费记录金币status改为2，coin_user对应用户coin_freeze-20
- 每日定时任务：coin_serial里一个月前的status为1的，status改为0，对应用户coin_freeze-20，coin_active+20
设计一个在线商城的数据库，并写以下sql：
1) 选出某个用户所有已付款交易
2) 选出某段时间所有有成交的商品
3) 按交易量排序选出某段时间top10商品
设计用户、分类、商品、交易流水几个表，其中交易流水表包含流水号（pk）、商品id、用户id、价格、交易时间、交易状态、收货地址等。
- select * from 交易流水 where 用户id='xxx' and 状态='已付款'
- select 商品id from 交易流水 where (时间>='xxxx' and 时间<='xxxx' and 状态='成交') group by 商品id
- select 商品id from 交易流水 order by count(商品id) limit 0,10
