一线IT企业面试中码农必须知道的六种数据结构

原创 码农  2020-01-11 20:01:34  阅读 208 次 评论 0 条

瑞士著名科学家N.Wirth教授曾提出:算法+数据结构=程序。如果说:数据结构是程序的骨架,那么算法就是程序的灵魂。

对于大部分程序员而言,算法在日常工作中占比不一定会很高,但如果想要找到一份好的工作,算法就显得格外重要。尤其是在腾讯、百度、阿里巴巴等国内的一线IT名企,招聘工程师的过程中,对算法和数据结构都会重点考察,而且通常要现场写代码实现。很多同学因为这个败走麦城,导致面试失败。

其实关于数据结构与算法的面试题是有规律,有套路的。只要大家将最基础的内容掌握踏实,那么解决面试中的问题就不会太困难。下面本号总结了面试中必然会遇到的数据结构相关的内容,对大家日后面试一定非常有帮助。

数据结构之队列

队列也是一种线性表,其插入和删除操作分别在表的不同端进行。插入元素的一端称为队尾,删除元素的一端称为队首。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第1张

队列是应用非常广泛的数据结构,在很多大规模程序中都有队列的身影。比如在多线程之间传输数据,或者是视窗操作系统的窗口管理等方面。

数据结构之数组

数组是所有数据结构中最简单的数据结构了,很多复杂的数据结构依赖数组实现,比如哈希表等。数组是一个连续的内存空间,因此我们可以一次定位其中的元素,也就是其查找是O(1)时间复杂度。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第2张

因此,数组相关的面试题也是最多的。很多面试官喜欢问数组相关的面试题,如果大家上力扣就会发现数组面试题是最多的。这主要是因为,数组的面试题可易,可难,因此面试起来非常自如。

数组的面试题归结起来其实就是对数组的各种遍历和操作。遍历就是查找了,核心是二分查找;操作就是对数组元素的移动和删除等操作。下面我们通过几个经典的面试题介绍一下数组面试题的解法。

面试题举例之两数之和

给定一个整数数组array和一个目标值 target,在该数组中找出和为目标值的那两个整数并返回他们的下标。为了简化问题,我们可以假设数组中只有一对答案。为了明确问题,我们举一个具体的例子。假设数组为[1, 3, 5, 7], target = 8

在上述数组中3+5=8,因此返回 [1, 2],也就是数组的下标。

该面试题是一个典型的数组遍历类的问题,最简单暴力的解法是对数组中的每一个元素进行遍历配对,找到合适的结果。但是这种情况的时间复杂度太高,通常不能通过面试。为了让大家清楚,我们还是介绍一下该算法。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第3张

如图2所示,我们逐次遍历数组中的元素,并将其与后面的元素进行对比,判断是否有符合要求的元素对。实现算法如下所示,该算法耗时很长,大家可以在力扣测试一下。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第4张

另外一种解法是借助哈希表,因为哈希表几乎可以在O(1)的时间复杂度找到元素,因此我们可以通过空间来换时间。具体方法是在遍历数组的时候,首先判断哈希表中是否有可以与当前元素配对的元素,如果没有则将该元素加入哈希表中(为后面查找做准备),如果有则说明找到了元素对。具体代码实现如下所示。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第5张

除了上面分析的面试题外,还有很多数组相关的面试题,具体可以参考《互联网大厂offer收割之数组及相关面试题解决方法》。

数据结构之链表

想必大家对数组都非常熟悉,数组在存储空间(内存)上是连续的。因此,我们可以根据偏移量轻易的找到数组中的数据。但数组最大的问题是大小固定,很多场景是无法预判需要的空间大小的。

这时就需要链表上场了,链表也是一种线性数据结构,但它最大的优势是可以动态的调整大小。这样,我们再也不用担心应该分配多少空间了。

链表是一种物理存储单元上非连续、非顺序的存储结构,元素的逻辑顺序是通过链表中的指针连接次序实现的

链表在日常开发中通常通过数据结构和指针的方式实现,其中包含一个本数据结构的next指针,用于指向下一个元素,这样指下去,就形成了一个单向链表。如下是数据结构的定义:

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第6张

为了便于链表的管理和使用,我们在实际定义的时候通常还会定义个专门的链表头,链表头的定义如下:

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第7张

