摘要：面試算法實踐與國外大廠習題指南翻譯自維護的倉庫，包含了在線練習算法概述與大廠習題實戰(zhàn)等內(nèi)容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點組成的線性集合，每個節(jié)點可以利用指針指向其他節(jié)點。

面試算法實踐與國外大廠習題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews，包含了在線練習、算法概述與大廠習題實戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和之前翻譯的 Java 語法清單 以及 Java 進階面試問題列表 構(gòu)成面試準備的一些資料合集，從屬于筆者的 Java 入門與實踐系列。

LeetCode

Virtual Judge

CareerCup

HackerRank

CodeFights

Gainlo

鏈表即是由節(jié)點（Node）組成的線性集合，每個節(jié)點可以利用指針指向其他節(jié)點。它是一種包含了多個節(jié)點的，能夠用于表示序列的數(shù)據(jù)結(jié)構(gòu)。

Singly-linked list: 鏈表中的節(jié)點僅指向下一個節(jié)點。

Doubly-linked list: 鏈表中的節(jié)點不僅指向下一個節(jié)點，還指向前一個節(jié)點。

時間復(fù)雜度:

索引: O(n)

搜索: O(n)

插入: O(1)

移除: O(1)

棧是元素的集合，其包含了兩個基本操作：push 操作可以用于將元素壓入棧，pop 操作可以將棧頂元素移除。

遵循后入先出（LIFO）原則。

時間復(fù)雜度:

索引: O(n)

搜索: O(n)

插入: O(1)

移除: O(1)

隊列是元素的集合，其包含了兩個基本操作：enqueue 操作可以用于將元素插入到隊列中，而 dequeeu 操作則是將元素從隊列中移除。

遵循先入先出原則 (FIFO)。

時間復(fù)雜度:

索引: O(n)

搜索: O(n)

插入: O(1)

移除: O(1)

樹即是無向非循環(huán)圖。

二叉樹即是每個節(jié)點最多包含左子節(jié)點與右子節(jié)點這兩個節(jié)點的樹形數(shù)據(jù)結(jié)構(gòu)。

滿二叉樹: 樹中的每個節(jié)點僅包含 0 或 2 個節(jié)點。

完美二叉樹: 二叉樹中的每個葉節(jié)點都擁有兩個子節(jié)點，并且具有相同的高度。

完全二叉樹: 除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。

二叉搜索樹（BST）是一種特殊的二叉樹，其任何節(jié)點中的值都會大于或者等于其左子樹中存儲的值并且小于或者等于其右子樹中存儲的值。

時間復(fù)雜度:

索引: O(log(n))

搜索: O(log(n))

插入: O(log(n))

刪除: O(log(n))

字典樹，又稱基數(shù)樹或者前綴樹，能夠用于存儲鍵為字符串的動態(tài)集合或者關(guān)聯(lián)數(shù)組的搜索樹。樹中的節(jié)點并沒有直接存儲關(guān)聯(lián)鍵值，而是該節(jié)點在樹中的掛載位置決定了其關(guān)聯(lián)鍵值。某個節(jié)點的所有子節(jié)點都擁有相同的前綴，整棵樹的根節(jié)點則是空字符串。

樹狀數(shù)組又稱 Binary Indexed Tree，其表現(xiàn)形式為樹，不過本質(zhì)上是以數(shù)組實現(xiàn)。數(shù)組中的下標代表著樹中的頂點，每個頂點的父節(jié)點或者子節(jié)點的下標能夠通過位運算獲得。數(shù)組中的每個元素包含了預(yù)計算的區(qū)間值之和，在整棵樹更新的過程中同樣會更新這些預(yù)計算的值。

時間復(fù)雜度:

區(qū)間求值: O(log(n))

更新: O(log(n))

線段樹是用于存放間隔或者線段的樹形數(shù)據(jù)結(jié)構(gòu)，它允許快速的查找某一個節(jié)點在若干條線段中出現(xiàn)的次數(shù).

時間復(fù)雜度:

區(qū)間查詢: O(log(n))

更新: O(log(n))

堆是一種特殊的基于樹的滿足某些特性的數(shù)據(jù)結(jié)構(gòu)，整個堆中的所有父子節(jié)點的鍵值都會滿足相同的排序條件。堆更準確地可以分為最大堆與最小堆，在最大堆中，父節(jié)點的鍵值永遠大于或者等于子節(jié)點的值，并且整個堆中的最大值存儲于根節(jié)點；而最小堆中，父節(jié)點的鍵值永遠小于或者等于其子節(jié)點的鍵值，并且整個堆中的最小值存儲于根節(jié)點。

時間復(fù)雜度:

訪問: O(log(n))

搜索: O(log(n))

插入: O(log(n))

移除: O(log(n))

移除最大值 / 最小值: O(1)

哈希能夠?qū)⑷我忾L度的數(shù)據(jù)映射到固定長度的數(shù)據(jù)。哈希函數(shù)返回的即是哈希值，如果兩個不同的鍵得到相同的哈希值，即將這種現(xiàn)象稱為碰撞。

