techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

constant time comparison of two strings represented as bits

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.

Neophyte Send private email
Wednesday, June 23, 2010
Given inputs x and y, the condition holds if and only if x & ~y and y & ~x each consist of one bit (is a power of 2) and (x & ~y) > (x & y) and (y & ~x) > (y & x).
d Send private email
Wednesday, June 23, 2010
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.
Neophyte Send private email
Thursday, June 24, 2010

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz