Menu Sidebar
Menu

Amazon

Maximum Minimum Path in Matrix

给一个矩阵, 先找所有从左上到右下的path. 找出每个path的最小值. 找出这些最小值中的最大值. 这题看着挺乱的, 给个例子就清楚了.

这个返回5 所有的path: 8->4->3->5->8 min:3 8->4->3->9->8 min:3 8->4->5->9->8 min:5 8->6->5->9->8 min:5 Result = Math.max(3,3,5,5,) = 5 Code:

   

[Amazon] Add Binary Number By 1 without using + 正数加1不用加号

Bit操作的题, 给一个整数+1,不能用加号. 其实很简单,扫一下整数的每个bit(从低位到高位), 对它做&操作, 如果结果是0, 证明此位是0, 那么我们在这位+1, 如果是1, 那么我们清空此位.

   

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]…..一直找就可以了.

[…]

[Amazon] Abstract Class 与 Anonymous Class

这是我面Amazon Intern的其中一个问题,  当时是解释什么是Abstract class, 我啪啦啪啦的说了一堆, 其中就说, 我们一般不实例化抽象类, 因为其中有抽象方法, 抽象方法会让实例变得毫无意义, 我的原话是meaningless, 这里的毫无意义是因为实例就是拿去直接用的, 然而其中如果有抽象方法, 说明这个实例是不完整的. 当时印度小哥立刻就问完, 你说抽象类能实例化么? 我说能的. 然后Amazon就那么离我而去了. Talk is cheap. Show me the code

Car是一个抽象类, 我下面的main方法初始化了它. 是不是可以? 上面的code是无错的,而且跑的飞快. 上面的code有两个tricks: Car虽然是抽象类, 但是没有抽象方法, 所以它不是那么的”抽象”. 初始化Car的时候, 我用了Anonymous Class类初始化它, 并且Car又没有抽象的方法, 所以这个初始化是可以的. 其中匿名类初始化我们在做Comparator的时候经常使用, 只是里面的compare方法是抽象的,每次使用都需要定义一下, 而这里, Car中没有抽象方法, 所以就可以被当做匿名类初始化. Again: 以上的代码并不和”抽象类不能实例化”冲突.

书脊

倾城与倾国, 佳人难再得