DEV Community

loading...

Discussion on: A coding interview question asked at Google

Collapse
tails128 profile image
Tails128

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.