Задачи по программированию  

Предисловие

• Ссылка в тему  Алгоритмы. Список тем для изучения
• Ко всем задачам этого раздела следует добавлять вопросы: "Какова особенность реализации данной задачи на W? Какие готовые решения можно использовать?", где W - язык программирования, по которому вы собираетесь собеседоваться
• Из книги Г. Макдауэлл "Карьера программиста" 

Задачи по алгоритмам и структурам данных на собеседованиях

Из книги Г. Макдауэлл "Карьера программиста" и просторов интернета (форумы, блоги и т.п.)

1. Напишите функцию, которая переставляет значения переменных без использования временных переменных.
2. Напишите метод, находящий максимальное из двух чисел без использования if-else или любых других операторов сравнения.
3. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются только один раз. А если при этом запрещено использование дополнительных структур данных?
4. Для двух строк напишите метод, определяющий, является ли одна строка перестановкой другой.
5. Реализуйте метод для выполнения простейшего сжатия строк с использованием счетчика повторяющихся символов. Например, строка ааbсссссааа превращается в а2b1с5а3. Если сжатая строка не становится короче исходной, то метод возвращает исходную строку. Предполагается, что строка состоит только из букв верхнего и нижнего регистра (a-z).
6. Задано целое число. Выведите его значение в текстовом виде (например, одна тысяча двести тридцать четыре).
7. Напишите алгоритм, реализующий следующее условие: если элемент матрицы MxN равен 0, то весь столбец и вся строка обнуляются.
8. Что такое разреженная матрица? Предложите структуры данных для хранения и выполнения операций с такими матрицами.
9. Напишите код для удаления дубликатов из несортированного связного списка.
10. Реализуйте алгоритм для нахождения в односвязном списке k-го элемента с конца.
11. В каких случаях выгоднее использовать массивы, а в каких - списки? Приведите примеры.
12. Для кольцевого связного списка реализуйте алгоритм, возвращающий начальный узел петли. Кольцевой связный список - это связный список, в котором указатель следующего узла ссылается на более ранний узел, образуя петлю. Пример:  A->B- >C->D->E->C (предыдущий узел C) Вывод: C
13. Опишите, как бы вы использовали один одномерный массив для реализации трех стеков.
14. Какие варианты разрешения коллизий в хеш-таблице?
15. Как реализовать стек, в котором кроме стандартных функций push и рор будет поддерживаться функция min, возвращающая минимальный элемент? Все операции - push, рор и min - должны выполняться за время O(1).
16. Как известно, слишком высокая стопка тарелок может развалиться. Следовательно, в реальной жизни, когда высота стопки превысила бы некоторое пороговое значение, мы начали бы складывать тарелки в новую стопку. Реализуйте структуру данных SetOfStacks, имитирующую реальную ситуацию. Структура SetOfStack должна состоять из нескольких стеков, новый стек создается, как только предыдущий достигнет порогового значения. Методы SetOfStacks.push ( ) и SetOfStacks.рор( ) должны вести себя так же, как при работе с одним стеком (то есть метод рор( ) должен возвращать те же значения, которые бы он возвращал при использовании одного большого стека).
17. Для заданного направленного графа разработайте алгоритм, проверяющий существование маршрута между двумя узлами.
18. Напишите алгоритм создания бинарного дерева поиска с минимальной высотой для отсортированного (по возрастанию) массива с уникальными целочисленными элементами.
19. Реализуйте функцию, проверяющую сбалансированность бинарного дерева. Будем считать дерево сбалансированным, если разница высот двух поддеревьев любого узла не превышает 1.
20. Реализуйте функцию для проверки того, является ли бинарное дерево бинарным деревом поиска.
21. В чем суть алгоритма Дейкстры?
22. Т1 и Т2 - два очень больших бинарных дерева, причем Т1 значительно больше Т2. Создайте алгоритм, проверяющий, является ли Т2 поддеревом Тl.  Дерево Т2 считается поддеревом Tl, если существует такой узел n в Тl, что поддерево, «растущее» из n, идентично дереву Т2. (Иначе говоря, если вырезать дерево в узле n, оно будет идентично Т2.)
23. Дано бинарное дерево, в котором каждый узел содержит целое число (положительное или отрицательное). Разработайте алгоритм для подсчета всех путей, сумма значений которых соответствует заданной величине. Обратите внимание, что путь не обязан начинаться или заканчиваться в корневом или листовом узле, но он должен идти вниз (переходя только от родительских узлов к дочерним).
24. Дано вещественное число в интервале между 0 и 1 (например, 0,72), которое передается в формате double. Выведите его двоичное представление. Если для точного двоичного представления числа не хватает 32 разрядов, выведите сообщение об ошибке.
25. Имеется целое число, в котором можно изменить ровно один бит из 0 в 1. Напишите код для определения длины самой длинной последовательности единиц, которая может быть при этом получена.
26. Напишите программу, меняющую местами четные и нечетные биты числа с минимальным количеством инструкций (например, меняются местами биты 0 и 1, биты 2 и 3 и т. д.).
27. Предложите алгоритм генерации случайных чисел.
28. Реализуйте метод rand7( ) на базе метода rand5( ) . Другими словами, имеется метод, генерирующий случайные числа в диапазоне от 0 до 4 (включительно). Напишите метод, который использует его для генерирования случайного числа в диапазоне от 0 до 6 (включительно).
29. Разработайте структуры данных для универсальной колоды карт. Объясните, как разделить структуры данных на субклассы, чтобы реализовать игру в блэкджек.
30. Разработайте модель автостоянки, используя принципы ООП.
31. Разработайте структуры данных для онлайн-библиотеки.
32. Как бы вы подошли к проектированию чат-сервера? Предоставьте информацию о компонентах внутренней подсистемы (backend), классах и методах. Перечислите самые трудные задачи, которые необходимо решить.
33. Объясните, какие структуры данных и алгоритмы вы бы использовали для разработки файловой системы, хранящейся в оперативной памяти. Напишите программный код, иллюстрирующий использование этих алгоритмов.
34. Спроектируйте и реализуйте хеш-таблицу, использующую связные списки для обработки коллизий.
35. Ребенок поднимается по лестнице из n ступенек. За один шаг он может переместиться на одну, две или три ступеньки. Реализуйте метод, рассчитывающий количество возможных вариантов перемещения ребенка по лестнице.
36. Робот стоит в левом верхнем углу сетки, состоящей из r строк и k столбцов. Робот может перемещаться в двух направлениях: вправо и вниз, но некоторые ячейки сетки заблокированы, то есть робот через них проходить не может. Разработайте алгоритм построения маршрута от левого верхнего до правого нижнего угла.
37. Напишите метод для вычисления всех перестановок строки, состоящей из уникальных символов.
38. Дано неограниченное количество монет достоинством 25, 1 0, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов.
39. Напишите алгоритм, находящий все варианты расстановки восьми ферзей на шахматной доске размером 8х8 так, чтобы никакие две фигуры не располагались на одной горизонтали, вертикали или диагонали (учитываются не только две главные, но и все остальные диагонали)
40. Имеются 10 миллиардов URL-aдpecoв. Как обнаружить все дублирующиеся документы? Дубликатом в данном случае считается совпадение URL-aдpecoв.
41. Опишите словами алгоритм сортировки пузырьком, далее напишите код.
42. Опишите словами алгоритм сортировки вставками, далее напишите код.
43. Приведите несколько итераций алгоритма сортировки выбором на конкретном массиве.
44. Опишите словами алгоритм быстрой сортировки, напишите код.
45. Имеются два отсортированных массива А и В. В конце массива А существует свободное место, достаточное для размещения массива В. Напишите метод слияния массивов В и А, сохраняющий сортировку.
46. Напишите метод сортировки массива строк, при котором анаграммы группируются друг за другом.
47. Имеется файл размером 20 Гбайт, состоящий из строк. Как бы вы выполнили сортировку такого файла?
48. Имеется входной файл с четырьмя миллиардами неотрицательных целых чисел. Предложите алгоритм для генерирования целого числа, отсутствующего в файле. Считайте, что для выполнения операции доступен 1 Гбайт памяти.
49. Для заданной матрицы MxN, в которой каждая строка и столбец отсортированы по возрастанию, напишите метод поиска элемента
50. Вам предоставили исходный код приложения, которое аварийно завершается после запуска. После десяти запусков в отладчике вы обнаруживаете, что каждый раз программа завершается в разных местах. Приложение однопотоковое и использует только стандартную библиотеку С. Какие ошибки могут вызвать сбой приложения? Как вы организуете тестирование?
51. Как вы проведете нагрузочный тест веб-страницы без использования специальных инструментов тестирования?
52. Для двух отрезков, заданных координатами начальной и конечной точек, вычислите координаты точки пересечения (если она существует).
53. Разработайте алгоритм, проверяющий результат игры в крестики-нолики (3х3).

к содержанию задачника