алгоритмы

[Alex_cs_gsp]

1) в строке хранятся любые числа с любым основанием системы счисления.
2) ASCII код однозначно определяет число, при условии, что знак "+" не употребляется и незначащие нули не стоят
3) Любой ASCII код есть целое число "123.456" --> 49505148525354d
4) Сравнение строк можно заменить сравнением простых чисел (кодов).
5) За один проход можно определить максимальный (max_n, max_k) и минимальный код (min_n, min_k) для обоих массивов.
6) Требуется дополнительной памяти MaxMax - MinMin, где  MaxMax =  max(max_n, max_k); MinMin = min(min_n, min_k); для пустого, инициализированного нулями массива.
7) За один проход элементы пустого массива с индексом = MaxMax - val инкрементируются. Где val - элемент любого из масива (строки) N,K
8 ) Все элементы массива значение которых >=2, говорят о совпадении элементов. В каждом элементе такого пустого массива может хранится структура, которая еще хранит позиции элементов в исходных массивах.

Вместо п.8 можно представить значение и позиции в массивах в виде предопределенной комбинации из суммы произведение последних на простые числа, но я не помню как это делать. Это даст возможность хранить в массиве одно число, а не структуру.

Похоже? По памяти не скажу, но алгоритм работает точно за линейное время.

[Авварон]

памяти слишком много потребуется на такой массив

[Alex_cs_gsp]

А что ты придумал?

[igor_bogomolov]

есть чего-нибудь почитать? А то был на собеседовании, не смог решить тамошние алгоритмические задачки... 
Есть ли какая-нибудь книга (учебник 1го курса пойдет) где есть какие-л алгоритмические задачки?

Недавно обсуждали похожую тему http://www.forum.crossplatform.ru/index.php?showtopic=5455
А вот тут я выкладывал свой архив книг по алгоритмам

[Авварон]

идею дал octree color quantization, к-ый я не так давно писал...
строим дерево, каждый нод содержит до 10 детей и отвечает за определенную цифру. То есть если очередная цифра '2', то создаем нод в позиции 2 и переходим к следующей. Кроме того, в листьях храним требуемые позиции в строках. Для реализациии требуется 1 проход по каждой из строк и не более чем K листьев (не N а К - меньшее) - O(K) памяти.
Хотелось бы еще увидеть варианты решения:)

[Alex_cs_gsp]

Проход то один, а сколько требуется сравнений, чтобы в дереве разместить элемент на нужной позиции? Если есть сравнения для размещения элементов, то линейное время не получится. Я б зашел в эту контору, пусть скажут решение, может его нет и в этом вся суть?

[Авварон]

сравнений нет вообще. Мы идем и строим дерево одновременно, в том и суть

[Alex_cs_gsp]

Как будет время по-подробнее можешь алгоритм описать и как дерево строить?

[Igors]

А вот тут я выкладывал свой архив книг по алгоритмам

Спасибо

[Igors]

идею дал octree color quantization, к-ый я не так давно писал...
строим дерево, каждый нод содержит до 10 детей и отвечает за определенную цифру. То есть если очередная цифра '2', то создаем нод в позиции 2 и переходим к следующей. Кроме того, в листьях храним требуемые позиции в строках. Для реализациии требуется 1 проход по каждой из строк и не более чем K листьев (не N а К - меньшее) - O(K) памяти.

Тоже недавно писал octree ;-) Мне кажется здесь у Вас "просто дерево". Да, это быстрее сортировки. Однако при 100 и более знаков на число - нодов надо распределить порядочно, так что памяти не меньше. Плюс приложить (небольшие) усилия чтобы поймать повторы.

Хотелось бы еще увидеть варианты решения:)

Ну вариант с QString::split и QStringList::indexOf всем понятен   По-моему задача интересна своим "полчаса используя базовый язык". Подумав несколько дней можно найти много др. ходоа, но это уже не так интересно

[Alex_cs_gsp]

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

[Авварон]

Igors
памяти потребуется меньше, ибо у меня O(K) а у вас O(N)
да, у меня константа больше, но у вас порядок

[Авварон]

Код:

struct Tree
{
     Tree(Tree *parent) {bla}
     Tree *parent;
     Tree *children[10];
     char ch;
     int pos1;
};

Tree *root = new Tree; // корень дерева
Tree *current = root;  // текущий элемент
int pos = 0; // начало числа
for(int i = 0; i < K; i++) {
    char c = str[i];
    if (c != ' ') {
        int val = c - '0';
        if (!current->children[val]) {
            current->children[val] = new Tree(current);
            current = current->children[val];
        }
    } else { // дошли до конца числа, листовой нод
        current->pos1 = pos; // записываем начало числа
        current = root; // возвращаемся в корень дерева
        pos = i + 1; // новое число (допустим для простоты что пробел одинарный)
    }
}

for(int i = 0; i < N; i++) {
тут похожий цикл, но новые ноды не создаем, а если получили лишнюю цифру, то просто скипаем это число до пробела (т.к. в дереве его уже нет)
когда доходим до пробела, достаем из current pos1 и печатаем ее и текущую в строке 2
}

[spectre71]

Только если длина числа ограничена!!!

- Имем максимально допустимую длину строки(число)
- Сортируем оба массива строк чисел алгоритмом поразрядной сортировки время O(N+K) память O(N).
- Дальше тревиально

время O(N, K) == O(max(N, K))  == O(N)
память O(N) никак не O(K) !!!

[sLiva]

есть чего-нибудь почитать? А то был на собеседовании, не смог решить тамошние алгоритмические задачки... Только дома решил... Глубоко уязвлен собственной тупостью. Есть ли какая-нибудь книга (учебник 1го курса пойдет) где есть какие-л алгоритмические задачки? А то у нас не было по большому счету ничего.

Опа, ситуация аналогичная, тоже недавно "там" был :-) тоже не справился именно с этой задачей, деморализовало на пару дней, конешн неприятно, вначале высылаешь исходники, им они (как говорят) очень нравятся а потом вот такие задачки, я даже не ожидал, ушел с очень плохим настроением.

"Там" это крупная компания, офис которой на метро отрадное, я правильно понял?