您剛剛從大學(xué)獲得計(jì)算機(jī)科學(xué)或軟件工程學(xué)位，并且正在尋找職業(yè)。您還記得自己喜歡單身漢編寫代碼，并與好友一起做過一些很棒的項(xiàng)目，然后決定要成為一名開發(fā)人員。

您開始準(zhǔn)備工作面試，卻無法弄清楚記住哪些算法對(duì)于評(píng)分工作很重要。如果您處于這樣的位置，并且足夠快地進(jìn)行面試，那么本文將幫助您記住求職面試可能需要的所有編碼算法。

軟件工程師的基本工作描述包括設(shè)計(jì)，增強(qiáng)和實(shí)施系統(tǒng)和應(yīng)用程序。

為此，軟件工程師無需記住許多復(fù)雜的算法。相反，要求他們使用工作庫，框架和數(shù)據(jù)庫的組合來創(chuàng)建滿足其軟件需求的工具。

根據(jù)軟件工程領(lǐng)域的專家介紹，了解一些高級(jí)搜索算法在優(yōu)化它們時(shí)會(huì)有所幫助，否則，您更有可能使用內(nèi)置庫。話雖如此，這里列出了一些重要的算法，在進(jìn)行面試時(shí)您應(yīng)該具有一些基本的知識(shí)。

動(dòng)態(tài)編程

動(dòng)態(tài)編程是通過消除對(duì)遞歸調(diào)用的需求來優(yōu)化隱性函數(shù)的策略。每當(dāng)我們看到一個(gè)遞歸函數(shù)，其中某個(gè)代碼的某個(gè)部分被多次調(diào)用時(shí)，可以通過使用動(dòng)態(tài)編程來大大改進(jìn)。通過存儲(chǔ)前一個(gè)子函數(shù)的結(jié)果，可以消除遞歸性，從而不必多次調(diào)用它們。這樣可以將時(shí)間復(fù)雜度從指數(shù)時(shí)間降低到多項(xiàng)式時(shí)間。屬于動(dòng)態(tài)編程類別的算法示例如下：

二進(jìn)制搜索

顧名思義，搜索算法用于從稱為數(shù)據(jù)結(jié)構(gòu)的給定集合中搜索元素。二進(jìn)制搜索在提供排序后的元素?cái)?shù)組和搜索鍵時(shí)有效。二進(jìn)制搜索通過選擇中間元素并將其與搜索關(guān)鍵字進(jìn)行比較來實(shí)現(xiàn)，如果該關(guān)鍵字小于中間元素的左側(cè)部分，則以相同的方式進(jìn)行遍歷。如果現(xiàn)在在右部分上搜索密鑰。二進(jìn)制搜索的時(shí)間復(fù)雜度為O(log n)，其中n是數(shù)組中元素的數(shù)量。

排序算法

排序算法用于對(duì)數(shù)組進(jìn)行排序，輸入中包含需要排序的數(shù)據(jù)類型。數(shù)據(jù)集可以按升序或降序排序。以下是一些要記住的重要排序算法。

合并排序

合并排序基于分而治之算法的原理進(jìn)行。它是指將問題分解為較小的部分，并一一解決并最終合并在一起的實(shí)踐。合并排序?qū)?shù)組分為兩半，并在兩個(gè)半部分上調(diào)用sort函數(shù)，對(duì)這兩個(gè)半部分進(jìn)行排序，然后使用merge函數(shù)合并在一起。合并排序的時(shí)間復(fù)雜度為O(n log n)。

快速排序

像合并排序一樣，快速排序也是基于分而治之的算法，它在排序功能方面與合并排序有所不同。Quicksort的工作原理是選擇最后一個(gè)元素作為樞軸數(shù)字，并將其放在中間，左側(cè)數(shù)字較小，而右側(cè)數(shù)字較大。左側(cè)和右側(cè)再次使用sort函數(shù)進(jìn)行調(diào)用，結(jié)果對(duì)整個(gè)數(shù)組進(jìn)行了排序。快速排序的時(shí)間復(fù)雜度為O(n ^ 2)。

深度優(yōu)先搜索

DFS是一種搜索算法，它從節(jié)點(diǎn)開始搜索過程，一直向下到最左邊分支的最后一個(gè)葉子。在到達(dá)最左邊的葉子之后，算法開始回溯并遍歷樹的右側(cè)，依此類推。此DFS的問題在于，如果存在一個(gè)周期，則可以多次訪問某個(gè)節(jié)點(diǎn)。DFS的時(shí)間復(fù)雜度為O(V + E)，其中V和E分別表示圖中的頂點(diǎn)和邊數(shù)。

廣度優(yōu)先搜索

BFS是一種與DFS一樣從根開始的搜索算法。但是，它沒有遍歷左側(cè)的所有葉子，而是在同一級(jí)別上的節(jié)點(diǎn)附近搜索。遍歷一個(gè)級(jí)別后，算法將前進(jìn)到下一個(gè)級(jí)別，并繼續(xù)遍歷直到找到元素。BFS的時(shí)間復(fù)雜度與DFS相同，為O(V + E)。

自定義數(shù)據(jù)結(jié)構(gòu)

有時(shí)，典型的預(yù)定義數(shù)據(jù)結(jié)構(gòu)無法完成任務(wù)，您需要更好，更強(qiáng)大的功能。自定義數(shù)據(jù)結(jié)構(gòu)可以是真實(shí)或抽象對(duì)象，具體取決于其數(shù)據(jù)成員的用途。數(shù)據(jù)成員可以視為屬于指定對(duì)象的變量。

哈希表

哈希表是一種數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)，訪問和修改時(shí)間為O(1)的數(shù)據(jù)。哈希數(shù)據(jù)結(jié)構(gòu)使用哈希函數(shù)將給定值映射到特定鍵。然后，使用此密鑰快速訪問和檢索這些值，哈希的執(zhí)行效率取決于所使用的哈希函數(shù)的類型。

鏈表

通常，數(shù)組的組件或任何鏈接的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在連續(xù)的內(nèi)存位置中。這將占用空間，并且某些內(nèi)存塊不可訪問(也就是說，如果內(nèi)存不足)。為了克服這個(gè)問題，使用了鏈表數(shù)據(jù)結(jié)構(gòu)，其中的數(shù)據(jù)不是連續(xù)存儲(chǔ)的，而是列表中的每個(gè)項(xiàng)目都有一個(gè)指向下一個(gè)元素的存儲(chǔ)位置的指針。第一個(gè)元素被稱為頭，最后一個(gè)元素被稱為尾。

問問題

軟件工程師應(yīng)該知道的最重要的事情是詢問客戶。大多數(shù)客戶無法理解他們的觀點(diǎn)，如果開發(fā)人員不提出任何問題，則可能由于溝通不暢而引起問題。這樣，您將能夠理解他們正在努力實(shí)現(xiàn)的核心問題，而不僅僅是他們面臨的困難。

結(jié)論

有了這些基本算法的知識(shí)，就可以輕松進(jìn)行面試。請(qǐng)記住，軟件工程師通常不依靠這些算法來完成工作。取而代之的是，它們被用來測(cè)試個(gè)人對(duì)他是否了解代碼工作的理解。如此說來，祝您下次面試順利。