Citadel 2019 summer SDE Intern OA

海投的citadel实习，刚做完OA，60分钟3道题，时间还是有些紧的

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

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

希望能帮到大家，也给自己攒攒人品

wy16119 发表于 2018-11-12 03:13
那楼主你是用什么结构存这个图的啊 能详细说下吗 另外第二题我是用O(n^2)做的  你说的那个O(n)方法能介绍 ...

我用的是邻接表，先用一个hashmap存下所有的字符串和index，然后对于每个字符串，分别删掉每个字符，看剩下的字符串是否在hashmap里。
第二题搜manacher palindromic substring，是个比较巧的方法，要统计个数的话就用hashset保存出现过的子串。

LaSeineFirenze 发表于 2018-11-11 14:08
这是个图不是树，所以会有一个节点多个root的情况。从入度为0的点开始做BFS就可以了

那楼主你是用什么结构存这个图的啊 能详细说下吗 另外第二题我是用O(n^2)做的  你说的那个O(n)方法能介绍下吗 给你加米了

wy16119 发表于 2018-11-11 13:37
楼主 第三题按照你的思路 我先用一个2D vector 存下来每个string对应的root 的 index  然后怎么处理这个2D  ...

这是个图不是树，所以会有一个节点多个root的情况。从入度为0的点开始做BFS就可以了

LZ你做的这个OA标题是叫 西塔戴尔和西塔戴尔证券 Campus Software Engineering Challenge (FALL) 么？

tsl665 发表于 2018-10-20 23:53
LZ你做的这个OA标题是叫 西塔戴尔和西塔戴尔证券 Campus Software Engineering Challenge (FALL) 么？

对，是叫这个

补充：OA做完4个工作日后收到电面，求加大米~~

楼主请问第二题你时暴力O(n^2)还是用马拉车O(n)去做的呀

dounainai 发表于 2018-11-10 14:03
楼主请问第二题你时暴力O(n^2)还是用马拉车O(n)去做的呀

当时用的马拉车，没试过暴力，不知道能不能过

LaSeineFirenze 发表于 2018-11-10 14:19
当时用的马拉车，没试过暴力，不知道能不能过

嗯嗯好的！！Hin感谢楼主！！

请问楼主 第二题马拉车是什么解法呀？

楼主 第三题按照你的思路 我先用一个2D vector 存下来每个string对应的root 的 index  然后怎么处理这个2D vector 呀？ 有些元素比如 ba 有两个root: bca & bda 这你是怎么处理的呀？