[编程题]贪吃的小Q-算法题记录

前几天隔壁宿舍同学在刷算法题,串门的时候看到了这道有趣的题,记录一下。 原题目是这样的: 链接:https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182?orderByHotValue=1&page=1&onlyReference=false 来源:牛客网 小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。
示例1

输入

3 7

输出

4

一开始打算找规律,使用2的n次方进行分配,最后也没有得出一个好的解法(虽然已经很接近了),于是看了一下牛客的参考答案,主要是两种解法:

二分查找法:

非常暴力的方法,意料之外情理之中。需要的结果为“第一天最多可以吃多少个”,这个值一定在0与巧克力总数M之间。于是可以在[0,M]区间内进行二分查找。复杂度为O(logM·N),代码如下:

//@小冲冲

#include
using namespace std;
int n,m;
//计算第一天吃s个巧克力一共需要多少个多少个巧克力
int sum(int s){
    int sum=0;
    for(int i=0;i<n;i++){ sum+=s; s=(s+1)>>1;//向上取整
    }
    return sum;
}
//二分查找
int fun(){
    if(n==1) return m;
    int low=1;
    int high=m;//第一天的巧克力一定是大于等于1小于等于m的
    while(low<high){ int mid=(low+high+1)>>1;//向上取整
        if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力,刚刚好吃完所有巧克力,那么直接返回
        else if(sum(mid)<m){ low=mid; }else{ high=mid-1; } } return high; } int main() { cin>>n>>m;
    int res=fun();
    cout<<res<<endl;
    return 0;
}

但是我个人觉得这个想法不太elegant,复杂度仍有一些高,于是再往下翻,找到一个比较有意思的解法,跟我一开始的想法差不多。他没有标明他的方法,我给他随便起个名字:

逐次分配法:

他的思路如下:

  1. 首先,每天分配一颗巧克力
  2. 计算得到剩余的可分配巧克力
  3. 按照2的N次方的顺序给各天分配,如:可分配的有7颗,则第一天分4个,第二天分2个,第三天分1个。
  4. 计算剩余的巧克力数量,如果还有剩余,跳转到2
  5. 没有剩余可分的巧克力,则完成分配。

代码如下:

//@域外創音
#include
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配:每天最少吃1块     
    int alignable = m-n; 
    int result = 1; //如果可以某种power2[i]-1的方式分配,便进入。具体的分配是:第一天多吃power2[i-1]块,第二天多吃power2[i-2]块,依此类推。 
    //这样一来,只要每个追加分配所对应的i不重复,每天吃的块数就依然能符合要求,因为第j天吃的块数最多等于power2[从i-j到0]+1,一定大于power2[从i-j-1到0]的二倍。 
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
    {
        result+=power2[i-1];
        alignable -= (power2[i]-1);
    }
    std::cout<<result<<std::endl;
    return 0;
}

这个代码非常的有意思,它可以把复杂度减少到O(log(m)),并且它还通过了所有测试用例。但是,作为预备役测试猿,我找到了它一个bug(笑)。当输入用例为(3天,20块巧克力)时,跑出来的结果是10,但是实际上,可以得到(11,6,3)的分配策略,与其得到的结果不符。使用二分查找法得出的结果也为11.问题出在哪里呢,通过代码走读很容易定位到问题出在18行:

alignable -= (power2[i]-1);

以(3天,20块)为用例,逐步推演,即可看到问题是怎么样发生的:

 

在第一轮分配的时候,@域外創音 的方法是,默认认为分配了pow(2,n)-1颗,而不是实际分出去的颗数。在此用例中,假如有4天或以上,分配列为(8,4,2,1),alignable -= 15无疑是正确的,但是当只有3天时,则会给不存在的第四天分配了一颗,从而导致最终结果的错误。

更正的方法也很简单,就是把alignable -= (power2[i]-1);改为alignable -= actually_assigned即可,而actually_assigned值的计算可以由代码中的i与天数n联合得出。

经过修改的代码如下,通过了牛客网的OJ所有测试用例,暂未发现未通过的其它反例。

