Задача на собеседовании - C/C++

Здравствуйте, shrecher, Вы писали:

NBN>>1. В условиях задачи оговорены какие-то условия на данные.
S>нет, как раз поэтому нужно предпологать наихудщие случаи. Т.к природа данных не указана, то выбор хеш-функции затруднен.
Для большого количества строк? Не шути, хеш в таком случае стандартное и проверенное решение.

NBN>>2. хеш со строками обычно работает великолепно
S>смотря какой хеш. Конечно, можно использовать SHA256, но это будет очень медленно.
Нет необходимости.

NBN>>3. хешфункцию можно подбирать под почти любые данные.
S>подбор хеш функции сделает твое решение не универсальным: одни данные — одна хеш-функция, другие данные — другая хеш-функция.
Подбор в данном случае необходим чтобы успокоить для особо нервных. В реальности никто ничего подбирать не будет.

Здравствуйте, Аноним, Вы писали:

А>У кого есть какие варианты?

хмм, это похоже на алгоритм синхронизации файлов. как раз пригодится.

1) я б их зверски пересортировал и пробежался по этим двум массивам.
можно не сортировать а выписывать по 1,2 начальных буквы(если так проще) из двух массивов. и тоже пересортировать.

2) пробегаем по полученным массивам. так как все идет по порядку можем определять выполняются ли наши условия и в каких массивах можно переходить к следующему элементы.

// блин, вот только щас заметил эти слова: added updated removed

если все сделать правильно скорость будет(примерно) офигенно быстрой. сложностей тоже вроде никаких

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, Сергей Мухин, Вы писали:

СМ>>давайте ближе к теме. флуд или флейм (надоел
NBN>Не я начал.

ну и не я. но я больше не читаю эту тему — бай

дали такую вот задачку:

Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
tepedef std::vector< Entry > Entries;

/**
@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
*/
void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
{
}

У кого есть какие варианты?

Здравствуйте, Аноним, Вы писали:

А>дали такую вот задачку:

А>Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

А>tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
А>tepedef std::vector< Entry > Entries;

А>/**
А>@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
А>@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
А>@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
А>*/
А>void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
А>{
А>}

А>У кого есть какие варианты?

А как данные хранятся в векторе? Отсортированы или нет?

Здравствуйте, Аноним, Вы писали:

Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
Заполняешь его данными из src, счётчик делаешь равным нулю.
Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

Здравствуйте, Аноним, Вы писали:

А>дали такую вот задачку:

А>Надо реализовать ф-цию, максимально быстро работающую и оценить ее сложность O(?).

А>tepedef std::pair<std::string /*name*/, int /*value*/> Entry;
А>tepedef std::vector< Entry > Entries;

А>/**
А>@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
А>@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
А>@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
А>@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
А>*/
А>void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
А>{
А>}

А>У кого есть какие варианты?

а что должна делать функция? составить последние 3 множества? если да, то почему merge?

Здравствуйте, seimur, Вы писали:

S>Здравствуйте, Аноним, Вы писали:

S>А как данные хранятся в векторе? Отсортированы или нет?
нет

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, Аноним, Вы писали:

NBN>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
— Это не очень понял, src каждому имени соотв только 1 Entry. Аналогично в dest
NBN>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).
— А сложность вставки в хеш тут учитывается?

Здравствуйте, ilnar, Вы писали:

I>а что должна делать функция? составить последние 3 множества?
да
если да, то почему merge?
не знаю, так назвали, суть не в этом

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, Аноним, Вы писали:

NBN>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
NBN>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

Вообще то 2 хэша понадобиться..

А>У кого есть какие варианты?

Сортируешь оба массива, находишь нужные данные двухпутевым слиянием. Получится O(N * log N + M * log M + N + M).

Здравствуйте, sch, Вы писали:

А>>У кого есть какие варианты?

sch>Сортируешь оба массива, находишь нужные данные двухпутевым слиянием. Получится O(N * log N + M * log M + N + M).

А если оба массива изначально отсортерованы по убыванию??? Если я не ошибаюсь у QuickSort в таком случае ассимптотика не N*log(N), а N^2 — худший случай..

Здравствуйте, Аноним, Вы писали:

А>У кого есть какие варианты?

Чтобы особенно не мудрить я бы сделал нечто подобное


typedef std::pair<std::string /*name*/, int /*value*/> Entry;
typedef std::vector< Entry > Entries;

