google onsite 7/25

今天面的， 虽然没遇到什么老题。 面之前没怎么刷题，基本上看看本版面经warm up, 感觉收获颇多，算回馈本版。R1:  印度phd,  问题很有意思， 一个2-D 矩阵，每个位置可以放一个字符。 有个文本，文本中每个词之间一个空格。问可以容纳多少次文本.   Follow up:  优化时间复杂度。 要写简单的O(RC) 算法。对给出的follow up 方法和时间复杂度分析表示很满意。 虽然还不是最优，但已经非常接近。此题follow up本身就不容易。  
R2：很nice 的美国大叔。 题目很有意思，10个digit(0,9), 任意取4个可重复构成密码,  求一个字符串可以cover所有密码。 举个例子：

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

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

nt>
最后总结， 无论有没offer, 都尽力了。 两次google interview 都碰到一些有意思的题目，也比较享受解决没有做过的题目。 每次交流的感觉还不错。 Let's see.

adrian_yang84 发表于 2016-7-26 11:00
感谢楼主。能麻烦再解释一下第二题的题意么？没看明白。。

举个例子
字符串 “123456” 能够cover 的密码 “1234”， “3456”， “2345”。 其实也已经把解法说出来了

第一题暴力解不就是rc ? 还是我理解有误？       
public static int coutFile(int r, int c, String[] strs) {
                if (strs == null || strs.length == 0) {
                        return 0;
                }
               
                int res = 0;
                int i = 0;
                int j = 0;
                while (j < r) {
                        for (String s: strs) {
                                i += s.length() + 1;
                                if (i > r) {
                                        j++;
                                        i = s.length() + 1;
                                }
                        }
                        if (j < r) {
                                res ++;
                        }
                }
               
                return res;
        }

第一题我的做法是可以先循环遍历文本，遍历的过程中不断记录新一行起始单词的坐标，如果找到一个重复的起始坐标就证明找到了循环节。然后可以算出第一次循环开始之前需要占多少空间 & 包含了多少次文本 + 每个循环占的空间&文本次数 * 循环次数 + 最后一次未完成的循环之中文本次数。
这个做法找循环节的worst case 是O(n^2)，n是文本单词个数
计算文本次数的worst case是O(n)

求问前两轮的题楼主是怎么做的。

请问第一题问可以容纳多少次文本是什么意思？可以详细解释一下吗？

awesomeG 发表于 2016-7-26 08:34
求问前两轮的题楼主是怎么做的。

解释起来比较费劲，周末整理下我的做法

mingruiyrh 发表于 2016-7-26 08:40
请问第一题问可以容纳多少次文本是什么意思？可以详细解释一下吗？

给个例子:  I am student.
2-D array： R=5, C=9

那么
I am
student I
am
student
I
所以res = 2 (可以容纳两次）

playgames 发表于 2016-7-26 08:50
给个例子:  I am student.
2-D array： R=5, C=9

暴力做法应该不难. 估计难点是 follow up

Good luck. 最后一题能具体点？

感谢楼主。能麻烦再解释一下第二题的题意么？没看明白。。

嗯，我知道这样解，但是我还是不清楚题干是什么。
是让你生成0-9的四位全排列么？一共10*10*10*10=10000中情况，所以长度上限是10000*4位＝40000
下限的话，不会少于10000 ＋ 3吧？但这个下限应该是达不到的。
生成下限的话，是不是从2个数字的组合开始推导。然后是3个数字（22组合 ＋ 3个数字都用上），一直递推到10个数字。