新聞資訊  快訊  焦點  財經  政策  社會
互 聯 網   電商  金融  數據  計算  技巧
生活百科  科技  職場  健康  法律  汽車
手機百科  知識  軟件  修理  測評  微信
軟件技術  應用  系統  圖像  視頻  經驗
硬件技術  知識  技術  測評  選購  維修
網絡技術  硬件  軟件  設置  安全  技術
程序開發  語言  移動  數據  開源  百科
安全防護  資訊  黑客  木馬  病毒  移動
站長技術  搜索  SEO  推廣  媒體  移動
財經百科  股票  知識  理財  財務  金融
教育考試  育兒  小學  高考  考研  留學
您當前的位置:首頁 > IT > 程序開發 > 語言 > 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   點擊:()  評論:()
聲明:本站部分內容來自互聯網,如有任何版權侵犯或其他問題請與我們聯系,我們將立即刪除或處理。
▌相關評論
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
▌相關推薦
一、先了解一下setInterval,AAAAA是執行函數,BBBBB是執行周期。 二、創建一個盒子,在腳本中取得元素對象。 三、開始用setinterval方法了。 F12打開控制臺,你可以看到,每秒一個l...【詳細內容】
2019-06-27   Java  點擊:(1)  評論:(0)  加入收藏
為了保證可讀性,本文采用意譯而非直譯。一些名詞JS引擎 — 一個讀取代碼并運行的引擎,沒有單一的“JS引擎”;,每個瀏覽器都有自己的引擎,如谷歌有V。作用域 — 可以從...【詳細內容】
2019-06-25   Java  點擊:(6)  評論:(0)  加入收藏
形參和實參我們知道,在Java中定義方法時,是可以定義參數的,比如:public static void main(String[] args){ }這里的args就是一個字符串數組類型的參數。在程序設計語言中,參數有...【詳細內容】
2019-06-21   Java  點擊:(5)  評論:(0)  加入收藏
瑞士計算機科學家Niklaus Wirth在1976年寫了一本書,名為《算法+數據結構=編程》。40多年后,這個等式仍被奉為真理。這就是為什么在面試過程中,需要考察軟件工程師對數據結構的...【詳細內容】
2019-06-18   Java  點擊:(8)  評論:(0)  加入收藏
多人都想知道架構師是做什么?我們看看下面的一段對話。菜鳥 —— 剛入門的程序員老鳥 —— 資深架構師老鳥:菜鳥,你的目標是什么?菜鳥:我要成為一個軟件架構...【詳細內容】
2019-06-18   Java  點擊:(2)  評論:(0)  加入收藏
JavaScript:基本概念:JavaScript一種直譯式腳本語言,是一種動態類型、弱類型、基于原型的語言,內置支持類型。它的解釋器被稱為JavaScript引擎,為瀏覽器的一部分,廣泛用于瀏覽...【詳細內容】
2019-06-18   Java  點擊:(3)  評論:(0)  加入收藏
這是我在知乎上的一個回答, 如果有興趣的同學可以在知乎上搜索我的賬戶: jsppedu。1、橫向分類前端:HTML、CSS、JavaScript后端:PHP、MySQL2、責任分類HTML:負責網頁結構部分CSS:...【詳細內容】
2019-06-18   Java  點擊:(3)  評論:(0)  加入收藏
一:問題首先我們要考慮的是為什么要解決高并發,高并發瓶頸出現在哪里,有了解過的朋友肯定知道是在數據庫,因為在大量請求去操作數據庫時會出現數據的錯亂,超賣,系統崩潰,mysql死鎖...【詳細內容】
2019-06-17   Java  點擊:(2)  評論:(0)  加入收藏
在JSP里,獲取客戶端的IP地址的方法是:request.getRemoteAddr(),這種方法在大部分情況下都是有效的。但是在通過了Apache,Squid等反向代理軟件就不能獲取到客戶端的真實IP地址了...【詳細內容】
2019-06-17   Java  點擊:(4)  評論:(0)  加入收藏
概述排序分為內部排序和外部排序,內部排序是待排序的元素全部放在內存,并在內存中調整它們的順序。外部排序是部分元素放到內存中,在內外存間調整元素的順序。我們通常說的八大...【詳細內容】
2019-06-17   Java  點擊:(2)  評論:(0)  加入收藏
一、前言一個成熟的大型網站(如淘寶、京東等)的系統架構并不是開始設計就具備完整的高性能、高可用、安全等特性,它總是隨著用戶量的增加,業務功能的擴展逐漸演變完善的,在這個過...【詳細內容】
2019-06-17   Java  點擊:(3)  評論:(0)  加入收藏
為了保證提交數據的正確性,用戶在填寫表單的過程中還需要編寫一堆的驗證操作,可以利用JavaScript來驗證完成。下面就給大家分享在web開發中JavaScript 表單驗證如何實現的?希望...【詳細內容】
2019-06-17   Java  點擊:(5)  評論:(0)  加入收藏
一、先做一張簡單的網頁。 二、加上相應的javacript代碼。 三、開始測試,判斷輸入框內的是否是6位數字。 四、判斷輸入框內為正整數,而不是負數。 五、判斷身份證位數吧...【詳細內容】
2019-06-14   Java  點擊:(3)  評論:(0)  加入收藏
在最近的項目中碰到一個數據源的配置需求,就是需要配置公司所有系統的數據庫、表等信息,其中大數據部門抽數時需要過濾某些表的敏感字段,如身份證號、手機號等敏感字段。需要后...【詳細內容】
2019-06-11   Java  點擊:(22)  評論:(0)  加入收藏
前言什么是 V8?JavaScript運行的背后發生了什么?如果你是一個 JS 開發者或者是正在學習這門語言的學生,很大概率上你會遇到雙字母詞”V8”。在這篇文章中,我將會為你簡述不同的...【詳細內容】
2019-06-05   Java  點擊:(6)  評論:(0)  加入收藏
一、排序 冒泡排序//冒泡排序function bubbleSort(arr) { for(var i = 1, len = arr.length; i < len - 1; ++i) { for(var j = 0; j <= len - i; ++j) { if (arr[j] > arr[...【詳細內容】
2019-05-17   Java  點擊:(9)  評論:(0)  加入收藏
JavaScript 引用類型所謂引用類型,在ECMAScript中表示一種數據結構,其中有一些數據和方法,在其他語言中大多被稱為類,但是在這里我們一般不這樣稱呼。即使ECMAScript是一門面...【詳細內容】
2019-05-15   Java  點擊:(9)  評論:(0)  加入收藏
一 命名規則1)包: 命名應該都是名詞或名詞性詞組,全部小寫,單詞之間用“.”分開,一般使用本公司網站域名的逆序后跟具體的軟件內部模塊名包命名舉例: package com.sun.java; packag...【詳細內容】
2019-05-09   Java  點擊:(10)  評論:(0)  加入收藏
1.引用的基本概念強引用:當我們使用new創建對象時,被創建的對象就是強引用,如Object object = new Object(),其中的object就是一個強引用了。如果一個對象具有強引用,JVM就不會去...【詳細內容】
2019-05-09   Java  點擊:(26)  評論:(0)  加入收藏
前言可能你會很熟練,但名稱不一定知道。正文從這開始~~ 讓我們談談什么是:lambdas(匿名函數)、 first-class functions(頭等函數)、higher-order functions(高階函數)、unary functi...【詳細內容】
2019-05-08   Java  點擊:(10)  評論:(0)  加入收藏
推薦資訊
相關文章
欄目更新
欄目熱門
31选7开奖11185