/**
@param [in] src — контейнер с большим количеством элементов уникальных по имени (name)
@param [in] dest — контейнер с большим количеством элементов уникальных по имени (name)
@param [out] added — элементы, которых нет в src, но есть в dest (сравнение по имени)
@param [out] updated — элементы, которые есть в src и в dest, но значения value отличаются
@param [out] removed — элементы, которые есть в src, но нет в dest (сравнение по имени)
*/
void merge( const Entries& src, const Entries& dest, Entries& added, Entries& updated, Entries& removed )
{
    struct VecSorter : public std::binary_function<Entry, Entry, bool >
    {
        bool operator() ( const Entry &lhs,  const Entry &rhs ) const 
        {
            return lhs.first < rhs.first;
        }
    };

    Entries dest_sorted = dest;
    std::sort( dest_sorted.begin(),  dest_sorted.end(), VecSorter() );


    for( unsigned int src_idx = 0; src_idx < src.size(); src_idx ++ )
    {
        Entries::iterator pos = std::lower_bound( dest_sorted.begin() , dest_sorted.end(), src[src_idx] );

        if( pos == dest_sorted.end() )
        {
            removed.push_back(src[src_idx]);    
        }
        else
        {
            if( pos->second != src[src_idx].second )
                updated.push_back (src[src_idx]);

            dest_sorted.erase (pos); // exclude item existing in both, so remaining items in dest will be "added"
        }
    }

    added = dest_sorted;
}


int _tmain(int argc, _TCHAR* argv[])
{

    Entries src;
    src.push_back ( Entry( "a", 1 ) );
    src.push_back ( Entry( "b", 2 ) );
    src.push_back ( Entry( "c", 3 ) );
    src.push_back ( Entry( "d", 4 ) );
    src.push_back ( Entry( "f", 0 ) );
    
    Entries dest;
    dest.push_back ( Entry( "b", 4 ) );
    dest.push_back ( Entry( "a", 1 ) );
    dest.push_back ( Entry( "e", 4 ) );
    dest.push_back ( Entry( "d", 4 ) );
    dest.push_back ( Entry( "c", 5 ) );
   
    Entries added, updated, removed; 

    merge( src, dest, added, updated, removed );

    return 0;
}

сложность:

N — Src
M — Dest

O( M*log(M)) — sort
O( N*log(M) ) — поиск
----
O( (M+N)*log(M))

Здравствуйте, seimur, Вы писали:

S>А если оба массива изначально отсортерованы по убыванию??? Если я не ошибаюсь у QuickSort в таком случае ассимптотика не N*log(N), а N^2 — худший случай..

А кто велит использовать Quick sort?

Здравствуйте, seimur, Вы писали:

NBN>>Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second и счётчиком пересечений с dest.
NBN>>Заполняешь его данными из src, счётчик делаешь равным нулю.
NBN>>Потом проходишься по всем dest и делаешь сравнение. Сложность будет линейная On(src + dest).

S>Вообще то 2 хэша понадобиться..

Зачем? После того как src захеширован — мы можем просто пройтись в цикле по всем элементам dst:
если данный элемент dst не найден в хеше — помещаем в аддед.
иначе увеличиваем счётчик хешзначения на единицу.
и помещаем данный элемент dst в упдейтед.

когда цикл пройден — проходимся по всем элементам хеша, если счётчик равен нулю — помещаем элемент в removed, иначе в updated.

O(N(src)) на добавление в хеш
O(N(dst)) на цикл
O(N(src)) на постобработку

Итого O(N(src + dst)).

Здравствуйте, NikeByNike, Вы писали:

Это все будет работать если мало коллизий для hash-функции, это сильно зависит какие данные и какая функция.

Здравствуйте, shrecher, Вы писали:

S>Это все будет работать если мало коллизий для hash-функции, это сильно зависит какие данные и какая функция.

Ну и что?
1. В условиях задачи оговорены какие-то условия на данные.
2. хеш со строками обычно работает великолепно
3. хешфункцию можно подбирать под почти любые данные.

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, shrecher, Вы писали:

NBN>1. В условиях задачи оговорены какие-то условия на данные.
нет, как раз поэтому нужно предпологать наихудщие случаи. Т.к природа данных не указана, то выбор хеш-функции затруднен.

NBN>2. хеш со строками обычно работает великолепно
смотря какой хеш. Конечно, можно использовать SHA256, но это будет очень медленно.

NBN>3. хешфункцию можно подбирать под почти любые данные.
подбор хеш функции сделает твое решение не универсальным: одни данные — одна хеш-функция, другие данные — другая хеш-функция.

S>А как данные хранятся в векторе? Отсортированы или нет?
А вроде они всегда отсортированы? Или я ошибся?

Аноним 469 пишет:

> У кого есть какие варианты?

0) sort по name, O( 2 * log N ) , где N — объем наборов. положим они
приблизительно равны.
1) merge join O( N )

Стоимость вставок в результирующие контейнеры не учитываем — берём например
список или вектор пре-выделяем на N.

Posted via RSDN NNTP Server 2.1 beta

NikeByNike пишет:

