Amazon Interview Experience | Set 199 (On-Campus for Internship) 题解

1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1.

二分搜索一下就可以, 注意一下返回-1的条件.

2.给一个二叉树, 找到最长的path. 如果最长不只一个, 返回字典序第一个最长.

这个需要点技巧, 我们自底向上,对树进行递归, 把path 放到一个stack里, 然后如果找到了一个更长的path(stack的size) 就更新一下. 因为最长的path不一定在root的同一侧, 所以最后我们还需要比较一下当前节点左右哪边有最长path.

3. 给一个二叉树, 求任意两个node的path长.

这个是个靠综合概念的题, 首先我们要知道这2个节点并不一定在root的同一侧. 所以我们需要找到两个节点的lca. 其次, 我们要知道root到两个节点分别的长度, 和root到lca的长度, 然后用d_node1 + d_node2 – 2*d_lca就是他们之间的长度.为什么呢? 试想一下, LCA的定义就是最短的两个节点的交点. 那么我们可以证明, 他们之间的path毕竟经过lca, 所以我们通过这个公式计算这两个节点之间的path的长度是可行的.

4. 给一个数组, 数字之间最大的差的绝对值是1, 让你找到一个数字n的第一次出现的坐标, 没有就返回-1

很简单, 我们可以证明, 在开始时, 数字n可能出现的地方, 就是n-nums[0], 如果没有, 就是n-nums[1]…..一直找就可以了.

5. 判断一个list是不是回文. Leetcode原题.