通过增加一个链表头可以方便链表的管理,同时通过增加的元数据可以很方便的得到一些链表的信息,从而提高效率。这样,整个链表的结构大概如图1所示。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第8张

链表相关的面试题在日常面试中是最常见的,特别是单向链表的面试题。因为链表面试题难易适中,且非常能考察人的编程能力,更多面试题请参考《互联网大厂offer收割之单向链表概念及常见面试题汇总》。

数据结构之栈

栈是一种特殊的线性表,但其特点是插入和删除都在同一端进行,这一端称为栈顶,另外一端称为栈底。如图所示,数字表示入栈的顺序,而右侧的图示为出栈的示意图。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第9张

栈是一个使用频度非常高的数据结构。由于栈结构和原理非常简单,栈本身很少单独作为面试题,但是经常作为基础结构用于复杂的面试题中。比如常见的面试题二叉树的遍历(非递归方法)、波兰表达式和汉诺塔问题等等。

数据结构之树

什么是二叉树(Binary Tree)

每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于2的结点)。并且,二叉树的子树有左右之分,其次序不能任意颠倒。

上面概念中提到了“度”的概念,“度”其实就是某个节点子节点的数量。如果某个节点的子节点数量为1,则该节点的度为1,如果有8个子节点,则度为8,以此类推。

二叉树的术语

除了二叉树的定义外,还有许多相关的术语。单纯介绍术语可能不容易理解,这里给出一幅图进行说明。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第10张

下面是对二叉树中主要术语的解释:

结点的度(Degree):结点的子树个数;

树的度:树的所有结点中最大的度数;

叶结点(Leaf):度为0的结点;

父结点(Parent):有子树的结点是其子树的根节点的父结点;

子结点/孩子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;

兄弟结点(Sibling):具有同一个父结点的各结点彼此是兄弟结点;

路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,...,nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度;

祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点;

子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙;

结点的层次(Level):规定根结点在1层,其他任一结点的层数是其父结点的层数加1;

树的深度(Depth):树中所有结点中的最大层次是这棵树的深度;

二叉树的性质

我们设定二叉树的根节点为为第1层,则二叉树有如下性质。这些性质可以通过数学方式进行证明,但本文暂时不做证明,大家了解即可,对于理解后续概念有一些帮助:

性质1:二叉树第i层上最多有 2^(i-1) 个结点(i≥1);

性质2:深度(高度)为k的二叉树至多有2^(k)-1个结点(k≥1,深度k也就是树的最大层级);

性质3:包含n个结点的二叉树的深度(高度)至少为log2 (n+1);

性质4:在任意一棵二叉树中,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

二叉树的数据存储

二叉树在C语言中可以通过结构体表示,其定义的方式可以是如下:

struct bitree_node {
 int b_data; //数据域,指向具体的数据
 struct bitree_node *left; //指向左子节点
 struct bitree_node *right; //指向右子节点
};

在这个实例中,为了简单,我们假设其存储的数据类型为整型数,当然最好的方式是void指针的形式。这样,二叉树就是一个通用的数据结构,可以存储任何类型的数据。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第11张

二叉树相关的面试题请参考《互联网大厂offer收割之二叉树的基本概念及常见面试题汇总》。

数据结构之图

图是用线或者边连接在一起的顶点或者节点的集合。这里面包含两个关键要素,一个是边,另外一个是节点。根据边的属性,如果边是有方向的,那么这个图就称为有向图,否则称为无向图。如图所示为一个有向图。

一线IT企业面试中码农必须知道的六种数据结构 编程代码 第12张

由于图本身比较复杂,因此关于图的面试题并不太多。这主要是现场面试需要在比较短的时间内完成,图相关的面试题不太合适。常见的面试题包括不邻接植花和寻找小镇法官等面试题。

本文对面试中常问的几种数据结构的概念及算法进行了介绍,如何大家准备跳槽BATD等大厂,应该重点关注这些数据结构及相关的面试题并准备准备。

本文地址:https://www.itcodeit.com/post/49.html
版权声明:本文为原创文章,版权归 码农 所有,欢迎分享本文,转载请保留出处!

发表评论


表情

还没有留言,还不快点抢沙发?