> Делаешь хеш. В качестве ключа — строка, значение — вектор Entry->second
> и счётчиком пересечений с dest.

Хэш — конечно хорошо, но
1) нет стандартного контейнера
2) алгоритм поиска в хэш-таблице статистически может быть нестабильной.
Могут быть провалы в линейный поиск. В итоге весь алгоритм ваш вывалится
в O(N**2)

Поэтому вы бы должны были заменить хэш — таблицу на std::map

А ежели так — будет O(log N). А ежели так, то можно
и просто отсортировать вектора.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, MasterZiv, Вы писали:

MZ>Хэш — конечно хорошо, но
MZ>1) нет стандартного контейнера
Где то есть. В любом случае он пишется на раз.

MZ>2) алгоритм поиска в хэш-таблице статистически может быть нестабильной.
MZ>Могут быть провалы в линейный поиск. В итоге весь алгоритм ваш вывалится
MZ>в O(N**2)
Табличная сложность хеша O(N). O(N^2) это лично ваши выдумки.

MZ>Поэтому вы бы должны были заменить хэш — таблицу на std::map
Не должен. Лучше хеша в данном конкретном случае ничего нет.

MZ>А ежели так — будет O(log N). А ежели так, то можно
MZ>и просто отсортировать вектора.
Можно и не сортировать, всёраавно решение с сортировкой неоптимальное

NikeByNike пишет:

> MZ>1) нет стандартного контейнера
> Где то есть. В любом случае он пишется на раз.

Нету.

> MZ>2) алгоритм поиска в хэш-таблице статистически может быть нестабильной.
> MZ>Могут быть провалы в линейный поиск. В итоге весь алгоритм ваш вывалится
> MZ>в O(N**2)
> Табличная сложность хеша O(N). O(N^2) это лично ваши выдумки.

сложность поиска в хэше O(1) (константа то есть). Если поиск
срывается в последовательный перебор, то получается O(N).
А поиск вы будете делать N раз. Итого, весь алгоритм — O(N**2).
Где я что выдумал ?

> Можно и не сортировать, всёраавно решение с сортировкой неоптимальное

Ну, докажите.

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, MasterZiv, Вы писали:

>> MZ>1) нет стандартного контейнера
>> Где то есть. В любом случае он пишется на раз.

MZ>Нету.
Во-первых он есть в некоторых реализация stl, в частности по моему в StlPort, и STL вижалки.
Во-вторых скорость его написания на основе того же вектора всёравно никто не отменял.

>> MZ>2) алгоритм поиска в хэш-таблице статистически может быть нестабильной.
>> MZ>Могут быть провалы в линейный поиск. В итоге весь алгоритм ваш вывалится
>> MZ>в O(N**2)
>> Табличная сложность хеша O(N). O(N^2) это лично ваши выдумки.

MZ>сложность поиска в хэше O(1) (константа то есть). Если поиск
MZ>срывается в последовательный перебор, то получается O(N).
MZ>А поиск вы будете делать N раз. Итого, весь алгоритм — O(N**2).
MZ>Где я что выдумал ?
_Если_ срывается. Для этого нет никаких оснований.
Практическая — та самая O(1) ( я чуть ошибся в формулировке ). И так же практически это самый быстрый алгоритм.

>> Можно и не сортировать, всёраавно решение с сортировкой неоптимальное
MZ>Ну, докажите.
Уже доказано, смотри сложности алгоритмов. O( Src + Dst ) быстрее всего.

void merge(const entry_set& src, const entry_set& dst, entry_set& removed, entry_set& added, entry_set& updated)
{
    entry_set src_sorted = src;
    std::sort(src_sorted.begin(), src_sorted.end());
    entry_set dst_sorted = dst;
    std::sort(dst_sorted.begin(), dst_sorted.end());
    entry_set::iterator src_it = src_sorted.begin(), dst_it = dst_sorted.begin();
    while(src_it!=src_sorted.end() && dst_it!=dst_sorted.end())
    {
        if(src_it->first < dst_it->first) added.push_back(*src_it++);
        else if(dst_it->first < src_it->first) removed.push_back(*dst_it++);
        else 
        { 
            if(src_it->second != dst_it->second) updated.push_back(*src_it);
            ++src_it; ++dst_it; 
        }
    }
    while(src_it != src_sorted.end()) added.push_back(*src_it++);
    while(dst_it != dst_sorted.end()) removed.push_back(*dst_it++);
}

если было бы можно сами src и dst отсортировать было б легче

Здравствуйте, sokel, Вы писали:

S>

S>    while(src_it != src_sorted.end()) added.push_back(*src_it++);
S>    while(dst_it != dst_sorted.end()) removed.push_back(*dst_it++);
S>

