Sunday, October 19, 2014

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。 

No comments:

Post a Comment