非算法工程师面试必问的算法面试理论

· jack · Created at · Last by kkmmi68 Replied at · 1356 hits
434 1549005614

非算法方向的你

面了多少次试?

最后,因为不懂算法,

死在了半路上?

这些痛,

作为技术创新型公司的小编——个推君

怎么会不懂?

为此,个推君特请了我司经验丰富的面试官

为你奉上一份热乎的面试宝典。

宝典可不是面试题哦

仅送给想认真钻研的童鞋

帮大家梳理知识点

让大家举一反三,

offer拿到手软!

注:此处建议大家使用 C 语言来学习数据结构与算法。

数据结构

首先我们得从数据结构开始,大家至少得数据结构有个概念,大部分的算法题均需要带入数据结构的概念来处理。
科班出身的程序员或多或少学习过数据结构,推荐大家重温下这本书,温故而知新。

时间复杂与空间复杂度

在说算法之前和大家科普两个重要的理论知识:算法的时间复杂度与空间复杂度

时间复杂度:

算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述,并且会忽略常量部分,。

举个例子

int aFunc(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

调用此方法,printf("Hello, World!\n"); 执行了一次,那么我们记做 T(n) = O(1)

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

此处输出语句被执行了 n 次,那么我们记做 T(n) = O(n)

再看一个

int aFunc(int n) {
    for(int i = 0; i<3*n; i++) {    
        for(int j = 0; j<2*n; i++) {       // 需要执行 (n) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;      
}

此处输出语句被执行了 (3*n)*(2*n) 次,f(n)=6n^2,由于我们是忽略常量的,所以 T(n)=O(n^2)

空间复杂度:

是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)。

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

字符串

字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2···an”(n>=0)。它是编程语言中表示文本的数据类型。在程序设计中,字符串(string)为符号或数值的一个连续序列,如符号串(一串字符)或二进制数字串(一串二进制数字)。

这个不多说了,敲代码的都懂,一切皆可字符串。

数组

所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。

在 C 语言中,数组可分为一维数组,二维数组,多维数组等。而涉及到怎么创建数组这边就细讲了,各个语言的的申明方法以及使用方法都不太相同。

二维数组结构图

举例

  • int a[10]; 说明整型数组a,有10个元素。若要表示第10个元素,则使用a[9]。第一个则是a[0]。
  • float b[10],c[20]; 说明实型数组b,有10个元素,实型数组c,有20个元素。
  • char ch[20]; 说明字符数组ch,有20个元素。

链表(Node)

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

链表是我们比较常用的数据结构,如果在编程的过程中,需要进行频繁 增&删 操作的,优先使用链式存储结构。
链表分为我们常见的单链表,还有双链表以及循环链表

单链表结构体

typedef struct LNode
{
    int data;           //data中存放结点数据域(默认是int型)
    struct LNode *next; //指向后继结点的指针
}LNode;

单链表结构图


栈 (Stack)

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

栈是一种先进后出的的数据结构,有入栈和入栈两种常见操作。

结构体

typedef struct Stack{   // 栈

    PNODE pTop;
    PNODE pBottom;

}STACK,*PSTACK;

结构图

队列(Queue)

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。

队列是一种先进先出的的数据结构,有入队和出队两种常见操作,一般有顺序队列,双向队列,循环队列。

结构体

typedef struct{
    ELemType data[MaxSize];
    int front, rear;
}SqQueue;

结构图

树(Tree)

它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

树是一个大类,树下面又分 二叉树,平衡二叉树,AVL 树,字典树,哈夫曼树,红黑树,b 树等,考察的最多的是二叉树与红黑树

结构体

下图是二叉树的结构体定义

typedef struct TNode{
    TElemType  data;
    struct TNode *lchild,*rchild;
}TNode,*Tree;

二叉树结构图

图(Graph)

图是由顶点的有穷非空集合和顶点之间边的集合组成, 通常表示为: G(V,E), 其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。顶点有时也称为节点或者交点,边有时也称为链接。

结构图

算法和数据操作

粗略的讲了下数据结构的理论,终于要进入正餐了。算法题大致分为以下几大类,还有一些小类就不举例了,比如位运算,回溯算法等。

查找

查找也可以叫做搜索,这是算法分类里面最最最普通的一个模块,查找分为 线性查找,数表查找,哈希查找

掌握程度: 查找 类型的较多问题,每一种数据结构都有自己的查找类型的经典算法,比如 数组对应的最小值/最大值查找、字符串对应的关键字查找、链表对应的回环判断等、树对应的深度/广度优先,二叉树对应的 前/中/后 遍历,最 小/大 堆查找 ,这些本质是都是和查找算法相关的。

推荐范例: 这个不好推荐,实在是太多了。

排序

说到排序,大家都非常熟悉了,排序分为内排序和外排序,因为外排序的出现频率较低,这边只进行内排序的分析,我们常见的选择,冒泡,快排均属于内排序。

具体的算法不展开了,百度有全家桶

掌握程度:除了基数排序和希尔排序,其他几个排序算法均需要可以默写算法的程度,接着要进行实战操作,刷完下面的这些题目,对排序算法会有个清晰的理解。
推荐范例排序范例

递归

讲到递归的时候,我们在使用的过程中,特别要对递归终止的条件有个清晰的把握,不然很容易陷入死循环当中

掌握程度:链接里面的就 14 到题目,希望全部刷一遍。值得注意的是,递归的题目一般来说会有多种解法。
推荐范例递归集合

动态规划

动态规划,又名DP算法(取自其Dynamic Programming的缩写),最初是运筹学的一个分支,是用来求解决策过程最优化的数学方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题,例如斐波那契数列,如果运用递归的方式来求解会重复计算很多相同的子问题,利用动态规划的思想可以减少计算量。比如我们常见的爬楼梯的问题,对了这个问题一般有多种解法。
掌握程度: 这类问题的相似度非常的高,希望大家可以达到触类旁通的境界
推荐范例买卖股票的最佳时机爬楼梯

贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。比如我们常见的爬楼梯问题
掌握程度: 如果不是面试算法工程师的话,建议刷完 10 道简单的题目即可
推荐范例贪心算法范例

图这块知识会涉及到很深很深的东西,如果不是从事这方向研究的,停留在理论层+一些简单算法即可,图里面有很多的经典算法需要掌握。

比如 普利姆算法,克鲁斯卡尔算法等,这些都是非常经典的算法,需要知道经典算法的设计逻辑以及优缺点。
掌握程度: 熟悉各类存储结构,精通经典算法的实现思路
推荐范例图算法的范例

LeetCode 正确的打开方式

大家有没有发现上个章节频繁的出现了 LeetCode 这个字眼,那么这个网站到底是什么呢?在介绍之前还得和大家说下该怎么刷题吗。刷题网站有力扣 (LeetCode 中文版),清华 ACM,浙大 ACM,这几个网站算法学习生态圈都比较稳定,LeetCode 也是其中的一种,我习惯用力扣(力扣的小编看到的话记得给我加个鸡腿),这是一个宝藏网站,里面的内容非常的多,大家感兴趣的可以深入研究下。

这上面的题目也就 1117 题而已,可以从不同的维度去刷题,比如难易度,问题分类,通过率等。我推荐是根据
数据结构的分类来,比如你今天学了二叉树,那么打开 LeetCode,耗时 2 天刷十道简单题的二叉树即可。按照这种思路,差不多 1 个月即可完成上述所描述的题目。希望大家时间还来得及


这些都是我个人的一些学习经历,通过这个网站的可视化界面,可以较直观对自己的学习有个回顾。
推荐是用 C 语言,因为 C 语言更接近底层,编译速度会快那么零点几毫秒,别小看几毫秒的时间哦,因为在 LeetCode 上,算法耗时的最小单位是 1 毫秒。。。差一毫秒可是差别巨大的。


如果你写的算法仅战胜了 40%的提交记录,老学长建议你重写提交下,算法魅力就在于此,毫秒必争!一个好的算法可以让程序的编译速度成几何倍速的增加。 也可以直接点击柱状图,会有当前算法耗时的最优算法解。

说了一些 LeetCode 的东西,我们看看实际开发过程中,安利大家一个 IDEA 的 LeetCode 的插件,名字就叫 leetcode ,使用这个小插件,可以帮助我们快速编译所写的 demo。

编写的算法可以直接在编译器里测试 & 提交。

杂谈

说个现实的问题,除非是算法工程师,大家在开发的过程中极少用到算法的,那是不是反向推论算法仅是停留在做题&面试,仅需要应付面试即可了?那是不是只要疯狂刷题就可以了!!!
不过话说回来,不推荐大家这么玩,推荐大家在理论的基础上加以实践,还是希望大家可以深入的学习数据结构与算法,会对计算机的运行有着更深入的理解,后面是我自己看过的一些书本与优秀公众号,链接是我的个人刷题库
https://github.com/LiuLei0571/LeetCode

书籍推荐

《算法 4 》,《漫画算法》,《大话设计模式》,《大话数据结构》,《剑指 offer》

大牛推荐

  • 任玉刚老师的《玉刚说》公众号:会讲很多关于算法面试,架构体系,职场分析的文章。
  • 波波老师的《是不是很酷》公众号:波波老师是我认为目前把算法与数据结构讲的最透彻的讲师,大家可以去 X课网搜一下就可知道

彩蛋

感谢各位看官阅读到最后,你们的支持是我创作的源泉,最后给大家放一道我在实际开发中遇到的算法问题。

有以下一个 json 字符串,编写一个算法测试此 json 是否有回路。action_chains 里面有若干个动作,入口动作是 actionid=1,接着去执行下一个动作,下一个动作的 actionid 是上一个动作的 do 参数,出口是 actionid=100。


{
    "action_chains": [
        {
            "actionid": "1",
            "do": "2"
        },
        {
            "actionid": "2",
            "do": "3"
        },
        {
            "actionid": "3",
            "do": "4"
        },
        {
            "actionid": "4",
            "do": "5"
        },
        {
            "actionid": "5"  
        }
    ]
}


请关注**个推技术学院**公众号回复“答案”即可查阅答案。

![](https://user-gold-cdn.xitu.io/2019/8/28/16cd6db235f68124?w=640&h=427&f=png&s=61758)


共收到 32 条回复
1Floor Deleted
2Floor Deleted
3Floor Deleted
4Floor Deleted
5Floor Deleted
6Floor Deleted
7Floor Deleted
8Floor Deleted
9Floor Deleted
10Floor Deleted
11Floor Deleted
12Floor Deleted
13Floor Deleted
14Floor Deleted
15Floor Deleted
16Floor Deleted
17Floor Deleted
18Floor Deleted
19Floor Deleted
20Floor Deleted
25Floor Deleted
26Floor Deleted
27Floor Deleted
24Floor Deleted
需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up