您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > JAVA

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

时间:2019-06-18 10:32:47  来源:  作者:

瑞士计算机科学家Niklaus Wirth在1976年写了一本书,名为《算法+数据结构=编程》。

40多年后,这个等式仍被奉为真理。这就是为什么在面试过程中,需要考察软件工程师对数据结构的理解。

几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业),还是拥有几十年经验的职场老鸟。

有些面试题会明确提及某种数据结构,例如,“给定一个二叉树。”而另一些则隐含在面试题中,例如,“我们希望记录每个作者相关的书籍数量。”

即便是对于一些非常基础的工作来说,学习数据结构也是必须的。那么,就让我们先从一些基本概念开始入手。

什么是数据结构?

简单地说,数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。首先我们需要理解各种数据结构,才能在处理实际问题时选取最合适的数据结构。

为什么我们需要数据结构?

数据是计算机科学当中最关键的实体,而数据结构则可以将数据以某种组织形式存储,因此,数据结构的价值不言而喻。

无论你以何种方式解决何种问题,你都需要处理数据——无论是涉及员工薪水、股票价格、购物清单,还是只是简单的电话簿问题。

数据需要根据不同的场景,按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

常见的数据结构

首先列出一些最常见的数据结构,我们将逐一说明:

数组

队列

链表

字典树(这是一种高效的树形结构,但值得单独说明)

散列表(哈希表)

数组

数组是最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素(1,2,3和4)的简单数组,数组长度为4。

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

每个数据元素都关联一个正数值,我们称之为索引,它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。关注JAVA技术栈微信公众号,回复"面试"获取更多博主精心整理的面试题。

以下是数组的两种类型:

一维数组(如上所示)

多维数组(数组的数组)

数组的基本操作

Insert——在指定索引位置插入一个元素

Get——返回指定索引位置的元素

Delete——删除指定索引位置的元素

Size——得到数组所有元素的数量

面试中关于数组的常见问题

寻找数组中第二小的元素

找到数组中第一个不重复出现的整数

合并两个有序数组

重新排列数组中的正值和负值

著名的撤销操作几乎遍布任意一个应用。但你有没有思考过它是如何工作的呢?这个问题的解决思路是按照将最后的状态排列在先的顺序,在内存中存储历史工作状态(当然,它会受限于一定的数量)。这没办法用数组实现。但有了栈,这就变得非常方便了。

可以把栈想象成一列垂直堆放的书。为了拿到中间的书,你需要移除放置在这上面的所有书。这就是LIFO(后进先出)的工作原理。

下图是包含三个数据元素(1,2和3)的栈,其中顶部的3将被最先移除:

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

栈的基本操作

Push——在顶部插入一个元素

Pop——返回并移除栈顶元素

isEmpty——如果栈为空,则返回true

Top——返回顶部元素,但并不移除它

面试中关于栈的常见问题

使用栈计算后缀表达式

对栈的元素进行排序

判断表达式是否括号平衡

队列

与栈相似,队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO(后进先出),而队列是FIFO,即先进先出。

一个完美的队列现实例子:售票亭排队队伍。如果有新人加入,他需要到队尾去排队,而非队首——排在前面的人会先拿到票,然后离开队伍。

下图是包含四个元素(1,2,3和4)的队列,其中在顶部的1将被最先移除:

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

移除先入队的元素、插入新元素

队列的基本操作

Enqueue() —— 在队列尾部插入元素

Dequeue() ——移除队列头部的元素

isEmpty()——如果队列为空,则返回true

Top() ——返回队列的第一个元素

面试中关于队列的常见问题

使用队列表示栈

对队列的前k个元素倒序

使用队列生成从1到n的二进制数

链表

链表是另一个重要的线性数据结构,乍一看可能有点像数组,但在内存分配、内部结构以及数据插入和删除的基本操作方面均有所不同。关注Java技术栈微信公众号,回复"面试"获取更多博主精心整理的面试题。

链表就像一个节点链,其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针,它指向链表的第一个元素,但当列表为空时,它指向null或无具体内容。

链表一般用于实现文件系统、哈希表和邻接表。

这是链表内部结构的展示:

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

链表包括以下类型:

单链表(单向)

双向链表(双向)

链表的基本操作:

InsertAtEnd - 在链表的末尾插入指定元素

InsertAtHead - 在链接列表的开头/头部插入指定元素

Delete - 从链接列表中删除指定元素

DeleteAtHead - 删除链接列表的第一个元素

Search - 从链表中返回指定元素

isEmpty - 如果链表为空,则返回true

面试中关于链表的常见问题

反转链表

检测链表中的循环

返回链表倒数第N个节点

删除链表中的重复项