даже так лучше:

    if(src_it != src_sorted.end()) added.insert(added.end(), src_it, src_sorted.end());
    else if(dst_it != dst_sorted.end()) removed.insert(removed.end(), dst_it, dst_sorted.end());

Здравствуйте, MasterZiv, Вы писали:

MZ>срывается в последовательный перебор, то получается O(N).
Было бы интересно посмотреть на последовательность строк которая может сорваться в последовательный перебор

Ещё интересны твои комментарии по воводу бинарного берева балансируемого random функцией.
Так-же — не зря ли мы делали локализационные системы и классы SpatialLocator на основе хеша?

Ну и на последок — не идиоты ли сидят в микрософте, которые в своих контейнерах основной упор сделали на хеши?

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, MasterZiv, Вы писали:

MZ>>срывается в последовательный перебор, то получается O(N).
NBN>Было бы интересно посмотреть на последовательность строк которая может сорваться в последовательный перебор

все значения одинаковые.

Здравствуйте, Сергей Мухин, Вы писали:

MZ>>>срывается в последовательный перебор, то получается O(N).
NBN>>Было бы интересно посмотреть на последовательность строк которая может сорваться в последовательный перебор

СМ>все значения одинаковые.

Противоречит условиям задачи и алгоритму использования. В изначально описываемом решении я это предусмотрел.

Здравствуйте, NikeByNike, Вы писали:

MZ>>>>срывается в последовательный перебор, то получается O(N).
NBN>>>Было бы интересно посмотреть на последовательность строк которая может сорваться в последовательный перебор

СМ>>все значения одинаковые.

NBN>Противоречит условиям задачи и алгоритму использования. В изначально описываемом решении я это предусмотрел.

что всю ветку читать? я ответил на вопрос когда хеш имеет o(n)

а иначе давай ф-ию, тогда и подберём

Здравствуйте, Сергей Мухин, Вы писали:

СМ>что всю ветку читать? я ответил на вопрос когда хеш имеет o(n)
Такой ответ я продумал ещё когда вопрос писал

СМ>а иначе давай ф-ию, тогда и подберём

Не, так не интересно. Подбери мне последовательность для чёрного ящика, про который известно только то что он выдаёт практически рандомное значение на основе ключа в диапазоне от 0 до 2^32-1.
Ибо по хорошему ничего не мешает мне сделать хеш с несколькими хешфункциями

Здравствуйте, NikeByNike, Вы писали:

NBN>Здравствуйте, Сергей Мухин, Вы писали:

СМ>>что всю ветку читать? я ответил на вопрос когда хеш имеет o(n)
NBN>Такой ответ я продумал ещё когда вопрос писал

молодец!

СМ>>а иначе давай ф-ию, тогда и подберём

NBN>Не, так не интересно. Подбери мне последовательность для чёрного ящика, про который известно только то что он выдаёт практически рандомное значение на основе ключа в диапазоне от 0 до 2^32-1.
NBN>Ибо по хорошему ничего не мешает мне сделать хеш с несколькими хешфункциями

давайте ближе к теме. флуд или флейм (надоел

Здравствуйте, Сергей Мухин, Вы писали:

СМ>давайте ближе к теме. флуд или флейм (надоел
Не я начал.

NikeByNike пишет:

> MZ>срывается в последовательный перебор, то получается O(N).
> Было бы интересно посмотреть на последовательность строк которая может
> сорваться в последовательный перебор

Ну это надо на хэш-функцию глядеть, и подбирать.

> Ещё интересны твои комментарии по воводу бинарного берева балансируемого
> random функцией.

> Так-же — не зря ли мы делали локализационные системы и классы
> SpatialLocator на основе хеша?

Да не, наверное не зря.

> Ну и на последок — не идиоты ли сидят в микрософте, которые в своих
> контейнерах основной упор сделали на хеши?

Нет, не идиоты, они наверняка тесты гоняли, и хэши хитрые изобретали.

Не, я не против хэш-таблиц, просто думаю в рамках этого задания
они неприменимы.

Posted via RSDN NNTP Server 2.1 beta

NikeByNike пишет:

> Не, так не интересно. Подбери мне последовательность для чёрного ящика,
> про который известно только то что он выдаёт практически рандомное
> значение на основе ключа в диапазоне от 0 до 2^32-1.

Практически рандомное он выдавать не может. Это — хэш-функция всё же.

Posted via RSDN NNTP Server 2.1 beta

	От:	NikeByNike
	Дата:	19.07.08 14:06
	Оценка:	1 (1) +1

От:	MikelSV	http://www.centerix.ru
Дата:	22.07.08 07:55
Оценка:	+1

	От:	Сергей Мухин
	Дата:	22.07.08 14:35
	Оценка:

	От:	Аноним
	Дата:	18.07.08 20:59
	Оценка:

	От:	seimur
	Дата:	18.07.08 21:09
	Оценка: