11.18~11.20 惨痛的字节以及招商银行面试记录

字节

手撕代码

算法：3sum
SQL：找出所有成绩都在80分以上的同学名字

数据库理论

SQL索引是什么、引擎有哪些

智力题

10个石子，你和对手轮流抓，可抓1个2个或者3个
求你先手的情况下胜算有多大：关键是用倒推法，假设自己要赢，那么自己最后需要面对的石子个数必须是1、2或3，那怎样才能保证一定是这几个石子数呢，那必须上一步对手面对的石子个数是4才行
具体解答可参考https://www.cxyxiaowu.com/2810.html

招商银行

算法理论题

排序算法：快速排序、堆排序的复杂度是多少，什么情况下会达到最坏复杂度，适用于什么场景
快速排序的实现过程
堆排序的原理与实现过程
https://www.cnblogs.com/chengxiao/p/6129630.html
图片说明

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

算法步骤
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

图的遍历方法
https://www.cnblogs.com/springbarley/articles/2558869.html
1、深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
2、图的广度优先遍历算法是一个分层遍历的过程，和树的层序遍历算法类同，是从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

数据库理论题

数据库的增删查改都是怎么实现的
数据库索引是怎么创建的，用什么语句
插入一个索引用什么语句、删除索引用什么语句

改：Update 语句用于修改表中的数据。语法：UPDATE 表名称 SET 列名称 = 新值 WHERE 列名称 = 某值；
    列名可以是多个，多个列名之间用豆号分开；
    例如：UPDATE Person SET FirstName = 'Fred' WHERE LastName = 'Wilson'
 UPDATE Person SET Address = 'Zhongshan 23', City = 'Nanjing' WHERE LastName = 'Wilson'

删：DELETE 语句用于删除表中的行。语法：DELETE FROM 表名称 WHERE 列名称 = 值，如：DELETE FROM Person WHERE LastName = 'Wilson' 
    删除所有行，DELETE FROM table_name或DELETE * FROM table_name或者TRUNCATE TABLE mytable;（注意，并不删除表）；
    删除列：ALTER TABLE mytable
           DROP COLUMN col;

增加行：INSERT INTO 语句用于向表格中插入新的行。语句：INSERT INTO 表名称 VALUES (值1, 值2,....)
或INSERT INTO table_name (列1, 列2,...) VALUES (值1, 值2,....)
    例如：INSERT INTO Persons VALUES ('Gates', 'Bill', 'Xuanwumen 10', 'Beijing')或
 INSERT INTO Persons (LastName, Address) VALUES ('Wilson', 'Champs-Elysees')
增加列：
ALTER TABLE mytable
ADD col CHAR(20);