图是一组以网络形式相互连接的节点。节点也称为顶点。 一对节点(x,y)称为边(edge),表示顶点x连接到顶点y。边可以包含权重/成本,显示从顶点x到y所需的成本。

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

图的类型

无向图

有向图

在程序语言中,图可以用两种形式表示:

邻接矩阵

邻接表

常见图遍历算法

广度优先搜索

深度优先搜索

面试中关于图的常见问题

实现广度和深度优先搜索

检查图是否为树

计算图的边数

找到两个顶点之间的最短路径

树形结构是一种层级式的数据结构,由顶点(节点)和连接它们的边组成。 树类似于图,但区分树和图的重要特征是树中不存在环路。

树形结构被广泛应用于人工智能和复杂算法,它可以提供解决问题的有效存储机制。

这是一个简单树的示意图,以及树数据结构中使用的基本术语:

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

Root - 根节点

Parent - 父节点

Child - 子节点

Leaf - 叶子节点

Sibling - 兄弟节点

想要学习Java高架构、分布式架构、高可扩展、高性能、高并发、性能优化、Spring boot、redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频免费获取 架构群:835544715

点击链接加入群聊【JAVA高级架构】:https://jq.qq.com/?_wv=1027&k=5dbERkY

以下是树形结构的主要类型:

N元树

平衡树

二叉树

二叉搜索树

AVL树

红黑树

2-3树

其中,二叉树和二叉搜索树是最常用的树。

面试中关于树结构的常见问题:

求二叉树的高度

在二叉搜索树中查找第k个最大值

查找与根节点距离k的节点

在二叉树中查找给定节点的祖先节点

字典树(Trie)

字典树,也称为“前缀树”,是一种特殊的树状数据结构,对于解决字符串相关问题非常有效。它能够提供快速检索,主要用于搜索字典中的单词,在搜索引擎中自动提供建议,甚至被用于IP的路由。

以下是在字典树中存储三个单词“top”,“so”和“their”的例子:

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

这些单词以顶部到底部的方式存储,其中绿色节点“p”,“s”和“r”分别表示“top”,“thus”和“theirs”的底部。

面试中关于字典树的常见问题

计算字典树中的总单词数

打印存储在字典树中的所有单词

使用字典树对数组的元素进行排序

使用字典树从字典中形成单词

构建T9字典(字典树+ DFS )

哈希表

哈希法(Hashing)是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引(称为“键(key)”)中的过程。因此,对象以键值对的形式存储,这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构,但最常用的数据结构是哈希表。

哈希表通常使用数组实现。

散列数据结构的性能取决于以下三个因素:

哈希函数

哈希表的大小

碰撞处理方法

下图为如何在数组中映射哈希键值对的说明。该数组的索引是通过哈希函数计算的。

Java 程序员必须掌握的 8 道数据结构面试题,你会几道?

面试中关于哈希结构的常见问题:

在数组中查找对称键值对

追踪遍历的完整路径

查找数组是否是另一个数组的子集

检查给定的数组是否不相交
 



