walmart sde intern面经

1月左右海投的， 一周前面的，挂了。 [hide=200] Given a string

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

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

p的时候面试官要求只能用O(1) 的空间复杂度。

可以模拟一个stack？就是拿一个指针指向栈顶元素，pop的时候直接往前回溯，并且用一个int记录碰到的右括号数量，每碰到一个左括号就减一，归零的时候就到顶了。因为pop的时候会做一次验证，前面的就保证是匹配的，只看栈顶即可。当然这么干时间复杂度会增加，最坏情况应该是O(N2)？

请问面前有做过hackerrank oa吗，之后多久联系的，我做了一段时间一直没理我不知道是不凉了

我没有过收到oa，我是投完之后一周左右直接收到hr邮件约面试的。只简单了聊了聊简历就开始问算法题了。 我也有同学1月底career fair和招聘会投的，1-2周前面试的，不过她好像因为投的前端面试全程问JavaScript....

很想知道怎么做到只用O（1）空间？只需要handle特殊的input吗？

如果能直接在input string上操作就可以O(1)了，本质上input string可以当作stack。如果input string是immutable感觉就稍微烦一些了。