/*
* 2. 输入是二维矩阵，输出二维矩阵，矩阵每个点是左上角所有数之和， 要求一次遍历
http://stackoverflow.com/questions/2277749/calculate-the-sum-of-elements-in-a-matrix-efficiently
*/
public class MatrixSum {
public static int[][] matrixSum(int[][] matrix){
if(matrix == null || matrix.length == 0){
return null;
}
int m = matrix.length, n = matrix[0].length;
int[][] res = new int[m][n];
int total = 0;
for(int i = 0; i < m; i++){
total += matrix[i][0];
res[i][0] = total;
}
total = 0;
for(int i = 0; i < n; i++){
total += matrix[0][i];
res[0][i] = total;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
res[i][j] = matrix[i][j] + res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1];
}
}
return res;
}
public static void print(int[][] matrix){
int m = matrix.length, n = matrix[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args){
int[][] matrix = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int[][] nums = matrixSum(matrix);
print(nums);
}
}
//update region sum
public static int matrixSum(int[][] matrix, int x, int y, int x1, int y1){
if(matrix == null || matrix.length == 0){
return 0;
}
int m = matrix.length, n = matrix[0].length;
int[][] res = new int[m][n];
int total = 0;
for(int i = 0; i < m; i++){
total += matrix[i][0];
res[i][0] = total;
}
total = 0;
for(int i = 0; i < n; i++){
total += matrix[0][i];
res[0][i] = total;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
res[i][j] = matrix[i][j] + res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1];
}
}
int num1 = (y - 1 < 0)? 0 : res[x1][y - 1];
int num2 = (x - 1 < 0)? 0 : res[x - 1][y1];
int num3 = (x - 1 < 0 || y -1 < 0)? 0 : res[x - 1][y - 1];
return res[x1][y1] - num1 - num2 + num3;
}
Amazon
two sum变种总结
import java.util.*;
public class TwoSum {
public boolean twoSum(int[] array, int target){
//check input
if(array == null || array.length < 2){
return false;
}
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i = 0; i < array.length; i++){
if(hashset.contains(target - array[i])){
return true;
}else{
hashset.add(array[i]);
}
}//end - for
return false;
}
/*
* follow up - leetcode, return index
* assume one solution
*/
public int[] twoSum2(int[] numbers, int target) {
int[] res = new int[2];
if(numbers == null || numbers.length < 2){
throw new IllegalArgumentException("invalid");
}
HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
for(int i = 0; i < numbers.length; i++){
int diff = target - numbers[i];
if(hashmap.containsKey(diff)){
res[0] = hashmap.get(diff) + 1;
res[1] = i + 1;
return res;
}
hashmap.put(numbers[i], i);
}
return null;
}
/*
* follow up: do not allow duplicates
* [7, 2, 2, 2, 9, 10, 2, 2, 11, 9, 1] target 9, just one solution
*/
public List<List<Integer>> twoSum3(int[] numbers, int target){
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(numbers == null || numbers.length < 2){
return res;
}
HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
HashSet<Integer> hashset = new HashSet<Integer>();
for(int i = 0; i < numbers.length; i++){
if(hashset.contains(numbers[i])) continue;
int diff = target - numbers[i];
if(hashmap.containsKey(diff)){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(hashmap.get(diff) + 1);
list.add(i + 1);
res.add(list);
hashset.add(diff);
hashset.add(numbers[i]);
}
hashmap.put(numbers[i], i);
}
return res;
}
/*
* follow up, do not allow to use hashmap
* do not allow duplicates
* return value not index
*/
public List<List<Integer>> twoSum4(int[] numbers, int target){
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(numbers == null || numbers.length < 2){
return res;
}
Arrays.sort(numbers);
int start = 0, end = numbers.length - 1;
while(start < end){
int sum = numbers[start] + numbers[end];
if(sum == target){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(numbers[start]);
list.add(numbers[end]);
res.add(list);
//update pointer
start++;
end--;
//avoid duplicates
while(start < end && numbers[start] == numbers[start - 1]){
start++;
}
while(start < end && numbers[end] == numbers[end + 1]){
end--;
}
}else if(sum < target){
start++;
}else{
end--;
}
}
return res;
}
/*
* follow up : need duplicates
*/
public List<List<Integer>> twoSum5(int[] numbers, int target){
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(numbers == null || numbers.length < 2){
return res;
}
Arrays.sort(numbers);
ArrayList<Integer> path = new ArrayList<Integer>();
dfs(res, path, numbers, target, 0);
return res;
}
private void dfs(List<List<Integer>> res, ArrayList<Integer> path, int[] numbers, int target, int pos){
if(path.size() == 2){
if(target == 0){
res.add(new ArrayList<Integer>(path)); //bug here
}
return;
}
for(int i = pos; i < numbers.length; i++){
path.add(numbers[i]);
dfs(res, path, numbers, target - numbers[i], i + 1);
path.remove(path.size() - 1);
}
}
public static void main(String[] args){
int[] nums = {1, 1, 1, 3, 3, 3};
TwoSum ins = new TwoSum();
System.out.println(ins.twoSum5(nums, 4));
}
}
Amazon Intern 面经
1,
ArrayList， Linklist的区别
HashMap 实现和复杂度
Coding :
Deletion in a linked list
First Bad Version
2,
设计动物园(animal kingdom)
public abstract class Animal();
public lass dog extends Animal();
overriden..
interface vs abstract
1,A class must be declared abstract when it has one or more abstract methods
2,The sole purpose of a abstract class is to be subclassed
3, An abstract class is good “is a relationship”
Diff:
A class can inherit from only one class, but can implements as many as interfaces
A java interface can only have method prototype and constants
When to use Abstract class and interface:
If you have a lot of methods and want default implementation for some of them, then go with abstract class
If you want to implement multiple inheritance then you have to use interface.
If your base contract keeps on changing, then you should use abstract class, as if you keep changing your base contract and use interface, then you have to change all the classes which implements that interface.
linux grep + regular expression
find highest order digit of a byte: byte >>> 7?
coding:
second largest elements, 问duplicate, 注意Corner case(array 长度小于2)
follow up: 3rd, kth, Sorting O(nlogn), minHeap O(nlogk), selection O(n),
3,
Why Amazon？
OO
Coding:
Nth to last element in LinkedList – two pointer
4,
Favorite Project
Hash Table: resizing + rehash
Coding:
Validate BST
method1 : inorder traversal ==> sorted array (assume no duplicates)
method2 : max min method
5,
coding:
leetcode : word ladder 2
big integer: implement plus operation
和 add binary不一样，binary 由于用two complement 直接相加就行，大树的考虑正负号！
6,
linkedlist 和array各自的优点，这个应该是老生常谈，大家都懂得
hash map的insert 和get average O(1) under uniform hashing assumption Each key is equally likely to hash to an integer between 0 and M – 1.
coding:
reverse一个string : String(char[] value, int offset, int count)
linked list loop : two pointers
有个数组长度是n，里面的元素是from 1 to n + 1， 貌似是一个元素少了，找出missing元素
sort + linear scan o(nlogn)
等差数列求和， sum of arithmetic sequence
扫描一次求和求sum, 用等差数列的差减去他
Follow up : O(N) 用hashmap/或者array/bucket-sort
Follow up : 少了两个数
Equation 1 a + b = x;
Equation 2 a^2 + b^2 = y;
不能用 a * b 因为overflow 和 integer division的问题
7,
leetcode : delete nth to last node in linked list
cc150: integer to english words TO DO
8,
1. 介绍项目
2. longest substring repeating characters
3. Abstract with interface
4. Polymorphism
http://simpledeveloper.com/java-interview-questions/
Encapsulation (data hiding) is a technique used for hiding the properties and behavior of an object and allowing outside access only as appropriate. This prevents other objects from directly altering or accessing the properties or methods of the encapsulated object.
example : private field and getter and setter method
Abstraction is process of hiding the implementation details and showing only the functionality. It is worth mentioning the idea that Abstraction talks about what it does, it never talks about how it does something.
Use abstraction if you know something needs to be in class but implementation of that varies.
example: List Interface add method
Polymorphism is the ability to create a variable, a function, or an object that has more than one form.
In a given class you can have methods. When you have two methods with the same name, but different parameters in the same class, you have polymorphism. Sometimes this kind of polymorphism is called overloading.
Math.abs() method
Another way of having polymorphism is when you have a method in a class and you reimplement it differently in a subclass. So, for the very same name and parameter list you have two different behaviors in two different (but related) classes.
Dog class, Babydog class eat method
Different kinds of objects often have a certain amount in common with each other. Yet each also defines additional features that make them different.
Object-oriented programming allows classes to inherit commonly used state and behavior from other classes.
Dog animal
9,
Map和List的区别，问除了考虑空间外 什么时候要优先使用List而不是Map
maintain the order, random access, not key,value pair
coding:
divide integer
10,
hashtable implementation
hashtable chaining / linear probing
coding:
shuffle cards
11,
0. Most challenging project
1. Process 和 thread的区别
A process is an executing instance of an application.
A thread is a path of execution within a process
http://www.programmerinterview.com/index.php/operating-systems/thread-vs-process/
2. Lock, dead lock. What will happen if there are too many locks in a program.
Deadlock, of course, is the evil situation in which Thread 1 holds lock A and is waiting for lock B while Thread 2 holds lock B and is waiting for lock A. Thus, neither can continue
When threads in a process share and update the same data, their activities must be synchronized to avoid errors. In Java, this is done with the synchronized keyword, or with wait and notify. Synchronization is achieved by the use of locks, each of which is associated with an object by the JVM
Too many locks应该容易造成死锁，如果前提是不产生死锁，那么就会造成效率变低
3. Design pattern（singleton, factory)
4. Object and class 区别
5. Polymorphism
6. Encapsulation
三道coding题：
1. find the number that occurs odd number of times
2. delete a node in a circular singly linked list
3. find nth fibonacci number
12,
coding
fibnacci BigInteger
zigzag level order traversal
13,
coding:
given an array, find the 2 largest number.
top k numbers
Priority queue
how to implement?
insert get time complexity?
O(k) space? — queue of length k — how to add elements?
hash table
time complexity how to store it in memory
14,
1. HashMap里面很多元素出现同样的Hash code怎么办, 然后我解释了linear chaining. linear probing, quadratic probing.
2. 如果往HashSet里面添加重复的元素会发生什么. 我说不会增加元素数量, HashSet里面元素都是独一无二的.
3. 写代码, third largest. 我按照Second largest的方法写的. 设定三个变量, first, second, thrid. 写的时候刚开始初始化成MIN_VALUE, 然后脑子抽又改成了MAX_VALUE, 然后看了一会儿有觉得不对, 改了回去. 写完以后让我自己写个input看看, 然后我写了一个, 感觉没啥问题. 接着他又问我出现重复元素怎么样, 然后他自己写了个{1, 2, 2, 3} 我试了一下, 我说没问题, 第三大还是2. 然后我又说当元素数小于3的时候需要返回exception. 这里我忽略了问他是返回1 还是2. 感觉要是跪的话这里是一个地方.
4. Leetcode原题Triangle. 不过这里是返回最大数. 由于已经做过了, 开始装逼, 说像是个最短路径问题, 另外建立一个三角形, 从上往下, 然后把所有元素都过一遍. 让我开始写代码. 然后我说还能inplace. 写了几行, 接着又说这样找到最下面还得找最大, 从下往上好像好点. 然后开始抄我在leetcode上的解答. 抄完他说Awesome, 时间已经6.40分.
15,
1. Why do you choose Amazon?
2. 问vector 和 map 区别, 他们一些操作的time complexity.
3. Implement a map and its functions insert(), find()
4. Find the middle of a singly linked list
16，
1. 问平时用什么数据结构，我按当年数据结构课讲义扯了几个。然后问vector和linked list有什么区别。
2. 编程题，给一个整数数组，返回最大值。然后又让改成返回第二大、第三大的值。我直接用heap写了个topK然后调用了一下，他说不用这么麻烦，就让我用数组操作写，那只好老老实实的写喽。
3. 设计题，问interface是什么意思，然后设计一个Deck类。
17，
1. Leetcode 原题，swap nodes in a linked list in pairs
2. Given Tree and Node n and int k, print all node which are at physical distance <=k from n.
18，
第一题是跟duplicates有关的，给你一个很大很大的文件，文件每行是一个integer,如何最快地找出文件中有没 duplicate
sort a.txt | uniq -c 或者 sort a.txt | uniq -d C代表count， d代表duplicate
这道题还跟duplicates有关，写一个method， parameters是一个array还有它的长度，返回有没有duplicates
0 < arr[i] <= length for all 0 <= i < length O(1) space
然后问了一道sudoku的题，就是给了一个已经填满的9*9的sudoku,让我判断这个sudoku是否valid。
follow up, 一个合法的sudoku的边长有什么特点？（n必须是某个整数的平方）
follow up, 把程序改成适合任意合法长度的sudoku。（也就是说不一定要填1-9，也可以是比如1-16,1-64什么的，随长度定）.
follow up, 把程序改成也可以判断有cell没填的sudoku是否valid。（只要已填的部分未重复就好）
19,
count string 中的words，edge cases
Binary Tree Level Order Traversal
Binary Tree序列化
DFS VS BFS
What is the difference between depth first search and breadth first search?
Both algorithms are graph traversal algorithms, and both will
eventually reach every node in the graph. They differ in the order in
which they visit nodes: depth first search explores all of the nodes
reachable from X before moving on to any of X's siblings, whereas
breadth first search explores siblings before children. In the case
of a tree, depth first tree will explore one path all the way to the
leaves, before backing up and trying another path, whereas breadth
first will explore all nodes at depth 0, then depth 1, then depth 2,
and so on, until the leaves of the tree are reached.
20,
给一棵二叉树，定义每个节点的sum为以这个节点为根的所有节点上的数字和。找到一个节点，它的sum离root的sum的一半最近。
count and say
21.
设计题，问interface是什么意思，然后设计一个Deck类
http://math.hws.edu/javanotes/c5/s4.html
给一个int array 打印bar height.
follow up： get highest water level
https://oj.leetcode.com/problems/trapping-rain-water/
flood fill
22,
第一个问题是在linux里面一大堆文件，要找文件里的东西－》我说用find命令找文件，cat打开文件，然后用regex匹配
数组intersection
two sum
23,
1. Given the root node of a binary tree of integers, determine if it’s a binary search tree.
2, Fib
overflow : 1, 用big integer 2, 判断下，会溢出就throw new RuntimeException()
24
一开始寒暄问了challenging project, 大概10分钟，然后问链表反转，写完大概15分钟。
问个数组里找duplicate,地里有这题，给定[0,n-1]范围的数放到size = n的数组里，看有没有重复，我一开始用的hashset，后来想优化减少memory到O(1),
我知道怎么做，刚想说方法，但小哥说不用我减少空间了…然后move on…
写TreeNode 的class，问BST是啥，然后validate a BST, 写完了之后问了下DFS的缺点，比如worst time cost. 如果树里有环，DFS会不会结束。
然后小哥又说回到上题，问我Hashset的一些知识，我说底层hashmap实现，然后hashcode什么的，小哥问你知道不知道hashcode的公式，我说我不记得了…╮(╯▽╰)╭
感觉小哥没啥问的了，就问问stack 和queue的区别，然后再说到priority queue, 问了下复杂度之类的。。基本时间就快到40分钟了，最后问了几个问题，42分钟结束电面。。.
25,
pow(x, n) 1,recursive 2, iterative
pascal triangle
26,
先随便介绍一个project，然后问你学过哪些数据结构？说说set和map的区别？arrayList 和LinkedList的区别？说说树的前中后序遍历？DFS BFS有什么区别？然后问了leet code上一个原题，树 sum from root to leaf equals to a specific value; 最后问了OO的题，Create a class for filesystem.当时就狂汗，基本没准备OO的题，后来他提示，感觉是要说filesystem里面有文件和folder， folder还有subfolder 要有个结构指向sub folder一类的。 还没结果，估计要跪。
27,
问了sort，让说了quick sort和merge sort怎么工作的。。
然后问了interface和abstract的区别。。其实我就不懂。。但是凭印象说了一下之前地里面筋里提到的。结果三哥继续问细节。。悲剧了。。
然后又问priority queue。没说清，但是举了个例子，大体应该是算我对了吧。然后我说priority queue可以用heap实现。然后三哥就让我说heap。然后又继续问remove root的big O，以及为啥是这个big O。。。
最后问了一个polymorphism。。。
28，
第一题：单向链表翻转，很简单，写完小哥说行，下一个。. 1point3acres.com/bbs
第二题：1-1000个数放到一个size为1000的array，怎么判断有没有duplication。我说了三个方法。然后开始follow up，说不用hashmap 就用array，我开始理解错了，以为让我implement 一个hashmap，我就开始写代码了，小哥说不是。让我只用Array做这个题，我才理解是让我用array代替hashmap，我说原来这样啊，那就直接对应就可以了哦，他说是的。然后又开始follow up，说如果是1-10billon 怎么办，内存不够。我卡了一分钟，再想有没有什么优化，然后小哥说你要用什么array，我突然明白他了，就说用bitset来做。他说对，然后又问用bitset需要多少空间。傻逼了，算错了应该是40/32. 楼主算成4/32, 被印度哥鄙视了，他说10个billlon int 是40个G，我连说对对对，我是傻逼。
然后小哥就让我提问，提问完小哥看表说还有15分钟，就说我们再来一发，说这个是bonus，没关系。是leetcode原题，flat binary tree。他说不用写，说就行，但是我说了他又听不懂，又让我写。我写完他说好好。继续让我提问。聊了一会儿时间到了。
29，
就一道题: Find First Unique Object in a list of objects. Objects can be any type.
一个hashset用来记录是否重复，一个linkedhashset，记录unique元素（linkedhashset是按照插入顺序），如果hashset中检测到重复，就从linkedhashset中去掉，最后返回linkedhashset的头就可以
30,
1.在singly linkedlist输出倒数第k个node；
2.给一个int数字输出English word，eg. 4500，输出four thousand five hundred，最多六位数。
昨天整理了一天的面经一题都没用到，回馈一下给地里，就是格式没有调整看起来不太舒服，大家将就吧。
31,
感觉运气超级好啊。。。面试官是美国人，叫alex，是kindle的sale组，人很nice。上来寒暄几句，然后介绍他是哪个team的，这个team是干啥的。之后自我介绍，我说了一个project，他专门问我有没有遇到过什么沟通困难之类的。。聊了感觉快20分钟的样子。
之后他说我们来coding吧，题目是find third node from the end of linked list。
写完之后他给了一个读文件的api，让找出两个文件里相同的line（line是他给的一个data structure）。写完之后他说不错。
然后开始问他问题之类的，48分钟结束。
32,
然后是Coding, 第一题是close parentheses, 只有这种:(). 开始我以为他问的是回文, 说了一会儿, 然后他打了几个括号. 我赶快说forgot what I said. 然后开始说争取的思路. 说完开始写代码, 我问他如果是空字符串返回啥, 他说你觉得应该是啥. 我说exception, 然后我写了个nullpointerexception. 他说用illegalelementexception更好. 写完他直接指出了一个bug, 少了一个括号……然后说还有一个, 写了个(())()的case让我找错, 看了半天没看出来, 然后他直接告诉我 for (int i = 0; i < input.length()-1; i++) 这一行不该有-1啊…..
说完又问我如何简化, 我也看不出来. 然后他说可以在最后直接return stack.isEmpty(); 接着又问我还能怎么简化, 在提示下写出了开始的时候判断输入字符数. 字符数应该是even number.-google 1point3acres
第二题是leetcode原题 valid parentheses, 也就是说现在有三种括号了. 这时候我终于想起了parentheses怎么拼写, 打开leetcode开始在上一题代码的基础上抄. 写完以后问在他的提示下稍作简化. 然后他想写个case让我改bug, 还没写完发现没有bug. 然后就是问问题环节了.
于是我就大概了解了一下面试官的情况. . from: 1point3acres.com/bbs
Dave同志在给客户发marketing邮件的组, 用mapreduce挖掘数据. 听到mapreduce我说好神奇啊, 最近我刚刚学到巴拉巴拉. 然后他说HR会通知你下一步该干啥(可能我听错了), 然后我说我cost Amazon a lot. 然后就完事了.
33,
第一题，给一个lists，lists里面有n个list，list里面是一些String，找出这样的String：在n个list里面都存在。
找出来以后，把结果排序输出。。。
这题比较tricky，很多难以想象的条件。。。。
比如, 如果用map，你需要克服这种情况
a,a
a,
a
这种要忽略掉第一行两个a，最后只输出一个a
但是这种情况你也要考虑到.
a,a,a
a,a,a
a,a,a
这种是要输出3个a的.
Remark: 不考虑duplicate 用rolling hashset, 考虑用rolling hashmap
时间复杂度O(nk), 空间复杂度O(n)
最恶心的是还要排序。。。我用的radix sort。。三哥整我，，结束后没有休息下一轮直接开始。。
下一轮相对容易一点。
给一个Binary Tree，找出所有和为k的从root 到 leaf的路径
然后follow up，如果路径可以任何地方结束
再follow up，如果路径可以任何地方开始任何地方结束。
DFS
shawnlincoding 