## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
Assume, you have two strings say ABC and ABF(the individual characters within the strings will be in sorted order) represented as:
ABC=0...00000111(represented in 64 bits) ABF=0...00100011(represented in 64 bits) Similarly, the inputs can be ABD and BDE, AFG and BGK etc etc So any string as input will be of maximum 64. You have to give a constant time bitwise algorithm which tells you if both strings differ only in the last character. May be this is easy but somehow I am not able to come up with an answer in constant time. Any Help greatly appreciated. Thanks
So, basically you first find the exact character bit positions which are different in both string using x&~y and y&~x and then ensure that it is always the last character by the check x&~y>x&y and y&~x>y&x.
For any strings which have 2 characters different, we discard by checking power of two. I think this looks perfect. Many Thanks d. |

Powered by FogBugz