1
$\begingroup$

Interview question.

Prove if all characters in the transformation from string A to string B are in some cycles then you cannot perform such transformation and you would need an additional character per cycle.

The above was the last question in the interview but here is what went on:

You are given two strings A and B. You need to return True if you can transform string A to string B one character at a time and you are only allowed to use the characters in the string A and B. E.g. foo translated to baa means that f -> b, o -> a. No additional characters can be used.

Another example where you will return True: A = ghijk, B = hkjki

A = ghijk

Transformation: j -> h gives ghihk 

Transformation: i -> j gives ghjhk

Transformation: k -> i gives ghjhi

Transformation: h -> k gives gkjki

Transformation: g -> h gives hkjki = B

An example where you return False: cannot convert abc to bca. Cannot convert abc to bac also. This is because abc -> bbc using a->b transformation. Then b translated to c would give ccc and you will not be able to get bca.

The following is the algorithm that we came up with: If both the strings are the same I returned True i.e. abc can be converted to abc.

If there exist cycles where all the vertices form part in at least one cycle then return False else return True. E.g. abc cannot be converted to bca because a maps to b b maps to a hence a cycle and a maps to a which is a self loop another cycle. foo can be mapped to baa because there is no cycle.

ghijk can be mapped to hkjki where g -> h -> k -> i -> j ->k. There is a cycle only from k to i to j to k but the other characters g and h are not part of a cycle.

Note that converting abc to bca can be done by having one more character i.e. abc -> xbc -> xba -> xca -> bca where you have the additonal transformation a -> x -> b

Was asked to prove: Prove if there exist cycles where all the vertices form part in at least one cycle then return False else return True. Prove whether you need an additional character per cycle if you return False.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

If you have even one cycle $l_1 \to l_2 \to \ldots \to l_k \to l_1$, then, since I don't see an option to transform two letters at once, inevitably one of the letters [in the loop/cycle] will be transformed first. W.l.o.g. assume this is $l_1$. Then at the moment you are ready to transform $l_2$ you can't distinguish between original $l_2$ and transformed $l_1$.

Adding one character to the loop helps, but only if it is not a part of some other transformation, i.e. if there exists $l_1 \to l_2$, you can't have a rule $l_3 \to l_1 \to l_4$.

Let say, you have a loop $l_1 \to l_2 \to \ldots \to l_k \to l_1$, then you add the new rule $l_1 \to x \to l_2$. And apply $l_1 \to x$ first, then all the rules in the loop from end to start. $l_k \to l_1$, then $l_{k-1} \to l_k$, etc. then $l_2 \to l_3$ and finally $x \to l_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .