Подготовка к собеседованию - алгоритмические задачи

[Heidel]

Для собеседования нужно в течение пары недель подготовится к решению задач типа таких

Подскажите учебники / сайты, где бы разбиралось решение таких задач?

@темы: Вопрос, Алгоритм, Computer Science

Comments

[CD_Eater]

разбирается такое, например, на stackoverflow

1)
каждый вызов функции помечает одного из сравниваемых как "точно не звезда", поэтому достаточно N-1 вызовов (отбор по принципу игры на вылет)
докажем, что необходимо как минимум N-1 вызовов. допустим, что имеются результаты не более чем N-2 вызовов, т.е., в матрице знакомств N на N известны значения в не более чем N-2 клетках. значит, можно не менее чем двумя разными способами выбрать диагональную клетку и доопределить остальные значения матрицы так, чтобы строка матрицы, проходящая через выбранный элемент, содержала бы только true, а столбец - только false

2)
каждый шаг вычислений занимает линейное время
вычисляем частичные суммы s(0)=0, s(j) = a(1)+...+a(j)
вычисляем правые максимумы right(j) = max(s(j),s(j+1),...,s(N))
перебором ищем такое m, при котором разность right(m)-s(m-1) максимальна
находим k, такое что right(m)=s(k)

[Heidel]

CD_Eater, Спасибо, но мне желательно материалы на русском языке, ну и не конкретно эти задачи, а вообще почитать про подходы к решению.

[CD_Eater]

учебник: Кормен. Алгоритмы: построение и анализ

CD_Eater,
по второму: а я бы считала сумму рядом стоящих положительных чисел и сравнивала бы ее с предыдущей посчитанной суммой. Таким образом достаточно одного прохода по массиву. Исхожу из того, что максимальная сумма, большая суммы всего массива, может иметь место только в массиве с отрицательными числами.

Heidel,
вы хотите краткое изложение высшего технического образования в одном сайтике/книжке. такого нет. есть форумы, где обсуждают задания на собеседованиях, но в основном идет упор на код конкретного языка. они все прекрасно гуглятся.
без инглиша соваться в программирование - это за пределами моего понимания. половину полезнейшей литературы тупо не переводят из соображений, что инглиш знают все. а если переводят, то часто настолько криво, что плакать хочется.
удачи вам

ЗЫ: есть еще, по идее, Н.Вирт "АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ"

[Bashkinator]

Если уж пошли по классике, то есть Кнут - Искусство программирования

[CD_Eater]

ninelya, а что у вас было бы для массива (-1), 1, 1, (-1), 1, 1, (-1) ?

CD_Eater,
согласна, не права