Massive Algorithms: Twitter Interview Misc

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/。

第三轮：
OOD，设计数据结构可以对表达式进行存储和evaluate。只有加减乘除运算。比如 2*5+2。用Tree做就可以了。
第四轮：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所有数据。

Twitter Interview Misc

Labels

Popular Posts