Google 2015-10-2 MTV 另求教

1. 印度人, 先问background

Question1:  Given two algorithms say A and B that solves the same problem, the time complexity of A is O(n) but B is O(logn), is there any reason you would pick A rather than B.

Question2: Given a list of boarding passes, each boarding pass contains two cities, say A-B, generate travel itinerary.  

写了整个code，整体表现感觉还可以。

2. 美国人, 先问background

Question3: Implement hasNext() and next() for an iterator, which takes an array such as [4,3,5,0,2,1] and its output should be [4,4,4,2]. Notice that a number with odd index is the number of items before it. 三个4， 零个5，一个2。

Question 4: moving range average. Given an input array，always output the average of k item, known as window size.

第二题没时间实现了，说了一下基本想法。他表示比较满意，临走前说了个well do

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

on.

6. Binary search. Say value of current mid is k, search first appearance index of k on left and last index of mid element on right. The number of times k appears is rightIndex-leftIndex+1.

7. 常见rotate question. build a mapping function between old index and new index. CC 和leetcode上好像都有

求问： 像那个中国人这种情况，要告知recruiter 么？感觉打小报告不太好，但是如果真是因为他本人的原因挂了，只能认倒霉了么？不过也是我不够优秀，如果一开始就刷刷刷把他的问题答出来，他估计会more engaged?

补充内容 (2015-10-5 07:18):
看在是当天报面经，而且比较详细，给点米吧。。。

第三题很多人没看懂，解释一下：index为偶数的是值，会出现在结果中，就是你call next()时有可能输出，index为奇数的是它前面那个数出现的次数。不知道说清楚了没。。

airwindow 发表于 2015-10-7 08:35
受四楼启发...
我觉得Question6可以这么来做:
假设数组的size为len，a = len / 8;分别检测以下9个坐标 ...

确实是这么做

LawranceH 发表于 2015-10-3 12:24
求问下中国人那题的解法， Question6。 我自己想到个解法不知道对不对。 比如Given a sorted input array,  ...

找1/2majority的话，其实没必要移整个范围。可以先取得a[(size-1)/2] == midval的值，如果1/2majority存在，那么必定是midval。理由是，大于和小于midval的数最多也只有(size-1)/2个，所以除midval以外，其他数都不可能是1/2majority。然后在数组左半二分找midval开始的位置begin，在数组右半找midval结束的位置end。如果(end-begin + 1) > sizel/2, 那么midval就是1/2maj，否则就没有1/2maj。

这样的话，可以省掉一次检查4个点的麻烦。

楼主怎么五轮面试？是因为不是new grad多加了一轮？ 我觉得这个..没法跟hr说吧。。

补充内容 (2015-10-3 10:08):
我们new grad 直接onsite也是4轮

有过两个面试官也全程严肃，面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示。

我觉得面试官或多或少在只写code的时候会发呆怎么的吧，楼主如果是边写边说的话。。。是不是当时沉默太久没交流了。

a341265353 发表于 2015-10-3 10:42
有过两个面试官也全程严肃，面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示 ...

层主是怎么知道哪个面试官给了什么样的feedback的呢？~我也想知道我得到什么样的feedback

请问楼主 第二题的问题到底是啥呀 要写hasNext() 和next()么？那为啥会有那样的输入输出？谢谢！

bless,不要太担心了，一面不好，还有其他的呢。lz你行的！

另外，中国人的那道题我觉得应该是用鸽笼原理做，split array into 4 parts, 重复元素在每一个part的头尾，或者是相邻part的尾或者头。

我当时去google面onsite的时候也遇到这种中国人，题目明显没有事前准备，出得很不清楚，跟他confirm的时候发现他又往里面加了好多东西，花了30分钟才搞明白他要我干的事，后来面着面着就出去打电话了，内容还是非工作的都是家里面的事。如果要反应就尽早，不要等到HC出结果后反应这个情况。

kelvinzhong 发表于 2015-10-3 10:56
层主是怎么知道哪个面试官给了什么样的feedback的呢？~我也想知道我得到什么样的feedback

哦，hr说给的feedback是好的

中国人那道是我Google电面时候做的题。。。。

For Q6, refer to leetcode https://leetcode.com/problems/search-for-a-range/