Twitter Interview Misc

http://instant.1point3acres.com/thread/168108
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原题 
http://instant.1point3acres.com/thread/157308
后来发现coordinator约了面试之后用系统邮件发的提醒，到spam了。
是一个老美面的，题目不是很正规。
让设计一个plagiarism detection system.
一开始有点蒙，没想到面这种，面试官提示了一下，然后我就开始吹，他觉得我的idea还行， 最后写了一点相关模块代码就过了
http://instant.1point3acres.com/thread/169242
http://instant.1point3acres.com/thread/169141
第一题是deleting substring，第二题是find 1st repeating letter in a string。 
第一题的思路就是找出所有第一次可能删除的位置，再递归找出最多删除次数。 
第二题就是用hash table保存所有letter的index，遇到相同的，更新变量minIndex，保证最后找到的是最先出现的repeating letter，时间复杂度是O(N)。 

第二题为什么要保存index呢？从前到后找到第一个repeating的不就可以return了吗？

这样不可以，比如string是abcba，需要返回的是a，因为a在string中的位置在b的前面。

建一个minIndex的变量，初始化成INT_MAX，保存一个最小的重复出现的letter的index，比如遇到b的时候，minIndex的值就是1，后面遇到a的时候，这个值就会更新成0。

http://www.1point3acres.com/bbs/thread-180310-1-1.html
第二题给你公式, 算pearson correlation...什么, 你说这么简单?基础概率论内容? 是啊。。。。。。。
https://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
http://instant.1point3acres.com/thread/169524
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();
      ret.add(b);
    }
    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);
    ret.add(String.valueOf(l1 / gcd(l1, l2)));
    ret.add(String.valueOf(l2 / gcd(l1, l2)));
    return ret;
  }

http://www.1point3acres.com/bbs/thread-181624-1-1.html
题目一： Delete SubStrings: 给一个String s和一个String t, 返回一共能在s中删除t多少次。 例如s = aabb, t = ab, return = 2; s = aabcbdc, t = abc, return 1; 
我基本上没太思考，直接给了最直观的答案，用helperfunction1返回s中与t相同的subString的起始位置start，用helperfunction2删除s.subString(start, t.length), 外层循环终止条件是helperfunction1返回-1或s.length < t.length, 时间复杂度是O(n^2)。应该有更好的办法，懒得想了，发烧刚好，神智还不太清楚。。。 

题目二：Find the first repeating letter in a string : 给定一个String s，返回第一个duplicate，例如s=abcba, return = a; 这题就更简单了，用一个hashtable = 记录出现过的char, 出现重复的时候再用一个global var记录最小的index就行了。时间和空间复杂度都是O(n)。 

  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;
  }

http://instant.1point3acres.com/thread/167785
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.
http://instant.1point3acres.com/thread/157599
第一道题，就是在一个字符串里找到与另一个字符串相同的所有subsequence，用backtracking就行 
第一题要返回一个整数 － str1有多少个subsequence与str2相同，比如 str1 = “abac”, str2 = “ac”, 应该返回2

第二道是很简单的regression概念题，有一堆数据，{xi, yi} ，问为什么用y的mean可以minize mean square errors，回答是把 sum((y_i-y_mean) ^2)求导，结果是零所以是最小值 

第二题条件是用一个平面{y=c}来估算，所以c取y bar的时候能让mean squared errors最小

http://instant.1point3acres.com/thread/167825
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
例如 ”20/40” 简化为“1/2"

  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};
  }

http://instant.1point3acres.com/thread/139954
第一题： http://www.cut-the-k...， 要考虑输入很大的情况，计算结果大于10^9的直接输出最后9个digits
最后就一道题 alien dictionary.
http://instant.1point3acres.com/thread/139423
1. 不用recursion遍历Binary Tree 设计 twitter ， 都还好。 
2. 给really large streaming data, 用O(n)时间找出第k大的数。国人大哥几经提醒终于做出来了。 

