不知疲倦刷题

在网上投了简历，一周后收到面试通知。面试是在 Snapchat LA 总部面的，公司环境很好，可以看到海景。另外，面试报销机票、住宿的所有费用。平常在大农村住久了，这次就当去 LA 玩一下。 整个面试过程包括一场电面和四场onsite。 电面1 电面比较轻松，先是自我介绍，然后问了一些我简历上的项目问题。因为这一部分可以提前准备，所以表现的比较好。另外还问了一道Lintcode上中等难度的算法题 1、 完美平方 这道题目之前在Lintcode上刷过，所以完成的还不错。 Lintcode原题链接：http://www.lintcode.com/zh-cn/problem/perfect-squares/ 参考答案：http://www.jiuzhang.com/solutions/perfect-squares/ 电面没多久被通知可以参加OnSite了，并约了OnSite的时间。 Onsite1 第一轮onsite问了一些计算机基础知识方面的问题和一道算法题。 1.给出一个数组，包括一些会议的起始时间和终止时间，判断一个人能否参加所有的会议。 LintCode原题链接：http://www.lintcode.com/zh-cn/problem/meeting-rooms/ 参考答案：http://www.jiuzhang.com/solutions/meeting-rooms/ O nsite2 这一轮问了两道算法题： 1.给出: class Throttler { int qps ; public Throttler ( int qps ) { } pubilc boolean allowAccess() { } } 实现速度限制器，allowAccess()，返回当前的时间是否允许 例如: qps is 2 request1 time 0.0 return true; request2 time 0.5 return true; request3 time 0.6 return false; 2.最小字串覆盖 LintCode原题链接：http://www.lintcode.com/zh-cn/problem/minimu...

【题目描述】 There is an integer array which has the following features: ·The numbers in adjacent positions are different. ·A[0] < A[1] && A[A.length - 2] > A[A.length - 1]. We define a position P is a peek if: A[P]>A[P-1]&&A[p]>A[P+1] Find a peak element in this array. Return the index of the peak. 你给出一个整数数组(size为n)，其具有以下特点： 1、相邻位置的数字是不同的 2、A[0] < A[1] 并且 A[n - 2] > A[n - 1] 假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。 【注意】：数组可能包含多个峰值，只需找到其中的任何一个即可 【题目链接】 www.lintcode.com/en/problem/find-peak-element/ 【题目解析】 此题可使用二分搜索。首先分析若使用传统的二分搜索，若A[mid] > A[mid - 1] && A[mid] < A[mid + 1]，则找到一个peak为A[mid]；若A[mid - 1] > A[mid]，则A[mid]左侧必定存在一个peak，可用反证法证明：若左侧不存在peak，则A[mid]左侧元素必满足A[0] > A[1] > ... > A[mid -1] > A[mid]，与已知A[0] < A[1]矛盾，证毕。同理可得若A[mid + 1] > A[mid]，则A[mid]右侧必定存在一个peak。如此迭代即可得解。 【参考答案】 www.jiuzhang.com/solutions/find-peak-element/

【题目描述】 The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case, so it caused this version and the following versions are all failed in the unit tests. Find the first bad version. You can callisBadVersionto help you determine which version is the first bad one. The details interface can be found in the code's annotation part. 代码库的版本号是从1 到n的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。 你可以通过isBadVersion的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。 【 注意 】 ：请阅读上述代码，对于不同的语言获取正确的调用isBadVersion的方法，比如java的调用方式是SVNRepo.isBadVersion(v) 【题目链接】 www.lintcode.com/en/problem/first-bad-version/ 【题目解析】 从最先出错的版本所在的位置开始，其后的所有版本也都是错误的，所以此题使用二分法解决。二分搜索的范围，使用[0，n）来控制边界。需要查找出错版本的左边界，找到时，令end=mid，未找到则令start=mid。最后返回的start就是第一个出错的版本号。 【参考答案】 www.jiuzhang.com/solutions/first-bad-version/

