15:23 

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

Heidel
If it's stupid but works, it isn't stupid.
Для собеседования нужно в течение пары недель подготовится к решению задач типа таких

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

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

Комментарии
2014-05-04 в 20:48 

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)

2014-05-04 в 21:30 

Heidel
If it's stupid but works, it isn't stupid.
CD_Eater, Спасибо, но мне желательно материалы на русском языке, ну и не конкретно эти задачи, а вообще почитать про подходы к решению.

2014-05-04 в 21:52 

CD_Eater
в опе ещё играет детство, а жить уже надо по-взрослому
учебник: Кормен. Алгоритмы: построение и анализ

2014-05-04 в 21:53 

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

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

2014-05-04 в 21:55 

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

2014-05-04 в 22:18 

Bashkinator
Антропоморфная Метафизическая Персонификация Природного Явления
Если уж пошли по классике, то есть Кнут - Искусство программирования

2014-05-04 в 22:52 

CD_Eater
в опе ещё играет детство, а жить уже надо по-взрослому
ninelya, а что у вас было бы для массива (-1), 1, 1, (-1), 1, 1, (-1) ?

2014-05-04 в 22:56 

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

Комментирование для вас недоступно.
Для того, чтобы получить возможность комментировать, авторизуйтесь:
 
РегистрацияЗабыли пароль?

ru_programming

главная