博文

Snapchat 面经(电面+onsite)

在网上投了简历，一周后收到面试通知。面试是在 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...
发表评论
阅读全文

Lintcode75 Find Peak Element solution 题解

【题目描述】 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/
发表评论
阅读全文

Lintcode 74 First Bad Version solution 题解

【题目描述】 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/
发表评论
阅读全文

Lintcode73 Construct Binary Tree from Preorder and Inorder Traversal solution 题解

【题目描述】 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/
发表评论
阅读全文

Lintcode72 Construct Binary Tree from Inorder and Postorder Traversal solution 题解

图片
【题目描述】 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/
发表评论
阅读全文

Lintcode71 Binary Tree Zigzag Level Order Traversal solution 题解

【题目描述】 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/
发表评论
阅读全文

Lintcode70 Binary Tree Level Order Traversal II solution 题解

【题目描述】 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/
发表评论
阅读全文