Google Interview : Find Crazy Distance Between Strings

Question

This Question was asked to me at the Google interview. I could do it O(n*n) ... Can I do it in better time. A string can be formed only by 1 and 0.

Definition:

X & Y are strings formed by 0 or 1

D(X,Y) = Remove the things common at the start from both X & Y. Then add the remaining lengths from both the strings.

For e.g.

D(1111, 1000) = Only First alphabet is common. So the remaining string is 111 & 000. Therefore the result length("111") & length("000") = 3 + 3 = 6

D(101, 1100) = Only First two alphabets are common. So the remaining string is 01 & 100. Therefore the result length("01") & length("100") = 2 + 3 = 5

It is pretty that obvious that do find out such a crazy distance is going to be linear. O(m).

Now the question is

given n input, say like

1111
1000
101
1100

Find out the maximum crazy distance possible.

n is the number of input strings. m is the max length of any input string.

The solution of O(n² * m) is pretty simple. Can it be done in a better way? Let's assume that m is fixed. Can we do this in better than O(n^2) ?

Answer 1

Put the strings into a tree, where 0 means go left and 1 means go right. So for example

1111
1000
101
1100

would result in a tree like

        Root
             1
          0     1
         0 1*  0  1
        0*    0*    1*

where the * means that an element ends there. Constructing this tree clearly takes O(n m).

Now we have to find the diameter of the tree (the longest path between two nodes, which is the same thing as the "crazy distance"). The optimized algorithm presented there hits each node in the tree once. There are at most min(n m, 2^m) such nodes.

So if n m < 2^m, then the the algorithm is O(n m).

If n m > 2^m (and we necessarily have repeated inputs), then the algorithm is still O(n m) from the first step.

This also works for strings with a general alphabet; for an alphabet with k letters build a k-ary tree, in which case the runtime is still O(n m) by the same reasoning, though it takes k times as much memory.

Answer 2

I think this is possible in O(nm) time by creating a binary tree where each bit in a string encodes the path (0 left, 1 right). Then finding the maximum distance between nodes of the tree which can be done in O(n) time.

Answer 3

This is my solution, I think it works:

1. Create a binary tree from all strings. The tree will be constructed in this way: at every round, select a string and add it to the tree. so for your example, the tree will be:

                     <root>
             <1>            <empty>
    <1>            <0>
   

   <1> <0> <1> <0> <1> <0> <0>

So each path from root to a leaf will represent a string.

1. Now the distance between each two leaves is the distance between two strings. To find the crazy distance, you must find the diameter of this graph, that you can do it easily by dfs or bfs.

The total complexity of this algorithm is: O(n*m) + O(n*m) = O(n*m).