quick select

第二题是用minheap吗？ 还有更好的方法吗？

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

请问，第二步为啥是k的，buffer就是k的，难道scan一遍就出来topk么，我觉得第二步是klgk的，一共是(n/k)*(klgk)=nlgk的

补充内容 (2016-3-29 14:04):
i see，是k的。lgk次，但是每次range变小了，总和是k

3. read4Bytes，分析好了写到一半突然问我“你以前一定做过这个题吧？”我说和同学讨论过类似的场景，他说，换一个，那时候还有15min...问我，给我50个bytes，不知道对方发来的内容是什么，怎么判断这个收到的消息是大端序还是小端序。我答的是协议上规定一个固定的帧结构。

http://instant.1point3acres.com/thread/168904
http://instant.1point3acres.com/thread/144247
第一轮 在log file里找东西 
0 xxxxxx 
1 xxxxxxx 
5 xxxxxx 
20 xxxxxx 
35 xxxxxx 

前面数字是timestamp，后面是内容。给你个range[7, 28], 让你找bytes的offset分别是多少。 
就是把整个log file当一个stream，然后找出比如
0 abcde
1 abc
2 abcd

你就return （8， 12）， 因为第一行有7byte，第二行5byte，所以前面的offset的开始就是第8byte，然后结尾的offset就是第12byte


第二轮是render tweets 
Inout: 
{ id: 0, reply_to_id: 3; 
id: 1, reply_to_id: 0} 如果reply to是0，就是主tweet，否则是回复。让你存住这个，并且render。每有一个新tweet最快让它在相应的tweet thread下显示。 
设计数据结构?
任务是你自己用一个方法去render一个回复界面，你要用啥储存以上信息，并implement。至于你用什么data structure储存随你。难点在于Tree根本是错的，他说有更好的方法，也没告诉我

然后设计一个ATM， OO design。 
然后behavior一轮。 
最后一轮给一个string a, string b，查用a的字母能否拼出b。每个字母只能用一次。 

还有最后一轮考的是anagram吧 

差不多，不过他说两个string都有可能很长很长。所以不要一次性把一个string都读完，要两个string一位一位读

一位一位读，最后还是要读完的么，那么为啥要一位一位的读。
比如a是sssssssst，b是ts，a要读完最后一个t才知道能不能弄出b来。

如果是ascii的话 可以用一个 array 做map
如果string 只有字母 那一个size 52的 array 就够了

我猜面试官想考的是
假设如果有很长一个string 不能放到全部放在memory里 应该怎么办

这时候应该带用pointer 一部分一部分的读string 进来
同时跟面试官说
因为一位一位读进来 每次下到hard disk 这个constant opreation
实际上的time比较长
所以我要bring a chunk of string to memory 再去读
我用string 代表一个很长的string
每个element是 a chunk of string
我假设已经有api 或者一定方法可以读chunk进来

  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;
  }

你考虑的是worst case，然而现实生活中哪里有那么多worst case。

要是这样呢：
s1 = “abcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”
s2 = “bc”

写出来的码不一定理论上最快，更重要的是实际上用起来最快。。。

http://instant.1point3acres.com/thread/169891
2. Super power 判断 z能否形成p的q次方。z, p, q都是正数。如果可行为1 不可行为0
http://instant.1point3acres.com/thread/167747
http://instant.1point3acres.com/thread/139854
第一题是问一个等差数列，一个等比数列，题目会给分别的首项，以及等差及等比的数值，然后找出两个数列有多少个相同的数值。

可以直接看等比数列中有多少个数值能整除等差数列中每一项的差

在检查能否整除之前要先减掉等差数列的首项，举例说：

等差：4 7 10 13 … 64

等比：2 4 8 16 32 64

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));
  }

第二题更简单一些，就是给N个三角形的三边长度，判断每一个是等边、等腰，还是其他（或不是三角形）。

  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
  }

