一亩三分地论坛

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

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

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

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

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

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

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

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,所以最后只做了一道题。

感觉面的不是很好,可能是国内小哥帮忙,最后还是给了二面,感恩中!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
大米
. 鍥磋鎴戜滑@1point 3 acres

评分

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. visit 1point3acres.com for more.
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,
.1point3acres缃如果上述 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++)
        {
                hash[s-'a'].push_back(i);
        }
        for(int i=0; i<t.size();i++). From 1point 3acres bbs
        {
                if(s!=t&&hash[t-'a'].size()>0). From 1point 3acres bbs
                {.1point3acres缃
                        for(auto index:hash[t-'a'])
                        {
                                ret[0]=i;
                                ret[1]=index;
                                if(t[index]==s) return ret;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }
                }
        }
        return ret;
}. 1point3acres.com/bbs

补充内容 (2015-9-23 01:08):. 鍥磋鎴戜滑@1point 3 acres
这个应该是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
楼主你是怎么做的?我觉得貌似只有暴力搜索或者用很大的空间存贮位置。。。

已回复在楼下
回复 支持 反对

使用道具 举报

 楼主| 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
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,在你交换的时候,可能交换之前他们本身就是相等的。. From 1point 3acres bbs
所以为觉得是不是只记录不相等的更合理些?
回复 支持 反对

使用道具 举报

 楼主| lchen77 发表于 2015-9-23 02:00:47 | 显示全部楼层
lchen77 发表于 2015-9-23 01:58
嗯,思路确实差不多,不过
  for(int i=0; i
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
万恶的下标,都没有啦。
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 02:08:26 | 显示全部楼层
lchen77 发表于 2015-9-23 02:00. 鍥磋鎴戜滑@1point 3 acres
万恶的下标,都没有啦。

是记录不相等的位置的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
vector editdistance(string s, string t)
{
        vector ret(2,-1);

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

使用道具 举报

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

你的代码时间复杂度是O(n^2)吧,. 鍥磋鎴戜滑@1point 3 acres
比如T = "aaaccc", S = "bbbaaa".
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 03:58:32 | 显示全部楼层
purplesky85 发表于 2015-9-23 03:48
你的代码时间复杂度是O(n^2)吧,
比如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
利用好lower case这个条件,应该可以O(1)空间,O(n)时间解决

能说说怎么做吗? 只想得出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]
</code></pre><p style="margin: 1em 0px; word-wrap: break-word;">来储存之前出现的所有s,t的组合怎么样?</p></div>
. 1point3acres.com/bbs
补充内容 (2015-9-23 17:41):
。。。不好意思,我不小心把整段HTML代码粘贴进来了。能否请版主删除此楼?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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