一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2004|回复: 19
收起左侧

Google电面面经

[复制链接] |试试Instant~ |关注本帖
brianyu 发表于 2016-1-27 13:11:00 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Pass在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
得到国人大哥的提携。两道中规中矩的题
- Given string s and string pattern, find the number of subsequences in s that forms pattern. All characters are discontinuous in s.
For example, pattern = ab, s = abcacb. Return 2. because {0, 5} and {3, 5} satisfy the rule.. 鍥磋鎴戜滑@1point 3 acres

- Given a stream, find the longest substring that has at most 3 distinct characters. Leetcode 经典题。

评分

2

查看全部评分

hzyslddm 发表于 2016-1-28 08:02:23 | 显示全部楼层
第一题用dp, 贴个我的代码,欢迎指正
count[i][j]表示pattern的前i个字符和s的前j个字符匹配有多少结果

count[i][j] = count[i][j-1] + count[i-1][j-2] (若p中第i个字符和s中第j个字符相等,可以选择两者配对或不配对)
               = count[i][j-1]  (字符不相等,则不配对,结果跟 p中前i个字符和s中前j-1个字符匹配 的结果一样)

        public static int countNum(String pattern, String s) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if(pattern == null || pattern.length() == 0 || s == null || s.length() == 0)
                                return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                int[][] count = new int[pattern.length()+1][s.length()+1];
                for(int i = 0; i <= s.length(); i++). from: 1point3acres.com/bbs
                        count[0][i] = 1;
                count[1][1] = s.charAt(0) == pattern.charAt(0) ? 1:0;
               
                for(int i = 1; i <= pattern.length(); i++) {
                        for(int j = 2; j <= s.length(); j++) {
                                count[i][j] = count[i][j-1];
                                if(pattern.charAt(i-1) == s.charAt(j-1)). 1point 3acres 璁哄潧
                                        count[i][j] += count[i-1][j-2];
. Waral 鍗氬鏈夋洿澶氭枃绔,                        }
                }
                return count[pattern.length()][s.length()];        -google 1point3acres
        }
回复 支持 1 反对 0

使用道具 举报

zjjcwb 发表于 2016-1-27 13:19:43 | 显示全部楼层
哪道经典题啊?题号多少?LeetCode好像没题目跟stream有关吧
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-27 13:30:44 | 显示全部楼层
zjjcwb 发表于 2016-1-27 13:19
哪道经典题啊?题号多少?LeetCode好像没题目跟stream有关吧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
159,会员才能看。stream只是个幌子,就是提示要O(n). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
https://leetcode.com/problems/lo ... istinct-characters/
回复 支持 反对

使用道具 举报

see_you2012 发表于 2016-1-27 13:34:58 | 显示全部楼层
第一题没太看懂,求楼主指点~

pattern = ab, s = abcacb. 为啥{0, 5} and {3, 5} 满足?  (0,1) 为啥不满足?
回复 支持 反对

使用道具 举报

kidzlike 发表于 2016-1-27 13:36:17 | 显示全部楼层
gx楼主 请问楼主是啥时候电面的?大概多久之后给的onsite通知?谢谢
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-27 13:41:35 | 显示全部楼层
kidzlike 发表于 2016-1-27 13:36
gx楼主 请问楼主是啥时候电面的?大概多久之后给的onsite通知?谢谢

周五面的,就过了俩工作日。
回复 支持 反对

使用道具 举报

kidzlike 发表于 2016-1-27 14:19:48 | 显示全部楼层
brianyu 发表于 2016-1-27 13:41
周五面的,就过了俩工作日。

谢谢你,希望我也能pass电面~
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-27 14:33:03 | 显示全部楼层
第一题dp,第二题用一个map(如果是ascii就256的array)记录sliding window里边的字符的个数,然后维护一个当前sliding window里边字符种类数量的变量,应该就可以了吧,可以followup到n.
我看第二题leetcode那个用两个指针分别记录sliding window里最后一个某字符的位置,这样扩展到k就崩了吧。
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-1-27 14:36:55 | 显示全部楼层
请问lz, pattern是2个字符么, 还是可以是多个字符? 多个字符也挺难写的
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-1-27 14:46:31 | 显示全部楼层
“得到国人大哥的提携”,点赞描述
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-27 15:45:05 | 显示全部楼层
guixi107 发表于 2016-1-27 14:36
请问lz, pattern是2个字符么, 还是可以是多个字符? 多个字符也挺难写的

可以是任意长度。
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-27 15:46:58 | 显示全部楼层
zxl9171 发表于 2016-1-27 14:33
第一题dp,第二题用一个map(如果是ascii就256的array)记录sliding window里边的字符的个数,然后维护一个当 ...

估计那个LC答案是针对题目要求做的优化,就算那样写了,面试官估计也会要求扩展到k。
回复 支持 反对

使用道具 举报

cbmbbz 发表于 2016-1-27 16:31:50 | 显示全部楼层
第一题为什么{0,1}不行呢?能说说第一题思路吗?谢谢
回复 支持 反对

使用道具 举报

 楼主| brianyu 发表于 2016-1-28 01:08:18 | 显示全部楼层
cbmbbz 发表于 2016-1-27 16:31
第一题为什么{0,1}不行呢?能说说第一题思路吗?谢谢

要求是subsequence with all characters not next to each other in s. 可以dp,也可以从recursion 入手。
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 02:37:37 | 显示全部楼层
brianyu 发表于 2016-1-28 01:08
要求是subsequence with all characters not next to each other in s. 可以dp,也可以从recursion 入手 ...

如果可以连续比较好dp,如果不能连续,转移方程有点想不清楚。。。。
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 02:41:28 | 显示全部楼层
brianyu 发表于 2016-1-28 01:08
要求是subsequence with all characters not next to each other in s. 可以dp,也可以从recursion 入手 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
难道是如果字符相等,看左边,如果左边为0,等于上边的左边的左边,如果左边不为0,等于左边的值+1?
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 08:43:33 | 显示全部楼层
hzyslddm 发表于 2016-1-28 08:02
第一题用dp, 贴个我的代码,欢迎指正 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
count[j]表示pattern的前i个字符和s的前j个字符匹配有多少结果

为什么count[0] = 1;啊,有点理解不能。。。。
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-1-28 11:34:21 | 显示全部楼层
zxl9171 发表于 2016-1-28 08:43. from: 1point3acres.com/bbs
为什么count[0] = 1;啊,有点理解不能。。。。

我的理解是count[0][0] = 1, 俩空串
count[0] = count[0][i-1] = ... count[0][0] = 1

补充内容 (2016-1-28 11:34):.鏈枃鍘熷垱鑷1point3acres璁哄潧
count[0] 怎么打出来一个括号被吃掉了
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-1-28 14:40:09 | 显示全部楼层
求问各位大神第一题该怎么解啊?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 12:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表