高频题
这题的完全解答（6步全）在 第三课：Facebook 与 Bloomberg 专题之OOD 课上给了代码答案
再贴下别人的面经：
今天一大早刚刚做的Stripe电面，一个白人小伙面的，题目是实现Database的老题。幸好看了面筋写的还算流畅。
不过感觉以前的资料写的不太全，自己再稍稍整理一下，算是回报吧。
第一、第二问以及背景： 看前人发的链接就好：
https://gist.github.com/weiqitoby600/fd3db87ae8123432c844fb1601413525
第三问：重写一个新的RecordComparator实现List<Map<String, Integer>> records 的排序，这道题把类的名字，构造函数都写好了，让你写
Compare就好。返回 0/-1/1。
函数：public int compare(Map<String, Integer> left, Map<String, Integer> right){return 0}
第四问：给一个LinkedHashMap<String, Integer>， 每一个都是key 和 direction， 先根据第一个key dir排序，再根据第二个、第三个… 排序。
这道题看以往面经的时候自己理解错了，以为先根据第一个拍，排序完的结果再根据第二排，犯傻了。实际情况是排序是第一个元素相等的序列根据第二个再排一次，自己再写了一个Collections.sort()里面重新定义一个Comparator写好了。排序后返回第一个元素即可。
函数：public String sortFirstByOrder(LinkedHashMap<String, Integer> sortedOrder, List<Map<String, Integer>> records){ return “” }
完后第三、第四问写了一点Test case, 再问我还有什么问题，就结束了。
就这样，我来美国1年半多了，也就第三回电面，没有on site。没大神那么牛逼，手握那么多on site，一个Career fair都有十几个电面。正常的New grads而已。
补充内容 (20181027):
补充说明，我已经挂了。诶，无语。
想问楼主，第四问的时候如果map里没有那个key要怎么办呢？
所有题目，没有那个Key就当作value=0处理
请问楼主step 1需要像前人github上一样写很多其他的方法和类吗，是不是只要写他要求的那一个minByKey方法就 ...
写一个minByKey方法就可以了
Step 4
Time to take this"firstby"
functionality further, to sort by more than one key at atime.
Consider an array of records likethis one:
[{“a”: 1, “b”: 1}, {“a”: 1, “b”: 2}, {“a”: 2, “b”: 1}, {“a”: 2, “b”: 2}]
Using first_by_key with this array ofrecords with key “a” might not give us as much control as we’d likeover the result, since more
than one record has the same value for"a" (similarly for “b”). More generally, we might say"order by the first key, in the first direction.
Break ties according tothe second key, in the second direction. Break remaining ties by the third key,in the third direction, and so on."
Note that the sort direction fordifferent keys need not be the same.
We might represent this ordering witha list of pairs like
[
("a", "asc"),
("b", "asc"),
("c", "desc"),
]
We’ll call this type of representation a sort_order.
You’ll need to write a function first_by_sort_order. It takes two arguments:
a sort_order
an array of records
It returns the first record according to the given sort_order.
As before, we’ll ask that you reimplement your previous functionality (first_by_key) in terms of first_by_sort_order.
Hint: can you construct a “sortorder” comparator using your comparator from the previous step? How might constructing a sort order comparator be helpful?
Java function signature:
public static Map<String, Integer> firstBySortOrder(LinkedHashMap<String, String> sortOrder, List<Map<String, Integer>> records);
Examples (in Python):
assert(
first_by_sort_order(
[("a", "desc")],
[{"a": 5.0}, {"a": 6.0}],
) == {"a": 6.0}
)
assert(
first_by_sort_order(
[("b", "asc"), ("a", "asc")],
[{"a": 5,
"b": 10}, {"a": 4,
"b": 9}],
) == {"a": 4,
"b": 9}
)
assert(
first_by_sort_order(
[("b", "asc"), ("a", "asc")],
[{"a": 5,
"b": 10}, {"a": 4,
"b": 10}],
) == {"a": 5,
"b": 10}
)
onsite
他家题都一样 唯一不同的是 debug 那轮我用的java 题是moshi中next index 的一个
algorithm那 轮的题目是
-
输入有一堆account, 包括name, time, due amount, 按照时间给每个人发多封pay due 的提醒邮件,输出所有按时间排序的email
-
再给一堆还钱的时间点,还清就不用发提醒邮件了,输出所有email
就和之前面经说的一样，面试官强调说不需要最好的O(n)速度，也允许我查 Java document， 查 Stack Overflow， 就希望我写得快,但题目和论坛里2016的已经不一样了，
有3个follow up。
内容大概就是给一个001010之类的字符串，从左到右扫。
碰到1会扣分，0不扣分，但一共有一次机会可以选择反面，也就是1不扣分而零扣分。
现在给反面的位置，求得分。
例如不使用反面，那就是一共扣 0+0+1+0+1+0=2分。
例如在"001"的1之前使用反面，那就是一共扣 0+0+0+1+0+1=2分。
follow up 1 那只给这个字符串，问哪里使用反面扣分最少。 暴力解，每个位置试一遍。没有研究过更好的解法，面试官也无所谓。
follow up 2 那再给一个带+和-的字符串，只有+和-中间的才算，例如+00+00-00-00-，那只有最中间的"+00-"才算。问这些该从哪里使用反面。followup 2 可以把所有的0/1 提取出来再call followup1 的API就行了。
补充内容 (2019114):
面完马上(3小时内)HR通知下一步了。
补充内容 (2019129)
第二面，HM。面了很多项目细节，问挑战是什么。感觉整个回答都是自己是个傻逼。毕竟没有能够当组里TL。面完挂了。还是自己水平太差