【题目描述】 Given preorder and inorder traversal of a tree, construct the binary tree. Notice:You may assume that duplicates do not exist in the tree. 根据前序遍历和中序遍历树构造二叉树. 注意：你可以假设树中不存在相同数值的节点 【题目链接】 www.lintcode.com/en/problem/construct-binary-tree-from-preorder-and-inorder-traversal/ 【题目解析】 相信学过数据结构的同学应该都对这道题目有深刻的印象，虽然它是二叉树的题目，但是其更多使用到的还是分治的思想。 对于给定的前序遍历preorder和中序遍历inorder，首先我们不难发现，这棵树的根结点其实就是preorder[0]。由于preorder和inorder是对同一棵树的遍历，我们可以知道preorder[0]在inorder中一定也存在，不妨设preorder[0]==inorder[k]。 由于inorder是中序遍历，所以k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。 并且，由于我们已经知道了根节点左子树的节点数（与中序遍历长度相同），不妨设为l，我们可以知道preorder从1到l+1就是根节点左子树的前序遍历，剩下的最后一部分就是根节点右子树的前序遍历。 也就是说，我们可以计算出左子树、右子树的前序遍历和中序遍历，从而可以用分治的思想，将规模较大的问题分解成为两个较小的问题，然后递归的进行处理，还原左子树和右子树，最后连通根节点一起组成一棵完整的树。 【参考答案】 www.jiuzhang.com/solutions/construct-binary-tree-from-preorder-and-inorder-traversal/

【题目描述】 Given inorder and postorder traversal of a tree, construct the binary tree. Notice:You may assume that duplicates do not exist in the tree. 根据中序遍历和后序遍历树构造二叉树 注意:你可以假设树中不存在相同数值的节点 【题目链接】 www.lintcode.com/en/problem/construct-binary-tree-from-inorder-and-postorder-traversal/ 【题目解析】 本题在属于二叉树遍历的经典题目，已知二叉树的两个遍历序列构造二叉树，有如下性质： 若已知先序和中序，则可以构造出唯一的二叉树 若已知先序和后序，则可以构造出多颗不同的二叉树 若已知中序和后序，则可以构造出唯一的二叉树 本题中我们已知的条件为中序遍历和后序遍历，所以我们一定可以构造出唯一的二叉树。 我们先将整棵树看作根节点和两颗子树，则其两种遍历得到的序列为 序列 可以肯定后序遍历序列中最后一个数一定是当前二叉树的根节点root。又因为二叉树不存在相同的数，我们可以找到root在中序遍历中位置p。 则我们可以分别找到两颗子树对应的中序和后序遍历： 左子树的中序= inOrder[1 .. p - 1] 左子树的后序= postOrder[1 .. p - 1] 右子树的中序= inOrder[p + 1 .. n] 右子树的后序= postOrder[p .. n - 1] 在此基础上我们就可以递归处理两颗子树。 当我们发现当前中序遍历和后序遍历长度都为1的时候，也就找到了叶子节点，此时我们开始回溯。 【参考答案】 www.jiuzhang.com/solutions/construct-binary-tree-from-inorder-and-postorder-traversal/

【题目描述】 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). 给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行） 【题目链接】 www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/ 【题目解析】 这道题目其实本质上还是一个按层遍历（或者说宽度优先搜索）的算法，我们不妨先不考虑“之”字形的限制，而是简单的按照一层一层、每层从左到右的顺序进行。 首先，我们可以简单的获取第一层：[root]，按照数学归纳法的思想，如果我们可以通过第K层求出第K＋1层的话，就意味着我们可以求出任意一层。 而这个过程也是简单的，如果第K层是[node1, node2, node3 ... nodek]的话，那么第K＋1层理想情况下就是[node1 -> left, node1 -> right, node2 -> left, node2 -> right, node3 -> left, node3 -> right ... nodek -> left, nodek -> right]。 但是实际上，由于有些节点不存在左右子节点，所以在对应位置上出现的是null，我们需要将这些null值去除掉，而在去除掉之后，我们就可以得到第K＋1按照从左到右顺序的排列结果。 至此，我们的问题已经基本解决，那么如何处理之字形呢？这个很简单，按照层数的奇偶将所有偶数层的顺序反转即可～ 【参考答案】 www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/

