How to compute palindrome from a stream of characters in sub-linear space/time?

Posted by wrick on Stack Overflow See other posts from Stack Overflow or by wrick
Published on 2011-02-10T22:40:50Z Indexed on 2011/02/10 23:25 UTC
Read the original article Hit count: 224

I don't even know if a solution exists or not. Here is the problem in detail. You are a program that is accepting an infinitely long stream of characters (for simplicity you can assume characters are either 1 or 0). At any point, I can stop the stream (let's say after N characters were passed through) and ask you if the string received so far is a palindrome or not. How can you do this using less sub-linear space and/or time.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about interview-questions