Задачи по программированию. Вторая часть.

Разбор решений заданий по программированию при приеме на работу.

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

Как и прежде, мы будем использовать язык Python 3.x

Начнем опять же с одной из классических задач бинарных нулей.

Задача 1 (Бинарные нули)

Задано целое натуральное число N. Необходимо найти длину максимальной непрерывной последовательности нулей в двоичном представлении заданного числа. При этом нули на краях не учитываются.

Например, число 78, записанное в двоичном виде как 1001110, должно давать ответ 2.

Решение

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

Натуральное число, записываемое в двоичной системе счисления как (a[n-1] a[n-2] … a[0]), имеет значение:

где:

 n – количество (цифр) знаков в числе,

 a – цифры из множества {0,1},

 k – порядковый номер цифры.

Для перевода натурального числа в двоичный вид, надо делить его на 2 и остаток (1 или 0 соответственно) записывать в конец числа справа налево. Используя это нехитрое правило, можно написать следующую функцию:

Альтернативный вариант решения это воспользоваться встроенным оператором bin, который переводит число в двоичный код и отсечь префикс ‘0b’.

Оба решения очень хорошие, имеющие time complexity O(logN), что должно оцениваться тестирующей системой в 100%.

Рассмотрим теперь более сложные задачи.

Задача 2 (Заполнение рельефа)

Задан массив A из N натуральных чисел, который задает рельеф местности по высоте. Надо определить максимальный объем воды, которым данный рельеф можно заполнить. При этом считается, что слева и справа стенок нет, то есть по краям вода выливается.

Например, пусть задан массив A = (2,4,1,2,3,4,5,7,6,2), который можно представить в графическом виде как:

Ответом в данном примере будет 6.

Решение

Чтобы эффективно решить эту задачу, очевидно, необходимо рассмотреть локальные максимумы. При этом ошибочно будет посчитать заполнение между соседними вершинами, так как они могут находиться внутри более глубокого «водоема».

Правильным алгоритмом было бы найти абсолютный максимум и потом сойтись к нему с двух сторон. Это дало бы нам эффективность всего двух последовательных циклов, что очень хорошо. Но, есть еще более эффективное решение поочередной сходимости по локальным максимумам справа и слева, в зависимости от того, какой максимум ниже.

В коде это выглядит очень просто и элегантно, несмотря на, казалось бы, сложность задачи.

Это решение имеет time complexity O(N) и очень компактно в коде и реализации.

Задача 3 (LR – преобразования)

Даны два целых числа L и R  с первоначальными значениями (0,1): L = О и R = 1. Они могут менять свои значения, выполняя следующие команды :

– команда «L» изменяет значение L на 2 * L – R;

– команда «R» изменяет значение R на 2 * R – L

При заданном целом числе N, надо найти кратчайшую последовательность команд, после выполнения которых либо L = N, либо R = N.

К примеру, рассмотрим N = – 11. Самая короткая последовательность команд, необходимых для принятия либо L, либо R значения -11, это [‘L’, ‘L’, ‘R’, ‘L’]:

• Начальные значения : L = О, R = 1;

• команда «L»: L = -1, R = 1;

• команда «L»: L = -3, R = 1;

• команда «R»: L = -3, R = 5;

• команда «L»: L = -11, R = 5.

После четвертой команды получаем L = N

Необходимо написать эффективный алгоритм при следующих условиях:

– N – целое число в диапазоне [ -2,147,483,648 : 2,147,483,647 ]

– Функция должна вернуть массив последовательности команд (например, [‘L’, ‘L’, ‘R’, ‘L’] как в приведенном примере)

– Если существует более одного ответа, то функция может вернуть любой из них

– Если решения не существует, то функция должна вернуть -1

Решение

Это более сложная задача, требующая предварительного математического анализа. Давайте сделаем несколько уровней таких LR-преобразований, чтобы понять закономерности в изменениях значений левого и правого регистра (L и R соответственно).

Нетрудно заметить следующее:

– Числа левого регистра отрицательные и находятся в диапазоне: [-2^n + 1, 0], где n – уровень преобразования;

– Числа правого регистра положительные и находятся в диапазоне: [1, 2^n], где n – уровень преобразования;

– Разница между значениями правого и левого регистра на каждом уровне равна 2^n, где n – уровень преобразования

Из этих закономерностей следует, что на каждом уровне n в обоих регистрах представлены все целые числа в диапазоне [-2^n + 1, 2^n]. То есть, для любого заданного целого числа N всегда найдется последовательность LR – преобразований, приводящих к ответу. Кроме того, так как данное множество уровней построено по принципу один к двум, последовательность преобразований, приводящих к ответу, всегда будет единственной. При этом, число N определяет уровень n, на котором будет достигнут ответ: log2(N). Далее просто необходимо производить обратные LR-преобразования, проверяя выполнение условия разности 2^n между значениями левого и правого регистров, таким образом определяя L или R переход был выполнен с предыдущего уровня.

Такое решение очень эффективно с time complexity O(logN).

(to be continued…)

Поделиться...
Share on facebook
Share on twitter
Share on vk