Hash Map: Hash Map 是一種能夠建立起鍵與值之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，Hash Map 能夠使用哈希函數(shù)將鍵轉(zhuǎn)化為桶或者槽中的下標，從而優(yōu)化對于目標值的搜索速度。

碰撞解決

鏈地址法（Separate Chaining）: 鏈地址法中，每個桶是相互獨立的，包含了一系列索引的列表。搜索操作的時間復(fù)雜度即是搜索桶的時間（固定時間）與遍歷列表的時間之和。

開地址法（Open Addressing）: 在開地址法中，當插入新值時，會判斷該值對應(yīng)的哈希桶是否存在，如果存在則根據(jù)某種算法依次選擇下一個可能的位置，直到找到一個尚未被占用的地址。所謂開地址法也是指某個元素的位置并不永遠由其哈希值決定。

圖是一種數(shù)據(jù)元素間為多對多關(guān)系的數(shù)據(jù)結(jié)構(gòu),加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型。

無向圖（Undirected Graph）: 無向圖具有對稱的鄰接矩陣，因此如果存在某條從節(jié)點 u 到節(jié)點 v 的邊，反之從 v 到 u 的邊也存在。

有向圖（Directed Graph）: 有向圖的鄰接矩陣是非對稱的，即如果存在從 u 到 v 的邊并不意味著一定存在從 v 到 u 的邊。

graph in which the adjacency relation is not symmetric. So if there exists an edge from node u to node v (u -> v), this does not imply that there exists an edge from node v to node u (v -> u)

穩(wěn)定: 否

時間復(fù)雜度:

最優(yōu)時間: O(nlog(n))

最壞時間: O(n^2)

平均時間: O(nlog(n))

合并排序是典型的分治算法，它不斷地將某個數(shù)組分為兩個部分，分別對左子數(shù)組與右子數(shù)組進行排序，然后將兩個數(shù)組合并為新的有序數(shù)組。

穩(wěn)定: 是

時間復(fù)雜度:

最優(yōu)時間: O(nlog(n))

最壞時間: O(nlog(n))`

平均時間: O(nlog(n))

桶排序?qū)?shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。

時間復(fù)雜度:

最優(yōu)時間: Ω(n + k)

最壞時間: O(n^2)

平均時間:Θ(n + k)

基數(shù)排序類似于桶排序，將數(shù)組分割到有限數(shù)目的桶中；不過其在分割之后并沒有讓每個桶多帶帶地進行排序，而是直接進行了合并操作。

時間復(fù)雜度:

最優(yōu)時間: Ω(nk)

最壞時間: O(nk)

平均時間: Θ(nk)

深度優(yōu)先算法是一種優(yōu)先遍歷子節(jié)點而不是回溯的算法。

時間復(fù)雜度: O(|V| + |E|)

廣度優(yōu)先搜索是優(yōu)先遍歷鄰居節(jié)點而不是子節(jié)點的圖遍歷算法。

時間復(fù)雜度: O(|V| + |E|)

拓撲排序是對于有向圖節(jié)點的線性排序，如果存在某條從 u 到 v 的邊，則認為 u 的下標先于 v。

時間復(fù)雜度: O(|V| + |E|)

Dijkstra 算法 用于計算有向圖中單源最短路徑問題。

時間復(fù)雜度: O(|V|^2)

Bellman-Ford 算法 是在帶權(quán)圖中計算從單一源點出發(fā)到其他節(jié)點的最短路徑的算法。

盡管算法復(fù)雜度大于 Dijkstra 算法，但是它適用于包含了負值邊的圖。

時間復(fù)雜度:

最優(yōu)時間: O(|E|)

最壞時間: O(|V||E|)

Floyd-Warshall 算法 能夠用于在無環(huán)帶權(quán)圖中尋找任意節(jié)點的最短路徑。

時間復(fù)雜度:

最優(yōu)時間: O(|V|^3)

最壞時間: O(|V|^3)

平均時間: O(|V|^3)

Prim"s 算法是用于在帶權(quán)無向圖中計算最小生成樹的貪婪算法。換言之，Prim 算法能夠在圖中抽取出連接所有節(jié)點的邊的最小代價子集。

時間復(fù)雜度: O(|V|^2)

Kruskal 算法 同樣是計算圖的最小生成樹的算法，與 Prim 的區(qū)別在于并不需要圖是連通的。

時間復(fù)雜度: O(|E|log|V|)

位運算即是在位級別進行操作的技術(shù)，合適的位運算能夠幫助我們得到更快地運算速度與更小的內(nèi)存使用。

測試第 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)

Extract lowest set bit: s & (-s)

Extract lowest unset bit: ~s & (s + 1)

大 O 表示 用于表示某個算法的上限，往往用于描述最壞的情況。

小 O 表示 用于描述某個算法的漸進上界，不過二者要更為緊密。

大 Ω 表示 用于描述某個算法的漸進下界。

Little Omega Notation 用于描述某個特定算法的下界，不過不一定很靠近。

Theta Notation 用于描述某個確定算法的確界。

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

Hacker News

.
├── 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

18 directories, 124 files