题是triangle 和complement number
q2 example input 1011(11) output 0100(4)

http://instant.1point3acres.com/thread/171354
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 
http://instant.1point3acres.com/thread/166449
1. Text Justification 
2. Shortest Path Between Two Nodes 
3. Iterator 
4. Nested Iterator 
5. Behavior
http://instant.1point3acres.com/thread/149299
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) 问了一堆比较简单的小问题
http://instant.1point3acres.com/thread/159319
在sentence里找出top K 的words，hashmap加size k priorityqueue。 followup是如何分布式解决。
就是每个node上取top k， 最后merge 成global top k
http://www.1point3acres.com/bbs/thread-181810-1-1.html
第一题，fibonacci。给你一个数字n，返回一个数组，里面包含前n项fibonacci number。比如n = 4，返回0 1 1 2
第二题，叫什么is the number repeat。我表达不太清楚，给个例子吧 
比如 给你一个 1 3 2 3 4 1， 
你的数组的第一个string 是 000101， 就是每个数字是否在之前出现，是就输出1，不是就是0； 
第二个string刚刚相反，是110000，就是说每一个数字是否在后面出现，是就输出1，不是就是0； 
第二题要输出的是那两个String，即 
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 {
        s.add(n[i]);
        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 {
        s.add(n[i]);
        sb.insert(0, 0);
      }
    }
    ret[1] = sb.toString();
    return ret;
  }

http://www.1point3acres.com/bbs/thread-169391-1-1.html
1. 面试官是engineering effectiveness组的，一开始问了基本的网络常识，比如描述DNS的resolution的过程。之后问如何用shell command来统计一个文本文件里出现的单词集合（其实就是用pipe来组合各种command，类似 http://www.devshed.com/c/a/brain ... -do-with-pipelines/）。
最后要求设计一个类似memcache的系统，过程中问了关于scalability和robustness的问题2. 面试官是platform engineering的，问如果给定一个目录，目录下有些二进制的文件，有个utility函数能对文件进行解析，声称plain text的文件，要求写个程序统计出目录下所有的plain text文件中出现的单词的频率。 考查的内容有software profiling，cucurrent programming，pipeline等等。 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
3. 面试官也是plaform engineering的，题目是：给两个大小分别为m和n的杯子，以及一个目标容量k，判断是否能够装出目标容量的水，就用BFS就可以了（也有数学的解法，但是面试官说不用数学的解法做），followup是求怎么装（这也就是为什么面试官不要用数学方法做的原因）。之后又讨论了下DFS和BFS的优劣。4. 面试官是engineering effectivieness组的，第一题是leetcode 53：Maximum Subarray。followup是把输入从一维数组改成二维矩阵，差不多的思路
5. 最后一轮是behavior，基本上就是随便聊聊。

http://instant.1point3acres.com/thread/168188
1. https://www.hackerra... 很多人都做过 很简单 看明白公式就没有任何难度 test case也很少 不知道提交以后有没有多余test
2. 地里常出现的triangle那道题，就是system in的输入 每一行都是三个数字 让你判断这三个数字能否组成 等腰三角形 等边三角形 还是都不是 没什么可以优化的 毕竟你每一行都要读 只要注意判断两边和大于第三边就好了
遇到这么简单的题也是醉了 欢迎讨论其他题的解法 我的做法不一定最优 但是我绝大多数题都努力全做了一遍。。。

