姑姑电面

十分钟前刚结束。高频。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

下面我把自己的整个doc po出来，不好意思，积分得稍微高一点儿。未必是对的，尤其是最后一个follow up，是第二问基础上临时往里凑代码解决，未必照顾到所有的问题。

您好！
本帖隐藏的内容需要积分高于 250 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 250 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2018-11-16 05:50):
11/15更新，电话通知onsite了，我打算安排在12月7号。cruise的电面也挂了……只剩下google了。我自己行业的synopsys积极地抛出了橄榄枝，要我onsite面仨组……实习过的cadence说，你不用onsite，电话就能解决……

补充内容 (2018-11-16 05:51):
总结一句，不想去的白给啊！要拿google我得拼命了555555

用一个unordered_map， key是string b里的char, value 是这个char的位置。然后traverse string a, 用map找到当前char的位置然后检查下一个是否和当前下一个的一样，如果一样 接着往后查，不一样就退出 查看我们match的start和end的位置，然后我们知道string b的长度，在start前和start后加‘#’，这样把a走一遍就可以了。前提是b里面的char不重复，重复的话我们可以用multimap.

可以做二分搜索，因为index是排好序的，最差时间是O(MlogN) M 是字符串a的长度，N是字符串b的长度

foryousee 发表于 2018-11-10 11:22
可以做二分搜索，因为index是排好序的，最差时间是O(MlogN) M 是字符串a的长度，N是字符串b的长度

唉……当时没想到……不知道interviewer最后会给什么样的评价

Heinrich 发表于 2018-11-10 13:00
唉……当时没想到……不知道interviewer最后会给什么样的评价

据说还有更优解。听说什么用KMP可以到更低的复杂度。反正我只能到binary search了

感谢楼主
第二问没太懂，为何a: zaza，b: baz， 返回的是 {"##z", "#az", "#a#"} 呀

这个应该用dfs吧？

或者trie树 把b放到trie树 搜索a