GOOGLE Onsite

Job Hunting Interview
, , , ,
1

一共五轮， 每轮45分钟，back to back中间没有休息， 第三轮和第四轮中间有lunch

  1. 美国大叔manager， 人超nice，互相介绍以后就是做题， 题目是在matrix里面找最大rectangle，
    但是不需要rectangle里面所有的元素都是1， 只要四个角是1就行了， 所以DP就没法做了
    当时只想到了brute force, 大叔给提示可以每行得到所有的边， 然后去match其他行的边，

    但是感觉这个方法time complexity不比brute force好

  2. 国人小姐姐， 题目是把String分组， 比如说 ‘abc’ 所有字符往上翻一位就是 ‘bcd’, 翻的次数不限，
    但是要求翻完以后两个String要相同，则为同一组。楼主的做法是， 从第二位开始， 每一个的字符
    减去第一位的字符， 得到位移， 然后乘以100， 比如上面的例子就是： （‘c’ - ‘b’）+ (‘d’ - ‘c’) * 100
    然后根据位数和上面的得出的数字进行排序放入PriorityQueue， 就得完成分组。

  3. 亚洲大哥。设计一个Sector API， 需要的功能是

     a.给一个分区ID的range， 把所有的分区都设为unavailable
 b.给一个sector的ID，求这个ID之后的第一个可用的分区

    需要实现查找和修改的时间复杂度的均衡，

    楼主是用array(array index 等于sector ID，便于修改) + binary search tree(存可用的分区，方便查找)
    然后就要实现binary search tree的删除和查找比给定index大的最小index

午餐跟一个美国小哥， 小哥超lucky，公司被Google收购，然后就变google employee了， 目前做到了technical lead
午饭各种聊生活， 还有google的午饭不提供feedback，所以不影响面试结果

  1. LY， system design给一个ads system设计一个budgeting system，LY超级不耐烦， 开始给了非常有限的说明，
    我问了几句clarify的问题他就开始不耐烦了， 说我不能给你回答其他的问题了， 所以写的时候对要求和题目还是不清晰

  2. 美国小哥， 纯BQ， 各种跟项目和team相关的问题

2

上门考了这题，大家看下？

Given a diagram with lines parallel to x axis and y axis, find the number of squares formed by these lines.

image

  1. Define data structure to represent diagram
  2. Algorithm to find the number of squares
3

分享一道onsite题目

Design an API that supports the following function calls: addService, addServiceCall(service, time, payload), getAllServiceCallsBetweenTimes(time1, time2)

Ex:
addService(“A”)
addService(“B”)
addServiceCall(“A”, 1, “abc”)
addServiceCall(“A”, 5, “abec”)
addServiceCall(“B”, 3, “ac”)
getAllServiceCallsBetweenTimes(1, 4) -> “abc”, “ac”

Follow up: what if you also had to filter by service?