Amazon

Amazon OA2 coding

useful link

http://wdxtub.com/interview/14520850399861.html
http://www.jianshu.com/p/807fc0ec0bc3

  • Same tree
  • Find minimum path sum of a binary tree
  • loop in linked list 检查是否有环，以及环的起点在哪里（leetcode原题）
  • Greatest common divisor （最大公约数）
  • Reverse second half of linked list
  • Search a 2D matrix
  • Merge two sorted list
  • Rectangle Overlap
  • Sliding window maximum/minimum （练习）
  • Search a 2D matrix II （练习练习）
  • Gray code
  • Rotate string
  • Remove vowel
  • BST minimum path sum
  • longest palindrome
  • copy list with random list (leetcode 138原题)
  • order dependency (类似leetcode 210：course schedule II)
  • Two sum count (leetcode 1原题)

  • LRU cache count miss ?? （题意？）

  • Rotate Matrix （注意，以前老做错。。） 把一个m*n的矩阵旋转90度，给一个flag规定是向左转还是向右转。（如果不需要in-place就比较简单，注意用简单的例子来确定index 的转换。）

  • Insert value into a circle linked-list
    插入一个新的节点到一个sorted cycle linkedlist，返回新的节点。（给的list节点不一定是最小节点，所以先要找到最小的点）

  • Day change
    给定一个cells 数组，和天数days。每天的变化规则是：左右相等，当前位置为0， 不等为1；（默认 cells[0]左边 和 cells[cells.length - 1]右边的位置元素都是0）。求days天后的cells数组。

  • Find path in maze
    给定一个2D array,其中只有一格是9，其他格子是0或1，0表示此路不通，1表示可以走，判断从（0,0) 点开始上下左右移动能否找到这个是9的格子。

  • Check subtree 给定两棵树（的根节点）T1和T2，检查T2是否为T1的子树。（注意：找到==T2的T1子节点（T2'）后需要检查两棵树是否相等。）

  • Valid parentheses 给定一个str,里面只有 '('和')'，求valid pairs一共有多少。如果不是valid就返回-1；是的话返回valid pair个数，即str.sizr()/2。

  • arithmetic sequence （易错）
    Given an array, return the number of possible arithmetic sequence. 给一个数组，返回可能的长度不小于3的等差数列个数。—>注意是等差数列的个数。

  • Tree amplitude Given a tree of N nodes, return the amplitude of the tree. （就是从 root 到 leaf max - min 的差）

  • Find optimal weights
    有一个容器Container，double capacity， 一个array(double[] weights)， 和int numOfContainers。
    要求在array中选出两个weights总和和小于等于capacity但最接近capacity，然后指定到一个Container object并且return。 

public Container findOptimalWeights(double capacity, double[] weights, int numOfContainers)

class Container {
    public double first;
    public double second;
}

  • K closest points
    Find the K closest points to the origin in a 2D plane, given an array containing N points.

    public static class Point { 
  double x;
  double y; 
  public Point(double a, double b) {
      x = a;
      y = b;
  }
}

  • Window sum
    给定一个数列和一个window size K，返回一个数列依次记录长度为K的sub-array的和。

  • Four integers （思考一下）
    Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.

  • Five scores
    给定一个Result类，输入是一堆Result对象，里面有两个属性学生id和分数，保证每个学生至少会有5个分数，求每个人最高的5个分数的平均分。返回的是Map<Integer, Double>, key是id，value是每个人最高5个分数的平均分double是平均分。

  • maximum subtree of average （感觉不好做的题）
    给定一棵多叉树，表示公司内部的上下级关系。每个节点表示一个员工，节点包含的成员是他工作了几个月(int)，以及一个下属数组(ArrayList<Node>)。目标就是找到一棵子树，满足：这棵子树所有节点的工作月数的平均数是所有子树中最大的。最后返回这棵子树的根节点。（这题补充一点，返回的不能是叶子节点，一定要是一个有子节点的节点。）

  • maximum minimum path （没见过的题）
    给一个int[][]的matirx，对于一条从左上到右下的path pi，pi中的最小值是mi，求所有mi中的最大值。只能往下或右。 比如：

    [8, 4, 7]
[6, 5, 9]

    有3条path：

    8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5

results matching ""

    No results matching ""