算法题

Jun 29, 2019

 interview  interview  cs

30分钟3个算法题，30分钟内解决它们。经典问题

资料

  • leetcode高频题、lintcode高频题、剑指offer，大概这三样准备好就够了，校招前保证100多道题的积累量，面试时候写code应该就手到擒来了

微软真题

- 设计一个并发的Cache系统
	- https://codingcompetitions.withgoogle.com/kickstart/submissions/0000000000050edb/eGlhb3d1YzE
	-  ### 真题
- 高频题：并查集

- 逆序数]
- 二叉树节点最远距离
- 完全二叉树有多少个节点
- 平均数 Longlong
- 10亿个数排序，10万个重复，1G内存 bitmap
- 复制复杂链表
- 平均数模板
- n个数问x是否存在,n>20亿，500M内存
- LRU算法
- 全相连的cache
- 快排
- 二叉树节点距离
- 链表中所有的负数在前面去，所有的正数在后面
- 一个数组如何创建一棵平衡二叉树
    - 二分：用有序数组中中间的数生成搜索二叉树的头节点，然后对数组的左右部分分别生成左右子树即可（重复过程）。生成的二叉树中序遍历一定还是这个序列。
- 如何用最短时间复杂度内找到一颗二叉树内距离最远的两个节点。

技术问题

  • 背包九讲
    • 负无穷加上一个数仍然为负无穷，因此只能有[0,0]开始的才能为可行解
    • 选与不选当前的结果的值都需要的时候为加（求的是解的个数），否则只能选一个的时候为max（求的是最优解）。
  • 给定一个有序数组，然后再给个关键字，写一个函数返回其下标
    • 二分
  • 二分查找树转变成排序的双向链表
  • 两个有序数组求中位数(leetcode)
  • 判断平衡二叉树(剑指offer)
  • 最长上升子序列(lintcode)
  • 二叉树转双向链表(剑指offer)
  • LRU cache实现(leetcode)
  • House Robber(leetcode)
  • 链表翻转
  • 判断平衡二叉树
  • 最长公共子序列
  • 海量数据topk问题
  • 蓄水池抽样算法
  • 摊还分析 （聚合分析，核算法，势能法）
  • 比较排序（插入，冒泡(n^2) 归并，堆(n log n) 快速排序 (avg: nlogn worst:n^2) ）
  • 线性时间排序 （计数排序(k+n)，基数排序d(n+k)，桶排序 avg:n,worst:n^2）
  • 树(二叉树，二叉搜索树，红黑树，B树，斐波那契堆，不交集合数据结构)
  • 基本图算法（BSF,DSG,拓扑排序）
  • 最小生成树 （kruskal,prim)
  • 单源最短路径（bellman-ford,有向无环图，dijkstra)
  • 所有结点对最短路径（Floyd-warshall,johnson)
  • 最大流
  • (因子分解)给定数字N，分解成素数因子的乘积形式
  • (素性测试)：给定数字N，判断是否为素数
  • 对数换底公式
  • 石蕊试纸算法，费马小定理
  • 快速傅里叶变换的细节
  • huffman编码
  • 背包问题
  • 单纯性算法 n维空间中的顶点和邻居
  • 网络流 石油运输
  • 线性规划 利润最大化 生产计划
  • NP完全问题 回溯，分支定界（智能穷举搜素） 顶点覆盖，聚类，TSP，背包问题（近似算法）
  • 约瑟夫环问题详解
  • 背包问题
  • LCS
  • LIS
  • 编辑距离
  • 最长回文子串
  • 树的前序中序后序遍历 判断镜像 判断是否是完全二叉树 满二叉树 求树的深度

一些比较少见的算法

  • 随机算法 （蒙特卡洛算法，拉斯维加斯算法,舍伍德算法）
  • 备忘录方法
    • 重叠子问题性质,动态规划算法对每个问题只解一次，将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。
    • 备忘录方法与动态规划和递归的区别： - 动态规划是自低向上 ，备忘录方法是自顶向下，递归是自顶向下 - 动态规划每个子问题都要解一次，但不会求解重复子问题；备忘录方法只解哪些确实需要解的子问题；递归方法每个子问题都要解一次，
  • 各种运算符的技巧 http://xingyaohuang.com/2017/09/06/%E7%AE%97%E6%B3%951/
  • 无序整数数组中找第k大的数
    • 解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)
  • [主定理的证明][主定理的证明]
  • 网络流 - 卜
  • 线性规划 - 卜
  • 非常经典的在n个数中找到和为target的k个数
    • Given [1,2,3,4], k = 2, target = 5.
    • There are 2 solutions: [1,4] and [2,3]. Return 2.
    • https://segmentfault.com/a/1190000004984393
    • 使用三维动规数组dp[i][j][t]，表示从0遍历到A[i]后找到的j个元素之和为t的情况的总数。最后返回从整个A数组找到的k个元素之和为target的情况总数即可。操作如下：首先，若第i个元素，也就是A[i-1]，大于t，那么“从前i个元素中取j个元素令j个元素之和为t的所有情况”和第i个元素无关。也就是说dp[i][j][t] = dp[i-1][j][t]。而如果最后一个元素A[i-1] <= t，那么这个元素一定能带来一些不同的“从前i个元素中取j个元素令j个元素之和为t的情况”，但是，还要加上完全不考虑这个元素A[i-1]时的解的集合，也就是dp[i-1][j-1][t-A[i-1]]。因为，加上这个元素之后的dp[i][j-1][t-A[i-1]]不会影响已经遍历过的dp[i-1][j-1][t-A[i-1]]。
    • 动态规划小结 https://zhuanlan.zhihu.com/p/35707293

      本科问题

  • Dijkstra最短路径算法
  • 辗转相除法
    • 如果a是任一整数而b是任一大于零的整数，则我们总能找到一整数q，使a=bq+r
    • 辗转相除法是告诉我们(a,b)=(b,r)
  • Hanoi塔问题
  • 动态规划算法和贪心算法的区别（都满足最优子结构，但贪心算法具有贪心选择性质 ）
  • 分治（ 大整数乘积 快速排序 性能取决于划分的对称性 归并算法 循环日程表 棋盘覆盖 ）
    • //将原来为N的问题分解为k个问题规模较小的子问题，这些子问题相互独立且与原问题相同，递归的解决这些子问题，然后将各个子问题的解合并得到原问题的解。
  • 动态规划 （ 最优子结构+重叠子问题 0/1背包 系统可靠性 最长子序列和）
    • //找出最优解的性质，并刻画其结构特征。 递归地定义最优值。 以自底向上方法计算出最优值。 根据计算最优值的时候得到的信息，得到最优解。
  • 回溯（剪枝函数 包括 约束函数 和 限界函数 0/1背包 ）
  • 分支限界（队列式/优先队列式（优先级） 0/1背包）
  • 0/1背包（动态规划/回溯/分支限界 不可用贪心，得不到最优解）
  • 分支限界和回溯
    • 分治法所能解决的问题一般具有的几个特征是：
      • 该问题的规模缩小到一定的程度就可以容易地解决；
      • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
      • 利用该问题分解出的子问题的解可以合并为该问题的解；
      • 原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
    • 用分支限界法设计算法的步骤是：
      • 针对所给问题，定义问题的解空间（对解进行编码）
      • 确定易于搜索的解空间结构（按树或图组织解）
      • 以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
    • 常见的两种分支限界算法框架
      • 队列式 (FIFO) 分支限界法：按照队列先进先出（ FIFO）原则选取下一个节点为扩展节点
      • 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

贪心算法

 Toc
 Tags
 Related