【精選乾貨】研發麵試最常用的10大算法,你遇到過幾個?

2021-02-20 Java我最強

作者 | 數盟

編輯 | Sandra

原文 | https://mp.weixin.qq.com

Ja強最新動態

推薦本公眾號給 2個好友,返回截圖即可領取《Java面試寶典》,後臺回復【寶典】查看詳情。Ja強最新獨家資源Java高級架構設計2017整理-視頻教程下載,後臺回復【架構師06】獲取!更有更多架構師資源下載。

面試也是一門學問,在面試之前做好充分的準備則是成功的必須條件,而程式設計師在代碼面試時,常會遇到編寫算法的相關問題,比如排序、二叉樹遍歷等等。

在程式設計師的職業生涯中,算法亦算是一門基礎課程,尤其是在面試的時候,很多公司都會讓程式設計師編寫一些算法實例,例如快速排序、二叉樹查找等等。

本文總結了程式設計師在代碼面試中最常遇到的10大算法類型,想要真正了解這些算法的原理,還需程式設計師們花些功夫。

在Java中,String是一個包含char數組和其它欄位、方法的類。如果沒有IDE自動完成代碼,下面這個方法大家應該記住:

String/arrays很容易理解,但與它們有關的問題常常需要高級的算法去解決,例如動態編程、遞歸等。

下面列出一些需要高級算法才能解決的經典問題:

Evaluate Reverse Polish Notation

Longest Palindromic Substring

單詞分割

字梯

Median of Two Sorted Arrays

正則表達式匹配

合併間隔

插入間隔

Two Sum

3Sum

4Sum

3Sum Closest

String to Integer

合併排序數組

Valid Parentheses

實現strStr()

Set Matrix Zeroes

搜索插入位置

Longest Consecutive Sequence

Valid Palindrome

螺旋矩陣

搜索一個二維矩陣

旋轉圖像

三角形

Distinct Subsequences Total

Maximum Subarray

刪除重複的排序數組

刪除重複的排序數組2

查找沒有重複的最長子串

包含兩個獨特字符的最長子串

Palindrome Partitioning

在Java中實現鍊表是非常簡單的,每個節點都有一個值,然後把它連結到下一個節點。

值得一提的是,Java標準庫中已經包含一個叫做Stack的類,鍊表也可以作為一個隊列使用(add()和remove())。(鍊表實現隊列接口)如果你在面試過程中,需要用到棧或隊列解決問題時,你可以直接使用它們。

下面是一些與二叉樹有關的概念:

二叉樹搜索:對於所有節點,順序是:left children <= current node <= right children;

平衡vs.非平衡:它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,並且左右兩個子樹都是一棵平衡二叉樹;

滿二叉樹:除最後一層無任何子節點外,每一層上的所有結點都有兩個子結點;

完美二叉樹(Perfect Binary Tree):一個滿二叉樹,所有葉子都在同一個深度或同一級,並且每個父節點都有兩個子節點;

完全二叉樹:若設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹。

堆(Heap)是一個基於樹的數據結構,也可以稱為優先隊列( PriorityQueue),在隊列中,調度程序反覆提取隊列中第一個作業並運行,因而實際情況中某些時間較短的任務將等待很長時間才能結束,或者某些不短小,但具有重要性的作業,同樣應當具有優先權。堆即為解決此類問題設計的一種數據結構。

二叉樹前序遍歷

二叉樹中序遍歷

二叉樹後序遍歷

字梯

驗證二叉查找樹

把二叉樹變平放到鍊表裡

二叉樹路徑和

從前序和後序構建二叉樹

把有序數組轉換為二叉查找樹

把有序列錶轉為二叉查找樹

最小深度二叉樹

二叉樹最大路徑和

平衡二叉樹

與Graph相關的問題主要集中在深度優先搜索和寬度優先搜索。深度優先搜索非常簡單,你可以從根節點開始循環整個鄰居節點。下面是一個非常簡單的寬度優先搜索例子,核心是用隊列去存儲節點。

不同排序算法的時間複雜度,大家可以到wiki上查看它們的基本思想。

BinSort、Radix Sort和CountSort使用了不同的假設,所有,它們不是一般的排序方法。

問題:

這裡有n個臺階,每次能爬1或2節,請問有多少種爬法?

步驟1:查找n和n-1之間的關係

為了獲得n,這裡有兩種方法:一個是從第一節臺階到n-1或者從2到n-2。如果f(n)種爬法剛好是爬到n節,那麼f(n)=f(n-1)+f(n-2)。

步驟2:確保開始條件是正確的

遞歸方法的時間複雜度指數為n,這裡會有很多冗餘計算。

動態規劃主要用來解決如下技術問題:

1、通過較小的子例來解決一個實例;

2、對於一個較小的實例,可能需要許多個解決方案;

3、把較小實例的解決方案存儲在一個表中,一旦遇上,就很容易解決;

4、附加空間用來節省時間。

