摘要:面試算法實踐與國外大廠習題指南翻譯自維護的倉庫,包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合,每個節點可以利用指針指向其他節點。
面試算法實踐與國外大廠習題指南 在線練習</>復制代碼
面試算法實踐與國外大廠習題指南 翻譯自 Kevin Naughton Jr. 維護的倉庫 interviews,包含了在線練習、算法概述與大廠習題實戰等內容。筆者發現正好和之前翻譯的 Java 語法清單 以及 Java 進階面試問題列表 構成面試準備的一些資料合集,從屬于筆者的 Java 入門與實踐系列。
LeetCode
Virtual Judge
CareerCup
HackerRank
CodeFights
在線面試編程Gainlo
數據結構 Linked List鏈表即是由節點(Node)組成的線性集合,每個節點可以利用指針指向其他節點。它是一種包含了多個節點的,能夠用于表示序列的數據結構。
Singly-linked list: 鏈表中的節點僅指向下一個節點。
Doubly-linked list: 鏈表中的節點不僅指向下一個節點,還指向前一個節點。
時間復雜度:
索引: O(n)
搜索: O(n)
插入: O(1)
移除: O(1)
Stack棧是元素的集合,其包含了兩個基本操作:push 操作可以用于將元素壓入棧,pop 操作可以將棧頂元素移除。
遵循后入先出(LIFO)原則。
時間復雜度:
索引: O(n)
搜索: O(n)
插入: O(1)
移除: O(1)
Queue隊列是元素的集合,其包含了兩個基本操作:enqueue 操作可以用于將元素插入到隊列中,而 dequeeu 操作則是將元素從隊列中移除。
遵循先入先出原則 (FIFO)。
時間復雜度:
索引: O(n)
搜索: O(n)
插入: O(1)
移除: O(1)
Tree樹即是無向非循環圖。
Binary Tree二叉樹即是每個節點最多包含左子節點與右子節點這兩個節點的樹形數據結構。
滿二叉樹: 樹中的每個節點僅包含 0 或 2 個節點。
完美二叉樹: 二叉樹中的每個葉節點都擁有兩個子節點,并且具有相同的高度。
完全二叉樹: 除最后一層外,每一層上的結點數均達到最大值;在最后一層上只缺少右邊的若干結點。
Binary Search Tree二叉搜索樹(BST)是一種特殊的二叉樹,其任何節點中的值都會大于或者等于其左子樹中存儲的值并且小于或者等于其右子樹中存儲的值。
時間復雜度:
索引: O(log(n))
搜索: O(log(n))
插入: O(log(n))
刪除: O(log(n))
Trie字典樹,又稱基數樹或者前綴樹,能夠用于存儲鍵為字符串的動態集合或者關聯數組的搜索樹。樹中的節點并沒有直接存儲關聯鍵值,而是該節點在樹中的掛載位置決定了其關聯鍵值。某個節點的所有子節點都擁有相同的前綴,整棵樹的根節點則是空字符串。
Fenwick Tree樹狀數組又稱 Binary Indexed Tree,其表現形式為樹,不過本質上是以數組實現。數組中的下標代表著樹中的頂點,每個頂點的父節點或者子節點的下標能夠通過位運算獲得。數組中的每個元素包含了預計算的區間值之和,在整棵樹更新的過程中同樣會更新這些預計算的值。
時間復雜度:
區間求值: O(log(n))
更新: O(log(n))
Segment Tree線段樹是用于存放間隔或者線段的樹形數據結構,它允許快速的查找某一個節點在若干條線段中出現的次數.
時間復雜度:
區間查詢: O(log(n))
更新: O(log(n))
Heap堆是一種特殊的基于樹的滿足某些特性的數據結構,整個堆中的所有父子節點的鍵值都會滿足相同的排序條件。堆更準確地可以分為最大堆與最小堆,在最大堆中,父節點的鍵值永遠大于或者等于子節點的值,并且整個堆中的最大值存儲于根節點;而最小堆中,父節點的鍵值永遠小于或者等于其子節點的鍵值,并且整個堆中的最小值存儲于根節點。
時間復雜度:
訪問: O(log(n))
搜索: O(log(n))
插入: O(log(n))
移除: O(log(n))
移除最大值 / 最小值: O(1)
Hashing哈希能夠將任意長度的數據映射到固定長度的數據。哈希函數返回的即是哈希值,如果兩個不同的鍵得到相同的哈希值,即將這種現象稱為碰撞。
Hash Map: Hash Map 是一種能夠建立起鍵與值之間關系的數據結構,Hash Map 能夠使用哈希函數將鍵轉化為桶或者槽中的下標,從而優化對于目標值的搜索速度。
碰撞解決
鏈地址法(Separate Chaining): 鏈地址法中,每個桶是相互獨立的,包含了一系列索引的列表。搜索操作的時間復雜度即是搜索桶的時間(固定時間)與遍歷列表的時間之和。
開地址法(Open Addressing): 在開地址法中,當插入新值時,會判斷該值對應的哈希桶是否存在,如果存在則根據某種算法依次選擇下一個可能的位置,直到找到一個尚未被占用的地址。所謂開地址法也是指某個元素的位置并不永遠由其哈希值決定。
Graph
圖是一種數據元素間為多對多關系的數據結構,加上一組基本操作構成的抽象數據類型。
無向圖(Undirected Graph): 無向圖具有對稱的鄰接矩陣,因此如果存在某條從節點 u 到節點 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)
算法 Sorting 快速排序穩定: 否
時間復雜度:
最優時間: O(nlog(n))
最壞時間: O(n^2)
平均時間: O(nlog(n))
合并排序合并排序是典型的分治算法,它不斷地將某個數組分為兩個部分,分別對左子數組與右子數組進行排序,然后將兩個數組合并為新的有序數組。
穩定: 是
時間復雜度:
最優時間: O(nlog(n))
最壞時間: O(nlog(n))`
平均時間: O(nlog(n))
桶排序桶排序將數組分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排序)。
時間復雜度:
最優時間: Ω(n + k)
最壞時間: O(n^2)
平均時間:Θ(n + k)
基數排序基數排序類似于桶排序,將數組分割到有限數目的桶中;不過其在分割之后并沒有讓每個桶多帶帶地進行排序,而是直接進行了合并操作。
時間復雜度:
最優時間: Ω(nk)
最壞時間: O(nk)
平均時間: Θ(nk)
圖算法 深度優先搜索深度優先算法是一種優先遍歷子節點而不是回溯的算法。
時間復雜度: O(|V| + |E|)
廣度優先搜索廣度優先搜索是優先遍歷鄰居節點而不是子節點的圖遍歷算法。
時間復雜度: O(|V| + |E|)
拓撲排序拓撲排序是對于有向圖節點的線性排序,如果存在某條從 u 到 v 的邊,則認為 u 的下標先于 v。
時間復雜度: O(|V| + |E|)
Dijkstra 算法Dijkstra 算法 用于計算有向圖中單源最短路徑問題。
時間復雜度: O(|V|^2)
Bellman-Ford 算法Bellman-Ford 算法 是在帶權圖中計算從單一源點出發到其他節點的最短路徑的算法。
盡管算法復雜度大于 Dijkstra 算法,但是它適用于包含了負值邊的圖。
時間復雜度:
最優時間: O(|E|)
最壞時間: O(|V||E|)
Floyd-Warshall 算法Floyd-Warshall 算法 能夠用于在無環帶權圖中尋找任意節點的最短路徑。
時間復雜度:
最優時間: O(|V|^3)
最壞時間: O(|V|^3)
平均時間: O(|V|^3)
Prim 算法Prim"s 算法是用于在帶權無向圖中計算最小生成樹的貪婪算法。換言之,Prim 算法能夠在圖中抽取出連接所有節點的邊的最小代價子集。
時間復雜度: O(|V|^2)
Kruskal 算法Kruskal 算法 同樣是計算圖的最小生成樹的算法,與 Prim 的區別在于并不需要圖是連通的。
時間復雜度: O(|E|log|V|)
位運算位運算即是在位級別進行操作的技術,合適的位運算能夠幫助我們得到更快地運算速度與更小的內存使用。
測試第 k 位: s & (1 << k)
設置第 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 表示 用于表示某個算法的上限,往往用于描述最壞的情況。
小 O 表示小 O 表示 用于描述某個算法的漸進上界,不過二者要更為緊密。
大 Ω 表示大 Ω 表示 用于描述某個算法的漸進下界。
小 ω 表示Little Omega Notation 用于描述某個特定算法的下界,不過不一定很靠近。
Theta Θ 表示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
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/66799.html
摘要:好不容易在月號這天中午點左右接到了來自阿里的面試電話。這里會不斷收集和更新基礎相關的面試題,目前已收集題。面試重難點的和的打包過程多線程機制機制系統啟動過程,啟動過程等等掃清面試障礙最新面試經驗分享,此為第一篇,開篇。 2016 年末,騰訊,百度,華為,搜狗和滴滴面試題匯總 2016 年未,騰訊,百度,華為,搜狗和滴滴面試題匯總 各大公司 Java 后端開發面試題總結 各大公司 Jav...
摘要:個高級多線程面試題及回答后端掘金在任何面試當中多線程和并發方面的問題都是必不可少的一部分。默認為提供了年杭州面試經歷掘金想換個環境試試覺得做的不是自己想要的。源碼網站安居客項目架構演進掘金本文已授權微信公眾號獨家發布。 15 個高級 Java 多線程面試題及回答 - 后端 - 掘金在任何Java面試當中多線程和并發方面的問題都是必不可少的一部分。如果你想獲得任何股票投資銀行的前臺資訊職...
閱讀 3328·2021-11-08 13:12
閱讀 2771·2021-10-15 09:41
閱讀 1462·2021-10-08 10:05
閱讀 3309·2021-10-08 10:04
閱讀 2122·2021-09-29 09:34
閱讀 2497·2019-08-30 15:55
閱讀 2991·2019-08-30 15:45
閱讀 2597·2019-08-29 14:17