Russian Qt Forum

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

Алгоритмические задачки по программированию, или iq-шные, как в мелкософте спрашивают???

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

Есть еще Мозговой М.В. "Занимательное программирование" - там по чуть-чуть всех алгоритмов, и тоже не сухо. Примеры на Pascal и С++.

Если можешь выложи пожалуйста задачку, и скажи сколько на нее времени дали. Хочу свою тупость проверить.

Задачка "в лоб" простейшая, а вот оптимизация по скорости/памяти хуже:)
В условии точно не сказано что можно использовать, но я решал на чистом си. Мб если б мозг работал бы, там бы и решил (тк идея решения была уже там, но я не смог в мозгу просчитать сколько оно съест памяти... Показалось много:) надо было просто написать на сам деле)
давалось полчаса на эту, еще 1 совсем простенькую + еще общего плана на IQ, на них можно было забить

Все, что быстро пришло в голову - это "смещать" меньший массив относительно большего и сравнивать символьно, но это не линейная сложность. А если хеши, то память не O(K) и также не линейная скорость.

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

Что-то я не увидел линейного времени и линейной зависимости расхода памяти от строки K.


Получается память O(K+N)
А сложность алгоритма, как я понял у тебя может быть даже больше чем O((K+N)^2) - быстрая сортировка, уже не за линейное время + потом еще проход по объединенному массиву. Или нет?

ну O(K+N) == O(max(K,N) == O(N) а решение ща гляну... мне тоже где-то час понадобился (30 минут там и полчаса дома на точный рассчет оценок).
Igors
Да, забыл уточнить - в задаче требование было что скорость не зависит от количества чисел. Но тем не менее, вы не укладываетесь по памяти

 O(K+N) == O(max(K,N) == O(N))
Это как если будет выделено памяти K+N, а не max(K,N) ?

O(x) == const*x => O(x+y) == c1*(x+y) <= c1*2*max(x,y) <= c2*max(x,y) == O(max(x,y))
это можно выделить памяти z*K но не z*N

Что-то не совсем понял. Выложенный исходник при любом N и К всегда требует памяти N+K, следовательно и сложность алгоритма зависит как от N так и от K.

Если скорость не зависит от количества чисел, то это уже O(1), такое вообще возможно???

если сложность зависит от 2х величин, то она зависит только от наибольшей их них (оценка сверху)
скорость должна зависеть не от количества чисел, а от длины строки (то есть она должна работать одинаково если строка из миллиона коротких чисел или из одного длинного - на N знаков)

Ага, теперь дошло что от Вас хотели: что-то типа "сдвиг решетки". Находим совпадения сравнивая до K сначала начиная с 0-го элемента большей строки, затем с 1-го и так N - K раз. Да, так короче, но это ж издевательство над скоростью  :)

нет, так вроде не хотели:) я имею решение удовлетворяющее условию, но имхо до него дойти сходу невозможно

Любой алгоритм сортировки с попарным сравнением не лучше N*log(N). Может нужно создать пустой массив и инкрементировать  элементы соответствующие какому-то хитрому разбиению строк. Это можно сделать за линейное время, если известен диапазон чисел и они целые ( количество символов между пробелами). С памятью согласен, если с точностью до постоянного коэффициента (тут он не больше N-1).

диапазон известен (от 0 и до 10 в степени N) числовое значение использовать бесполезно

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 можно представить значение и позиции в массивах в виде предопределенной комбинации из суммы произведение последних на простые числа, но я не помню как это делать. Это даст возможность хранить в массиве одно число, а не структуру.

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

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

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

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

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

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

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

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

Спасибо

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

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

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
}

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

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

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

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

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

Ха, выпил пивка и понял как сделать:
время O(N)
память O(K)

В задании нет, что числа целые. И вообще, очень много с деревьями нужно работать, чтобы за пол-часа догадаться и написать код.

Задача достаточно примитивна. Ее можно и обобщить.
Исходные данные:
- Имеем два списка строк A и B.
- Размер алфавита является константой и имет размер S
- Общее кол-во символов по всем строкам в списке A равно N
- Общее кол-во символов по всем строкам в списке B равно K
- N >= K
Задача:
- Найти все совпадающие/несовпадающие строки между списками
- Агоритм должен иметь сложность O(N)
- Ограничение на дополнительную память O(K)

sLiva
ага, именно там

Авварон.
Если не сложно, напиши остальные задачи которые давались на собеседовании.

да там фигня, реализовать ф-ию
f(x,y) == [f(x-1,y)^3 + f(x, y-1)]^4;
f(x,0) == x^5;
f(0,y) == y^2;
сложность в том что рекурсия их не устроила:) Просто развернуть в цикл (а-ля хвостовая рекурсия) тоже не прокатит. Там надо было построчно разбивать
+еще 3 общие задачи на IQ

Короче говоря ничего путного. Задачи для кодеров, а не для программистов. :(

Всё как в лучших домах Ландона и Редмонда ;D.