Выпуск №40: It-Обучение – Актуальные Вопросы И Задачи От Ведущих Компаний

Привет, привет! Мы представляем вам (не)регулярную колонку IT-обучения.

Вам скучно? Мы тоже!



Осенью мы будем возвращаться к вам еженедельно, а пока ловите нашу подборку задач из интервью в норвежской компании Opera Software! Рубрика издается при поддержке рекрутингового агентства.

Спайс ИТ .

Вопросы

На остров помещают молодую пару шиншилл (по одному каждого пола).

Пара шиншилл не размножается, пока им не исполнится 2 месяца.

По достижении двухмесячного возраста каждая пара шиншилл ежемесячно производит еще одну пару (см.

рисунок ниже).

Найдите рекуррентное соотношение для числа пар шиншилл на острове через n месяцев, предполагая, что ни одна шиншилла никогда не умрет.

Пара шиншилл не размножается, пока им не исполнится 2 месяца.

По достижении двухмесячного возраста каждая пара шиншилл производит еще одну пару каждый месяц (см.

рисунок выше).

Найдите рекуррентное соотношение для количества пар шиншилл на острове через n месяцев, предполагая, что ни одна шиншилла никогда не умирает. 2. Священники в храме

В храме 20 священников.

Однажды Господь Шива появляется перед ними и говорит, что некоторые из них согрешили и что на лбу всех согрешивших священников появится черное пятно.

Священнослужителям не разрешается смотреться в зеркало и общаться друг с другом.

Когда какой-либо священник узнает, что у него на лбу пятно, он должен покинуть храм в тот же день.

По крайней мере 1 священник согрешил.

Как священнику узнать, есть ли у него пятно на лбу? Каков был порядок выхода священников из храма?

Однажды Господь Шива предстает перед ними и говорит, что некоторые из них согрешили и что на лбу всех согрешивших священников появится черное пятно.

Священнослужителям не разрешается смотреться в зеркало и общаться друг с другом.

Когда какой-либо священник узнает, что у него на лбу пятно, он должен в этот день покинуть храм.

Хоть один священник согрешил.

Как священник может узнать, есть ли у него пятно на лбу? Каков будет порядок выхода священников из храма?

Задания

Даны два целых числа л и р , найдите количество чисел в диапазоне [Л, П] (включительно), имеющие простое число установленных битов в их двоичном представлении.

(Напомним, что число установленных битов целого числа — это количество единиц, присутствующих при записи в двоичном формате.

Например, 21 записанный в двоичном формате 10101 который имеет 3 установленных бита.

Кроме того, 1 не является простым числом.

) Пример 1: Вход: Л=6, Р=10 Выход: 4 Объяснение: 6 -> 110 (2 заданных бита, 2 — простое число) 7 -> 111 (3 заданных бита, 3 — простое число) 9 -> 1001 (2 заданных бита, 2 — простое число) 10-> 1010 (2 бита, 2 — простое число) Пример 2: Вход: Л=10, П=15 Выход: 5 Объяснение: 10 -> 1010 (2 бита, 2 — простое число) 11 -> 1011 (3 бита, 3 — простое число) 12 -> 1100 (2 бита, 2 — простое число) 13 -> 1101 (3 бита, 3 — простое число) 14 -> 1110 (3 бита, 3 — простое число) 15 -> 1111 (4 бита, 4 не простое число) Примечание: L, R будут целыми числами L <= R in the range [1, 10^6].

R - L будет не более 10000.

(Напомним, что количество битов целого числа — это число единиц, присутствующих при записи в двоичном формате.

Например, число 21, записанное в двоичном формате, — это 10101, которое имеет набор битов из 3. Кроме того, 1 не является простым числом.

) Пример 1: Вход: Л=6, Р=10 Выход: 4 Объяснение: 6 -> 110 (2 набора бит, 2 — простое число) 7 -> 111 (3 набора бит, 3 — простое число) 9 -> 1001 (2 набора бит, 2 — простое число) 10-> 1010 (2 набора бит, 2 — простое число) Пример 2: Вход: Л=10, П=15 Выход: 5 Объяснение: 10 -> 1010 (2 набора бит, 2 — простое число) 11 -> 1011 (3 набора бит, 3 — простое число) 12 -> 1100 (2 набора бит, 2 — простое число) 13 -> 1101 (3 набора бит, 3 — простое число) 14 -> 1110 (3 набора бит, 3 — простое число) 15 -> 1111 (4 набора бит, 4 — не простое число) Примечание: L, R будут целыми числами L <= R in the range [1, 10^6].

Р-Л будет не более 10 000. 2. Круговой подмассив максимальной суммы

Учитывая круговой массив C целых чисел, представленных А , найдите максимально возможную сумму непустого подмассива С .

Здесь круговой массив означает, что конец массива соединяется с началом массива.

(Формально, С[я] = А[я] когда 0 <= i < A.length , и C[i+A.length] = C[i], когда i > = 0 .

) Кроме того, подмассив может включать только каждый элемент фиксированного буфера.

А максимум один раз.

