仅限周四-周六三天
戳这里:一年VIP通行证额外打折$70,半年额外打折$30
戳这里:learn.1point3acres.com选课超过$500+折扣码thanks1p3a -> 15% off

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

有你有策略
微策略(MicroStrategy)
2019校园招聘火热进行中
E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 777|回复: 16
收起左侧

请教一道Google面经题

[复制链接] |试试Instant~
我的人缘0
Yada_Z 发表于 2018-11-10 14:16:39 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (10)
 
 
0% (0)  踩

2018(10-12月) 码农类General 硕士 合同工@Google - Other - 技术电面  | Other | fresh grad应届毕业生

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

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

x
题目很多人在面经里贴过:给定一个字符串s,问能不能转化成另一个字符串p,条件是每次转换要把所有相同的字母一起变动,例子如: abca(两个a一起变) -> dbcd(变c
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
false
请大家指点一下思路,或者说下证明过程,谢谢啦!

评分

参与人数 1大米 +1 收起 理由
maxnima + 1 赞一个

查看全部评分


上一篇:Transfix纽约startup公司面经
下一篇:报一个Airbnb的实习offer
我的人缘0
magicsets 发表于 2018-11-11 08:18:54 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (343)
 
 
1% (6)  踩
magicsets 发表于 2018-11-11 08:15
之前写了一个回帖,但是好像写太长被审核了.. 不知道要审核到什么时候,这里先分三个部分贴出来

这个题 ...

接上贴,现在证明定理1:如果A是B的真子集,那么s可以变换到p,当且仅当R是一个函数。

(1) 充分性
-baidu 1point3acres
这里使用反证法,假定s可以变换到p时,不妨设R不是一个函数,那么存在三个字符x, y, z,使得<x, y>和<x, z>都在R中且y != z —— 也就是楼主说的s中字符相等的几个位置,在p中对应的字符不一样的情况。

现在记s到p的每一步的变换得到的序列依次为 m(0) = s, m(1), m(2), ..., m(k-1), m(k) = p

那么,中间必然存在某个编号i,使得由m(i)到m(i+1)这一变换所定义出来的二元关系不是一个函数(这里再用一个反证法因为函数的复合必须仍是函数),也就是当前这步的变换将某个字符在不同的位置变成了不同的字符,这与题目所给的变换方法矛盾,得证。

(2) 必要性

假定R是一个函数,现在我们构造性证明s可以变换到p,也就是给出生成变换序列的方法。

首先,按如下方法构造有向图G:
-- 对于集合A中每个元素x,在图中创建一个对应的节点
-- 对于二元关系R中每个有序对 <x, y>,在图中连接有向边 x -> y

那么,由R是函数易知有如下关键性质:
(a) 有向图G中每个节点的出度至多为1

这里举个稍微复杂一点的例子,s = "abcda", p = bcabb",那么图上有4个节点 a, b, c, d,有四条边 a -> b, d -> b, b -> c, c -> a —— 注意这个图是有环的,每个节点可以有多条入边但至多只有一条出边。

此外性质(a)的一个推论是,G中每个连通分量里至多有一个环。

现在,我们对图G求所有强连通分量(SCC,Strongly Connected Components),记其将每个强连通分量都收缩到一个点所得到的凝聚图(condensation of graph G,必然是一个有向无环图)为G',那么有如下性质:
(b) G'中每个节点出度至多为1,如果其出度为1,那么必然对应G中单个节点;如果其出度为0,那么要么对应G中某个单点,要么是由G中一个“单环”收缩而来 —— 这一性质由上面所说性质(a)易证。
-baidu 1point3acres
然后对凝聚图G'进行反向拓扑排序,并依次进行变换即可。这里还是使用上面的例子s = "abcda", p = "bcabb",那么图G'中有两个强连通分量,分别记为 X = { d }, Y = { a -> b -> c -> a },边为 X -> Y,所以反向拓扑序为先Y然后X,变换时根据上面的性质(b)我们知道有两种情况:
--
(i) 强连通分量对应G中一个环:由于集合A是集合B的真子集,所以用额外元素来破环即可(类似于swap时用的“tmp”变量)。

例如上面例子中对于Y = { a -> b -> c -> a }这个环,可以用任意额外元素X执行变换:
c -> X
b -> c
a -> b
X -> a

(ii) 强连通分量对应G中一个点:直接根据其出边进行对应变换即可

例如上面例子中对于X = { d }这个点,直接执行变换:
d -> b

所以对于s = "abcda", p = bcabb"的例子,其完全的变换序列就是:
--
c -> X: "abXda"
b -> c: "acXda"
a -> b: "bcXdb"
X -> a: "bcadb"
d -> b: "bcabb"

最后,要证明上述构造方法的正确性的话,关键点在于反向拓扑排序后,每组强连通分量的变换结果将不会被后续的“上游”变换所修改,这里就略去具体证明了。
回复

使用道具 举报

我的人缘0
mmyn 发表于 2018-11-10 20:03:07 来自一亩三分地官方APP | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (126)
 
 
0% (0)  踩
按你看位置的想法就是LC原题了,这道题的问题在于你在变化的过程中需要用到辅助字母,所以多了一个限制,在你判断位置的基础上要检
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
大于等于环的数量,这是比LC原题要多考虑的点
回复

使用道具 举报

我的人缘0
wofaint 发表于 2018-11-10 15:59:17 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
应该是记录一个 map(char to char),
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
则返回 false。
回复

使用道具 举报

我的人缘0
2018moment 发表于 2018-11-10 15:15:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
我的想法是如果 abca 把 b 改成 a 之后得到 aaca, 再次变换的时候,3个a都需要同时修改的话,那么说明每次变换只可能会增加联动的字符的数量,但是绝对不会减少。所以可
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
然后判断 dced 中{0,3}两个位置上的字母是不是相同的。
回复

使用道具 举报

我的人缘0
lzyprint 发表于 2018-11-10 15:37:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
你想到的没问题啊,s中每个字符,对它出现的所有位置,p在这些位置上的字符一定相同,否则返回false
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
些位置上由不同字符的话永远也变不出p。
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-11-10 18:42:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (343)
 
 
1% (6)  踩
这个问题有两点要回答,一是存在性(能不能),二是如果存在的话怎么变换(构造变换序列),这两点下面都展开写一下。

首先可以只考虑s和p长度相同的情况,因为长度不同是肯定是无法变换的。

现在,定义集合A为字符串s和p中所有字符的集合,定义集合B为变换中所允许使用的所有字符的集合。
--
例如s = "abca", p = "dced",那么 A = { a, b, c, d, e }
-baidu 1point3acres
而常见的B的设定就是所有英文字母的集合 { a .. z, A .. Z }。当然也可以有其他限定方式,比如只能是小写字母,亦可以扩大到使用0-255的ASCII取值 —— 这不影响我们讨论时的一般性,但有一点可以确定的是A一定是B的子集。

下面是最关键的一步:定义二元关系 R = { <x, y> | x, y是字符s和p中在每个对应位置上的元素 }。
--
还是上面的例子,我们有 R = { <a, d>, <b, c>, <c, e> }

然后我们有如下存在性定理:

定理1:如果A是B的真子集,那么s可以变换到p,当且仅当R是一个函数。

定理2:如果A与B相等,那么s可以变换到p,当且仅当R是一个函数并且其不是一个除恒等(identity)以外的双射函数。

. check 1point3acres for more.
******************************************************************************************************

定理1的证明
--
(1) 充分性

这里使用反证法,给定了s可以变换到p,不妨设R不是一个函数,那么存在三个字符x, y, z,使得<x, y>和<x, z>都在R中 —— 也就是楼主说的s中字符相等的几个位置,在p中对应的字符不一样的情况。

现在记s到p的每一步的变换得到的序列依次为 m(0) = s, m(1), m(2), ..., m(k-1), m(k) = p

那么,中间必然存在某个编号i,使得由m(i)到m(i+1)这一变换所定义出来的二元关系不是一个函数(这里再用一个反证法因为函数的复合必须仍是函数),也就是当前这步的变换将某个字符在不同的位置变成了不同的字符,这与题目所规定的一对一的变换方法矛盾,得证。

(2) 必要性

假定R是一个函数,现在我们构造性证明s可以变换到p,也就是给出生成变换序列的方法。

首先,按如下方法构造有向图G:
-- 对于集合A中每个元素x,在图中创建一个对应的节点
-- 对于二元关系R中每个有序对 <x, y>,在图中连接有向边 x -> y. check 1point3acres for more.

那么,由R是函数易知有如下关键性质:
(a) 有向图G中每个节点的出度至多为1

这里举个稍微复杂一点的例子,s = "abcda", p = bcabb",那么图上有4个节点 a, b, c, d,有四条边 a -> b, d -> b, b -> c, c -> a —— 注意这个图是有环的,每个节点可以有多条入边但至多只有一条出边。

此外性质(a)的一个推论是,G中每个连通分量里至多有一个环。

现在,我们对图G求所有强连通分量(SCC,Strongly Connected Components),记其将每个强连通分量都收缩到一个点所得到的凝聚图(condensation of graph G,必然是一个有向无环图)为G',那么有如下性质:
(b) G'中每个节点出度至多为1,如果其出度为1,那么必然对应G中单个节点;如果其出度为0,那么要么对应G中某个单点,要么是由G中一个“单环”收缩而来 —— 这一性质由上面所说性质(a)易证。

然后对凝聚图G'进行反向拓扑排序,并依次进行变换即可。这里还是使用上面的例子s = "abcda", p = "bcabb",那么图G'中有两个强连通分量,分别记为 X = { d }, Y = { a -> b -> c -> a },边为 X -> Y,所以反向拓扑序为先Y然后X,变换时根据上面的性质(b)我们知道有两种情况:
--
(i) 强连通分量对应G中一个环:由于集合A是集合B的真子集,所以用额外元素来破环即可(类似于swap时用的“tmp”变量)。

例如上面例子中对于Y = { a -&
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
边并做一步变换X -> Y,然后不管X所在的连通分量,将X当做额外字符并按反向拓扑序处理图G中其他连通分量,最后处理X所在的连通分量时(注意到已经破环了),按反向拓扑序变换即可。

例如前面给的tricky例子 s = "abcde", p = "badcc",易知满足(a.2),其中W = "c",X = "d", Y = "e",那么变换序列如下:
--
先断开边X(字符"d") -> W(字符"c")

并做一步X变换到Y(字符"e")
d -> e: "abcee"

然后将X作为额外字符,处理其它连通分量,也就是{ a -> b -> a }
a -> d: "dbcee"
b -> a: "dacee"
d -> b: "bacee"

最后回到X所在的连通分量,注意到断开X -> W的边后剩下部分为e -> c -> d,所以按反向拓扑序即
c -> d: "badee"
e -> c: "badcc"

补充内容 (2018-11-12 06:37):. 1point3acres
定理2需要修改一下,首先明确一下这里所说的函数是以s的字符集合作为定义域、p的字符集合作为值域考虑的,然后当A=B时,可以进行变换的另一个条件是 R是一个函数且s的字符集合是A的真子集 —— 参考13楼的讨论
回复

使用道具 举报

我的人缘0
 楼主| Yada_Z 发表于 2018-11-11 00:23:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (10)
 
 
0% (0)  踩
mmyn 发表于 2018-11-10 20:03
按你看位置的想法就是LC原题了,这道题的问题在于你在变化的过程中需要用到辅助字母,所以多了一个限制,在 ...

我暂时觉得这层楼主说的比较对,我也意识到环的问题,一个环需要一个辅助字母来转换,但在想怎么证明只要辅助字母数量大于等于环的数量必然可以找到一个方案转换过去,把自己绕懵了也想不到构造一个转化的方案...

补充内容 (2018-11-11 01:11):
我觉得先检查本来就相等的对应位置是不是相等,否则直接return false;
然后检测转换结果的string是不是26个字母都用完而且存在环。若这样必然会导致“联动”,return false;
然后再return true
回复

使用道具 举报

我的人缘0
mmyn 发表于 2018-11-11 02:02:25 来自一亩三分地官方APP | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (126)
 
 
0% (0)  踩
Yada_Z 发表于 2018/11/11 00:23:45


我暂时觉得这层楼主说的比较对,我也意识到环的问题,一个环需要一个辅助字母来转换,但在想怎么证明只要辅助字母数量大于等于环的数量必然可以找到一个方案转换过去,把自己绕懵了也想不到构造一个转化的方案....

每个字母只能映射成某一种字母,但是可以被不同字母映射,所以你想想是不是不同的环是没办法拥有公共部分的,因为没有一个节点能分岔出去,在此基础上,辅助字母也会有只能映射成一种字母的限制,所以不同的环没有公共字母意味着他们需要的辅助字母也无法相同
回复

使用道具 举报

我的人缘0
magicsets 发表于 2018-11-11 08:15:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (343)
 
 
1% (6)  踩
之前写了一个回帖,但是好像写太长被审核了.. 不知道要审核到什么时候,这里先分三个部分贴出来

这个题目有些并不trivial的情况 —— 先做个练习题,考虑s = "abcde", p = "badcc"的情况,如果只让使用a、b、c、d、e作为中间字符,那么是否有可行的变换序列?
(这个问题在后面会有解答,答案是有)

言归正传,下面先给出存在性定理。

首先可以只考虑s和p长度相同的情况,因为长度不同是肯定是无法变换的。
. 1point3acres
然后,定义集合A为字符串s和p中所有字符的集合,定义集合B为变换中所允许使用的所有字符的集合。
--
例如s = "abca", p = "dced",那么 A = { a, b, c, d, e }

而常见的B的设定就是所有英文字母的集合 { a .. z, A .. Z }。当然也可以有其他限定方式,比如只能是小写字母,亦可以扩大到使用0-255的ASCII取值 ——
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
al_approach)

接下来两个回帖分别写一下定理1和定理2的证明,其中包含的构造性证明描述了生成变换序列的方法 —— 三个主要步骤:(1) 由映射关系构造有向图,(2) 求强连通分量(SCC,Stronly Connected Component),(3) 对强连通分量的凝聚图进行反向拓扑排序,然后依序生成每一步变换
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

手机版|小黑屋|联系我们&一亩三分地论坛声明

GMT+8, 2018-11-22 18:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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