Tags:Java   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
面向对象的特征之一封装 面向对象的特征之二继承 方法重写(override/overWrite) 方法的重载(overload)和重写(override)的区别: 面向对象特征之三:多态 Instanceof关键字...【详细内容】
2021-12-28  Tags: Java  点击:(2)  评论:(0)  加入收藏
一、Redis使用过程中一些小的注意点1、不要把Redis当成数据库来使用二、Arrays.asList常见失误需求:把数组转成list集合去处理。方法:Arrays.asList 或者 Java8的stream流式处...【详细内容】
2021-12-27  Tags: Java  点击:(3)  评论:(0)  加入收藏
文章目录 如何理解面向对象编程? JDK 和 JRE 有什么区别? 如何理解Java中封装,继承、多态特性? 如何理解Java中的字节码对象? 你是如何理解Java中的泛型的? 说说泛型应用...【详细内容】
2021-12-24  Tags: Java  点击:(5)  评论:(0)  加入收藏
1、通过条件判断给变量赋值布尔值的正确姿势// badif (a === 'a') { b = true} else { b = false}// goodb = a === 'a'2、在if中判断数组长度不为零...【详细内容】
2021-12-24  Tags: Java  点击:(6)  评论:(0)  加入收藏
Java与Lua相互调用案例比较少,因此项目使用需要做详细的性能测试,本内容只做粗略测试。目前已完成初版Lua-Java调用框架开发,后期有时间准备把框架进行抽象,并开源出来,感兴趣的...【详细内容】
2021-12-23  Tags: Java  点击:(11)  评论:(0)  加入收藏
传统游戏项目一般使用TCP协议进行通信,得益于它的稳定和可靠,不过在网络不稳定的情况下,会出现丢包严重。不过近期有不少基于UDP的应用层协议,声称对UDP的不可靠进行了改造,这意...【详细内容】
2021-12-23  Tags: Java  点击:(12)  评论:(0)  加入收藏
文章目录1、Quartz1.1 引入依赖<dependency> <groupId>org.quartz-scheduler</groupId> <artifactId>quartz</artifactId> <version>2.3.2</version></dependency>...【详细内容】
2021-12-22  Tags: Java  点击:(12)  评论:(0)  加入收藏
Java从版本5开始,在 java.util.concurrent.locks包内给我们提供了除了synchronized关键字以外的几个新的锁功能的实现,ReentrantLock就是其中的一个。但是这并不意味着我们可...【详细内容】
2021-12-17  Tags: Java  点击:(11)  评论:(0)  加入收藏
一、概述final是Java关键字中最常见之一,表示“最终的,不可更改”之意,在Java中也正是这个意思。有final修饰的内容,就会变得与众不同,它们会变成终极存在,其内容成为固定的存在。...【详细内容】
2021-12-15  Tags: Java  点击:(17)  评论:(0)  加入收藏
1、问题描述关于java中的日志管理logback,去年写过关于logback介绍的文章,这次项目中又优化了下,记录下,希望能帮到需要的朋友。2、解决方案这次其实是碰到了一个问题,一般的情况...【详细内容】
2021-12-15  Tags: Java  点击:(19)  评论:(0)  加入收藏
▌简易百科推荐
面向对象的特征之一封装 面向对象的特征之二继承 方法重写(override/overWrite) 方法的重载(overload)和重写(override)的区别: 面向对象特征之三:多态 Instanceof关键字...【详细内容】
2021-12-28  顶顶架构师    Tags:面向对象   点击:(2)  评论:(0)  加入收藏
一、Redis使用过程中一些小的注意点1、不要把Redis当成数据库来使用二、Arrays.asList常见失误需求:把数组转成list集合去处理。方法:Arrays.asList 或者 Java8的stream流式处...【详细内容】
2021-12-27  CF07    Tags:Java   点击:(3)  评论:(0)  加入收藏
文章目录 如何理解面向对象编程? JDK 和 JRE 有什么区别? 如何理解Java中封装,继承、多态特性? 如何理解Java中的字节码对象? 你是如何理解Java中的泛型的? 说说泛型应用...【详细内容】
2021-12-24  Java架构师之路    Tags:JAVA   点击:(5)  评论:(0)  加入收藏
大家好!我是老码农,一个喜欢技术、爱分享的同学,从今天开始和大家持续分享JVM调优方面的经验。JVM调优是个大话题,涉及的知识点很庞大 Java内存模型 垃圾回收机制 各种工具使用 ...【详细内容】
2021-12-23  小码匠和老码农    Tags:JVM调优   点击:(12)  评论:(0)  加入收藏
前言JDBC访问Postgresql的jsonb类型字段当然可以使用Postgresql jdbc驱动中提供的PGobject,但是这样在需要兼容多种数据库的系统开发中显得不那么通用,需要特殊处理。本文介绍...【详细内容】
2021-12-23  dingle    Tags:JDBC   点击:(13)  评论:(0)  加入收藏
Java与Lua相互调用案例比较少,因此项目使用需要做详细的性能测试,本内容只做粗略测试。目前已完成初版Lua-Java调用框架开发,后期有时间准备把框架进行抽象,并开源出来,感兴趣的...【详细内容】
2021-12-23  JAVA小白    Tags:Java   点击:(11)  评论:(0)  加入收藏
Java从版本5开始,在 java.util.concurrent.locks包内给我们提供了除了synchronized关键字以外的几个新的锁功能的实现,ReentrantLock就是其中的一个。但是这并不意味着我们可...【详细内容】
2021-12-17  小西学JAVA    Tags:JAVA并发   点击:(11)  评论:(0)  加入收藏
一、概述final是Java关键字中最常见之一,表示“最终的,不可更改”之意,在Java中也正是这个意思。有final修饰的内容,就会变得与众不同,它们会变成终极存在,其内容成为固定的存在。...【详细内容】
2021-12-15  唯一浩哥    Tags:Java基础   点击:(17)  评论:(0)  加入收藏
1、问题描述关于java中的日志管理logback,去年写过关于logback介绍的文章,这次项目中又优化了下,记录下,希望能帮到需要的朋友。2、解决方案这次其实是碰到了一个问题,一般的情况...【详细内容】
2021-12-15  软件老王    Tags:logback   点击:(19)  评论:(0)  加入收藏
本篇文章我们以AtomicInteger为例子,主要讲解下CAS(Compare And Swap)功能是如何在AtomicInteger中使用的,以及提供CAS功能的Unsafe对象。我们先从一个例子开始吧。假设现在我们...【详细内容】
2021-12-14  小西学JAVA    Tags:JAVA   点击:(22)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条