资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/面试算法实践与国外大厂习题指南

面试算法实践与国外大厂习题指南

genedna / 1978人阅读

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。

</>复制代码 
  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
GPU云服务器 云服务器 云计算实践指南 机器学习实践指南 devops实践指南 微服务架构与实践

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66799.html

相关文章

  • Android-Java面试

    摘要：好不容易在月号这天中午点左右接到了来自阿里的面试电话。这里会不断收集和更新基础相关的面试题，目前已收集题。面试重难点的和的打包过程多线程机制机制系统启动过程，启动过程等等扫清面试障碍最新面试经验分享，此为第一篇，开篇。 2016 年末，腾讯，百度，华为，搜狗和滴滴面试题汇总 2016 年未，腾讯，百度，华为，搜狗和滴滴面试题汇总 各大公司 Java 后端开发面试题总结 各大公司 Jav...

    TalkingData 评论0 收藏0

  • Tools - 收藏集 - 掘金

    摘要：个高级多线程面试题及回答后端掘金在任何面试当中多线程和并发方面的问题都是必不可少的一部分。默认为提供了年杭州面试经历掘金想换个环境试试觉得做的不是自己想要的。源码网站安居客项目架构演进掘金本文已授权微信公众号独家发布。 15 个高级 Java 多线程面试题及回答 - 后端 - 掘金在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职...

    KitorinZero 评论0 收藏0

发表评论

登陆后可评论

0条评论

genedna

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<