## Saturday, February 20, 2016

Utopian Tree: Utopian树一年有两个cycle可以长高： 季风季和夏季。 季风季高度double，夏季高度+1。初始高度是1，从季风季开始算，
input是cycle总数目的int array, output是高度的int array
2. Count Duplicates: input是int array nums, output是 nums里有多少数是重复出现过的
System io都是写好的，只写方法本身就好

int to roman 把int转换成罗马数字，lc原题

https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
1. Valid Parentheses。一个vector包含很多个字符串，判断每一串括号是否是valid parentheses. 输出一个vector
```  public static List<Boolean> validParentheses(List<String> l) {
List<Boolean> ret = new ArrayList<>();
for (String s : l) {
boolean b = true;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
stack.pop();
} else {
b = false;
break;
}
}
}
b = b && stack.isEmpty();
}
return ret;
}```
2. Reduce Fractions。就是找最大公约数，然后分子分母同除。给的string, 要注意一下string和int间的转换
```  static long gcd(long a, long b) {
if (a == 0 || b == 0)
return a + b;
return gcd(b, a % b);
}
static List<String> reduceFractions(String s1, String s2) {
List<String> ret = new ArrayList<>();
long l1 = Long.parseLong(s1);
long l2 = Long.parseLong(s2);
return ret;
}```

```  static char FindFirstDuplicate(String a) {
Map<Character, Integer> m = new HashMap<>();
for (int i = 0; i < a.length(); i++) {
if (!m.containsKey(a.charAt(i))) {
m.put(a.charAt(i), i);
} else {
m.put(a.charAt(i), -1); //\\ or count it, key -> count
}
}
for (int i = 0; i < a.length(); i++) {
if (m.get(a.charAt(i)) == -1) {
return a.charAt(i);
}
}
return 0;
}```
1. 对于某个数N， 算出其是否能够被写成 N ＝ p^q 的形式。 求出所有质因数，统计各个质因数的个数，再求出他们的最大公约数，。如果最大公约数是1就返回false，这里有加入负数的考虑情况。
```  static int gcd(int a, int b) {
if (a == 0 || b == 0)
return a + b;
return gcd(b, a % b);
}
static boolean pq(int a) {
if (a == 0 || a == 1)
return true;
Map<Integer, Integer> m = new HashMap<>();
for (int i = 2; i <= a; i++) {
if (a % i == 0) {
int count = 0;
while (a % i == 0) {
count++;
a /= i;
}
m.put(i, count);
}
}
List<Integer> l = m.values().stream().collect(Collectors.toList());
int g = l.get(0);
for (Integer i : l) {
g = gcd(g, i);
}
return g != 1;
}
public static void main(String[] args) {
System.out.println(pq(144));
}```
2. Game of Thrones.

1. Brace 。 （， {, , }, ）, 判断给出的字符串内的括号是否都是正确地对应

“}“是错的
```  static boolean brace(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
stack.push('(');
break;
case '[':
stack.push('[');
break;
case '{':
stack.push('{');
break;
case ')':
if (!stack.isEmpty() && stack.peek() == '(')
stack.pop();
else
return false;
break;
case ']':
if (!stack.isEmpty() && stack.peek() == '[')
stack.pop();
else
return false;
break;
case '}':
if (!stack.isEmpty() && stack.peek() == '{')
stack.pop();
else
return false;
break;
}
}
return true;
}
public static void main(String[] args) {
for (String s : new String[] {"{}[]()", "[{]}"}) {
System.out.println(brace(s));
}
}```
2. 简化小数 Reduce Fraction

```  static int gcd(int a, int b) {
if (a == 0 || b == 0)
return a + b;
return gcd(b, a % b);
}
static int[] ReduceFraction(int[] a) {
int g = gcd(a[0], a[1]);
return new int[] {a[0] / g, a[1] / g};
}```

1. 不用recursion遍历Binary Tree 设计 twitter ， 都还好。
2. 给really large streaming data, 用O(n)时间找出第k大的数。国人大哥几经提醒终于做出来了。
quick select

stream实现O(N)是：
1. 读2k个数到buffer
2. quick select找到第k大的数，和比他大的数。现在buffer里面一共k个数。 耗时O(k)
3. 重复1， 直到读完。一共O(n/k)次。

i see，是k的。lgk次，但是每次range变小了，总和是k

0 xxxxxx
1 xxxxxxx
5 xxxxxx
20 xxxxxx
35 xxxxxx

0 abcde
1 abc
2 abcd

Inout:

