G家还是直接面题了,没有问BQ。背靠背两轮:
第一轮:
刷题网求combination变种。
Given a string S (of size N), and an int K, generate and return all K-sized combinations of the letters of S.
Example input: S = “abcd”, K = 2
Expected output: {“ab”, “ac”, “ad”, “bc”, “bd”, “cd”}
followup重复的letter如何处理。
==== If duplicates:
duplicates? S = “aaa”, k = 2, ouput: “aa”
再followup 求 permutation。另外就是permutation有几种。重复的letter如何处理。
==== If permutations:
Expected output: {“ab”, “ac”, “ad”, “bc”, “bd”, “cd”, “ba”, “ca”, “da”, “bc”, “bd”, “cd”}
第二轮:
判断给出的人中某两人是否有血缘关系。
Dataset: persons
know parents or children
Input: two persons
Output: if they are blood related
class Person {
// identify
List<Person> parents; // size 0,1,2
}
boolean isBloodRelated(Person a, Person b)
假设 a has m ancestors, b has n ancestors, 可以先把a的m个ancestors 全部找出,再找b的。
followup如何优化。就是并行同时找a和b的,用同一个visited set, 这里注意会有edge case。