聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

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

google 电话面试一面(已获二面)

[复制链接] |试试Instant~ |关注本帖
lchen77 发表于 2015-9-23 00:35:57 | 显示全部楼层 |阅读模式

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

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

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

x
国内小哥,人很好,上来啥也没说,直接上题目:
Given two string S and T with same length, the distance is defined as the number of positions in which S and T have different characters. Your task is to minimize this distance, by swap at most 2 characters (which means at most 1 swap) in S. Return the two index. If it is not necessary to swap, return -1, -1. Both S and T contain only lowercase alphabets. If there is multiple solutions, return anyone.

题目不难,只是要考虑case偏多,当时有点紧张,开始没有问清楚,做好后,经提醒,说要考虑有repeat,然后又接近于重新写一遍。
到最后花了大概10多分钟走test case,所以最后只做了一道题。

感觉面的不是很好,可能是国内小哥帮忙,最后还是给了二面,感恩中!

大米

评分

2

查看全部评分

本帖被以下淘专辑推荐:

stellari 发表于 2015-9-23 23:20:45 | 显示全部楼层

其实对于定长的character set来说,这解法已经可以称O(1)内存了。single可以用一个int[26]代替,而location也可以用int[26][26]代替。
回复 支持 1 反对 0

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 01:49:34 | 显示全部楼层
case 1: swap distance - 2. from: 1point3acres
case 2: swap distance -1
case 3: swao no use, do not need to swap
我当时是用两个map<char, vector<int>> one for S, one for T,  when S[i] != T[i], save both
然后对于scan map for s, 寻找T中是否有 best case,就是 swap 可以使得 distance - 2,
如果上述 scan 没有找到 best case 但是map T中有另外一个可以被换过来使得当前的S[i] == T[i],那就 是 case 2, swap 可以使得 distance -1,
如果 上面两种情况都没有找到,那就是说,swap 没有作用,甚至swap会增加 distance,所以就不swap
在处理case 1 的时候, 可以记录找到的case2,因为case 2 是case 1 的必须条件,
回复 支持 1 反对 0

使用道具 举报

Augustus 发表于 2015-9-23 00:47:50 | 显示全部楼层
楼主你是怎么做的?我觉得貌似只有暴力搜索或者用很大的空间存贮位置。。。
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-9-23 00:56:40 | 显示全部楼层
how to solve it?

for(int i = 0; i < size();i++){
for(int j = i + 1; j < size(); j++)
{
    swap(a[i], a[j]);
}
}

这样O(n^2)  每次 swap , 只能减少2,1,0, -1, -2是这样吗?
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 01:05:57 | 显示全部楼层
vector<int> editdistance(string s, string t)
{
        vector<int> ret(2,-1);. 牛人云集,一亩三分地
        vector<vector<int>> hash(26,vector<int>());
        for(int i=0; i<s.size(); i++) . Waral 博客有更多文章,
        {
                hash[s-'a'].push_back(i);. From 1point 3acres bbs
        }. 牛人云集,一亩三分地
        for(int i=0; i<t.size();i++)
        {. 一亩-三分-地,独家发布
                if(s!=t&&hash[t-'a'].size()>0)
                {
                        for(auto index:hash[t-'a'])
                        {
                                ret[0]=i;. 围观我们@1point 3 acres
                                ret[1]=index;
                                if(t[index]==s) return ret;
                        }
                }
        }
        return ret;
}

补充内容 (2015-9-23 01:08):
这个应该是O(N),虽然下面有两个for嵌套,但只可能比较N次。

补充内容 (2015-9-23 01:09):
好像也不对啊!
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-23 01:19:44 | 显示全部楼层
楼主牛逼 感谢分享
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 01:52:10 | 显示全部楼层
Augustus 发表于 2015-9-23 00:47
楼主你是怎么做的?我觉得貌似只有暴力搜索或者用很大的空间存贮位置。。。