```  static boolean ab(String a, String b) {
Map<Integer, Long> ma = a.chars().boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
Map<Integer, Long> mb = b.chars().boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
for (Integer i : mb.keySet()) {
if (ma.containsKey(i) && ma.get(i) >= mb.get(i)) {
// nop
} else {
return false;
}
}
return true;
}```

s1 = “abcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”
s2 = “bc”

2. Super power 判断 z能否形成p的q次方。z, p, q都是正数。如果可行为1 不可行为0

4 -> (4 - 4) % 3 = 0
8 -> (8 - 4) % 3 = 1
64 -> (64 - 4) % 3 = 0
```  static boolean is(int start, int end, int delta, int x) {
if (x >= start && x < end && (x - start) % delta == 0)
return true;
return false;
}
public static int count(int start, int end, int delta, int start2, int end2, int c) {
int ret = 0;
for (int i = start2; i < end2; i *= c) {
if (is(start, end, delta, i)) {
ret++;
}
}
return ret;
}
public static void main(String[] args) {
System.out.println(count(4, 65, 3, 2, 65, 2));
}```

```  static int is(int a, int b, int c) {
int l[] = new int[] {a, b, c};
Arrays.sort(l);
if (l[0] + l[1] <= l[2])
return 0; // invalid
else if (a == b && b == c)
return 1; // type 1
else if (a == b || b == c || c == a)
return 2; // type 2
else
return 3; // type other
}```

q2 example input 1011(11) output 0100(4)

Given a 2D matrix a two cells inside the matrix, find the length of the shortest path between the two points. The matrix have two types of cells: 0 and 1.
You can pass through 0 cells, but not 1 cells. Also, you can only go up, down, left, right, but not outside the matrix or diagonally.

Exxample 1:
matrix:
0, 0
0, 0
start: (0, 0), end (1, 1), then return 2
start: (0, 0), end (0, 1), then return 1

Example 2:
matrix:
0, 1, 0
0, 1, 0
0, 0, 0
start (0, 0), end (0, 2), then return 6
1. Text Justification
2. Shortest Path Between Two Nodes
3. Iterator
4. Nested Iterator
5. Behavior
1) 三哥，SWE，一个巨大的graph，用多个machine存，每个machine存了一部分edge，找出所有的联通分量。三哥说想考MapReduce
LZ当时第一轮是自己想的一个方法用的DHT，感觉做的不好，效率不高。烙印也不给提示，总是摇着头说Yes。最后结束时问他，他说想要考MR。
2) 国人小哥，senior，聊了简历。两个容积分别为v1, v2升的瓶子，能不能倒来倒去得到p升的水。用BFS
3) 白人小哥，senior，system design：1TB的data，经常被访问，read-heavy，1000 server；聊了简历。我用的3-tier4) 白人小哥，senior，聊了简历，leetcode https://leetcode.com...
138. Copy List with Random Pointer

1) 经典题 design parking lot
2) http://www.programcr...  LeetCode – Set Matrix Zeroes
3) 4个数，算24点，可以用+,-,*,/,^4) 雷同检测器，检测2个document是不是相似5) 问了一堆比较简单的小问题

input：1 3 2 3 4 1
output：000101
110000

```  public static String[] isRepeatNumber(int[] n) {
String[] ret = new String[2];
Set<Integer> s = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n.length; i++) {
if (s.contains(n[i])) {
sb.append(1);
} else {
sb.append(0);
}
}
ret[0] = sb.toString();
s.clear();
sb.setLength(0);
for (int i = n.length - 1; i >= 0; i--) {
if (s.contains(n[i])) {
sb.insert(0, 1);
} else {
sb.insert(0, 0);
}
}
ret[1] = sb.toString();
return ret;
}```
1. 面试官是engineering effectiveness组的，一开始问了基本的网络常识，比如描述DNS的resolution的过程。之后问如何用shell command来统计一个文本文件里出现的单词集合（其实就是用pipe来组合各种command，类似 http://www.devshed.com/c/a/brain ... -do-with-pipelines/）。

3. 面试官也是plaform engineering的，题目是：给两个大小分别为m和n的杯子，以及一个目标容量k，判断是否能够装出目标容量的水，就用BFS就可以了（也有数学的解法，但是面试官说不用数学的解法做），followup是求怎么装（这也就是为什么面试官不要用数学方法做的原因）。之后又讨论了下DFS和BFS的优劣。4. 面试官是engineering effectivieness组的，第一题是leetcode 53：Maximum Subarray。followup是把输入从一维数组改成二维矩阵，差不多的思路
5. 最后一轮是behavior，基本上就是随便聊聊。

