Ищете работу программистом в Яндекс? Пройдите сначала онлайн Яндекс тестирование! Вот такие шесть задач попались мне. Привожу и мои решения. Может, кому пригодится 🙂
Содержание
скрыть
Количество простых чисел строго меньше n
Опишите словами алгоритм решения задачи
Ввод: натуральное число n
Вывод: количество простых чисел строго меньше n
Решение должно быть вычислительно-эффективным
Решение:
Среди алгоритмов поиска простых чисел, меньших некоторого натурального n, вычислительно-эффективным является алгоритм «Решето Эратосфена». Основная идея алгоритма: некоторое число k является простым, если не делится ни на одно простое число, меньшее k.
Создаем последовательность натуральных чисел, упорядоченных по возрастанию, от 2 до n-1 включительно. Последовательность начинается с 2, т.к. 1 — не является простым числом. В последовательность не включено число n из-за условия задачи.
Перебираем по очереди все элементы последовательности. Если элемент последовательности ненулевой, то обнуляем все элементы последовательности, кратные этому элементу.
Ответом задачи будет количество оставшихся ненулевых элементов в последовательности.
Сортировка массива ASCII символов по алфавиту за линейное время
Дан неупорядоченный массив из печатных ASCII символов
Опишите своими словами (без кода и псевдокода) алгоритм сортировки, позволяющий упорядочить этот массив по алфавиту за линейное время
Необходимо описать действия на каждом шаге алгоритма
Возможен ли стабильный вариант такого алгоритма сортировки?
Решение:
В таблице ASCII печатные символы уже отсортированы по алфавиту. В заданном неотсортированном массиве символы могут повторяться.
Создаем массив нулей с размером, равным количеству символов в таблице ASCII. Индексация массива начинается с нуля.
Перебираем заданный неотсортированный массив. Значение элемента созданного массива увеличиваем на 1, индекс которого равен коду символа из неотсортированного массива. Другими словами, в созданном массиве будет храниться количество найденных символов из заданного неотсортированного массива.
Ответом задачи будет вывод созданного массива следующим образом: код выводимого символа ASCII равен индексу элемента массива, а количество (сколько штук) выводимого символа ASCII равно значению элемента массива.
Максимум в отсортированном и циклически сдвинутом массиве
Дан массив неповторяющихся чисел, который был отсортирован, а затем циклически сдвинут на неизвестное число позиций.
Опишите без кода и псевдокода алгоритм поиска максимума в таком массиве
Оцените сложность предложенного алгоритма
Изменится ли сложность если массив содержит повторяющиеся числа?
Решение:
В условии задачи не сказано, отсортирован исходный массив по возрастанию или по убыванию. Направление сортировки определяется сравнением первых элементов массива. Сложность — О(1).
Предположим, что массив был отсортирован по возрастанию. Если левая граница массива меньше правой границы, значит сдвиг равен нулю и максимум — это правая граница.
Иначе, применим бинарный поиск. Рекурсивно. Т.е. будем делить массив пополам. Если в обеих половинах массива левая граница меньше правой, то максимум — это больший из двух правых границ.
Иначе, работаем дальше с той половиной массива, у которой левая граница БОЛЬШЕ правой границы. Будем продолжать деление массива пополам до тех пор, пока обе половины не будут состоять из двух элементов. Там, где левый элемент больше правого, левый и будет максимумом.
Сложность бинарного поиска логарифмическая, т.е. O(log n).
Если числа в заданном массиве повторяются, бинарный поиск по-прежнему подойдет, т.е. сложность алгоритма не изменится.
На первом шаге добавится проверка на равенство левой и правой границы массива. А в теле рекурсии добавится условие: если у одной половины массива левая граница меньше правой, а у другой половины массива левая граница равна правой — это максимум и есть.
Яндекс тестирование. Напишите регулярное выражение
Напишите регулярное выражение, которое позволяет выделить все строки отвечающие условиям:
Состоят только из букв
Одна и только одна из букв является заглавной
Пример строк которые могут быть выделены выражением:
«Мама»,
«авТо»,
«гриБ»,
‘Яблоко’, ‘яБлоко’, ‘ябЛоко’, ‘яблОко’, ‘яблоКо’, ‘яблокО’
Пример строк которые не должны быть выделены выражением:
«агент007» — содержит цифры
«стриж» — только строчные буквы
«ГТО», — более одной заглавной буквы
«Три богатыря» — содержит пробел, допустимы только буквы
Решение:
^[a-zа-яё]*[A-ZА-ЯЁ]{1}[a-zа-яё]*$Дерево является двоичным деревом поиска?
Дан указатель на корень двоичного дерева
Опишите словами алгоритм, который вернёт True, если дерево является двоичным деревом поиска, и False, если не является
Вершина дерева содержит целочисленное значение (value) и два указателя на поддеревья (left и right).
В виде структуры на языке C это можно записать так:
struct node {
int value;
node* left;
node* right;
}Решение:
Нужно реализовать рекурсивную функцию, которая получает для текущего узла от его левого потомка (при его наличии) минимальное и максимальное значения, проверяет, что значение текущего узла больше максимального значения левого потомка, т.е. левое поддерево лежит слева. Получает для текущего узла от правого потомка (при его наличии) минимальное и максимальное значения, проверяет, что значение узла меньше минимального значение правого потомка, т.е. правое поддерево лежит справа.
Если какое условие не выполняется, возвращает False, т.е. дерево не является двоичным деревом поиска.
Функция возвращает минимальное и максимальное значения, при отсутствии потомков равные значению текущего узла. Иначе, возвращаемое минимальное значение — это минимальное левого потомка, а возвращаемое максимальное значение — это максимальное значение правого потомка.
Если текущий узел — корень и условия все выполнились, то возвращает True, т.е. дерево является двоичным деревом поиска.
Яндекс тестирование. Напишите SQL запрос
В реляционной базе данных существуют таблицы:
Cities — список городов
id — первичный ключ
name — название
population — численность населения
founded — год основания
country_id — id страны
Countries — список стран
id — первичный ключ
name — название
population — численность населения
gdp — валовый продукт в долларах
Companies — компании
id — первичный ключ
name — название
city_id — город в котором находится штаб-квартира
revenue — годовая выручка в долларах
labors — численность сотрудников
Постройте таблицу, где для каждой страны посчитано число компаний, удовлетворяющих условиям:
1) штаб квартира компании находится в этой стране
2) число сотрудников компании не менее 1000 человек
Решение:
SELECT Countries.*, COUNT(CASE WHEN Companies.labors>=1000 THEN 1 ELSE NULL END) AS NumOfCompanies FROM Countries LEFT JOIN Cities ON Countries.id=Cities.country_id LEFT JOIN Companies ON Cities.id=Companies.city_id GROUP BY 1Выводы
Вот такое онлайн Яндекс тестирование предлагается перед собеседованием на должность Асессор-разработчик в Яндекс. Критику и вопросы к решениям, пожалуйста, оставляйте в комментариях. Всем удачи!
Комментарии