DEV Community


Discussion on: A coding interview question asked at Google

tails128 profile image

I think a stack-based solution is the most efficient and readable method, to be fair...

If we think about the complexity it should be around O(n)
(n (to compute first) + n (to compute second) + n(to go once over both))
Which is ofc not as good as the O(log(n)), but I am not sure there's a way to cut times.

Also we can do a sneaky trick such as

if(stack1.length !== stack2.length) {
  return false;

But... to be 100% correct, in order to determine if this is helpful or just added time for our average case we would need to know the context a bit more in depth.