Интервью Google: найти сумасшедшее расстояние между строками

Ответ 1

Поместите строки в дерево, где 0 означает идти влево, а 1 означает идти вправо. Так, например,

1111
1000
101
1100

приведет к дереву, подобному

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

где * означает, что элемент заканчивается там. Построение этого дерева явно занимает O(n m).

Теперь мы должны найти диаметр дерева (самый длинный путь между двумя узлами, что является тем же самым, что и "сумасшедшее расстояние" ). Оптимизированный алгоритм, представленный там, попадает в каждый node в дереве один раз. Существует не более min(n m, 2^m) таких узлов.

Итак, если n m < 2^m, то алгоритм O(n m).

Если n m > 2^m (и мы обязательно имеем повторяющиеся входы), то алгоритм все еще O(n m) с первого шага.

Это также работает для строк с общим алфавитом; для алфавита с буквами k строят дерево k -ary, в этом случае время выполнения по-прежнему равно O (n m) по тем же аргументам, хотя оно занимает k раз больше памяти.

Ответ 2

Я думаю, что это возможно в O (нм) времени, создавая двоичное дерево, где каждый бит в строке кодирует путь (0 слева, 1 справа). Затем найдите максимальное расстояние между узлами дерева которое можно выполнить в O (n) времени.

Ответ 3

Это мое решение, я думаю, он работает:

• Создайте двоичное дерево из всех строк. Дерево будет построено таким образом: в каждом раунде выберите строку и добавьте ее в дерево. поэтому для вашего примера дерево будет:

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

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

Таким образом, каждый путь от корня до листа будет представлять собой строку.

• Теперь расстояние между каждыми двумя листьями - это расстояние между двумя строками. Чтобы найти сумасшедшее расстояние, вы должны найти диаметр этого графика, что вы можете сделать это легко с помощью dfs или bfs.

Общая сложность этого алгоритма: O (n * m) + O (n * m) = O (n * m).

Ответ 4

Чтобы получить ответ в O (nm), просто перебирайте символы всей строки (это операция O (n)). Мы сравним не более m символов, так что это будет сделано O (m). Это дает общее количество O (нм). Здесь С++-решение:

int max_distance(char** strings, int numstrings, int &distance) {
    distance = 0;
    // loop O(n) for initialization
    for (int i=0; i<numstrings; i++) 
        distance += strlen(strings[i]);

    int max_prefix = 0;
    bool done = false;
    // loop max O(m)
    while (!done) {
        int c = -1;
        // loop O(n)
        for (int i=0; i<numstrings; i++) {
            if (strings[i][max_prefix] == 0) {
                done = true; // it is enough to reach the end of one string to be done
                break;  
            }

            int new_element = strings[i][max_prefix] - '0';
            if (-1 == c)
                c = new_element;
            else {
                if (c != new_element) {
                    done = true;    // mismatch
                     break;
                }
            }
        }
        if (!done) {
            max_prefix++;
            distance -= numstrings;
        }
    }

    return max_prefix;
}


void test_misc() {
    char* strings[] = { 
        "10100",
        "10101110",
        "101011",
        "101"
    };

    std::cout << std::endl;
    int distance = 0;
    std::cout << "max_prefix = " << max_distance(strings, sizeof(strings)/sizeof(strings[0]), distance) << std::endl;
}

Ответ 5

Я думаю, что эта проблема похожа на "найти префикс для двух строк", вы можете использовать trie (http://en.wikipedia.org/wiki/Trie), чтобы ускорить поиск

У меня есть телефонное интервью в Google за 3 дня до этого, но, возможно, я потерпел неудачу...

Удачи вам

Ответ 6

Не знаю, почему использовать деревья, когда итерация дает вам такую ​​же большую вычислительную сложность O без сложности кода. в любом случае здесь моя версия этого в javascript O (mn)

var len = process.argv.length -2; // in node first 2 arguments are node and program file
var input = process.argv.splice(2);
var current;
var currentCount = 0;
var currentCharLoc = 0;
var totalCount = 0;
var totalComplete = 0;
var same = true;
while ( totalComplete < len ) {
        current = null;
        currentCount = 0;
        for ( var loc = 0 ; loc < len ; loc++) {
                if ( input[loc].length === currentCharLoc) {
                        totalComplete++;
                        same = false;
                } else if (input[loc].length > currentCharLoc) {
                        currentCount++;
                        if (same) {
                                if ( current === null ) {
                                        current = input[loc][currentCharLoc];
                                } else {
                                        if (current !== input[loc][currentCharLoc]) {
                                                same = false;
                                        }
                                }
                        }
                }
        }
        if (!same) {
                totalCount += currentCount;
        }
        currentCharLoc++;
}

console.log(totalCount);