考的是在一个有括号的string里找longest well formed subsequence, 比如“((()())”， 就是“(()())”
word break I 
http://instant.1point3acres.com/thread/161148
上来先让介绍project，然后来一道permutation。

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

follow up如果要产生的Permutation有序怎么做？ 用dfs加个boolean数组，最基本的方法
follow up上面你用了extra memory来产生有序的结果，那不用extra memory怎么做？ 这里没让写code，只需给idea。这里可以观察permutation的规律，类似next permutation那道题，说了一下大概的idea，要解释清楚。
http://instant.1point3acres.com/thread/172547
我说exclusive or 直接就做出来了。他说不要用这个。我说那就用HashMap吧，写好后优化成了HashSet，问了两个问题结束了。这部分大概10分钟。。。。 

没有就加，有就移除

http://instant.1point3acres.com/thread/139890

Letter combinations of phone number 

做完说出一道设计题吧不用coding。 
设计一个电话号码dispatch system，三个api 
void takeNumber(Number) //从pool 里take一个number 
boolean isTaken(Number) //check 这个number有没有被用 
Number getANumber() //从pool里随便取一个number 

我说用一个set应该就可以了。 
问multi thread怎么办。我说把三个method 都synchronized。我发现这个multi thread的问题经常被问起。 
问memory consumption如何，我说O(n) 
问想想能不能improve一下memory。 
我想了想说可以试试用个trie，把三个api怎么实现都解释了一下。 
问这样memory怎么样呢，我说worst case应该是9^9吧。感觉不是很好比，取决于number的distribution。现在想想如果每个数字存一个char的话用trie worst case是9^9， 用set的话应该是9^10，因为每个电话号码是9个char。但实际上应该也差不了多少。 

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

http://www.1point3acres.com/bbs/thread-185118-1-1.html
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 璁哄潧
第三轮：
OOD，设计数据结构可以对表达式进行存储和evaluate。只有加减乘除运算。比如 2*5+2。用Tree做就可以了。. more info on 1point3acres.com
第四轮：https://leetcode.com/problems/alien-dictionary/。哎，之前没刷到这题。在面试官的反复提示下才做出来。

第五轮：看一个parking lot的代码是否已读已维护，易扩展。这轮答的不好，就只发现有个函数太长了，不够模块化。完全被那代码带进去了，连没注释什么的都没说。应该先自己在白板上画画图在看代码的。
期间伴随各种聊简历。最后跟manager也聊了很多behavior方面的。喜欢大公司还是小公司，最看重一份工作的什么之类的。你举得T家是干啥的，你用不用
http://www.1point3acres.com/bbs/thread-108166-1-1.html
1，给一个数组，找到数组里，两两元素之间差的绝对值最小的pair, 打印所有pair

2, 一个等差数列，一个等比数列，给初值，等差的值，初值，等比的值，和数组上界，求两个数组里公共元素个数，例子
http://www.1point3acres.com/bbs/thread-167011-1-1.html
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

唯一想到的能优化的地方是查t在s中出现的所有位置可以用kmp，这样复杂度可以降一个层级，这样也许能过吧...
可以这样优化，就是比如说，上一步删除的是s[i:i+m], m是t的长度。那么下一步规定可以删除的startIndex范围是 i - m < startIndex < n - m
比如说 s = abaxxabaxxxx, t = aba
出现的位置是[0,2]和[5,7]
上一步删除了aba在[5,7]的话，下一步可以删除的位置是从3开始的
这样可以避免生成存绝大多数的重复字符串，我觉得甚至可以去掉那个全局的map。
这样在s中查找t也可以不用从头查找了，记住上一次的删除位置，从i - m + 1开始查找

查找t在s中的所有位置是不是可以preprocess并保持一个matching list。
我的意思是每一步跟前一步比，只有startIndex是[i-m+1, i]有可能出现新的Match，只要把在这里面的查找出来并插入到matching list里。
当然删除的时候也要删除matching list里受影响的部分。

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)));
    maxheap.addAll(m.keySet());
    List<Character> ret = new ArrayList<>();
    while (!maxheap.isEmpty()) {
      ret.add(maxheap.poll());
    }
    return ret;
  }

顺序反了。。
(x, y) -> (int) (m.get(y) - m.get(x))
4）最后一题只用讲思路。如果现在有100G的数据，然而你只有10G的Ram，该怎么sort所有数据。