1. https://www.hackerra... 很多人都做过 很简单 看明白公式就没有任何难度 test case也很少 不知道提交以后有没有多余test
2. 地里常出现的triangle那道题，就是system in的输入 每一行都是三个数字 让你判断这三个数字能否组成 等腰三角形 等边三角形 还是都不是 没什么可以优化的 毕竟你每一行都要读 只要注意判断两边和大于第三边就好了

word break I

lz一开始没有用dfs做，直接用不断swap的方法来产生permutation（这样产生的Permutations是无序的），你这个国人大哥你这方法最后一个permutation是多少。有点卡壳，后来提示可以用草稿纸算一下，并且证明给他看怎么的出来的。

follow up上面你用了extra memory来产生有序的结果，那不用extra memory怎么做？ 这里没让写code，只需给idea。这里可以观察permutation的规律，类似next permutation那道题，说了一下大概的idea，要解释清楚。

Letter combinations of phone number

void takeNumber(Number) //从pool 里take一个number
boolean isTaken(Number) //check 这个number有没有被用
Number getANumber() //从pool里随便取一个number

2. 用set的话空间应该是O(10N)， 用Trie的应该是 10 ^10

1. 有两个数组A1和A2，求两者之间的交集。有三种情况，请分别给出解法：1）A1，A2都是无序的。2）A1和A2都是有序的。3）A1和A2都是有序的，且A1的size远远大于A2。我的解法是，1）HashMap。2）和3），对A2的每个元素在A1中进行二分搜索，同时保持上次搜索的结果的index，这样下次就只用搜index往右的元素就好了，不用还是从0开始。
2. 有一堆文件，里面有duplicates。输入这些文件的路径，也就是Set<String> paths。要求返回去掉duplicates后的结果，同样也是Set《Stirng》。比如输入是，文件1，文件2，文件3的路径集合，而且文件1和文件3是完全一样的。那么返回文件1和文件2的集合或者文件2和文件3的集合都行。我是先把文件按文件大小分类，对于那些同一个size下有多个文件的，就对每个文件算一个one way hashing值作为fingerprint （MD5或者SHA2），然后就对比这fingerprint就知道是否重复了。

1. 实现一个随机函数。也就是给你n个数（1-n），产生每个数的概率不一样。比如输入可能是 double prob[] = new double[]{0.3, 0.1, 0.3, 0.2, 0.1};各个概率加起来等于1。 同时再给你一个参数m，要你产生m个samples。 按概率切成小段后二分搜索。2. https://leetcode.com/problems/unique-paths/
. 1point 3acres 璁哄潧

1，给一个数组，找到数组里，两两元素之间差的绝对值最小的pair, 打印所有pair

2, 一个等差数列，一个等比数列，给初值，等差的值，初值，等比的值，和数组上界，求两个数组里公共元素个数，例子
1. 求一个数的二进制补数，从左边第一个1开始，每一位0变1，1变0
2. 给两个string s, t, 问最多能从s中删去t几次（每删除一次剩下两个字符串拼成新的s）
http://algobox.org/remove-substring-recursively/
Given two strings `s` and `t`. Find the maximum number of times that one can recursively remove `t` from `s`.
Example 1:
`s` = `"aabcbc"`
`t` = `"abc"`
Return `2`.
We can first remove `s[1:3]` and `s` becomes `"abc"`. We can then remove it all.
Example 2:
`s` = `"abababaaba"`
`t` = `"ababa"`
Return `2`.
dfs做的，开了个全局的map做cache

2）Java的一些基础知识，equal() 跟 hashCode(), comparison of ArrayList and LinkdedList，comparsion of HashMap & TreeMap (and time Complexity comparion)

3) 终于是coding啦，地里有基本一样的题目。给一个String， 然后对出现的每个字母，按照出现频率从高到低的逐渐输出。比如，“banana”， 输出就是 “a 3, n 2, b 1”。 如果有两个字母拥有相同的次数，那就无关顺序。我觉得这个题目有多种做法，但肯定得有个map 记录字母出现频率，之后可以用Sort，或者Priority Queue， 或者TreeMap来降序输出。

```  public static List<Character> count(String s) {
Map<Character, Long> m = s.chars().mapToObj(x -> Character.valueOf((char) x))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
Queue<Character> maxheap = new PriorityQueue<>((x, y) -> (int) (m.get(x) - m.get(y)));
List<Character> ret = new ArrayList<>();
while (!maxheap.isEmpty()) {
}
return ret;
}```

(x, y) -> (int) (m.get(y) - m.get(x))

4）最后一题只用讲思路。如果现在有100G的数据，然而你只有10G的Ram，该怎么sort所有数据。