(Формально, для подмассива C[i], C[i+1], .

, C[j] , не существует я <= k1, k2 <= j с k1 % A.длина = k2 % A.длина .

) Пример 1: Вход: [1,-2,3,-2] Выход: 3 Объяснение: Подмассив [3] имеет максимальную сумму 3 Пример 2: Вход: [5,-3,5] Выход: 10 Объяснение: Подмассив [5,5] имеет максимальную сумму 5 + 5 = 10. Пример 3: Вход: [3,-1,2,-1] Выход: 4 Объяснение: Подмассив [2,-1,3] имеет максимальную сумму 2 + (-1) + 3 = 4. Пример 4: Вход: [3,-2,2,-3] Выход: 3 Объяснение: Подмассивы [3] и [3,-2,2] имеют максимальную сумму 3 Пример 5: Вход: [-2,-3,-1] Выход: -1 Объяснение: Подмассив [-1] имеет максимальную сумму -1 Примечание:

-30000 <= A[i] <= 30000 1 <= A.length <= 30000

Здесь круговой массив означает, что конец массива соединен с началом массива.

(Формально С[я] = А[я] , 0 <= i < A.length , И C[i+A.length] = C[i] , Когда я > = 0 .

) Кроме того, подмассив может включать каждый элемент фиксированного буфера A не более одного раза.

(Формально для подмассива C[i], C[i+1],.

, C[j] , не существует я <= k1, k2 <= j С k1 % A.длина = k2 % A.длина .

) Пример 1: Входные данные: [1, -2,3, -2] Выход: 3 Объяснение: Подмассив[3] имеет максимальную сумму 3 Пример 2: Вход: [5,-3,5] Выход: 10 Объяснение: Подмассив [5,5] имеет максимальную сумму 5 + 5 = 10. Пример 3: Входные данные: [3,-1,2, -1] Выход: 4 Объяснение: Подмассив [2, -1,3] имеет максимальную сумму 2 + (-1) + 3 = 4. Пример 4: Входные данные: [3,-2,2,-3] Выход: 3 Объяснение: Подмассивы [3] и [3,-2,2] имеют максимальную сумму 3 Пример 5: Входные данные: [-2,-3, -1] Выход: -1 Объяснение: Подмассив [-1] имеет максимальную сумму -1. Примечание:

-30000 <= A[i] <= 30000 1 <= A.length <= 30000

3. Кратчайший путь с посещением всех узлов

Неориентированный связный граф из N узлов (обозначенный как 0, 1, 2, .

, Н-1 ) представлен в виде графика.

граф.

длина = N , и j != я есть в списке график[я] ровно один раз, тогда и только тогда, когда узлы я и дж подключены.

Возвращает длину кратчайшего пути, который посещает каждый узел.

Вы можете начать и остановиться на любом узле, можете посещать узлы несколько раз и повторно использовать ребра.

Пример 1: Вход: [[1,2,3],[0],[0],[0]] Выход: 4 Объяснение: Один из возможных путей: [1,0,2,0,3] Пример 2: Вход: [[1],[0,2,4],[1,3,4],[2],[1,2]] Выход: 4 Объяснение: Один из возможных путей: [0,1,4,2,3] Примечание:

1 <= graph.length <= 12 0 <= graph[i].

length < graph.length

, Н-1 ) представлена в виде графика.

граф.

длина = N И j != я есть в списке график[я] ровно один раз тогда и только тогда, когда узлы я И дж связанный.

Выведите длину кратчайшего пути, который посетил каждый узел.

Вы можете начать и остановить на любом узле, можете посещать узлы несколько раз и повторно использовать ребра.

Пример 1: Входная информация: [[1,2,3],[0],[0],[0]] Выход: 4 Объяснение: один из возможных путей — [1,0,2,0,3] Пример 2: Входная информация: [[1],[0,2,4],[1,3,4],[2],[1,2]] Выход: 4 Объяснение: один возможный путь — [0,1,4,2,3] Примечание:

1 <= graph.length <= 12 0 <= graph[i].

length < graph.length

Ответы на задачи будут даны в течение следующей недели — успейте их решить.

Удачи! Теги: #программирование #обучение #веселые задачи #поиск работы #интервью #веселые задачи #spiceit #ittraining #поиск в ширину #кратчайший путь #алгоритм Кадане

• Эмоции

  19 Oct, 24

• Геометрия

  19 Oct, 24

• Mcdonald’s Продаст 80% Бизнеса В Китае За $2 Млрд

  19 Oct, 24

• Задача Коммивояжера С Использованием Метода Литтла На C++

  19 Oct, 24

• Стив Возняк — Энтузиаст, Изменивший Мир Персональных Компьютеров

  19 Oct, 24

• Спасет Ли Вас Python От Казни?

  19 Oct, 24

• Выпущен Jquery 1.6.2

  19 Oct, 24

• Текст В Перспективе

  19 Oct, 24

• Gradle: 5 Полезных Вещей Для Разработчиков

  19 Oct, 24

• Мобильный Телефон Учит

  19 Oct, 24