回复: 34
跳转到指定楼层
上一主题 下一主题
收起左侧

Google电面

全局:

2019(1-3月) 码农类General 硕士 全职@google - 猎头 - 技术电面  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
今天下午面的Google 全职电面 面试官感觉像个国人大哥 挺nice的 题也不难 但是一开始想复杂了

给两个长度一样的string A,B  把他们对齐切一刀 这样就得到了A1 A2 B1 B2 四个substring
写一个func check 能不能找到这一刀  A1和B2 拼起来
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
的时候把速度放慢了点 顺带着解释 虽然也没啥好解释的 就尽量interact 所以后面没啥时间 followup时候就讲了idea怎么实现 没具体写code了 希望能给个旅游的机会吧


评分

参与人数 8大米 +38 收起 理由
vivivic + 2 给你点个赞!
sdnbig + 3 写的仔细!
sanmi0814 + 3 给你点个赞!
alexws + 3 给你点个赞!
Scala688 + 3 给你点个赞!

查看全部评分


上一篇:1/31/2019 Google MTV onsite
下一篇:Akuna Quant Dynamic OA

本帖被以下淘专辑推荐:

全局:
这道题考双指针的灵活用法。先只考虑a1b2的情况(另外那种情况a2b1是对称的,互换一下s1和s2就可以了。)双指针,一个指向s1的左边,一个s2的右边,同时扫,如果字母不同,就考虑切割,切割完有两种可能路径,可以选择s2那个指针跳到s1去,也可以反过来。这两种路径只要一个能走通就返回true,否则false。follow up比较类似,不过现在有两次切割机会。当字母不同时用掉第一次切割,s2那个指针跳到s1去,或者反过来也可以。这时候问题变成了找两个指针指向的这段substring中包含首(尾)字母最长palindrome的问题了。这个问题应该有o(n)解吧?高手讲解一下?
回复

使用道具 举报

推荐
henryqcy 2019-2-7 20:37:38 | 只看该作者
全局:
follow up是有O(n)的解的,关键点是不一样了选A还是B切,然后切在什么地方。
切肯定是以不一样了的那个char开始的在长的回文除,而找longest prefix parlindrome可以先flip string,然后用KMP找longest identical suffix,因为回文flip以后和原本的回文还是一样的。参考里扣214
回复

使用道具 举报

推荐
vividlau 2019-2-8 04:20:24 | 只看该作者
全局:
follow up 用 马拉车 来处理剩下的字符串。
比如 A 切在 index 3, 我们对A[3]之后的跑马拉车,然后马拉车中,遍历每个中心,遇到每个中心对应的回文半径能覆盖到A[4]的, 则证明这是从A[4]开始的最长回文,更新最长回文。
对B也做一遍,比较两个最长回文然后判断怎么切。
回复

使用道具 举报

全局:
Follow up是枚举所有切法,然后选出最长的palindrome ?
回复

使用道具 举报

🔗
hongjiw 2019-2-2 15:54:50 | 只看该作者
全局:
对其切的话怎么样用two pointer呢? 难道不需要枚举所有的切法吗 求提示
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
 楼主| Srrrr 2019-2-3 03:33:48 | 只看该作者
全局:
wtcupup 发表于 2019-2-2 15:32
Follow up是枚举所有切法,然后选出最长的palindrome ?

就是如果A B的切口可以不在同一个地方 然后找拼出来的最长的palindrome 我当时给的解法也是双指针 感觉不需要枚举呀
回复

使用道具 举报

🔗
 楼主| Srrrr 2019-2-3 03:38:05 | 只看该作者
全局:
hongjiw 发表于 2019-2-2 15:54
对其切的话怎么样用two pointer呢? 难道不需要枚举所有的切法吗 求提示

楼下有个大哥的解释 和我当时想的差不多 就主要是因为这个新生成的palindrome 如果存在的话 他的头和尾一定一个来自A的头(尾), 一个来自B的头(尾) 所以双指针指向A B的两端 然后往中间扫
回复

使用道具 举报

🔗
 楼主| Srrrr 2019-2-3 03:44:06 | 只看该作者
全局:
cheerier 发表于 2019-2-3 00:42
不对齐切的话,l 从A的左边开始,r从B的右边开始 然后一起扫? 如果l和r对应的char相同则继续,不相同就是 ...

不相同的话 就必须切了 但是切A 还是切B 此时还是不一定的 比如  “ABCDCF”  “ZZZZBA”  这样“AB” “BA”之后就肯定需要选一个String切一刀了 其实可以发现 String A 还可以往后 因为“CDC” 是个 parlindrome 所以String A 可以等到C之后在切  同理 String B 也可以往后 “ZZZZ” 也是个parlindrome 这时候 两者相比我们取长的 就是“ZZZZ” 这样新组的parlindrome 就是 “ABZZZZBA” 就肯定最长了 我当时是这么说的 不知道会不会有啥edge case
回复

使用道具 举报

🔗
 楼主| Srrrr 2019-2-3 03:50:12 | 只看该作者
全局:
richpanda 发表于 2019-2-3 02:57
这道题考双指针的灵活用法。先只考虑a1b2的情况(另外那种情况a2b1是对称的,互换一下s1和s2就可以了。)双 ...

嗯 和我当时说的差不多 但是followup里其实不需要s1的指针跳到s2 比如
“ABCDCF”  
“ZZZZBA”

s1 指针在2, s2指针在3
就直接s1开始找以2为首最长的parlindrome
s2开始找以3为尾最长的parlindrome
然后比下俩parlindrome的长度就成了
回复

使用道具 举报

🔗
peauxseches 2019-2-3 04:02:17 | 只看该作者
本楼:
全局:
祝好运
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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