已回复在楼下
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 01:52:30 | 显示全部楼层
cbwcs 发表于 2015-9-23 01:05
vector editdistance(string s, string t)
{
        vector ret(2,-1);

统一回复在楼下
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 01:54:09 | 显示全部楼层
lchen77 发表于 2015-9-23 01:49. visit 1point3acres for more.
case 1: swap distance - 2
case 2: swap distance -1
case 3: swao no use, do not need to swap

楼主,我的想法跟你基本一致,但不需要用到map,开个数组就好,因为都是lowcase的。
然后只需要记录S的char就好,然后从T开始每个字母遍历,我的代码复制上去的时候有点问题,很多index都看不到,但我test了下是可以的。
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 01:58:06 | 显示全部楼层
cbwcs 发表于 2015-9-23 01:54
楼主,我的想法跟你基本一致,但不需要用到map,开个数组就好,因为都是lowcase的。
然后只需要记录S的ch ...
. 一亩-三分-地,独家发布
嗯,思路确实差不多,不过
  for(int i=0; i<s.size(); i++)
        {
                hash[s-'a'].push_back(i);
        }
如果记录所有的idex,而不是当 S != T 的index,在你交换的时候,可能交换之前他们本身就是相等的。
所以为觉得是不是只记录不相等的更合理些?
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 02:00:47 | 显示全部楼层
lchen77 发表于 2015-9-23 01:58. 1point3acres
嗯,思路确实差不多,不过
  for(int i=0; i

万恶的下标,都没有啦。
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 02:08:26 | 显示全部楼层
lchen77 发表于 2015-9-23 02:00
万恶的下标,都没有啦。

是记录不相等的位置的index,只是我打进去的code都没有index了
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 02:29:13 | 显示全部楼层
cbwcs 发表于 2015-9-23 02:08
是记录不相等的位置的index,只是我打进去的code都没有index了

嗯,后来为明白啦。
楼主你的代码比为的简洁。
我当时那个code写的那就一个庞大。google doc 又不方便对齐,写的我自己都觉得难看。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-23 03:03:33 | 显示全部楼层
楼主, 给个example麻
回复 支持 反对

使用道具 举报

purplesky85 发表于 2015-9-23 03:48:47 | 显示全部楼层
cbwcs 发表于 2015-9-23 01:05. From 1point 3acres bbs
vector editdistance(string s, string t). 1point3acres
{. 1point3acres
        vector ret(2,-1);

你的代码时间复杂度是O(n^2)吧,
比如T = "aaaccc", S = "bbbaaa".
回复 支持 反对

使用道具 举报

purplesky85 发表于 2015-9-23 03:48:54 | 显示全部楼层
cbwcs 发表于 2015-9-23 01:05
. From 1point 3acres bbsvector editdistance(string s, string t)
{
        vector ret(2,-1);

你的代码时间复杂度是O(n^2)吧,
比如T = "aaaccc", S = "bbbaaa".
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 03:58:32 | 显示全部楼层
purplesky85 发表于 2015-9-23 03:48
. from: 1point3acres 你的代码时间复杂度是O(n^2)吧,. 1point 3acres 论坛
比如T = "aaaccc", S = "bbbaaa".

对,是O(N^2)
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-23 04:13:23 | 显示全部楼层
利用好lower case这个条件,应该可以O(1)空间,O(n)时间解决
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-23 14:21:33 | 显示全部楼层
坐看云起 发表于 2015-9-23 04:13. more info on 1point3acres
利用好lower case这个条件,应该可以O(1)空间,O(n)时间解决
. Waral 博客有更多文章,
能说说怎么做吗? 只想得出o(n^2)的方法...
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-23 17:39:34 | 显示全部楼层
<div style="font-family: 'Lucida Grande', 'Segoe UI', 'Apple SD Gothic Neo', 'Malgun Gothic', 'Lucida Sans Unicode', Helvetica, Arial, sans-serif; font-size: 0.9em; overflow-x: hidden; overflow-y: auto; margin: 0px !important; padding: 5px 20px 26px !important; background-color: rgb(255, 255, 255);font-family: 'Hiragino Sans GB', 'Microsoft YaHei', STHeiti, SimSun, 'Lucida Grande', 'Lucida Sans Unicode', 'Lucida Sans', 'Segoe UI', AppleSDGothicNeo-Medium, 'Malgun Gothic', Verdana, Tahoma, sans-serif; padding: 20px;padding: 20px; color: rgb(34, 34, 34); font-size: 15px; font-family: 'Roboto Condensed', Tauri, 'Hiragino Sans GB', 'Microsoft YaHei', STHeiti, SimSun, 'Lucida Grande', 'Lucida Sans Unicode', 'Lucida Sans', 'Segoe UI', AppleSDGothicNeo-Medium, 'Malgun Gothic', Verdana, Tahoma, sans-serif; line-height: 1.6; -webkit-font-smoothing: antialiased; background: rgb(255, 255, 255);"><h4 id="我想应该是可以做到o(n)的,只要能够" style="clear: both;font-size: 1.4em; font-weight: bold; margin: 0.99em 0px 0.66em;margin-top: 0px;"><a name="我想应该是可以做到o(n)的,只要能够" href="#我想应该是可以做到o(n)的,只要能够" style="text-decoration: none; vertical-align: baseline;color: rgb(50, 105, 160);"></a>我想应该是可以做到O(N)的,只要能够</h4><p style="margin-top: 0px;margin: 1em 0px; word-wrap: break-word;">抓住字符数<span><span class="MathJax_Preview" style="color: rgb(136, 136, 136);"></span><span class="MathJax" id="MathJax-Element-56-Frame" role="textbox" aria-readonly="true" style="display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px;"><nobr style="border: 0px; padding: 0px; margin: 0px; max-width: 5000em; max-height: 5000em; min-width: 0px; min-height: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;white-space: nowrap !important;-webkit-transition: none; transition: none;"><span class="math" id="MathJax-Span-234" style="width: 3.617em; display: inline-block;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span style="display: inline-block; position: relative; width: 2.951em; height: 0px; font-size: 122%;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span style="position: absolute; clip: rect(1.848em 1000em 2.864em -0.471em); top: -2.678em; left: 0em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span class="mrow" id="MathJax-Span-235" style="display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"><span class="mi" id="MathJax-Span-236" style="font-family: MathJax_Math; font-style: italic;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">n</span><span class="mo" id="MathJax-Span-237" style="font-family: MathJax_Main; padding-left: 0.278em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">=</span><span class="mn" id="MathJax-Span-238" style="font-family: MathJax_Main; padding-left: 0.278em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;">26</span></span><span style="display: inline-block; width: 0px; height: 2.678em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"></span></span></span><span style="border-left-width: 0em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.973em; vertical-align: -0.094em;display: inline; position: static; border: 0px; padding: 0px; margin: 0px; vertical-align: 0px; line-height: normal; text-decoration: none;-webkit-transition: none; transition: none;"></span></span></nobr></span><script type="math/tex" id="MathJax-Element-56">n=26</script></span>这个特点。比如开一个26x26的数组</p><pre style="border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-wrap: break-word; border: 1px solid rgb(204, 204, 204); overflow: auto; padding: 0.5em;"><code class="c++" data-origin="<pre><code class=&quot;c++&quot;>int P[26][26]
</code></pre>" style="border: 0px; display: block;font-family: Consolas, Inconsolata, Courier, monospace; font-weight: bold; white-space: pre; margin: 0px;border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-wrap: break-word; border: 1px solid rgb(204, 204, 204); padding: 0px 5px; margin: 0px 2px;font-size: 1em; letter-spacing: -1px; font-weight: bold;">int P[26][26]. from: 1point3acres
</code></pre><p style="margin: 1em 0px; word-wrap: break-word;">来储存之前出现的所有s,t的组合怎么样?</p></div>
-google 1point3acres
补充内容 (2015-9-23 17:41):
。。。不好意思,我不小心把整段HTML代码粘贴进来了。能否请版主删除此楼?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-22 12:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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