一亩三分地论坛

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

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

Google电面(雪崩)

[复制链接] |试试Instant~ |关注本帖
deephama001 发表于 2015-6-9 07:14:03 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
Full-time 第一家,上周Google HR发来邮件,简短的聊了一下就安排了今天的电面。刚面完,雪崩。。。45分钟就答了一道题。。。
面试的应该是个国人,上来都没寒暄,直接写题:Word break problem (Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. E.g. Input "iamgoingtoworktoday" dict {i, am, going, to, work, today, day}, Google一搜便知),改成了输出space seperated string。
刚看到题脑子一片空白,只能想到简单recursion的算法,试着说了一下思路,对面半天就回了一个ok。知道肯定不optimal,巨尴尬,硬着头皮写完,他让分析复杂度,我说O(n^2),他问do you think it is really that simple? 吓到了,然后写了个aaaaaab的worst case,估计是O(n!),说完了他半天没动静。。。这哥们话非常少,必须主动催才有回复。然后我俩纠结了一会,我又硬着头皮问他要hint,他就说了一句让我想想有多少种substring的可能,我说O(n!),感觉他觉得我说的不对但是又继续不说话。。。最后我已经要疯了,说回复杂度是O(n^2),他终于放过我了。
放下电话就知道肯定没戏了,上网搜了下发现是经典DP,就是把每层recursion的结果存hashmap就解决了。。。。这大哥估计是想给我送分,结果我完全掉坑里了。郁闷死了。。。
PS. 地里的各位大神能不能帮我分析下naive算法和DP算法的时空复杂度,这是我的分析,供大家参考. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Naive: worst case 时间复杂度T(n) = T(n - 1) + T(n - 2) + ... + T(1) => T(n) = O(2^n), 空间复杂度S(n) = O(n)因为最多会递归n - 1层
DP: 空间复杂度应该是O(n)因为要用hashmap存n - 1个中间结果,时间复杂度目前还没想明白。。。-google 1point3acres

PPS: 各位都怎么应付这类话少的面试官啊?

评分

4

查看全部评分

ethan11015 发表于 2015-6-9 07:24:57 | 显示全部楼层
只能默默承受吧....
回复 支持 反对

使用道具 举报

nikee 发表于 2015-6-9 08:06:35 | 显示全部楼层
遇到话少的面试官真的会很难受。lz第一家就面google好熊!!
回复 支持 反对

使用道具 举报

coolzai 发表于 2015-6-9 08:19:01 | 显示全部楼层
周三就要电面google了好紧张。。。希望不会遇到这么沉默的面试官
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-6-9 08:29:50 | 显示全部楼层
遇到给你Leetcode原题如果还是不会的话就没办法了。。毕竟这是最好的放水方式了
回复 支持 反对

使用道具 举报

 楼主| deephama001 发表于 2015-6-9 08:45:49 | 显示全部楼层
57656929bb 发表于 2015-6-9 08:29
遇到给你Leetcode原题如果还是不会的话就没办法了。。毕竟这是最好的放水方式了

最郁闷的是这题我做过,但是在你说之前我完全想不起来。。。
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-6-9 08:50:49 | 显示全部楼层
deephama001 发表于 2015-6-9 08:45
最郁闷的是这题我做过,但是在你说之前我完全想不起来。。。

多刷几遍,楼主加油!
回复 支持 反对

使用道具 举报

asdfyou6 发表于 2015-6-9 09:04:09 | 显示全部楼层
放水不够彻底

要我出就two sum+另外一道同等难度的

还有楼主,你不会打开leetcode直接抄么
回复 支持 反对

使用道具 举报

bluestarwing 发表于 2015-6-9 09:04:32 | 显示全部楼层
LZ是海投的还是请朋友refer的?大概是什么时候投的呢?
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-9 09:31:17 | 显示全部楼层
AC过的解法
  1. public class Solution {
  2.     /**
  3.      * @param s: A string s 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  4.      * @param dict: A dictionary of words dict
  5.      */
  6.     public boolean wordBreak(String s, Set<String> dict) {. From 1point 3acres bbs
  7.         // write your code here
  8.         boolean[] t = new boolean[s.length()+1];
  9.         t[0] = true;
  10.         
  11.         for(int i = 0; i < s.length(); i++)
  12.         {
  13.             if(!t[i])
  14.             {
  15.                 continue;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  16.             }
  17.             
  18.             for(String a : dict)
  19.             {
  20.                 int len = a.length();
  21.                 int end = i + len;
  22.                
  23.                 if(end > s.length()).鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                 {
  25.                     continue;
  26.                 }
  27.                
  28.                 if(t[end])
  29.                 {
  30.                     continue;
  31.                 }
  32.                 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.                 if(s.substring(i, end).equals(a)).鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                 {. from: 1point3acres.com/bbs
  35.                     t[end] = true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.                 }
  37.             }
  38.         }. From 1point 3acres bbs
  39.         return t[s.length()];
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  40.     }
  41. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| deephama001 发表于 2015-6-9 09:50:44 | 显示全部楼层
bluestarwing 发表于 2015-6-9 09:04
LZ是海投的还是请朋友refer的?大概是什么时候投的呢?

都没有,Google HR给我发的邮件,本来没准备现在去面的,确实题刷的不够
回复 支持 反对

使用道具 举报

KOoshebe 发表于 2015-6-9 10:11:53 | 显示全部楼层
话少真的会让气氛紧张,影响仕途
回复 支持 反对

使用道具 举报

 楼主| deephama001 发表于 2015-6-9 10:56:52 | 显示全部楼层
KOoshebe 发表于 2015-6-9 10:11
话少真的会让气氛紧张,影响仕途

是的!就像我在对着空气讲题,超级尴尬
回复 支持 反对

使用道具 举报

summerjx 发表于 2015-6-9 11:34:23 | 显示全部楼层
deephama001 发表于 2015-6-9 10:56
是的!就像我在对着空气讲题,超级尴尬

我还遇到过讲了半天都没有反应的。。最后逼得我问are you still there
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-9 17:42:58 | 显示全部楼层
DP解法就是用一个数组DP,其中. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

DP[i] = (substring[0, i]能够被segment)? 1 : 0。. From 1point 3acres bbs

对于每一个位置i,检查[0, i-1]内的所有的j,如果能找到一个j使得substring[0, j]能够被segment(即DP[j] = 1),且substring[j+1, i]是一个词典中的词,则表示substring[0, i]也能够被segment。检查一个substring[0, j]是否能够被segment,和检查substring[j+1, i]是否为单词都需要O(1). 判断每个位置i时,总共要重复检查前面i-1个位置。所以平均在每个位置上都花掉O(N)时间,总共在N个位置上花掉O(N^2)时间。

这样的面试官确实对面试者的心理状态要求比较高。他不多说,你就尽量自己多说,不要冷场就好。虽然他可能没有什么反应,但是你说的话他都会听到并且心中有数的。
回复 支持 反对

使用道具 举报

Rain 发表于 2016-6-23 03:05:59 | 显示全部楼层
stellari 发表于 2015-6-9 03:42
DP解法就是用一个数组DP,其中. from: 1point3acres.com/bbs

DP = (substring[0, i]能够被segment)? 1 : 0。

stellari大神你好
你讲的是用DP检查那个String能否segment, 输出boolean。这个是n^2
但是如果这里要求"输出space separated string", 就只能用DFS按照Word Break II 解法来做了吧?

补充内容 (2016-6-22 13:45):
哦nvm... 用DP 加memory可以简化
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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