国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

面試算法實踐與國外大廠習題指南

genedna / 1909人閱讀

摘要:面試算法實踐與國外大廠習題指南翻譯自維護的倉庫,包含了在線練習算法概述與大廠習題實戰等內容。面試算法實踐與國外大廠習題指南在線練習在線面試編程數據結構鏈表即是由節點組成的線性集合,每個節點可以利用指針指向其他節點。

</>復制代碼

  1. 面試算法實踐與國外大廠習題指南 翻譯自 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

文件結構

</>復制代碼

  1. .
  2. ├── Array
  3. │ ├── bestTimeToBuyAndSellStock.java
  4. │ ├── findTheCelebrity.java
  5. │ ├── gameOfLife.java
  6. │ ├── increasingTripletSubsequence.java
  7. │ ├── insertInterval.java
  8. │ ├── longestConsecutiveSequence.java
  9. │ ├── maximumProductSubarray.java
  10. │ ├── maximumSubarray.java
  11. │ ├── mergeIntervals.java
  12. │ ├── missingRanges.java
  13. │ ├── productOfArrayExceptSelf.java
  14. │ ├── rotateImage.java
  15. │ ├── searchInRotatedSortedArray.java
  16. │ ├── spiralMatrixII.java
  17. │ ├── subsetsII.java
  18. │ ├── subsets.java
  19. │ ├── summaryRanges.java
  20. │ ├── wiggleSort.java
  21. │ └── wordSearch.java
  22. ├── Backtracking
  23. │ ├── androidUnlockPatterns.java
  24. │ ├── generalizedAbbreviation.java
  25. │ └── letterCombinationsOfAPhoneNumber.java
  26. ├── BinarySearch
  27. │ ├── closestBinarySearchTreeValue.java
  28. │ ├── firstBadVersion.java
  29. │ ├── guessNumberHigherOrLower.java
  30. │ ├── pow(x,n).java
  31. │ └── sqrt(x).java
  32. ├── BitManipulation
  33. │ ├── binaryWatch.java
  34. │ ├── countingBits.java
  35. │ ├── hammingDistance.java
  36. │ ├── maximumProductOfWordLengths.java
  37. │ ├── numberOf1Bits.java
  38. │ ├── sumOfTwoIntegers.java
  39. │ └── utf-8Validation.java
  40. ├── BreadthFirstSearch
  41. │ ├── binaryTreeLevelOrderTraversal.java
  42. │ ├── cloneGraph.java
  43. │ ├── pacificAtlanticWaterFlow.java
  44. │ ├── removeInvalidParentheses.java
  45. │ ├── shortestDistanceFromAllBuildings.java
  46. │ ├── symmetricTree.java
  47. │ └── wallsAndGates.java
  48. ├── DepthFirstSearch
  49. │ ├── balancedBinaryTree.java
  50. │ ├── battleshipsInABoard.java
  51. │ ├── convertSortedArrayToBinarySearchTree.java
  52. │ ├── maximumDepthOfABinaryTree.java
  53. │ ├── numberOfIslands.java
  54. │ ├── populatingNextRightPointersInEachNode.java
  55. │ └── sameTree.java
  56. ├── Design
  57. │ └── zigzagIterator.java
  58. ├── DivideAndConquer
  59. │ ├── expressionAddOperators.java
  60. │ └── kthLargestElementInAnArray.java
  61. ├── DynamicProgramming
  62. │ ├── bombEnemy.java
  63. │ ├── climbingStairs.java
  64. │ ├── combinationSumIV.java
  65. │ ├── countingBits.java
  66. │ ├── editDistance.java
  67. │ ├── houseRobber.java
  68. │ ├── paintFence.java
  69. │ ├── paintHouseII.java
  70. │ ├── regularExpressionMatching.java
  71. │ ├── sentenceScreenFitting.java
  72. │ ├── uniqueBinarySearchTrees.java
  73. │ └── wordBreak.java
  74. ├── HashTable
  75. │ ├── binaryTreeVerticalOrderTraversal.java
  76. │ ├── findTheDifference.java
  77. │ ├── groupAnagrams.java
  78. │ ├── groupShiftedStrings.java
  79. │ ├── islandPerimeter.java
  80. │ ├── loggerRateLimiter.java
  81. │ ├── maximumSizeSubarraySumEqualsK.java
  82. │ ├── minimumWindowSubstring.java
  83. │ ├── sparseMatrixMultiplication.java
  84. │ ├── strobogrammaticNumber.java
  85. │ ├── twoSum.java
  86. │ └── uniqueWordAbbreviation.java
  87. ├── LinkedList
  88. │ ├── addTwoNumbers.java
  89. │ ├── deleteNodeInALinkedList.java
  90. │ ├── mergeKSortedLists.java
  91. │ ├── palindromeLinkedList.java
  92. │ ├── plusOneLinkedList.java
  93. │ ├── README.md
  94. │ └── reverseLinkedList.java
  95. ├── Queue
  96. │ └── movingAverageFromDataStream.java
  97. ├── README.md
  98. ├── Sort
  99. │ ├── meetingRoomsII.java
  100. │ └── meetingRooms.java
  101. ├── Stack
  102. │ ├── binarySearchTreeIterator.java
  103. │ ├── decodeString.java
  104. │ ├── flattenNestedListIterator.java
  105. │ └── trappingRainWater.java
  106. ├── String
  107. │ ├── addBinary.java
  108. │ ├── countAndSay.java
  109. │ ├── decodeWays.java
  110. │ ├── editDistance.java
  111. │ ├── integerToEnglishWords.java
  112. │ ├── longestPalindrome.java
  113. │ ├── longestSubstringWithAtMostKDistinctCharacters.java
  114. │ ├── minimumWindowSubstring.java
  115. │ ├── multiplyString.java
  116. │ ├── oneEditDistance.java
  117. │ ├── palindromePermutation.java
  118. │ ├── README.md
  119. │ ├── reverseVowelsOfAString.java
  120. │ ├── romanToInteger.java
  121. │ ├── validPalindrome.java
  122. │ └── validParentheses.java
  123. ├── Tree
  124. │ ├── binaryTreeMaximumPathSum.java
  125. │ ├── binaryTreePaths.java
  126. │ ├── inorderSuccessorInBST.java
  127. │ ├── invertBinaryTree.java
  128. │ ├── lowestCommonAncestorOfABinaryTree.java
  129. │ ├── sumOfLeftLeaves.java
  130. │ └── validateBinarySearchTree.java
  131. ├── Trie
  132. │ ├── addAndSearchWordDataStructureDesign.java
  133. │ ├── implementTrie.java
  134. │ └── wordSquares.java
  135. └── TwoPointers
  136. ├── 3Sum.java
  137. ├── 3SumSmaller.java
  138. ├── mergeSortedArray.java
  139. ├── minimumSizeSubarraySum.java
  140. ├── moveZeros.java
  141. ├── removeDuplicatesFromSortedArray.java
  142. ├── reverseString.java
  143. └── sortColors.java
  144. 18 directories, 124 files

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/66799.html

相關文章

  • Android-Java面試

    摘要:好不容易在月號這天中午點左右接到了來自阿里的面試電話。這里會不斷收集和更新基礎相關的面試題,目前已收集題。面試重難點的和的打包過程多線程機制機制系統啟動過程,啟動過程等等掃清面試障礙最新面試經驗分享,此為第一篇,開篇。 2016 年末,騰訊,百度,華為,搜狗和滴滴面試題匯總 2016 年未,騰訊,百度,華為,搜狗和滴滴面試題匯總 各大公司 Java 后端開發面試題總結 各大公司 Jav...

    TalkingData 評論0 收藏0
  • Tools - 收藏集 - 掘金

    摘要:個高級多線程面試題及回答后端掘金在任何面試當中多線程和并發方面的問題都是必不可少的一部分。默認為提供了年杭州面試經歷掘金想換個環境試試覺得做的不是自己想要的。源碼網站安居客項目架構演進掘金本文已授權微信公眾號獨家發布。 15 個高級 Java 多線程面試題及回答 - 后端 - 掘金在任何Java面試當中多線程和并發方面的問題都是必不可少的一部分。如果你想獲得任何股票投資銀行的前臺資訊職...

    KitorinZero 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<