10/18 Google onsite 应该是凉凉面经

一共 5 rounds,4tech round + 1 behavior

1st round: Giveneach object has four attribute, and each attribute can be value 0 or 1 or 2.First question: if you are given 3 objects, assuming for each attribtute, theobjects either all have different attribute value, or they have all sameattribute value. Determine whether an object list is valid. For example:

A valid example:         An invalid example:
obj1: 0, 1, 2, 0           obj1: 0, 1, 2, 0
obj2: 1, 1, 0, 0           obj2: 1, 1, 1, 0
obj3: 2, 1, 1, 0           obj3: 1, 0, 0, 0

解法:一个attribute一个attribute看,碰到前两个一样,如果第三个不一样就return false,前两个不一样,create a set of numbersof the attribute, if length(set) != 3, return false. 我完全没想到用set,是他提示我之后才知道的。
follow up question, if you are given a list ofobjects, with 4 attributes, and each attribute have value 1 or 2 or 3. Designan algorithm to choose 3 objects from the list such that they form a valid setof objects.
解法:先从list 里取两个objects,这两个object 就可以决定第三个 valid object是什么样子的了。直接找就可以。

2nd round: behavior
Q1: name a time when you advocate for yourselfor for others
Follow up: what wouldyou do differently
Q2: You have deadline to submit a finishedproduct by tomorrow, but you just received a bad review from user. What wouldyou do?
Follow up: what wouldyou do differently
Q3: How would you maintain a good workingenvironment (assuming you are not a manager or anything)
Follow up: How wouldyou approach this if you are the manager
Q4: If you organize a team outing. You have manyoptions and everyone voted for their favorite. On the day of the trip, stillhalf the people didn’t participate. What would you do?

其实有更多follow up,不过都太细节了不太记得起来。这轮面试体验有点差。面试官感觉是个英文不太好的中国小哥,问了问题之后,没有任何交流,我说什么他就疯狂在电脑上打字,然后很制式地问我下一个follow up.

3rd round: warm up question: 有一个global variable,他让我implement一个很简单的class + class function to update this variable. 然后问:如果我有两个instance of this class, 会有什么问题?我就说会有racecondition。当时内心十分慌张,以为他会让我写python 的lock。但幸好没有。正题:Implement a class that updates at mostCapacity times within 1 minute.

Lunch break 跟西裔小哥侃天侃地侃空气。之前面挂的阴霾一扫而光。

4th round: A group of friends went out for an outing.Several people paid for the costs, and others didn’t pay. Determine how muchmoney should each payer get back. Follow up, determine how the group shouldsettle up the costs. Output should be a list of tuples, with (payer, payee,cost) which means payer should give payee ‘cost’ amount of money.
解法:sum up the total cost, and divide itby total number of people to get average cost each person should pay. Given alist of payments [2,3,10, 0, 0], subtract each element by average cost, andsort the outcome. [-3,-3,-1,0,7]. Keep two pointers initially at left end andright end. add to output tuple (left_idx, right_idx, absolute value of smallernumber), always update the number with larger absolute value= left_number+right_number, and move pointer pointing to number with smaller absolute valuetowards middle. (After check with interviewer, assuming there will be no caseslike [-3,3], where you need to move both pointers towards middle)

5th round: 乐扣 叁衣整体感觉题都不是特别难,怪自己状态不好。今年是面挂了,来年再战吧_(:з」∠)_





就是每组你竖着看,each column either all same, or all different. 每一列如果既有一样的又有不一样的,就不valid

哦哦我大概懂了,就是要一个list里面三个object都valid就return true

其实准确的说应该是4个attribute都valid (因为我们是每次对比一个column,一个column代表一个attribute)



多谢楼主分享面经! 第四题好像是lc司柳武, greedy的解法有些情况不能处理,需要用dfs暴力解,例如[-5,-4,-4,5,8]



任意一种,不需要次数最少。(我最开始听到这个题也以为是lc上那道hard,但是确认细节之后确定就只需要很简单的一个list 就好)


我用的python,是keep a variable self.capacity, 一个 FIFO deque of events. 每个events会跟一个时间。update的时候,注意check list 有没有到capacity, 并且head of list 是不是1 min 以内就好了。

10月份的面经都是女生的? 感觉有些题也很难啊