Google Onsite Interview 面经

2020年初Google Onsite面经

第一轮：超级nice的国人姐姐。因为到的比较早，先去kitchen拿了点零食然后闲聊了半天G家的室内装潢（……）和简历上的经历。题目是给一个positive integer N，求N最少能由几个2^i组成。比如N=1的时候，1=2^0，那么N最少能被1个2^0组成。再比如N=7的时候，7=4+2+1=2^2+2^1+2^0，这个case中N最少被3个2^i组成。然后follow up是，可以同时使用正或负的2^i。同样的例子N=7，在这个情况下，7=8-1=2^3-2^0，这样最少只需要2个2^i就能组成N。

第二轮：台湾葛格，人也挺nice的。没有废话直接上题，就是lc的bomb enemy，不同的是bomb也能放在enemy所在的位置。第二题是给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8… 

第三轮：印度姐，关于最近时间的问题，当前显示时间为 ab:cd，求下一个离当前时间最近的时间，并且只能用｛a,b,c,d｝这个集合里面的数字，数字可以重复使用，不一定要全部用到。输入输出都是字符串。
举个栗子
当前时间为“23:02”，下一个最近的时间为“23:03”
当前时间为“23:58”，下一个最近的时间为“22:55” （第二天的）
我用的方法很蠢，就是找出所有可能的组合，去掉那些不合法的（比如42:23这种），然后求出和当前时间的时间差，取最小的。

第四轮：白人小哥，看起来就智商很高的那种。题目是给一瓶药，里面100颗完整的药片，每天需要吃半颗。每天吃的方法是随机从瓶子里取一颗药，如果是整颗就吃半颗，剩下半颗扔回瓶子里；如果取出的是半颗，那就直接吃掉。第一小问是simulate这个过程，然后print每天瓶中剩下的整颗和半颗的数量，直到空瓶。第二问是，求整个simulation过程中，瓶中剩下1整颗，0半颗的概率。最后问了running time。

除了印度姐姐全程冷漠脸以外其他面试官都很热情友好一天下来感觉面试总体难度还行，并没有某些面经那么难（面之前看别人的面经真是吓得不轻……） 接下来默默等结果吧