Week1
时间
9.3 - 9.9
cover letter
[Add content here...]
第一个项目
[Add content here...]
第二个项目
[Add content here...]
算法
以下算法题来自AMAZON-OA2
Binary Search
1. Search 2D matrix
+ leetcode: 74
+ Linglu Wang
要求在m x n的matrix里面找到一个给定的值，能找到返回TRUE， 不能返回FALSE
Matrix的特性：
每行从左到右升序
每行第一个数值大于上一行最后一个数值
思路：Binary Search
分析：
根据题目要求 2）MATRIX的第一列是从上而下的升序，可以对第一列做binary search，找到target所在的行数
根据题目要求1）Matrix每一行是从左到右的升序，可以对target所在的行再做一个binary search 找到target
2. Search 2D matrix II
+ leetcode 240
+ XinxinWang
+ 矩阵类问题注意点
+ 第一次做没想到最优解，需要看答案
+ 数值在矩阵中的规律
+ 矩阵四个方向，八个方向
+ 矩阵区别于二维数组 java中
3. Gray Code
（Yifan Tian)
LINEAR STRUCTURE
1. Valid Parentheses (No 423)
leetcode20---XinxinWang
2. Merge Two Sorted Lists
+ (http://lintcode.com/en/problem/merge-two-sorted-lists/)
+ leetcode21
+ xinxinWang
3. (Two Pointer) Find Optimal Weight ：与Two Sum - Closest to target类似
+ 自己搞测试用例
+ XinxinWang
题目
有一个容器double capacity, 還有一個array(double[] weights), 和int numOfContainers。
要求在array中选出两个weights總总和小于等于capacity但最接近capacity 然後指定到一個Container object並且return。
first和second的顺序不做要求，numOfContainer在java里好像没用,因为double[]本身就自带length信息。
public Container findOptimalWeights(double capacity, double[] weights, int numOfContainers)
class Container {
public double first;
public double second;
}
4. LinkedList
a. Reverse Second Half of Linked List (用快慢指针找到中点，再用reverse linked list的步骤
相关题目
b. Reverse Linked List 2 --- leetcode 92 --- Xinxin Wang
c. Reverse Linked List --- leetcode 206 --- Xinxin Wang
d Palindrome Linked List --- leetcode 234 ---Xinxin Wang
Other
1. 这道题与Leetcode 223题RectangleArea十分相似。
（Yifan Tian)
//题目
//给定两个长方形左下角和右上角的坐标，判断是否有重叠，返回true或者false。
2. GCD Greatest Common Divisor 最大公约数
(xinxin he)
题目
找一个数组中所有数的最大公约数。
欧几里得算法
又称为辗转相除法，用于计算两个整数a和b的最大公约数。
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
3. Given an array, return the number of possible arithmetic sequence.
(Linglu Wang)
给一个数组，返回可能的等差数列个数
4. Day change(cell growth)
(Linglu Wang)
题目
int[] dayChange(int[] cells, int days),，cells数组，一共8个元素。
一个cell，如果左右两边的数一样，则将这个数设置为0，否则设置为1，题中用inactive和active来描述，后来给出的coding中用0和1表示。因为第一个数和最后一个数都只有一个相邻的数，因此设置为0。给出天数days，求days之后的结果。
例子：
cells: [1 0 0 0 0 1 0 0]
days: 1
output: [0 1 0 0 1 0 1 0]
5. Round Robin
题目
一个处理器要处理一堆request，一次只能处理一条，每次执行一个任务最多执行时间q，接着执行等待着的下一个任务。若前一个任务没执行完则放到队尾，等待下一次执行。
假设只要有任务开始以后cpu是不会空闲的，也就是说cpu开始后如果空闲了就说明没有任务了，另外Robin Round最后返回值是float。
OA 示例：
例子： 【0，1，4】 【5，2，3】 q=3. 输出的是average wait time 2.3333333
第0秒，任务1进队列。我们peek目前队列中有的任务是任务1，我们发现任务1开始时间第0秒，目前也是第0秒，所以任务1等待时间是0。然后任务1执行3秒，它自身还有2秒钟。
这时候我们查看3秒的时候哪些任务达到了，发现任务2在第1秒到达。于是任务2进队列。
这时候我们查看任务1有没有执行完，发现没有执行完，于是我们poll任务1，再把任务1 add到队列末尾。
这时候队列的顺序是任务2，任务1.
现在我们再次peek队列，于是找到任务2.我们发现任务2在第1秒到达了，目前我们在第3秒。所以等待时间是3-1=2.
我们重复刚刚的步骤，发现任务2执行时间只要2秒，于是我们到第5秒。这时候我们查找第5秒哪些任务到达了。我们发现任务3也到达了。于是任务3进队列。
所以目前队列顺序是任务2，任务1，任务3.
我们又发现任务2已经执行完了，于是我们把任务2 poll出队列，不再把它放进队列里了。
所以现在队列里面剩余的任务是任务1，任务3.
于是我们再peek队列。请注意，这时候的q被重新设置过了，不是3－2=1秒，而是又是3秒。
我们再次peek队列，找到任务1，目前是在第5秒，我们刚刚执行过任务1，他暂停在第3秒，所以任务1又等了2秒。目前秒数是2+2=4秒。
目前任务1还有2秒。我们执行完任务1以后，到达第5+2 ＝ 7把他扔出队列。目前队列里只有任务3了。
然后我们再peek，现在只有任务3了，目前我们在第7秒。任务3进来的时候在第4秒。所以任务3等了7-4 ＝ 3秒。所以等待时间又加3秒。
所以最终等待时间是2+2+3 ＝ 7秒。平均等待时间是7/3 ＝ 2.3333秒。
6. Four Integer
题目
Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.
String
1. Rotate String (No.8)
2. Remove vowel (给定一个字符串，需要将其中的vowel字符给去掉)
DFS
1. Maximum Minimum Path
(xinxin he)
给一个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
//dp 方法
int helper(int[][] matrix){
int[] result = new int[matrix[0].length];
result[0] = matrix[0][0];
for(int i=1; i<matrix[0].length; i++){
result[i] = Math.min(result[i-1], matrix[0][i]);
}
for(int i=1; i<matrix.length; i++){
result[0] = Math.min(matrix[i][0], result[0]);
for(int j=1; j<matrix[0].length; j++){
result[j] = (result[j]<matrix[i][j] && result[j-1]<matrix[i][j])?Math.max(result[j-1], result[j]):matrix[i][j];
}
}
return result[result.length-1];
}
dfs
public class MaximumMinimumPath {
private int min, max, row, col;
public int maxMinPath(int[][] matrix) {
row = matrix.length;
col = matrix[0].length;
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
dfsHelper(matrix, min, 0, 0);
return max;
}
public void dfsHelper(int[][] matrix, int min, int i, int j ){
if (i >= row || j >= col) return;
if (i == row - 1 && j == col - 1) {
min = Math.min(min, matrix[i][j]);
max = Math.max(max, min);
return;
}
min = Math.min(min, matrix[i][j]);
dfsHelper(matrix, min, i, j + 1);
dfsHelper(matrix, min, i + 1, j);
}
}
系统设计
[Add content here...]
