- 原文地址:github.com/kdn251/interviews
- 譯文出自:掘金翻譯計(jì)劃
- 譯者:王下邀月熊
- 校對(duì)者:PhxNirvana腿箩、根號(hào)三
- 這個(gè) 鏈接 用來(lái)查看本翻譯與英文版是否有差別(如果你沒(méi)有看到 README.md 發(fā)生變化沐兵,那就意味著這份翻譯文檔是最新的)态辛。
Interviews
軟件工程技術(shù)面試個(gè)人指南哩都。
Maintainer - Kevin Naughton Jr.
其他語(yǔ)言版本
目錄
- 在線練習(xí)
- 在線面試編程
- 數(shù)據(jù)結(jié)構(gòu)
- 算法
- 位運(yùn)算
- 算法復(fù)雜度分析
- 視頻教程
- 面試書籍
- 計(jì)算機(jī)科學(xué)與技術(shù)資訊
- 文件結(jié)構(gòu)
在線練習(xí)
在線面試編程
數(shù)據(jù)結(jié)構(gòu)
Linked List
- 鏈表即是由節(jié)點(diǎn)(Node)組成的線性集合暮的,每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)焕妙。它是一種包含了多個(gè)節(jié)點(diǎn)的盯腌、能夠用于表示序列的數(shù)據(jù)結(jié)構(gòu)践剂。
- 單向鏈表: 鏈表中的節(jié)點(diǎn)僅指向下一個(gè)節(jié)點(diǎn)鬼譬,并且最后一個(gè)節(jié)點(diǎn)指向空。
- 雙向鏈表: 其中每個(gè)節(jié)點(diǎn)具有兩個(gè)指針 p逊脯、n优质,使得 p 指向先前節(jié)點(diǎn)并且 n 指向下一個(gè)節(jié)點(diǎn);最后一個(gè)節(jié)點(diǎn)的 n 指針指向 null男窟。
- 循環(huán)鏈表:每個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)并且最后一個(gè)節(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)的鏈表盆赤。
- 時(shí)間復(fù)雜度:
- 索引:
O(n)
- 搜索:
O(n)
- 插入:
O(1)
- 移除:
O(1)
- 索引:
Stack
- 棧是元素的集合,其包含了兩個(gè)基本操作:push 操作可以用于將元素壓入棧歉眷,pop 操作可以將棧頂元素移除牺六。
- 遵循后入先出(LIFO)原則。
- 時(shí)間復(fù)雜度:
- 索引:
O(n)
- 搜索:
O(n)
- 插入:
O(1)
- 移除:
O(1)
Queue
- 隊(duì)列是元素的集合汗捡,其包含了兩個(gè)基本操作:enqueue 操作可以用于將元素插入到隊(duì)列中淑际,而 dequeeu 操作則是將元素從隊(duì)列中移除。
- 遵循先入先出原則 (FIFO)扇住。
- 時(shí)間復(fù)雜度:
- 索引:
O(n)
- 搜索:
O(n)
- 插入:
O(1)
- 移除:
O(1)
Tree
- 樹是無(wú)向春缕、連通的無(wú)環(huán)圖。
Binary Tree
- 二叉樹即是每個(gè)節(jié)點(diǎn)最多包含左子節(jié)點(diǎn)與右子節(jié)點(diǎn)這兩個(gè)節(jié)點(diǎn)的樹形數(shù)據(jù)結(jié)構(gòu)艘蹋。
- 滿二叉樹: 樹中的每個(gè)節(jié)點(diǎn)僅包含 0 或 2 個(gè)節(jié)點(diǎn)锄贼。
- 完美二叉樹(Perfect Binary Tree): 二叉樹中的每個(gè)葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn),并且具有相同的高度女阀。
- 完全二叉樹: 除最后一層外宅荤,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)浸策。
Binary Search Tree
- 二叉搜索樹(BST)是一種特殊的二叉樹冯键,其任何節(jié)點(diǎn)中的值都會(huì)大于或者等于其左子樹中存儲(chǔ)的值并且小于或者等于其右子樹中存儲(chǔ)的值。
- 時(shí)間復(fù)雜度:
- 索引:
O(log(n))
- 搜索:
O(log(n))
- 插入:
O(log(n))
- 刪除:
O(log(n))
- 索引:
![Binary Search Tree](https://github.com/kdn251/interviews/raw/master/Images/BST.png?raw=true)
Binary Search Tree
Trie
- 字典樹庸汗,又稱基數(shù)樹或者前綴樹惫确,能夠用于存儲(chǔ)鍵為字符串的動(dòng)態(tài)集合或者關(guān)聯(lián)數(shù)組的搜索樹。樹中的節(jié)點(diǎn)并沒(méi)有直接存儲(chǔ)關(guān)聯(lián)鍵值蚯舱,而是該節(jié)點(diǎn)在樹中的掛載位置決定了其關(guān)聯(lián)鍵值改化。某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都擁有相同的前綴,整棵樹的根節(jié)點(diǎn)則是空字符串枉昏。
Fenwick Tree
- 樹狀數(shù)組又稱 Binary Indexed Tree陈肛,其表現(xiàn)形式為樹,不過(guò)本質(zhì)上是以數(shù)組實(shí)現(xiàn)凶掰。數(shù)組中的下標(biāo)代表著樹中的頂點(diǎn)燥爷,每個(gè)頂點(diǎn)的父節(jié)點(diǎn)或者子節(jié)點(diǎn)的下標(biāo)能夠通過(guò)位運(yùn)算獲得。數(shù)組中的每個(gè)元素包含了預(yù)計(jì)算的區(qū)間值之和懦窘,在整棵樹更新的過(guò)程中同樣會(huì)更新這些預(yù)計(jì)算的值前翎。
- 時(shí)間復(fù)雜度:
- 區(qū)間求值:
O(log(n))
- 更新:
O(log(n))
- 區(qū)間求值:
Segment Tree
- 線段樹是用于存放間隔或者線段的樹形數(shù)據(jù)結(jié)構(gòu),它允許快速的查找某一個(gè)節(jié)點(diǎn)在若干條線段中出現(xiàn)的次數(shù).
- 時(shí)間復(fù)雜度:
- 區(qū)間查詢:
O(log(n))
- 更新:
O(log(n))
- 區(qū)間查詢:
Heap
- 堆是一種特殊的基于樹的滿足某些特性的數(shù)據(jù)結(jié)構(gòu)畅涂,整個(gè)堆中的所有父子節(jié)點(diǎn)的鍵值都會(huì)滿足相同的排序條件港华。堆更準(zhǔn)確地可以分為最大堆與最小堆,在最大堆中午衰,父節(jié)點(diǎn)的鍵值永遠(yuǎn)大于或者等于子節(jié)點(diǎn)的值立宜,并且整個(gè)堆中的最大值存儲(chǔ)于根節(jié)點(diǎn);而最小堆中臊岸,父節(jié)點(diǎn)的鍵值永遠(yuǎn)小于或者等于其子節(jié)點(diǎn)的鍵值橙数,并且整個(gè)堆中的最小值存儲(chǔ)于根節(jié)點(diǎn)。
- 時(shí)間復(fù)雜度:
- 訪問(wèn):
O(log(n))
- 搜索:
O(log(n))
- 插入:
O(log(n))
- 移除:
O(log(n))
- 移除最大值 / 最小值:
O(1)
- 訪問(wèn):
Hashing
- 哈希能夠?qū)⑷我忾L(zhǎng)度的數(shù)據(jù)映射到固定長(zhǎng)度的數(shù)據(jù)帅戒。哈希函數(shù)返回的即是哈希值灯帮,如果兩個(gè)不同的鍵得到相同的哈希值,即將這種現(xiàn)象稱為碰撞逻住。
- Hash Map: Hash Map 是一種能夠建立起鍵與值之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)钟哥,Hash Map 能夠使用哈希函數(shù)將鍵轉(zhuǎn)化為桶或者槽中的下標(biāo),從而優(yōu)化對(duì)于目標(biāo)值的搜索速度瞎访。
- 碰撞解決
- 鏈地址法(Separate Chaining): 鏈地址法中腻贰,每個(gè)桶是相互獨(dú)立的,包含了一系列索引的列表扒秸。搜索操作的時(shí)間復(fù)雜度即是搜索桶的時(shí)間(固定時(shí)間)與遍歷列表的時(shí)間之和播演。
- 開地址法(Open Addressing): 在開地址法中并徘,當(dāng)插入新值時(shí)驼抹,會(huì)判斷該值對(duì)應(yīng)的哈希桶是否存在,如果存在則根據(jù)某種算法依次選擇下一個(gè)可能的位置丈甸,直到找到一個(gè)尚未被占用的地址渔伯。所謂開地址法也是指某個(gè)元素的位置并不永遠(yuǎn)由其哈希值決定顶霞。
Graph
- 圖是一種數(shù)據(jù)元素間為多對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu),加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型锣吼。
- 無(wú)向圖(Undirected Graph): 無(wú)向圖具有對(duì)稱的鄰接矩陣选浑,因此如果存在某條從節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的邊,反之從 v 到 u 的邊也存在玄叠。
- 有向圖(Directed Graph): 有向圖的鄰接矩陣是非對(duì)稱的古徒,即如果存在從 u 到 v 的邊并不意味著一定存在從 v 到 u 的邊。
算法
排序
快速排序
- 穩(wěn)定: 否
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
O(nlog(n))
- 最壞時(shí)間:
O(n^2)
- 平均時(shí)間:
O(nlog(n))
- 最優(yōu)時(shí)間:
歸并排序
- 歸并排序是典型的分治算法读恃,它不斷地將某個(gè)數(shù)組分為兩個(gè)部分隧膘,分別對(duì)左子數(shù)組與右子數(shù)組進(jìn)行排序代态,然后將兩個(gè)數(shù)組合并為新的有序數(shù)組。
- 穩(wěn)定: 是
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
O(nlog(n))
- 最壞時(shí)間:
O(nlog(n))
- 平均時(shí)間:
O(nlog(n))
- 最優(yōu)時(shí)間:
桶排序
- 桶排序?qū)?shù)組分到有限數(shù)量的桶子里疹吃。每個(gè)桶子再個(gè)別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序)蹦疑。
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
Ω(n + k)
- 最壞時(shí)間:
O(n^2)
- 平均時(shí)間:
Θ(n + k)
- 最優(yōu)時(shí)間:
基數(shù)排序
- 基數(shù)排序類似于桶排序,將數(shù)組分割到有限數(shù)目的桶中萨驶;不過(guò)其在分割之后并沒(méi)有讓每個(gè)桶單獨(dú)地進(jìn)行排序歉摧,而是直接進(jìn)行了合并操作。
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
Ω(nk)
- 最壞時(shí)間:
O(nk)
- 平均時(shí)間:
Θ(nk)
- 最優(yōu)時(shí)間:
圖算法
深度優(yōu)先搜索
- 深度優(yōu)先算法是一種優(yōu)先遍歷子節(jié)點(diǎn)而不是回溯的算法腔呜。
- 時(shí)間復(fù)雜度:
O(|V| + |E|)
廣度優(yōu)先搜索
- 廣度優(yōu)先搜索是優(yōu)先遍歷鄰居節(jié)點(diǎn)而不是子節(jié)點(diǎn)的圖遍歷算法叁温。
- 時(shí)間復(fù)雜度:
O(|V| + |E|)
拓?fù)渑判?/h4>
- 拓?fù)渑判蚴菍?duì)于有向圖節(jié)點(diǎn)的線性排序,如果存在某條從 u 到 v 的邊核畴,則認(rèn)為 u 的下標(biāo)先于 v膝但。
- 時(shí)間復(fù)雜度:
O(|V| + |E|)
Dijkstra 算法
-
Dijkstra 算法 用于計(jì)算有向圖中單源最短路徑問(wèn)題。
- 時(shí)間復(fù)雜度:
O(|V|^2)
O(|V| + |E|)
O(|V|^2)
Bellman-Ford 算法
- Bellman-Ford 算法是在帶權(quán)圖中計(jì)算從單一源點(diǎn)出發(fā)到其他節(jié)點(diǎn)的最短路徑的算法谤草。
- 盡管算法復(fù)雜度大于 Dijkstra 算法锰镀,但是它適用于包含了負(fù)值邊的圖。
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
O(|E|)
- 最壞時(shí)間:
O(|V||E|)
- 最優(yōu)時(shí)間:
Floyd-Warshall 算法
- Floyd-Warshall 算法 能夠用于在無(wú)環(huán)帶權(quán)圖中尋找任意節(jié)點(diǎn)的最短路徑咖刃。
- 時(shí)間復(fù)雜度:
- 最優(yōu)時(shí)間:
O(|V|^3)
- 最壞時(shí)間:
O(|V|^3)
- 平均時(shí)間:
O(|V|^3)
- 最優(yōu)時(shí)間:
Prim 算法
- Prim 算法是用于在帶權(quán)無(wú)向圖中計(jì)算最小生成樹的貪婪算法泳炉。換言之,Prim 算法能夠在圖中抽取出連接所有節(jié)點(diǎn)的邊的最小代價(jià)子集嚎杨。
- 時(shí)間復(fù)雜度:
O(|V|^2)
Kruskal 算法
- Kruskal 算法同樣是計(jì)算圖的最小生成樹的算法花鹅,與 Prim 的區(qū)別在于并不需要圖是連通的。
- 時(shí)間復(fù)雜度:
O(|E|log|V|)
Kruskal's Algorithm
位運(yùn)算
- 位運(yùn)算即是在位級(jí)別進(jìn)行操作的技術(shù)枫浙,合適的位運(yùn)算能夠幫助我們得到更快地運(yùn)算速度與更小的內(nèi)存使用刨肃。
- 測(cè)試第 k 位:
s & (1 << k)
- 設(shè)置第 k 位:
s |= (1 << k)
- 第 k 位置零:
s &= ~(1 << k)
- 切換第 k 位值:
s ^= ~(1 << k)
- 乘以 2:
s << n
- 除以 2:
s >> n
- 交集:
s & t
- 并集:
s | t
- 減法:
s & ~t
- 交換
x = x ^ y ^ (y = x)
- 取出最小非 0 位(Extract lowest set bit):
s & (-s)
- 取出最小 0 位(Extract lowest unset bit):
~s & (s + 1)
- 交換值:
x ^= y; y ^= x; x ^= y;
算法復(fù)雜度分析
大 O 表示
- 大 O 表示 用于表示某個(gè)算法的上限,往往用于描述最壞的情況箩帚。
小 O 表示
- 小 O 表示用于描述某個(gè)算法的漸進(jìn)上界真友,不過(guò)二者要更為緊密。
大 Ω 表示
- 大 Ω 表示用于描述某個(gè)算法的漸進(jìn)下界紧帕。
小 ω 表示
- Little Omega Notation用于描述某個(gè)特定算法的下界盔然,不過(guò)不一定很靠近。
Theta Θ 表示
- Theta Notation用于描述某個(gè)確定算法的確界是嗜。
視頻教程
- Data Structures
- UC Berkeley Data Structures
- MIT Advanced Data Structures
- Algorithms
- MIT Introduction to Algorithms
- MIT Advanced Algorithms
面試書籍
- Competitive Programming 3 - Steven Halim & Felix Halim
- Cracking The Coding Interview - Gayle Laakmann McDowell
- Cracking The PM Interview - Gayle Laakmann McDowell & Jackie Bavaro
計(jì)算機(jī)科學(xué)與技術(shù)資訊
文件結(jié)構(gòu)
.
├── Array
│ ├── bestTimeToBuyAndSellStock.java
│ ├── findTheCelebrity.java
│ ├── gameOfLife.java
│ ├── increasingTripletSubsequence.java
│ ├── insertInterval.java
│ ├── longestConsecutiveSequence.java
│ ├── maximumProductSubarray.java
│ ├── maximumSubarray.java
│ ├── mergeIntervals.java
│ ├── missingRanges.java
│ ├── productOfArrayExceptSelf.java
│ ├── rotateImage.java
│ ├── searchInRotatedSortedArray.java
│ ├── spiralMatrixII.java
│ ├── subsetsII.java
│ ├── subsets.java
│ ├── summaryRanges.java
│ ├── wiggleSort.java
│ └── wordSearch.java
├── Backtracking
│ ├── androidUnlockPatterns.java
│ ├── generalizedAbbreviation.java
│ └── letterCombinationsOfAPhoneNumber.java
├── BinarySearch
│ ├── closestBinarySearchTreeValue.java
│ ├── firstBadVersion.java
│ ├── guessNumberHigherOrLower.java
│ ├── pow(x,n).java
│ └── sqrt(x).java
├── BitManipulation
│ ├── binaryWatch.java
│ ├── countingBits.java
│ ├── hammingDistance.java
│ ├── maximumProductOfWordLengths.java
│ ├── numberOf1Bits.java
│ ├── sumOfTwoIntegers.java
│ └── utf-8Validation.java
├── BreadthFirstSearch
│ ├── binaryTreeLevelOrderTraversal.java
│ ├── cloneGraph.java
│ ├── pacificAtlanticWaterFlow.java
│ ├── removeInvalidParentheses.java
│ ├── shortestDistanceFromAllBuildings.java
│ ├── symmetricTree.java
│ └── wallsAndGates.java
├── DepthFirstSearch
│ ├── balancedBinaryTree.java
│ ├── battleshipsInABoard.java
│ ├── convertSortedArrayToBinarySearchTree.java
│ ├── maximumDepthOfABinaryTree.java
│ ├── numberOfIslands.java
│ ├── populatingNextRightPointersInEachNode.java
│ └── sameTree.java
├── Design
│ └── zigzagIterator.java
├── DivideAndConquer
│ ├── expressionAddOperators.java
│ └── kthLargestElementInAnArray.java
├── DynamicProgramming
│ ├── bombEnemy.java
│ ├── climbingStairs.java
│ ├── combinationSumIV.java
│ ├── countingBits.java
│ ├── editDistance.java
│ ├── houseRobber.java
│ ├── paintFence.java
│ ├── paintHouseII.java
│ ├── regularExpressionMatching.java
│ ├── sentenceScreenFitting.java
│ ├── uniqueBinarySearchTrees.java
│ └── wordBreak.java
├── HashTable
│ ├── binaryTreeVerticalOrderTraversal.java
│ ├── findTheDifference.java
│ ├── groupAnagrams.java
│ ├── groupShiftedStrings.java
│ ├── islandPerimeter.java
│ ├── loggerRateLimiter.java
│ ├── maximumSizeSubarraySumEqualsK.java
│ ├── minimumWindowSubstring.java
│ ├── sparseMatrixMultiplication.java
│ ├── strobogrammaticNumber.java
│ ├── twoSum.java
│ └── uniqueWordAbbreviation.java
├── LinkedList
│ ├── addTwoNumbers.java
│ ├── deleteNodeInALinkedList.java
│ ├── mergeKSortedLists.java
│ ├── palindromeLinkedList.java
│ ├── plusOneLinkedList.java
│ ├── README.md
│ └── reverseLinkedList.java
├── Queue
│ └── movingAverageFromDataStream.java
├── README.md
├── Sort
│ ├── meetingRoomsII.java
│ └── meetingRooms.java
├── Stack
│ ├── binarySearchTreeIterator.java
│ ├── decodeString.java
│ ├── flattenNestedListIterator.java
│ └── trappingRainWater.java
├── String
│ ├── addBinary.java
│ ├── countAndSay.java
│ ├── decodeWays.java
│ ├── editDistance.java
│ ├── integerToEnglishWords.java
│ ├── longestPalindrome.java
│ ├── longestSubstringWithAtMostKDistinctCharacters.java
│ ├── minimumWindowSubstring.java
│ ├── multiplyString.java
│ ├── oneEditDistance.java
│ ├── palindromePermutation.java
│ ├── README.md
│ ├── reverseVowelsOfAString.java
│ ├── romanToInteger.java
│ ├── validPalindrome.java
│ └── validParentheses.java
├── Tree
│ ├── binaryTreeMaximumPathSum.java
│ ├── binaryTreePaths.java
│ ├── inorderSuccessorInBST.java
│ ├── invertBinaryTree.java
│ ├── lowestCommonAncestorOfABinaryTree.java
│ ├── sumOfLeftLeaves.java
│ └── validateBinarySearchTree.java
├── Trie
│ ├── addAndSearchWordDataStructureDesign.java
│ ├── implementTrie.java
│ └── wordSquares.java
└── TwoPointers
├── 3Sum.java
├── 3SumSmaller.java
├── mergeSortedArray.java
├── minimumSizeSubarraySum.java
├── moveZeros.java
├── removeDuplicatesFromSortedArray.java
├── reverseString.java
└── sortColors.java