10/14 Google onsite 面经

2014.10.14 by CrackerCracked

onsite 4轮， 在google总部mountain view 面的
一轮：
tourament question:  input is players like（A,B,C,D）, print total rounds[[(A, B), (C, D)], [(A, C), (B, D)], [(A, D), (B, C)]]
recursion 做的
二轮：
tic－tac－toe： 给一个board，以current state判断是o 赢， x 赢， 还是没人赢。follow up每次只能取一行的信息，每次只能存储O（2N＋K）的数据
简单的dp
三轮：
1. color schema："#c1a2b3”类型的css coloe schema，要求转化成类似"#ccaabb"这样三组相同字母的pattern， “＃cba” 可以代表“＃ccbbaa”，最后输出颜色最相近三个字母的color schema
2. 给三个API, Register（phone ＃）, GetUnused(), isUnused(phone #), 设计一个数据结构可以有效率的调用三个API。Register先check sUnused(phone #)，看phone num在不在used num里面，如果在，调用GetUnused()，将生成的num放进used num的结构里；如果不在，直接放进used num里
四轮：
1. 给个board，有且仅有一片连续的1，其他位置是0，找一个最小的box（rectangular）将1全部装进去。用BFS解决
2. 给一个list和k（number）。找一个区域k，使得这个区域里k的最大值和最小值的差值最大，返回这个值。用heap或priority queue做dp。