【题目描述】 Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). 给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历） 【题目链接】 www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/ 【题目解析】 这道题目是相对简单的，只需要计算出从上往下的按层遍历之后，将答案在层的维度上进行翻转即可。 对于答案的翻转，可以直接通过将第1个和最后1个交换，第2个和倒数第2个交换……来完成 【参考答案】 www.jiuzhang.com/solutions/binary-tree-level-order-traversal-ii/

【题目描述】 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). 给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问） 【题目链接】 www.lintcode.com/en/problem/binary-tree-level-order-traversal/ 【题目解析】 对于二叉树的问题，我们第一想到的就是DFS或者BFS, DFS更易于理解代码，如果处理数据量不是很大的话.对于这样的面试题，我建议用DFS来求解. 需要注意的点为: 对于一棵树，如果我们要求每一层的节点，并且存在一个二维数组里，首先我们要建一个二维数组，但是这个二维数组建多大的合适呢？我们就要求出这颗树的深度，根据深度来建立二维数组. 题目要求为从左往右添加,所以我们也就是要先放左边的节点，再放右边的节点. 对于这道题，我们首先就是要用DFS来求出这颗树的高度，之后再用DFS对于每一层遍历，这样节省了空间复杂度. 时间复杂度分析:由于两次DFS是并列的，并没有嵌套，所以我们的时间复杂度为O(n). 【参考答案】 www.jiuzhang.com/solutions/binary-tree-level-order-traversal/

【题目描述】 Given a binary tree, return the postorder traversal of its nodes' values. 给出一棵二叉树，返回其节点值的后序遍历。 【题目链接】 www.lintcode.com/en/problem/binary-tree-postorder-traversal/ 【题目解析】 二叉树后序遍历。刚接触leetcode时也做过这道题，用了很蠢笨的方法。现在学习discuss里大神们的版本，真的进步很多。下面这个版本是基于上道题目-二叉树先序遍历的。由于后序遍历是left -> right -> root，先序是root -> left -> right， 所以我们改变的只是如何插入结果到list里，以及被压入栈的先后顺序而已。在这里，pop出的结果要插入到list前部，而且要先把左子树压入栈，其次是右子树。 【参考答案】 www.jiuzhang.com/solutions/binary-tree-postorder-traversal/

【题目描述】 Given a binary tree, return the inorder traversal of its nodes' values. 给出一棵二叉树,返回其中序遍历 【题目链接】 www.lintcode.com/en/problem/binary-tree-inorder-traversal/ 【题目解析】 递归版 最好理解，递归调用时注意返回值和递归左右子树的顺序即可。 迭代版 使用辅助栈，空间复杂度O(n),时间复杂度O(n). 中序遍历没有前序遍历好写，其中之一就在于入栈出栈的顺序和限制规则。我们采用「左根右」的访问顺序可知主要有如下四步构成。 1.首先需要一直对左子树迭代并将非空节点入栈 2.节点指针为空后不再入栈 3.当前节点为空时进行出栈操作，并访问栈顶节点 4.将当前指针p用其右子节点替代 步骤2,3,4对应「左根右」的遍历结构，只是此时的步骤2取的左值为空。 【参考答案】 www.jiuzhang.com/solutions/binary-tree-inorder-traversal/

【题目描述】 Given a binary tree, return the preorder traversal of its nodes' values. 给出一棵二叉树，返回其节点值的前序遍历。 【题目链接】 www.lintcode.com/en/problem/binary-tree-preorder-traversal/ 【题目解析】 递归 递归版很好理解，首先判断当前节点(根节点)是否为null，是则返回空vector，否则先返回当前节点的值，然后对当前节点的左节点递归，最后对当前节点的右 节点递归。递归时对结果的处理方式不同可进一步细分为遍历和分治两种方法。 分治 使用分治的方法和递归类似，但是不同的是递归是将结果作为参数传入递归函数中，而分治则是先将结果保留，随后再合并到最终结果中。 迭代 迭代时需要利用栈来保存遍历到的节点，首先进行出栈抛出当前节点，保存当前节点的值，随后将右、左节点分别入栈，迭代到其为叶子节点(NULL)为止。 【参考答案】 www.jiuzhang.com/solutions/binary-tree-preorder-traversal/