Можно ли хранить только значения без списков?

Что проверяют

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

Как отвечать

Ответ начинается со встречного вопроса: какие операции нужны и что мы собираемся спрашивать у структуры потом. От этого зависит всё.

Часть информации действительно избыточна. Классический пример это стек с минимумом: наивно кладут пару из значения и текущего минимума, хотя достаточно второго стека, куда минимум пишется только при обновлении. Точно так же сумма, счётчик и среднее не хранятся поэлементно, а поддерживаются одним числом на каждой операции.

Часть выбрасывать нельзя. В задачах вида «следующий больший элемент» в стеке держат именно позиции, а не значения: по позиции значение достаётся за константу, а обратно нет, особенно когда значения повторяются.

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

Ещё про стоимость самих значений: список целых чисел в Python это список ссылок на объекты, и экономия появляется не от отказа от вложенности, а от перехода к массиву с фиксированным типом.

Где спотыкаются

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

Отвечают «да, можно» и молчат про инвариант. Ждут именно формулировки, почему выброшенное восстановимо: либо оно пересчитывается за константу, либо поддерживается на каждой операции. Без этого ответ выглядит угадыванием.

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