tusimple 店面面经 （general）

45 min 一个问题

Given a string "ABA"
get the sum value of

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

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

= 8

required time: O(n)

求米！

感觉是刷题网828，线性扫一遍，用一个hashtable记录每个字符前两次出现的index i和j，之后如果再在index k遇到该字符 x，可以直接sum += (k-j) * (j-i)来加上区间(i,k)所有包含该字符的substring（该区间只包含一个x，那个x在j上），最后再更新i和j；用 (k-j) * (j-i)来替代一次内部线性遍历，就可以从n2变成n

求hint。。

找出所有的substring至少要On2吧？

动态规划

请问lz哪天面试 多久出结果呢

差不多四天前，面试官给了比较多的hints写出来的，确实比较难

论坛匿名账号 发表于 2020/01/29 11:13:27
差不多四天前，面试官给了比较多的hints写出来的，确实比较难

层主能说下有什么hint吗？谢谢！（匿名貌似加不了米…

请问楼主是一面吗？电话是不是从东部某城市打过来的？有消息了吗？

ABA

1 使用hashmap记录每个元素出现的index
2 针对每一个元素（其所在index为k）找到其左边duplicate letter所在index i和右边duplicate letter所在index j
3 当前元素对最终结果的贡献为 (k - i) * (j - k)
累加即可

ABCBCBA
对第二个B，其拥有有效贡献的区段为 CBC
左边界可以为C or B
右边界可以为B or C
有效左边界个数 * 有效右边界个数 = 当前元素的总共贡献