資訊專(zhuān)欄INFORMATION COLUMN
摘要：面試算法實(shí)踐與國(guó)外大廠習(xí)題指南翻譯自維護(hù)的倉(cāng)庫(kù)，包含了在線練習(xí)算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。面試算法實(shí)踐與國(guó)外大廠習(xí)題指南在線練習(xí)在線面試編程數(shù)據(jù)結(jié)構(gòu)鏈表即是由節(jié)點(diǎn)組成的線性集合，每個(gè)節(jié)點(diǎn)可以利用指針指向其他節(jié)點(diǎn)。
面試算法實(shí)踐與國(guó)外大廠習(xí)題指南 在線練習(xí)面試算法實(shí)踐與國(guó)外大廠習(xí)題指南 翻譯自 Kevin Naughton Jr. 維護(hù)的倉(cāng)庫(kù) interviews，包含了在線練習(xí)、算法概述與大廠習(xí)題實(shí)戰(zhàn)等內(nèi)容。筆者發(fā)現(xiàn)正好和之前翻譯的 Java 語(yǔ)法清單 以及 Java 進(jìn)階面試問(wèn)題列表 構(gòu)成面試準(zhǔn)備的一些資料合集，從屬于筆者的 Java 入門(mén)與實(shí)踐系列。
LeetCode
Virtual Judge
CareerCup
HackerRank
CodeFights
在線面試編程Gainlo
數(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)。
Singly-linked list: 鏈表中的節(jié)點(diǎn)僅指向下一個(gè)節(jié)點(diǎn)。
Doubly-linked list: 鏈表中的節(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樹(shù)即是無(wú)向非循環(huán)圖。
Binary Tree二叉樹(shù)即是每個(gè)節(jié)點(diǎn)最多包含左子節(jié)點(diǎn)與右子節(jié)點(diǎn)這兩個(gè)節(jié)點(diǎn)的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。
滿二叉樹(shù): 樹(shù)中的每個(gè)節(jié)點(diǎn)僅包含 0 或 2 個(gè)節(jié)點(diǎn)。
完美二叉樹(shù): 二叉樹(shù)中的每個(gè)葉節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)，并且具有相同的高度。
完全二叉樹(shù): 除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。
Binary Search Tree二叉搜索樹(shù)（BST）是一種特殊的二叉樹(shù)，其任何節(jié)點(diǎn)中的值都會(huì)大于或者等于其左子樹(shù)中存儲(chǔ)的值并且小于或者等于其右子樹(shù)中存儲(chǔ)的值。
時(shí)間復(fù)雜度:
索引: O(log(n))
搜索: O(log(n))
插入: O(log(n))
刪除: O(log(n))
Trie字典樹(shù)，又稱(chēng)基數(shù)樹(shù)或者前綴樹(shù)，能夠用于存儲(chǔ)鍵為字符串的動(dòng)態(tài)集合或者關(guān)聯(lián)數(shù)組的搜索樹(shù)。樹(shù)中的節(jié)點(diǎn)并沒(méi)有直接存儲(chǔ)關(guān)聯(lián)鍵值，而是該節(jié)點(diǎn)在樹(shù)中的掛載位置決定了其關(guān)聯(lián)鍵值。某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都擁有相同的前綴，整棵樹(shù)的根節(jié)點(diǎn)則是空字符串。
Fenwick Tree樹(shù)狀數(shù)組又稱(chēng) Binary Indexed Tree，其表現(xiàn)形式為樹(shù)，不過(guò)本質(zhì)上是以數(shù)組實(shí)現(xiàn)。數(shù)組中的下標(biāo)代表著樹(shù)中的頂點(diǎn)，每個(gè)頂點(diǎn)的父節(jié)點(diǎn)或者子節(jié)點(diǎn)的下標(biāo)能夠通過(guò)位運(yùn)算獲得。數(shù)組中的每個(gè)元素包含了預(yù)計(jì)算的區(qū)間值之和，在整棵樹(shù)更新的過(guò)程中同樣會(huì)更新這些預(yù)計(jì)算的值。
時(shí)間復(fù)雜度:
區(qū)間求值: O(log(n))
更新: O(log(n))
Segment Tree線段樹(shù)是用于存放間隔或者線段的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，它允許快速的查找某一個(gè)節(jié)點(diǎn)在若干條線段中出現(xiàn)的次數(shù).
時(shí)間復(fù)雜度:
區(qū)間查詢(xún): O(log(n))
更新: O(log(n))
Heap堆是一種特殊的基于樹(shù)的滿足某些特性的數(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)
Hashing哈希能夠?qū)⑷我忾L(zhǎng)度的數(shù)據(jù)映射到固定長(zhǎng)度的數(shù)據(jù)。哈希函數(shù)返回的即是哈希值，如果兩個(gè)不同的鍵得到相同的哈希值，即將這種現(xiàn)象稱(chēng)為碰撞。
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í)間之和。
開(kāi)地址法（Open Addressing）: 在開(kāi)地址法中，當(dāng)插入新值時(shí)，會(huì)判斷該值對(duì)應(yīng)的哈希桶是否存在，如果存在則根據(jù)某種算法依次選擇下一個(gè)可能的位置，直到找到一個(gè)尚未被占用的地址。所謂開(kāi)地址法也是指某個(gè)元素的位置并不永遠(yuǎn)由其哈希值決定。
Graph
圖是一種數(shù)據(jù)元素間為多對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu),加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類(lèi)型。
無(wú)向圖（Undirected Graph）: 無(wú)向圖具有對(duì)稱(chēng)的鄰接矩陣，因此如果存在某條從節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的邊，反之從 v 到 u 的邊也存在。
有向圖（Directed Graph）: 有向圖的鄰接矩陣是非對(duì)稱(chēng)的，即如果存在從 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)
算法 Sorting 快速排序穩(wěn)定: 否
時(shí)間復(fù)雜度:
最優(yōu)時(shí)間: O(nlog(n))
最壞時(shí)間: O(n^2)
平均時(shí)間: O(nlog(n))
合并排序合并排序是典型的分治算法，它不斷地將某個(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))
桶排序桶排序?qū)?shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。
時(shí)間復(fù)雜度:
最優(yōu)時(shí)間: Ω(n + k)
最壞時(shí)間: O(n^2)
平均時(shí)間:Θ(n + k)
基數(shù)排序基數(shù)排序類(lèi)似于桶排序，將數(shù)組分割到有限數(shù)目的桶中；不過(guò)其在分割之后并沒(méi)有讓每個(gè)桶多帶帶地進(jìn)行排序，而是直接進(jìn)行了合并操作。
時(shí)間復(fù)雜度:
最優(yōu)時(shí)間: Ω(nk)
最壞時(shí)間: O(nk)
平均時(shí)間: Θ(nk)
圖算法 深度優(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ù)渑判?/b>拓?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)
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|)
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)
Prim 算法Prim"s 算法是用于在帶權(quán)無(wú)向圖中計(jì)算最小生成樹(shù)的貪婪算法。換言之，Prim 算法能夠在圖中抽取出連接所有節(jié)點(diǎn)的邊的最小代價(jià)子集。
時(shí)間復(fù)雜度: O(|V|^2)
Kruskal 算法Kruskal 算法 同樣是計(jì)算圖的最小生成樹(shù)的算法，與 Prim 的區(qū)別在于并不需要圖是連通的。
時(shí)間復(fù)雜度: O(|E|log|V|)
位運(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)
Extract lowest set bit: s & (-s)
Extract lowest unset bit: ~s & (s + 1)
算法復(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
面試書(shū)籍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ù)資訊Hacker News
文件結(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
18 directories, 124 files
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66799.html
摘要：好不容易在月號(hào)這天中午點(diǎn)左右接到了來(lái)自阿里的面試電話。這里會(huì)不斷收集和更新基礎(chǔ)相關(guān)的面試題，目前已收集題。面試重難點(diǎn)的和的打包過(guò)程多線程機(jī)制機(jī)制系統(tǒng)啟動(dòng)過(guò)程，啟動(dòng)過(guò)程等等掃清面試障礙最新面試經(jīng)驗(yàn)分享，此為第一篇，開(kāi)篇。 2016 年末，騰訊，百度，華為，搜狗和滴滴面試題匯總 2016 年未，騰訊，百度，華為，搜狗和滴滴面試題匯總 各大公司 Java 后端開(kāi)發(fā)面試題總結(jié) 各大公司 Jav...
摘要：個(gè)高級(jí)多線程面試題及回答后端掘金在任何面試當(dāng)中多線程和并發(fā)方面的問(wèn)題都是必不可少的一部分。默認(rèn)為提供了年杭州面試經(jīng)歷掘金想換個(gè)環(huán)境試試覺(jué)得做的不是自己想要的。源碼網(wǎng)站安居客項(xiàng)目架構(gòu)演進(jìn)掘金本文已授權(quán)微信公眾號(hào)獨(dú)家發(fā)布。 15 個(gè)高級(jí) Java 多線程面試題及回答 - 后端 - 掘金在任何Java面試當(dāng)中多線程和并發(fā)方面的問(wèn)題都是必不可少的一部分。如果你想獲得任何股票投資銀行的前臺(tái)資訊職...
閱讀 3328·2021-11-08 13:12
閱讀 2773·2021-10-15 09:41
閱讀 1468·2021-10-08 10:05
閱讀 3314·2021-10-08 10:04
閱讀 2127·2021-09-29 09:34
閱讀 2502·2019-08-30 15:55
閱讀 2992·2019-08-30 15:45
閱讀 2605·2019-08-29 14:17
