记录思考

面试中,最重要的数据结构知识

数据结构是面试中永远少不了的话题。数据结构和算法称为面试中考核一个工程师能力非常重要的标准。

数据结构是面试中永远少不了的话题。数据结构和算法称为面试中考核一个工程师能力非常重要的标准。很多公司在面试的时候非常注重数据结构和算法题,而这些题目往往是比较难的,很多人会在这方面失手。即使是多年工作经验的老手,在面试前,刷刷数据结构和算法的题目也是一种非常的需要。我们经常调侃,面试造飞机,实际拧螺丝。那能有什么办法。

1976 年,一个叫 Niklaus Wirth 计算机科学家写了一本书,Algorithms + Data Structures = Programs 。40 年过去了,这个等式还是成立的。所以在面试的时候,对数据结构和算法的考核一直是永远不变的话题。

什么是数据结构

a data structure is a container that stores data in a specific layout. 简单的说,数据结构就是一个容器,以一定的布局组织这些数据。这样的布局导致这些数据在某些操作中是高效的,而有些操作上低效的。我们的目标就是理解这些数据结构,在使用的时候,我们可以选出合适的一种布局。

为什么需要数据结构

数据结构用来以一定的组织来存储数据,而数据是计算机世界最重要的元素,所有,数据结构的重要性就不言而喻了。

不管你在解决什么问题,你总是和数据打交道,员工的薪水,股票的价格,电话本,等待。

常用的数据结构

  1. 数组 Arrays
  2. 栈 Stacks
  3. 队列 Queues
  4. 链表 Linked Lists
  5. 树 Trees
  6. 图 Graphs
  7. Tries
  8. 哈希表 Hash Tables

数组

数组是简单并且广泛使用的数据结构,栈和队列也经常是时候用数据来实现的。

数组中的每个元素都有一个表示其位置的值,称为索引 index。大部分语言中,索引是从 0 开始的。

数组的基本操作

数组的基本操作主要有插入、读取、删除、大小。

面试中常见的题目

栈 Stacks

在很多应用中,我们都有撤销(undo)的操作。实现的思路就是类似栈的实现。

LIFO Last In First Out 是栈最显著的特征。

基本操作

常见面试题

队列 Queues

队列和栈比较相似,区别是 FIFO,First In First Out,先进先出。真实生活中也是比较常见的,咱们日常排队就是这样的。

常见操作

常见面试题

链表 Linked List

链表是另外一个重要的线性的数据结构,表面上看和数组很像,但是实际上在内存上,还是有很大区别的。

链表是一个由节点组成的链,中文表达好像很别扭,英文是这样的 A linked list is like a chain of nodes 。每个节点包含数据和一个指向下一个节点的指针。链表有个头指针,指向列表的第一个元素。但这个头指针指向 null 的时候,这个列表是空的。

链表又有单向链表和双向链表。

基本操作

常见面试题

图 Graphs

图是节点的集合,这些节点以网的形式相互连接。这些节点通常被称为顶点。pair(x,y) 表示一个边,连接 x 顶点到 y 顶点。一个边包含权重或者消费的信息,显示了从 x 顶点到 y 顶点的消费。

图分为无向图和有向图,在计算机语言中,图有两种表示形式,Adjacency Matrix 相邻矩阵 和 Adjacency List 邻接表。常见的算法有广度优先算法(Breadth First Search)和深度优先算法(Depth First Search)。

常见的面试题

树 Trees

树是由节点和连接节点的边组成的层级的数据结构。树和图有点像,关键的区别是树没有循环。树被用在人工智能和一些复杂的算法上。

树有很多种

常见的面试题

字典树 Trie

Trie,which is also known as "Prefix Tresss"。这是一个类似于树的数据结构。经常被用来做字典单词的查找,搜索引擎的自动联想,IP 路由等。

常见的面试题

哈希表 Hash Table

散列算法是一种用来唯一标识对象,并且以通过键值来索引对象的方式来存储对象的一种程序。Hashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its “key.” 所有对象被以键值对的形式存储,所以也被称为字典。每个对象都可以通过 key 被访问。

哈希表通常是通过数组来实现的。散列数据结构的性能通常以以下三个要素决定,哈希函数(Hash Function),哈希表的大小和碰撞出来方法(Collision Handling Method)。

常见的面试题

参考 : https://medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3

- EOF -

本文链接 https://spacepage.top/articles/2018.08.03-12_06_29-data-structures-interview.html,欢迎转载,转载请注明出处。