Несколько раз мне попадалась задача из разряда «собеседование в Google»:
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция max()
, возвращающая максимальный элемент за O(1)
времени и с использованием O(1)
дополнительной памяти (в сравнении со стеком без этой операции).
Предполагаю, что многие тоже о ней слышали, а может даже знакомы с каким-либо решением. Про решения я и предлагаю поговорить, там всё очень интересно.
Подробная формулировка
Чтобы точно не возникало вопросов, предлагаю сперва зафиксировать требуемые сигнатуры. Я буду использовать язык Java, но всё должно быть понятно даже если вы с ним не знакомы.
// Обычные методы стека. void push(int value); int pop(); // Дополнительный метод. int max();
Решения с O(n)
Разберёмся с решениями задачи, которые используют ослабленные условия.
-
Если нам разрешено тратить
O(n)
времени, то поиск максимума можно реализовать банальным поиском в стеке. Скучно и неинтересно. -
Если нам разрешено тратить
O(n)
памяти, ноO(1)
времени, то в качестве реализации можно использовать стек пар вида{value, max}
— текущий элемент стека и текущий максимум стека. Или вообще сделать два стека, если совсем лень думать. Потребление памяти в таком подходе линейное. Тоже скучно и неинтересно.
Как решают задачу люди из интернета
Мне встречалось 2 решения. Они по своей сути эквивалентны, но на всякий случай приведу оба.
Решение 1
Воспользуемся тем фактом, что максимум всегда больше либо равен текущего элемента в стеке. То есть если отнять текущий элемент от текущего максимума, мы всегда получим число >= 0
. Это даёт нам весь диапазон отрицательных чисел для кодирования чего-нибудь полезного, в случае если текущий элемент — максимальный. Например, мы можем закодировать предыдущий максимум.
Рассмотрим пример того, как в стек будут добавляться элементы:
stack := null push 10: // На дне стека всегда 0. stack := {10 - 10 = 0} -> null max := 10 push 7: // 7 меньше максимума, поэтому значение в стеке положительное. stack := {10 - 7 = 3} -> {10 - 10 = 0} -> null max := 10 push 18: // 18 больше максимума, поэтому значение в стеке отрицательное. stack := {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null max := 18
Обратная операция удаления из стека осуществляется похожим образом:
stack = {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null max = 18 pop, -8 < 0: result := max = 18 max := max + -8 = 10 // Вычислили предыдущий максимум. stack := {10 - 7 = 3} -> {10 - 10 = 0} -> null pop, 3 >= 0: result := max - 3 = 10 - 3 = 7 max := max = 10 // Не меняется. stack := {10 - 10 = 0} -> null pop, 0 >= 0: result := max - 0 = 10 - 0 = 10 max := max = 10 // Не меняется, но это не важно, стек пустой. stack := null
Код решения 1:
Скрытый текст
public class MaxStack1 { static class Node { final int value; final Node next; Node(int value, Node next) { this.value = value; this.next = next; } } private Node top; private int max; public void push(int value) { if (top == null) { top = new Node(0, null); // max - value == 0 max = value; } else { top = new Node(max - value, top); max = Math.max(value, max); } } public int pop() { if (top == null) { throw new NoSuchElementException("Stack is empty"); } Node oldTop = top; top = oldTop.next; if (oldTop.value >= 0) { return max - oldTop.value; } else { int res = max; max = max + oldTop.value; return res; } } public int max() { if (top == null) { throw new NoSuchElementException("Stack is empty"); } return max; } }
Решение 2
Оно уже более громоздкое, и построено на том же принципе — текущий элемент не может быть больше максимума. Но тут мы не будем вычислять разницу между value
и max
и сравнивать её с 0
, мы сразу будем сравнивать value
и max
.
Если текущий элемент не максимальный, просто кладём его на вершину стека. Если же текущий элемент максимальный, то на вершину стека нужно положить какое-то значение, которое будет больше вставляемого value
(которое станет новым max
), по которому мы могли бы восстановить предыдущий максимум. Предлагается использовать следующую формулу:
value := 2 * value - max = value + (value - max) max := value
Здесь, конечно, делается небольшой финт ушами, который требует комментария:
-
Первое, что нужно заметить — это что
value - max > 0
. Помним, чтоvalue
в этом контексте — это новый максимум. -
Второе, что нужно заметить — это что
value + (value - max) > value
, то есть значение на вершине стека будет больше хранимого впоследствии значенияmax
. Ровно то, чего хотели достичь.
Рассмотрим пример на тех же числах, что и раньше:
stack := null push 10: // Тут нет предыдущего максимума, поэтому вставка // в пустой стек выглядит особым образом. stack := {10} -> null max := 10 push 7: // 7 меньше максимума. stack := {7} -> {10} -> null max := 10 push 18: // 18 больше максимума. stack := {2 * 18 - 10 = 26} -> {7} -> {10} -> null max := 18
Доставать элементы будем так:
stack = {2 * 18 - 10 = 26} -> {7} -> {10} -> null max = 18 pop, 26 > 18: result := max = 18 max := 2 * max - 26 = 2 * 18 - 26 = 10 // Тут просто обратная формула. stack := {7} -> {10} -> null pop, 7 <= 10: result := 7 max := max = 10 // Не меняется. stack := {10} -> null pop, 10 <= 10: result := 10 max := max = 10 // Не меняется, но это не важно, стек пустой. stack := null
Данный подход, если судить по примеру, проще первого, вот только формула может вызвать больше вопросов, поэтому я и описал его вторым. Код решения 2:
Скрытый текст
public class MaxStack2 { static class Node { final int value; final Node next; Node(int value, Node next) { this.value = value; this.next = next; } } private Node top; private int max; public void push(int value) { if (top == null) { top = new Node(value, null); max = value; } else if (value <= max) { top = new Node(value, top); } else { // value > max top = new Node(2 * value - max, top); max = value; } } public int pop() { if (top == null) { throw new NoSuchElementException("Stack is empty"); } Node oldTop = top; top = oldTop.next; if (oldTop.value <= max) { return oldTop.value; } else { int res = max; max = 2 * max - oldTop.value; return res; } } public int max() { if (top == null) { throw new NoSuchElementException("Stack is empty"); } return max; } }
Что не так с этими решениями?
Да вроде всё хорошо, если как на литкоде, брать -107 <= x <= 107. А если взять любой int
, без читерских ограничений, которые обычно никем и не упоминаются?
Самое время рассказать, о чём эта статья на самом деле. Оба этих решения содержат очень похожие ошибки, которые я сейчас объясню.
Решение 1
Первое решение строилось на том свойстве, что если a >= b
, то a - b >= 0
. И наоборот, если a <= b
, то a - b <= 0
. А это, естественно, неправда!
Поскольку код я приводил на Java, мне проще считать, что все используемые числа — знаковые. С беззнаковыми типами нужно обращаться аккуратнее, но и на них можно было бы перенести все сделанные мною выводы.
Чтобы показать неверность указанного свойства, достаточно вспомнить про то, что числа «в компьютере» могут переполняться, и внезапно превращаться из положительных в отрицательные при, казалось бы, увеличении. Рассмотрим следующий пример:
-
a == Integer.MAX_VALUE
, или же 231-1 -
b == -1
-
a > b
, очевидно -
a - b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < 0
Если взять числа, достаточно далеко расположенные друг от друга, то их разница может оказаться больше либо равной 231 и переполнить целочисленный диапазон. А это сломает инварианты, необходимые для правильного восстановления значения в коде pop
. При использовании -107 <= x <= 107 такого переполнения, конечно же, случиться не может.
В общем случае это решение — неверное.
Решение 2
Уже вооружившись нужным инструментом, показать ошибочность решения 2 будет ещё проще. В нём мы, помимо свойства из решения 1, полагались на то, что если b > 0
,
то a + b > a
. То есть совершили ту же самую ошибку дважды.
Контрпример будет почти идентичный:
-
a == Integer.MAX_VALUE
-
b == 1
-
b > 0
, очевидно -
a + b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < a
Оно и понятно, всё же решения 1 и 2 мало отличаются что по подходу, что по требуемым предпосылкам. Итого оказывается, что нельзя просто так снять ограничения на входные данные и не упомянуть этого.
Почему?
Причина допущенной ошибки проста — авторы решений отождествляли свойства классической целочисленной арифметики и свойства 32-разрядной двоичной целочисленной арифметики. Делать этого ни в коем случае нельзя. Страшно даже представить, сколько из-за подобного мышления было совершено реальных ошибок в реальных проектах.
Казалось бы, в интернете кто-то не прав, и что с того? Если спросить меня об этом, то я скажу примерно следующее: одно дело, когда ты читаешь политические срачи в комментариях, и совершенно другое дело, когда ты читаешь образовательные материалы от людей, которые должны тебя чему-то учить. Авторы подобных образовательных материалов не выполнили свою работу должным образом и ввели читателей в заблуждение, это плохо.
Я спокойно могу себе представить собеседование в условный «Яндекс», на котором собеседующий мог бы дать эту конкретную задачу с неверными граничными условиями и буквально ожидать от собеседуемого неправильного решения. Ведь давайте будем честны — часто ли мы настолько внимательно проверяем то, что прочитали в интернете, или скопировали из ответа на StackOverflow, к примеру? Нам тоже стоит помнить, что ответы в интернете пишут люди, которые могут ошибаться, даже если у ответа много плюсиков.
Но это я отвлёкся.
Как тогда выглядит правильное решение?
Вероятнее всего, никак. Мой тезис таков — при условиях O(1)
времени и O(1)
дополнительной памяти задача вообще не имеет решения.
Формального доказательства не будет, вместо этого будет обзор определённого класса решений и некоторое количество рассуждений. Возможно я в них ошибаюсь, это уже уйдёт на суд читателя.
Что общего между решениями 1 и 2, если посмотреть на них совсем абстрактно? То, что в дополнение к стеку с целыми числами они вводят ровно одну дополнительную целочисленную переменную. Я попробую обосновать, почему это — совершенно бесперспективный подход, для этого понадобится вспомнить немного информатики.
Чтобы было совсем наглядно, предлагаю работать не с 32-битными числами, а с 2-битными числами. Так же я буду их интерпретировать как беззнаковые числа, чтобы упросить понимание текста. Очевидно, что знаковость/беззнаковость интерпретации битов фундаментально ничего не меняет.
Если хранить максимум
Представим, что у нас есть 2-битное число на вершине стека (cur
) и дополнительно хранимый 2-битный максимум (max
). Хранение в дополнительной переменной какого-то значения, отличного от максимума, я прокомментирую позже. Суммарно это 4 бита информации.
Сколько информации нам нужно при выполнении операции pop
? Рассмотрим все возможные варианты:
-
Максимум равен
0
(минимальное допустимое значение), текущее значение обязано тоже быть равным0
. -
Максимум равен
1
.-
Текущее значение может быть равно
0
или1
, предыдущий максимум всё ещё равен1
. -
Текущее значение равно
1
(текущий максимум), предыдущий максимум равен0
.
-
-
Максимум равен
2
.-
Текущее значение может быть равно
0
,1
или2
, предыдущий максимум всё ещё равен2
. -
Текущее значение равно
2
(текущий максимум), предыдущий максимум равен0
или1
.
-
-
Максимум равен
3
.-
Текущее значение может быть равно
0
,1
,2
или3
, предыдущий максимум всё ещё равен3
. -
Текущее значение равно
3
(текущий максимум), предыдущий максимум равен0
,1
или2
.
-
Итого, имеем (1) + (2 + 1) + (3 + 2) + (4 + 3) = 16
различных вариантов. Вплотную ровно для того, чтобы всё можно было уместить в 4 бита информации. Для больших разрядностей битов тоже будет хватать, причём также впритык.
Небольшая математическая выкладка для пояснения, приводится без доказательства:
В чём же проблема?
Проблема в том, как эта информация должна быть закодирована. Если переменная max
хранит текущий максимальный элемент, то в случае, когда она равна 3
(максимальный из всех максимальных), мы оставшимися двумя битами должны покрыть 7 возможных исходов, а именно:
-
4 варианта текущего значения, если оно не максимально.
-
3 варианта значения предыдущего максимума.
Это просто невозможно сделать оставшимися двумя битами, и будет невозможно для всех разрядностей.
Что если кодировать данные иначе?
Представим, что у нас есть некое 2-битное значение на вершине стека (cur
) и дополнительно хранимая 2-битная переменная (extra
). Вместе они каким-либо способом образуют 4-х битное число, способное описать все требуемые нам 16 вариантов исхода. К примеру, мы просто пронумеровали все возможные исходы и поместили их в таблицу. Достаточно ли будет так поступить? Давайте думать.
Мы способны однозначно восстановить текущий элемент, текущий максимум и предыдущий максимум, используя данные нам 4 бита. Это уже хорошо. После того, как вершина стека будет удалена, нам требуется восстановить предыдущее состояние переменной extra
, то есть какие-то 2 бита из выбранной нами нумерации.
Фактически, перед нами встала ровно та же проблема, что была при наличии переменной max
вместо extra
. Если выяснится то, что предыдущий максимум должен быть равен 3
(исходя из текущего состояния вершины стека), то после удаления текущей вершины стека у нас появится ровно 2 бита дополнительной информации (элемент в стеке), чтобы различить всё те же 7 вариантов, повторю их:
-
4 варианта текущего значения, если оно не максимально.
-
3 варианта значения предыдущего максимума.
Получается очень забавно. У нас достаточно бит информации, но в них тупо не хватает энтропии (так часто бывает в неверных решениях задач про рычажные весы и монетки). Судя по всему, иная кодировка данных не способна фундаментально ничего изменить. Без дополнительных бит в стеке у нас не хватает информации, а дополнительные биты — это уже O(n)
дополнительной памяти.
Что если мы расширим количество бит в переменной extra
? Лучше не станет. На вершине стека то всё ещё 2 бита, их не будет хватать.
Конечно, есть ненулевой шанс того, что и я всё напутал и пришёл к неверным выводам. Ошибаюсь, бывает. Но я правда не вижу здесь места для ошибки, так что всех несогласных приглашаю к диалогу в комментариях, вместе мы найдём истину.
Что в итоге
Если в задаче не задаются должным образом ограничения на входные значения, то это очень плохо, ведь буквально от этого зависит то, какие алгоритмы применимы для решения, а какие неприменимы. На том же литкоде ограничения пишут не просто так, и если ты видишь работу с массивами длиной в миллион, то скорее всего наивный алгоритм с O(n^2)
не прокатит. Тут почти то же самое.
Люди в интернете, которые стараются вас чему-то научить, могут про такие ограничения забыть. Вряд-ли специально. Когда я впервые ознакомился с решением данной задачи про стек, оно как раз было преподнесено мне в виде «должно работать для всех значений int
».
Так что будьте аккуратны с целыми числами и граничными условиями. Спасибо за внимание!
ссылка на оригинал статьи https://habr.com/ru/articles/843596/
Добавить комментарий