#include<iostream>
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配:每天最少吃1块
    int alignable = m-n;
    int result = 1; //如果可以某种power2[i]-1的方式分配,便进入。具体的分配是:第一天多吃power2[i-1]块,第二天多吃power2[i-2]块,依此类推。
    //这样一来,只要每个追加分配所对应的i不重复,每天吃的块数就依然能符合要求,因为第j天吃的块数最多等于power2[从i-j到0]+1,一定大于power2[从i-j-1到0]的二倍。
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
        {
            if(i>0)//防止越界
                result+=power2[i-1];
            int assigned = 0;
            if(i>n)
                assigned = (power2[i]-1) - (power2[i-n]-1);
            else
                assigned = (power2[i]-1);
            alignable -= assigned;
        }
    std::cout<<result<<std::endl;
    return 0;
}

 

Tokens in Python

本文主要归纳python的parse过程中,词法分析中,生成的Token的名字以及其含义。
此文章归纳自https://github.com/python/cpython/blob/3.6/Parser/tokenizer.c,版本为python3.6。

 

ENDMARKER, 结束标记符
NAME, 名字
NUMBER, 数字
STRING, 字符串
NEWLINE, 换行
INDENT, 缩进
DEDENT, 未明,在tokenizer.c里面找不到
LPAR, 左括号(
RPAR, 右括号)
LSQB, 左中括号[
RSQB, 右中括号]
COLON, 冒号:
COMMA, 逗号,
SEMI, 分号;
PLUS, 加号+
MINUS, 减号-
STAR, 星号*
SLASH, 斜杠/
VBAR, 或号|
AMPER, 与&
LESS, 小于号<
GREATER, 大于号>
EQUAL, 等于号=
DOT, 点.
PERCENT, 百分号%
LBRACE, 左花括号{
RBRACE, 右花括号}
EQEQUAL, 判断相等==
NOTEQUAL, 不相等!=或者<>
LESSEQUAL, 小于等于<=
GREATEREQUAL, 大于等于>=
TILDE, 波浪线~
CIRCUMFLEX, 音调符号^
LEFTSHIFT, 左移<<
RIGHTSHIFT, 右移>>
DOUBLESTAR, 双星号**
PLUSEQUAL, 加等于+=
MINEQUAL, 减等于
STAREQUAL, 星等于*=
SLASHEQUAL, 除等于/=
PERCENTEQUAL, 百分号等于%=
AMPEREQUAL, 与等于&=
VBAREQUAL, 或等于|=
CIRCUMFLEXEQUAL, 次等于^=
LEFTSHIFTEQUAL, 左移等于<<=
RIGHTSHIFTEQUAL, 右移等于>>=
DOUBLESTAREQUAL, 双星号等于**=
DOUBLESLASH, 双斜杠//
DOUBLESLASHEQUAL, 双斜杠等于//=
AT, AT号@
ATEQUAL, @=
RARROW, ->
ELLIPSIS, 省略号…
/* This table must match the #defines in token.h! */
OP,
AWAIT, 关键字await
ASYNC, 关键字async
<ERRORTOKEN>, 错误的token
<N_TOKENS> 不知道是啥

使用python撸一个支持四则运算的计算器

代码地址:https://github.com/MakDon/toy_calculator
效果如下:


实现的功能为读入一个字符串格式的算式,然后输出数字格式的结果。

计算器主要包括如下几个部分:

  1. 词法分析器
  2. 语法分析器
  3. 伪指令生成器
  4. 伪VM

词法分析器

词法分析器对输入的文本进行分析,输出为一串token。如输入为

"1 + 2 + 3 + 5 + 7"

则输出为:

<class 'list'>:
 [['NUMBER', '1'], ['+', '+'], ['NUMBER', '2'], ['+', '+'], 
['NUMBER', '3'], ['+','+'], ['NUMBER', '5'], ['+', '+'], ['NUMBER', '7']]