上面所列的爬臺階問題完全符合這四個屬性,因此,可以使用動態規劃來解決:

從一個給定的數n中找位i(i從0開始,然後向右開始)

Find Single Number

Maximum Binary Gap

通常要解決概率相關問題,都需要很好地格式化問題,下面提供一個簡單的例子:

有50個人在一個房間,那麼有兩個人是同一天生日的可能性有多大?(忽略閏年,即一年有365天)

1、2、3、4、5這5個數字,輸出不同的順序,其中4不可以排在第三位,3和5不能相鄰,請問有多少種組合?

例2:

有5個香蕉、4個梨、3個蘋果,假設每種水果都是一樣的,請問有多少種不同的組合?

Java我最強,是專注Java技術的垂直社群,加入精品技術群請公眾號後臺留言「加群」。投稿合作請郵件至:javawozuiqiang@qq.com,註明「Java我最強投稿」。

相關焦點

  • 研發麵試最常用的10大算法,你遇到過幾個?
    面試也是一門學問,在面試之前做好充分的準備則是成功的必須條件,而程式設計師在代碼面試時,常會遇到編寫算法的相關問題,比如排序、二叉樹遍歷等等
  • 【面試分享】大三本科生拿到阿里研發、網易郵件、騰訊微信實習offer面試經驗分享
    常用的設計模式10. 算法題 * 211. 自己有什麼優點…面完之後, 感覺整個人都不好了。內存管理部分, 都能說出那麼一些, 但是一說多了, 就不知道怎麼回答了。總體來說, 還是基礎不夠紮實。研究不夠透徹。然後面試完, 一個很大的感受就是,一次面試, 學到的, 比自己悶頭看書一個月, 學到的還多。
  • 算法工程師研發技能表
    所以很難有一個一概而論的算法工程師技術棧。比如說做圖像方向的有機器視覺算法崗、做文本方向的有自然語言處理算法崗、做語音的又有語音識別算法崗。本文僅對算法工程師常用的、基礎的、必備的研發技能進行梳理。也就是說,不論你是做哪個業務場景下的算法工作,這些基礎研發技能都是必知必會的。這組技能清單主要包括兩大類型,一類是理論技術,另一類是程式語言和工具類。
  • Java面試的的時候你被提過哪些問題?
    同學們在踏出校園那一刻起,邊開始進入了社會,面臨著找工作、面試,那麼,當你被面試的時候,哪些Java題被面試官提問過?OOM你遇到過哪些情況,SOF你遇到過哪些情況。16. Java面向對象的三個特徵與含義。17. Override和Overload的含義去區別。18. Interface與abstract類的區別。19. Static class 與non static class的區別。20. java多態的實現原理。21.
  • 10大機器學習算法及應用,你知道幾個?
    來源:kdnuggets作者:James Le翻譯:序媛本文導讀:本文將為大家盤點,機器學習領域都有哪些常用的算法。毫無疑問,在過去兩年中,機器學習和人工智慧的普及度都得到了大幅提升。機器學習算法可分為三個大類:有監督學習、無監督學習和強化學習。
  • 算法崗面經分享 | 字節跳動CV算法實習生面試(含超多知識點乾貨)
    同時提供每月大咖直播分享、真實項目需求對接、乾貨資訊匯總,行業技術交流。點擊文末「閱讀原文」立刻申請入群~分享一篇字節跳動CV算法實習生面試經驗帖,涉及較多視覺算法知識點分析,很有參考意義,希望對大家工作和求職有所幫助~作者 | JustDoIT原文 | https://zhuanlan.zhihu.com/p/59270912崗位信息如下:
  • 乾貨 | 算法和編程面試題精選TOP50!(附代碼+解題思路+答案)
    這次營長表示要翻 Java 的牌子啦~ 應大家的強烈反饋,我們找了一套 Java 語言的算法和編程的面試題。這份面試資源主要包含五部分內容:數組、鍊表、字符串、二叉樹和重要算法(如排序算法)的編程面試題,其中每部分內容我們都列出了一些最常被問到的熱門問題,並且在每個題目後給出了可以參考的解決思路和代碼,因為題目較多,我們沒有羅列所有的方法和代碼,只給出了訪問地址。相信大家在掌握了這些內容後,一定可以提升實力、信心大增。
  • 備戰跳槽季:大廠面試官總結 16 大常考算法知識點
    在如今的環境下,想要換一份理想的工作更是需要「找準時機,抓住機會」,當然在面試前的準備是必不可少的。極客大學邀請了算法訓練營的助教,請他們分享一下作為面試官喜歡考察候選人哪些能力、他們有哪些「 精選算法面試題 」。我們的助教們來自美團、百度或海外的一線網際網路公司,希望他們分享的經驗可以幫助到你。
  • 九章算法班 | 1個月搞定面試算法,更有內推等著你
    《九章算法V5.0》配套最新 LintCode OJ 題庫。根據最新的面經對配套作業題進行了大換血,在面試中遇到原題的概率更高了。比如,樹狀數組是近期 Facebook、 Google面試中出現過數據結構考點。
  • 程序開發最常用的10大算法
    } }}值得一提的是,Java標準庫中已經包含一個叫做Stack的類,鍊表也可以作為一個隊列使用(add()和remove())。下面列出一些基於二叉樹和堆的算法:●二叉樹前序遍歷●二叉樹中序遍歷●二叉樹後序遍歷●字梯●驗證二叉查找樹●把二叉樹變平放到鍊表裡●二叉樹路徑和●從前序和後序構建二叉樹●把有序數組轉換為二叉查找樹●把有序列錶轉為二叉查找樹●最小深度二叉樹
  • 面試時,這幾個最常問的問題,你遇到過嗎?
    下面,我就總結了幾個職場中,面試時,HR最喜歡問的幾個問題。2:其實這些東西,HR在電話讓你來面試之前,就已經在你的簡歷上了解到了。他們最想聽的是:「應聘者哪方面技能比較出色、最專業知識領域是什麼、做過什麼成功的案例」這才是HR最想了解的,因為企業需要確定的是,你是否能夠更好地,勝任目前正在招聘的崗位。第二:對於薪資,你的心理預期是多少呢?
  • 面試經驗分享之數據結構、算法題
    前言面試 IT 企業的研發崗位,數據結構和算法顯然是必考的項目。俺只學過普通的數據結構課程,沒讀過 STL,也沒有過 ACM 的訓練和比賽經歷,在一開始面對這樣類型題目的時候,心裡還是十分忐忑的。大大小小几十場面試下來,自己在這方面總算有了一定的心得積累,在此拋磚引玉, 以饗讀者。
  • 獨家 | 在Python編程面試前需要學會的10個算法(附代碼)
    本文為大家介紹了最近在Python編程面試中反覆出現的10個基礎算法問題,並且給出了相應的解答過程。
  • KDnuggets調查數據科學家最常用的10種算法
    翻譯|姜範波 lizyjieshu   校對|Lorine大數據文摘作品,轉載具體要求見文末 最新的KDnuggets調查統計了數據科學家們實際工作中最常使用的算法,在大多數學術和產業界,都有驚人發現哦!
  • 看看高薪,算法工程師面試,讓你懷疑人生
    面試一下午,從1:40到5:20,共四面,前三個為技術面,第四個為leader面,leader也問了一些技術,未來的規劃,來這裡之後會幹什麼,反正就是泛泛的聊,還有就是你印象最深刻的一件事,最感動的,最難忘的一件事,哎,這些問題。先是40分鐘一套卷子,讓做題,5道編程題,3道問答題可以選擇做。我當時40分鐘把5道編程寫完就沒時間了。
  • 算法工程師面試前需掌握的18大面試題!
    【IT168 評論】算法是比較複雜又基礎的學科,每個學編程的人都會學習大量的算法。而根據統計,以下這18個問題是面試中最容易遇到的,本文給出了一些基本答案,供算法方向工程師或對此感興趣的程式設計師參考。1)請簡單解釋算法是什麼?
  • 超實用乾貨!籤證被拒的N個雷區 你遇到過幾個?
    如申請時遞交的材料不齊全,使領館一定會要求你補交材料或者直接拒籤,所以遞交材料時一定要仔細,該準備的材料每一項都必須準備,不要抱著僥倖心理來對待。白本護照白本護照就是指沒有辦理過任何籤證的護照本。白本護照的拒籤率相對會高一些。
  • 你距離通過亞馬遜面試還差多少?
    與面試官愉快地交流了幾句話之後,就直接進入了編程挑戰,筆者當時緊張得發抖。還好幸運之神站在我這邊,我遇到了複習過的類似題目。第二次面試就難得多。面試官在操作方面進行轟炸式提問,筆者只剩下20分鐘的編程時間。筆者盡力去理解這個問題,最終縮小範圍,找到了一個最佳的解決辦法。其實筆者的解釋不夠清晰,但不管怎樣,我還是通過了那次面試。
  • 程式設計師面試過關必備的5大網站,你用過幾個?
    但是,也有部分程式設計師面試掛掉了,暫時還找不到工作。其實,要順利通過面試還是非常有必要去刷一些編程面試題,認識一些面試指南。下面w3cschool給程式設計師小夥伴們推薦5大面試相關的網站,幫助你順利通過各種面試。
  • 推薦4個基於 Java語言的開源 Leetcode 題解!算法面試不愁了!
    2、☞ 《Java面試手冊》.PDF    點擊查看一個很明顯的現象,現在大廠的應屆生面試,甚至是社招面試都開始越來越重視算法了。經常會有人問 Guide 如何準備算法面試,今天統一回答一下。為了能夠更好地準備算法面試,我們大部分人能做的就是刷 Leetcode 來積累解決算法題的經驗和套路。為了能夠幫助我們更好的刷 Leetcode,Guide 精選了一些不錯的基於 Java 題解的開源項目,文末有項目連結。