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

Android · jack · Created at · Last by line0997520 Replied at · 325 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)


共收到 1 条回复
96

大台灣啵比舒壓茶坊+賴:0997520
外送地區:北部【台北市區/新北市區/竹北市區】
中部【台中市區/彰化市區/南投市】
南部【高雄市區/台南市區】
營業時間:為下午13:00—凌晨04:00
交易方式:不刷卡~不轉賬~不買點數~不匯款~一律現金~無定金
約會地點:住家~飯店~汽旅~外約~商旅~酒店~
加入啵比+賴:0997520 賬號即可享受2000現金優惠券唷....
妹妹類型:台灣各行各業純本土正妹兼職(提前預約會比較準確)
特別類型:中(日.巴.荷.韓.俄)網紅/混血/空姐/麻豆/二線/三線藝人.....

啵比外約活動大優惠+賴:0997520

1.消費一次不管金額不小免費+免車資送絲襪
2.消費金額5k送絲襪+免車資+3000 優惠券+9折會員
3.消費金額8k送絲襪+原味內褲消費第二次直接半價
4.消費金額10k送超級VIP(永久7折)免費試車10k小模+免費進入約炮群
5.消費金額15k送黃金VIP(永久半價)免費試車15k小模2個小時無限次數

【包夜套餐】+賴:0997520
1.買六節【6小時+免費送2小時】+送3000優惠券
2.買九節【9小時+免費送3小時】+送5000優惠券+半價2次
3.買十二節【12小時+免費4小時】+一次免費試車小姐+永久半價+VIP

【加時套餐】+賴:0997520
1.兩節送一節/兩節送兩節/三節送一節/三節送兩節
2.喝茶連一杯半價
3.還可約3p妹妹
【北中南套餐都可以挑選.詳情咨詢我喲】
外送茶這個行業在台灣真的超多的
很多人會問我好不好做 是不是賺很多
就像你們知道的 我的工作是網路貼貼廣告
跟客人聊聊天 再介紹推薦一下小姐 足不出戶
就會有客人來約來消費 看起來很簡單很輕鬆

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up