此处实现的基本思路是,使用正则对字符串从头进行匹配,若匹配到结果,则截取为一个token,然后继续匹配;若一直匹配不到结果,则认为输入的串存在词法错误。使用的正则分别如下:

 {
    "NUMBER": r"([0-9]+\.)?[0-9]+",# 数字
    "+": r"\+",# 加号
    "-": r"-",# 减号
    "*": r"\*",# 乘号
    "/": r"/",# 除号
    "LBRA": r"\(",# 左括号
    "RBRA": r"\)",# 右括号
    "SEPARATOR": r"( |\n)"# 分隔符,此处使用空格与换行
}

 

语法分析器:

语法分析,是把词法分析器生成的token串,转换为抽象语法树(Abstract Syntax Tree,AST)。上节的token串生成的AST如下:

在此计算器中,我选择的是自顶向下的生成方式。四则运算语法如下:

Expr      ->    Term ExprTail
ExprTail  ->    + Term ExprTail
          |     - Term ExprTail
          |     null

Term      ->    Factor TermTail
TermTail  ->    * Factor TermTail
          |     / Factor TermTail
          |     null

Factor    ->    (Expr)
          |     num

reference:https://zhuanlan.zhihu.com/p/24035780

其中各个符号的含义与消除左递归的推导过程详见《编译原理》。

伪指令生成

上一节的语法分析器中,生成得到了AST。这一步的作用,则是把上一节得到的树,转化为顺序的指令序列。此处使用了递归的深度遍历的方法,此处生成的每条指令包括如下两个部分:

  1. 操作:操作可以为入栈,或者是运算(加减乘除)。
  2. 操作数:可选,当操作为入栈时,操作数是被入栈的数值。当操作为运算时为None。

上一节的AST可以生成如下指令:

[(PUSH,1), (PUSH,2), (+,None), (PUSH,3), (+,None), (PUSH,5), (+,None), (PUSH,7), (+,None)]

 

伪VM

伪VM的作用,为自行上一节生成的伪指令,最后返回结算的结果。伪VM维护一个栈,用于数值计算。获得指令序列后,开始顺序执行指令。当指令的操作为入栈时,把指令的操作数push入栈顶。当指令为运算时,pop出栈顶的两个数字,进行指令的运算,然后把运算结果push回栈顶。在指令序列执行完后,伪VM的栈内应有且只有一个数值,为计算结果。

在伪VM执行完指令后,就得到结果了,计算的全过程也就此结束了。

复习总结(9)数据库原理(1)

范式:

第一范式:属性不可再分

第二范式:所有非关键字段都完全依赖于任意一组候选关键字。
可以理解为:单关键字的表都符合。多关键字表其中部分关键字跟其它属性没有依赖关系。
例如:
(学号,课程名称) → (姓名,年龄,成绩,学分)是违反第二范式,因为
(课程名称) → (学分)
(学号) → (姓名,年龄)
*例子来自百度百科
所以不满足第二范式

第三范式:满足第二范式的情况下,不存在传递的函数依赖
假如
关键字段 → 非关键字段x → 非关键字段y
则违反第三范式。

 

 

SQL语句:

常用SQL关键字:
SELECT 选择
SELECT DISTINCT选择并返回不重复的值
WHERE 限定选择条件,如值大小
AND OR 在WHERE语句中连接条件
ORDER BY 对语句进行排序
INSERT INTO 表名称 VALUES (值1, 值2,….) 对表插入值
JOIN 合并表(还有left join、right join等也需要了解)
GROUP BY分组(常用于聚合函数)
LIMIT 限制

还有其它常用语句,需要了解。

事务:

数据库事务(简称:事务)是数据库管理系统执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成。

数据库的ACID特征:

  • 原子性(Atomicity):事务作为一个整体被执行,包含在其中的对数据库的操作要么全部被执行,要么都不执行
  • 一致性(Consistency):事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束
  • 隔离性(Isolation):多个事务并发执行时,一个事务的执行不应影响其他事务的执行
  • 持久性(Durability):已被提交的事务对数据库的修改应该永久保存在数据库中

 

