[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4228|回复: 19
收起左侧

Google电面面经

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

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

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

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

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

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

评分

2

查看全部评分

hzyslddm 发表于 2016-1-28 08:02:23 | 显示全部楼层
第一题用dp, 贴个我的代码,欢迎指正.1point3acres网
count[i][j]表示pattern的前i个字符和s的前j个字符匹配有多少结果
.1point3acres网
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) {. 围观我们@1point 3 acres
                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++)
                        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++) {.本文原创自1point3acres论坛
                                count[i][j] = count[i][j-1];
                                if(pattern.charAt(i-1) == s.charAt(j-1))
                                        count[i][j] += count[i-1][j-2];.本文原创自1point3acres论坛
                        }. 1point3acres
                }. 1point 3acres 论坛
                return count[pattern.length()][s.length()];       
        }
回复 支持 2 反对 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有关吧
. from: 1point3acres
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. 1point3acres
gx楼主 请问楼主是啥时候电面的?大概多久之后给的onsite通知?谢谢

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

使用道具 举报

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

谢谢你,希望我也能pass电面~
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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
为什么count[0] = 1;啊,有点理解不能。。。。

我的理解是count[0][0] = 1, 俩空串.本文原创自1point3acres论坛
count[0] = count[0][i-1] = ... count[0][0] = 1

补充内容 (2016-1-28 11:34):
count[0] 怎么打出来一个括号被吃掉了
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 01:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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