google mtv onsite面经 5/9

整体感觉题不难，非常重视complexity的分析，自己还是有很多地方做的不好，所以报答案的时候也没有底气，

ps: onsite一般每轮都问几个问题啊？ 只问了一道题是要挂的表现么？

第一轮: 最简单contains duplicates，注意在没有dup的时候返回值的处理，如果返回类型是int，就不能返回null。要把返回值改成Integer

           加了限制条件：1.所有数字>=1,<=n-1 2.sorted 3.只有一组duplicates

           binary search：分隔条件是，1，2，3，4，5，5

                                     index：     0，1，2，3，4，5 可以看到一个数字如果前面没有dup num[i]=i+1，否则 num[i]=i,以此为比较条件

第二轮：一个string，如何插入数目最少的字符使得它变成panlindrome.     

             two pointers，指向首尾两个字符，如果一样start++,end—, 如果不一样，就要在start前面加char(end)，end—或者在end后面加char(start),start++找最小值

                       

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

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

              index    0  1 2 3 4   5

              output  4  4 3 4 -1  -1 没有是-1

用栈里维护所有递减的数字，每来一个新的数字就与栈顶元素比较，并且赋值

找popular element in sorted array，频率n/4  这种数只可能出现在四分之一，二分之一，四分之三的位置

第五轮： double sqrt(double x) 要求误差小于epslon

             1：注意binary search的范围 end=（num>1） num: 1

             2:  while(end-start>epslon)

时间复杂度： num/(2^n)<epslon           O(n)是log(num/epslon)         

第二题好像是lc原题吧

不是完全一样，这个可以往任何地方插入字符，不是非常插到前面

第二题用dp? dp[i][j] = Min(dp[i][j - 1], dp[i - 1][j]) + 1?如果i和j不同的话。
第三题是不是和LC上面scramble string类似。

GavinM 发表于 2016-5-11 03:38
第二题用dp? dp[j] = Min(dp[j - 1], dp[j]) + 1?如果i和j不同的话。
第三题是不是和LC上面scramble strin ...

我觉得第二题也是dp。有点类似edit distance

第一题二分条件不对吧， 按照例子，如果duplicate出现在前面的话，你这样就往后搜索了。。。

lll_2013 发表于 2016-5-11 04:18
楼主，你能不能解释下第三题complexity是不是T（n） = T（n/2) + T(n/2) + T(n /2)。
所以O(3^logn) ?

请问到底是O(3^logn)还是 O（n^log3）呀？谢谢