数据库引擎:

  • ISAM:执行读取操作的速度很快,而且不占用大量的内存和存储资源。不支持事务处理,也不能够容错
  • MYISAM:MYISAM是MYSQL的ISAM扩展格式和缺省的数据库引擎。强调了快速读取操作。

  • HEAP:允许只驻留在内存里的临时表格。驻留在内存里让HEAP要比ISAM和MYISAM都快,但是它所管理的数据是不稳定的,而且如果在关机之前没有进行保存,那么所有的数据都会丢失。
  • INNODB和BERKLEYDB:比ISAM和MYISAM引擎慢很多,但是INNODB和BDB包括了对事务处理外来键的支持

更详细可以参考:http://www.cnblogs.com/0201zcr/p/5296843.html

复习总结(2)数据结构data structure(2)树

图片未标明出处的均为使用ProcessOn(https://www.processon.com/)作图。

二叉树(Binary Tree)

每个节点(node)最多有两个子树(children)。

—Wikipedia

二叉树的遍历:

深度优先遍历(depth-first order)、广度优先遍历(Breadth-first order)

前序遍历(pre-order)、中序遍历(in-order)、后序遍历(post-order)

 

二叉搜索树(Binary Search Tree)

是一颗二叉树同时有以下性质:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。—wikipedia

当插入的数据有序时,查找效率跟顺序查找的效率相当,所以有了平衡树,使得左右子树高度严格平衡(相差0或1)。

 

平衡二叉搜索树(Balanced Binary Tree)

平衡二叉搜索树跟二叉搜索树差别在于,当插入、删除数据导致树的高度相差大于1时,会对树进行旋转(rotate)。

平衡二叉树可以保证查找时间,但是删除节点需要检查从删除节点开始到根的路径上所有的平衡因子,因此删除代价较大。

图自百度百科

红黑树(Red-black tree) # 划重点

牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。—wikipedia

删除节点时只需要进行最多3次的旋转。

 

  1. 节点是红色或黑色。
  2. 根是黑色。
  3. 所有叶子都是黑色(叶子是NIL节点)。
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

—-wikipedia

 

B树(B-Tree)

一般化的二叉查找树,可以拥有多于2个子节点。

 

B+树(B+Tree) # 划重点

 

插入搜索删除都是重点

 

 

 

 

复习总结(1)数据结构data structure(1)

对学过的数据结构做一个简单的归纳总结,且作为以后的复习提纲。

图片未标明出处的均为使用ProcessOn(https://www.processon.com/)作图。

数组(Array)

线性结构。

 

链表(Linked List)

包括单向链表(Singly linked list)、双向链表(Doubly linked list)、循环链表(Circular linked list)等。

单向链表 —-Wikipedia

双向链表 —-Wikipedia

循环链表—-Wikipedia

 

 

队列(queue)

先进先出(First-In-First_Out)的线性表(Linear List),常用数组(Array)或者链表(Linked list)实现。

栈(Stack)

先进后出(First-In-Last-Out),从同一端进(push)和出(pop)

 

哈希表(Hash Table)

散列函数为F(),通过index = F(key)获得元素在哈希表内的位置。

—Wikipedia

重点:

哈希函数(Hash function)

冲突处理(Collision resolution)

 

堆(heap)

使用线性结构存储的二叉树(通常情况下),满足

(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4… n/2) —wikipedia

常用于堆排序

 

2018春季头条实习面试总结

3月1号投了今日头条深圳的后台开发岗位,第二天HR就打电话商量面试时间,定在了3月6号下午。

到达之后,在前台签到,签到本可以看见在我之前有几个人也是去面试的,但是人数不多。签到之后,HR安排了一小间会议室,让我在里面等面试官,不久就进来一位面试官,一对一面试。

首先是给了一张试卷,上面有仨算法题,给10分钟的时间,选一题得出思路,然后10分钟之后给他讲思路。题目难度都不算大,大约在中等題的难度。因为可能他们还会使用同样题目面试,所以这里就不总结算法题了。10分钟之后,面试官进来,我讲了思路,他的反应我感觉还行。然后给我30分钟,用纸和笔写下代码。(这里我写的是python,因为他们岗位要求python或者golang,但是他看见我写python的时候愣了一下然后说了一句“python也可以,不规定语言”,似乎python不是回答的首选语言)

然后就开始问问题,都是比较基础的题,我把回忆到的题归纳了一下。顺序不一定是当时面试顺序。

有哪些排序算法

这个是算法里面基础知识,当时回答了冒泡、插入、选择排序,快排、归并排序,堆排序。回来查一下,排序还有希尔排序、计数排序、桶排序、基数排序等等排序算法。这次没有问到其中哪种的具体实现。

linux的常用命令

问了查看内存占用的命令和创建文件夹的命令。就是考察linux的常用命令,看看有没有相关经验。可惜当时一个紧张死活想不起来查看内存命令是哪个了,而文件管理相关我都是用winscp于是也想不起来了,于是面试官补问了删除的命令,这个我终于答上了。(毕竟rm是个梗)所以linux的常规命令还是需要熟悉下记住的。

僵尸进程、孤儿进程

在类UNIX系统中,僵尸进程是指完成执行(通过 exit 系统调用,或运行时发生致命错误或收到终止信号所致)但在操作系统的进程表中仍然有一个表项(进程控制块PCB),处于”终止状态”的进程。—-wikipedia

在操作系统领域中,孤儿进程指的是在其父进程执行完成或被终止后仍继续运行的一类进程。—-wikipedia

孤儿进程会被init进程收养善后,没有危害。如果僵尸进程过多,则会大量占用系统的进程号,导致不能创建新进程。可以通过kill父进程,让僵尸进程被init进程收养善后。

附相关的知识“守护进程”:

在一个多任务的电脑操作系统中,守护进程英语:daemon/ˈdmən//ˈdmən/)是一种在后台执行的电脑程序。此类程序会被以进程的形式初始化。守护进程程序的名称通常以字母“d”结尾:例如,syslogd就是指管理系统日志的守护进程。

通常,守护进程没有任何存在的父进程(即PPID=1),且在UNIX系统进程层级中直接位于init之下。守护进程程序通常通过如下方法使自己成为守护进程:对一个子进程运行fork,然后使其父进程立即终止,使得这个子进程能在init下运行。这种方法通常被称为“脱壳”。

系统通常在启动时一同起动守护进程。守护进程为对网络请求,硬件活动等进行响应,或其他通过某些任务对其他应用程序的请求进行回应提供支持。守护进程也能够对硬件进行配置(如在某些Linux系统上的devfsd),运行计划任务(例如cron),以及运行其他任务。—-wikipedia

进程间通讯方式
  1. 管道(pipe),流管道(s_pipe)和有名管道(FIFO)
  2. 信号(signal)
  3. 消息队列
  4. 共享内存
  5. 信号量
  6. 套接字(socket)

进程间通讯主要是这6种通讯方式,要注意的是,pipe(无名管道)只能在父子进程之间通讯,要在任意两个进程直接通讯的话需要有名管道(FIFO)

TCP为什么需要三次握手和4次分手

这个据说是面试中的经典题,网上也有很多答案,此处就不贴了。

cookie和session的区别

cookie 和session 的区别:

1、cookie数据存放在客户的浏览器上,session数据放在服务器上。

2、cookie不是很安全,别人可以分析存放在本地的COOKIE并进行COOKIE欺骗
考虑到安全应当使用session。

3、session会在一定时间内保存在服务器上。当访问增多,会比较占用你服务器的性能
考虑到减轻服务器性能方面,应当使用COOKIE。

4、单个cookie保存的数据不能超过4K,很多浏览器都限制一个站点最多保存20个cookie。

5、所以个人建议:
将登陆信息等重要信息存放为SESSION
其他信息如果需要保留,可以放在COOKIE中

(以上摘自http://www.cnblogs.com/shiyangxt/articles/1305506.html)

也有其它相关的比较详细的解答可以参考https://www.zhihu.com/question/19786827

HTTP请求报文的结构

一个HTTP请求报文由请求行(request line)、请求头部(header)、空行和请求数据4个部分组成,下图给出了请求报文的一般格式。

典型的请求头有:

User-Agent:产生请求的浏览器类型。

Accept:客户端可识别的内容类型列表。

Host:请求的主机名,允许多个域名同处一个IP地址,即虚拟主机。

附相关内容:

  • 200 OK:客户端请求成功。
  • 301 redirect: 301 代表永久性转移(Permanently Moved)。
  • 302 redirect: 302 代表暂时性转移(Temporarily Moved )。
  • 400 Bad Request:客户端请求有语法错误,不能被服务器所理解。
  • 401 Unauthorized:请求未经授权,这个状态代码必须和WWW-Authenticate报头域一起使用。
  • 403 Forbidden:服务器收到请求,但是拒绝提供服务。
  • 404 Not Found:请求资源不存在,举个例子:输入了错误的URL。
  • 500 Internal Server Error:服务器发生不可预期的错误。
  • 503 Server Unavailable:服务器当前不能处理客户端的请求,一段时间后可能恢复正常,举个例子:HTTP/1.1 200 OK(CRLF)。
数据库是怎么样做索引的

应该是考察B树和B+树和相关内容,此处可以参阅

http://blog.csdn.net/suifeng3051/article/details/52669644

有哪些数据库引擎

面试官让我说出我记得的数据库引擎的名字,应该是考察有没有了解不同数据库引擎特征和区别。现在总结了一下主要这几种:

  • ISAM:执行读取操作的速度很快,而且不占用大量的内存和存储资源。不支持事务处理,也不能够容错
  • MYISAM:MYISAM是MYSQL的ISAM扩展格式和缺省的数据库引擎。强调了快速读取操作。

  • HEAP:允许只驻留在内存里的临时表格。驻留在内存里让HEAP要比ISAM和MYISAM都快,但是它所管理的数据是不稳定的,而且如果在关机之前没有进行保存,那么所有的数据都会丢失。
  • INNODB和BERKLEYDB:比ISAM和MYISAM引擎慢很多,但是INNODB和BDB包括了对事务处理外来键的支持

更详细可以参考:http://www.cnblogs.com/0201zcr/p/5296843.html

数据库单个表数据量量多大时需要做分表

先是问了我们项目的数据库数据量一般有多大,然后就问到了这个问题。在数据量多大的时候,查询速度会明显下降,我们需要进行分表操作。这个问题我至今仍不能确定答案。有说法是百万条到千万条的时候需要做分表。

计算字符串种类

面试最后的一题,算法题。有一个很大的TB级的文件,里面是一个一个字符串,用空格隔开。问里面有多少种字符串。例如aab和aab是一种,aab和aac是两种。使用一个分布式的系统解决。当时我提出使用map-reduce,一开始说按照字符串首几位分发,被提醒后改为按SHA1后的首几位分发,然后reduce的过程当时说得不太清楚,就说把种类加起来就可以了(已经被问到一愣一愣了)。现在觉得应该在每个系统维护一个哈希表,然后就可以在O(1)的时间内对单条记录计算种类累加了,最后表有多少项就是有多少种,把所有的加起来就是总的种类数了。此题可能有更好的解法。

面试小结:

面试问的基本都是计算机基础题,算法、操作系统、计网、数据库系统。然后还会问到项目的内容和项目相关的问题。可见基础在面试里面的比重非常的大,项目经历也要有,会根据项目经历问一些题目。没有问到python相关的问题,面试前几天把蛇书《python高性能编程》过了一遍,白看了。本来预计他4月才面试,才刚刚开始复习课本,没想到面试来得猝不及防,基础题回答得一塌糊涂。问完后他说找下一个面试官,然后出去没一会就回来了,说下一面面试官不在。当时就知道凉了。拒信在面试完第二天中午就发过来,HR一直都很有效率。。。