前几天刚刚在 Shanghai 参加的 onsite，1 轮 SD + 4 轮算法
第一轮
- remove the extra edge from a given binary tree.
- max product path alone a binary tree. (Follow up: what if the node contains a negative value)
第二轮
- given a string only contains ‘‘0’’ and ‘‘1’’, for each query, you are given an integer K, find the total number of substrings that contains exactly K '‘1’'s and arbitrary '‘0’'s.
第三轮
-
设计 2 人对战游戏，每个人有 5 x 5 的棋盘和 5 条船（长度分别是 1 ~ 5，宽度固定是 1，摆到棋盘上，不能重叠，互相不知道对方摆法）
-
回合制，one by one call 类似 attack(i, j) 的函数打击对方棋盘的 (i, j) 点
-
每条船必须所有 parts 被打掉之后才算沉，比如：4 x 1 的船，必须 4 个方格全部被打击掉才算沉）
-
获胜条件是打掉对方所有的船
-
题目的要求是不考虑玩家的策略，是在 high level 设计整个游戏
some tips: -
怎么选型？1 server + 2 clients 还是 1 client + 1 client？）
第五轮
- 里扣 扒腰吾 (Follow up: 考虑真实世界中， station 多或者 line 多的情况下，该如何选择算法)
面完第 2 天通知挂了，很是难过，feedback 是 SD 答的非常好，但是算法没到 bar。
哎，第二次 fail onsite了，题目到也不是特别难，move on。