Interview Question
Software Engineer / DevelopersIt's possible if you can store the last n/2 characters. The idea is to store a recursive hash of the first floor(n/2) characters and compare that to a reverse string hash of the last n/2 characters. To avoid collisions we cache the previous hash of the first {0,...,n-2/2} characters because it's highly unlikely that two different strings of length n will also have the same hashcodes at length n+1. If this is a concern, we can ensure that we use the results of several different hash functions.
Example string: abababa
c[0]: hash(a) == hash(a) [TRUE]
prevHash = ""
c[1]: hash(a) != hash(b) && prevHash == "" [FALSE]
c[2]: hash(a) == hash(a) && prevHash == ""
prevHash = hash(a)
c[3]: hash(hash(a)+b) != hash(hash(b)+a) && prevHash == hash(a) [FALSE]
c[4]: hash(hash(a)+b) == hash(hash(a)+b) && prevHash == hash(a) [TRUE]
prevHash = hash(hash(a)+b)
c[5]: hash(hash(hash(a)+b)+a) != hash(hash(hash(b)+a)+b) && prevHash == hash(a) [FALSE]
c[6]: hash(hash(hash(hash(a)+b)+a) == hash(hash(hash(hash(a)+b)+a) && prevHash == hash(a) [TRUE]
prevHash == hash(hash(hash(hash(a)+b)+a)
If space is not an issue , then take a stack and push input characters until there is no match with the top of the stack
- Coder November 25, 2010If match is there then pop that character.
If stack is empty upto the entry of characters then input so far is a palindrome
else not a palindrome so far .