OA和店面总结一下是5题
- radar rule
3月24日条带Stripe的OA
周一做完的，今天收到了下一轮VC邀请。
一道代码题一道主观题。题目是地里去年10，11月份的那道题，有一点细微改动写在下面了：
Rader Rule, 改动的地方是只有 == 和 != 但是 rule里空格是optional的，就是可以出现"amount==100" 或者 “amount ==100”, 如果用split() 比如我，就要小心这个，要先用replace把"==" 都换成" == " 然后再split。
13个 样例过了12个，满打满算用完了75分钟。我没有特殊处理过corner case。可能是中间处理方式不同造成的吧。
- platform balance
2019 Intern OA
刚做完的stripe oa，75min，一道编程，一道分析
编程题是 给了一个list，包含两种api, "API: "和 "BAL: "
“API” 用来更新账户的banalce
“API: amount=1000&merchant=121212” （这种情况下钱减去手续费，会全部存到merchant）
“API: amount=1000&merchant=121212&destination[account]=123456&destination[amount]=877” （这种情况会钱先分给
destination[account]， 剩余的存到merchant）
“BAL” 用来查询
“BAL: merchant=121212”
要求返回所有"BAL"查询的结果
分析题就是如何优化上面的代码。就往系统设计方向答，如何对账户建模，如何处理异常，如何提高安全性这样，你可以参考下。
实习OA 挂经
过了比较奇葩的test5 和 test 12，但是没有过test 8，
注意的地方
a. 推荐用的那个库，URLEncodedUtils 记得还要配合一个namevaluepair的库用
b. test4 确实可能是没有这个merchant就返回0
c. test 5 和 test 12可能是要考虑 只有destination[account]或者只有destination[amount]的情况。只有destination[account] 就是所有钱给merchant， 只有destination[amount]就是要考虑减掉这部分钱
（我记得当时还考虑很多其他情况，如 有没有merchant, 有没有merchant amount，但是好像对test case没啥影响）
- missing server
社招店面
第一題可以直接用set（每一個數字的前後 減1 ，加入 set，每個 input數字 比對一下，最後 sort就得到）。不用set可以寫個 priority queue。
第二題應該是 hashmap 和 set，我所指的set，是按第一題input list計算出來
GHC Job Fair - new grad
技术面，自带笔记本，给出一组int数组A，表示机器id(从1)开始，让你找出第一个available的server id给assign给新的一个server，其实就是找first missing number，扫两遍可以做到线性求解，也可以排序后找，但是时间复杂度是O(n log n), 但是面试官在这一步不care效率，只要求快速求解，然后我就用sorting的方式秒了，中间follow up是怎么test，要考虑什么， 答考虑duplicate ids，然后改了下算法处理这个问题。
问题2是上面的提升版，有一组String数组A，element的形式是若干个letter最后跟着几个数字，比如apibox1, apibox2，表示对apibox这个type的server的备份，需要实现String allocate(String type), void deallocate(String name)这两个函数，功能和第一题一样，只不过要针对不同的server type分别处理。第一个版本是HashMap<String, LinkedList>实现，实现的过程中我说这不是最优方式，但是因为要快速实现first version所以先这么写。跑通后开始讨论最优方式，LinkedList部分用一个priorityqueue取代，并且每个server type记录一个upperbound， priorityqueue存的是missing numbers，每次allocate时，取最小的missing number x，如果x == upperbound，再把(x+1)丢到priorityqueue里， upperbound++. priorityqueue直接把当前的id扔到queue里。
deallocate的时候如果需要先查找number是否存在，应该可以用一个HashSet存着哪些number还在, 这样就不用查heap了
社招电面跪经
- 给个数组，查找第一个miss的int，从1开始。
>> next_server_number([5, 3, 1]) 2 >> next_server_number([5, 4, 1, 2]) 3 >> next_server_number([3, 2, 1]) 4 >>
next_server_number([2, 3]) 1 >> next_server_number([]) 1
- 在此基础上，实现allocate和deallocate两个函数，给定server_type之后要能返回拼出来的hostname。
>> tracker = Tracker.new()>> tracker.allocate("apibox")"apibox1">> tracker.allocate("apibox")"apibox2">>
tracker.deallocate("apibox1")nil>> tracker.allocate("apibox")"apibox1">> tracker.allocate("sitebox")"sitebox1"
第二题用HashMap<String, Set>就够了
题目很简单，Test case要考虑全面，不然会有不少没有考虑到的地方。题目写好并测试完，面试官给了很positive的评价，根本没提到有什么遗漏的地方。
New Grad 店面
面试时两个人视频，共享屏幕。面试可以查资料，可以在IDE上写。
Q1: String allocate（String serverType) 参考leetcode41
Q2: deallocate(String ServerName) 这个serverName 里包含数字，需要用regex解析出来。
- score
海投社招视频店面
就和之前面经说的一样，面试官强调说不需要最好的O(n)速度，也允许我查 Java document， 查 Stack Overflow，就希望我写得快
有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
那只给这个字符串，问哪里使用反面扣分最少。暴力解，每个位置试一遍。没有研究过更好的解法，面试官也无所谓。
O(n) 解法可以是从左扫一遍得到 leftPresum, 然后从右扫一遍得到 rightPresum, 从右扫的时候翻转一下。
follow up 2 那再给一个带+和-的字符串，只有+和-中间的才算，例如+00+00-00-00-，那只有最中间的"+00-"才算。问这些该从哪里使用反面
可以把所有的0/1 提取出来再call followup1 的API就行了
面完马上(3小时内)HR通知下一步了。
第二面，HM。面了很多项目细节，问挑战是什么。感觉整个回答都是自己是个傻逼。毕竟没有能够当组里TL。面完挂了。还是自己水平太差
- rate limiter
校招面经
第一问： 2秒之内只能发5个request， 怎么limit
第二问： 如果request 里面有customer id, 怎么让这个rate limit是customer specific的 （就是 customer 1 的limit超过了 并不影响 customer 2 的 request）
第三问： 有的request 会比其他的request 更 expensive。那么如果 input 里面还有一个关于 request weight 的信息，怎么改这个function。（比如 request 1 要占两个request的位置，怎么改）这个要自己多加一点test case， 就什么limit是 5 request/2s, 那么一个weight 是6 的request就直接fail之类的。
Onsite
社招挂经
第一轮: 找json parse bug。解析json的库，问题在于解析object或是array的时候，index没有+1，所以解析出来的下标不对，在怀疑的地方打log追踪可以找到parse的时候少调一行nextElement
第二轮: 设计一个转账系统。主要是转账，入账和payout，比如有人付了一笔钱，merchant卖完后我们把这笔钱转给merchant。这轮系统设计挂了，应该要有点儿金融经验才知道设计trick在哪里。除了大框架，你要准备数据库设计，支持多种payment，balance计算，atomic transactions, 同时入账出帐请求什么的
第三轮: coding 类似于 https://leetcode.com/problems/time-based-key-value-store/
具体应用就是用户10天前欠了一笔钱，期间用户可能还钱，所以某天发邮件提醒时要找出那天之前用户的操作，以便知道该提醒欠款多少
第四轮: integration request replay。parse一个json file，里面是array of objects, 每个object又包含一个request和一个response，replay request和response 做比较。给的是log，需要自己写class，不过格式一致，所以一个response class就可以，我本说写个基类，然后不同api response extends base class, 他说不用，看log file里只有一种request，response格式。