0

На интервью задали такую задачу: дан массив длиной n, необходимо реализовать методы добавления элемента и обнуление(значения всех элементов сбрасывается на 0) массива за константное время. Важное уточнение: использовать тот же массив, без создания нового. Варианты, вроде int[] array = new int[]; не подходят.

Возник вопрос с методом обнуления, не могу понять как реализовать. Есть вот такой способ, с использованием дополнительных массивов: http://efesx.com/2009/11/05/reset-an-array-in-constant-time/ но не могу понять логику решения.

2
  • 2
    Не, в статье - это метод на грани фола... Он не обнуляется физически, просто объявляется обнуленным, только и всего. Цена - повышенная сложность (и время) обращения к элементам массива...
    – Harry
    5 фев 2020 в 14:09
  • Да, но как обнулить? Где то слышал о использовании второго массива и хранении переменной generation с увеличением после каждого добавления элемента. Но не могу найти, только это нашел 5 фев 2020 в 22:16

1 ответ 1

0

Вставка/удаление

Массив в котором вставка и удаление делаются за константное время это связанный список, то есть список в каждом элементе которого есть ссылка на следующий и/или предыдущий элемент. Обычно реализуется в виде LinkedList

Операция вставки в нем это всего лишь переписывание ссылки на следующий элемент, соответственно это не зависит от размера. Удаление аналогично.

Операция обнуления.

Ну как вариант можно завести булевскую переменную, типа boolean isZero, если он становится true, то любая операция получения значения должна возвращать 0 - надо всего лишь переписать метод получения значения элемента get()

4
  • Наверное имеется в виду обнуление с возможностью снова записывать значения. С одним булом если поменять элемент в обнулённом массиве (и сделать isZero = false), то все старые значения снова вернуться, либо просто всё время будет нули возвращать
    – IR42
    5 фев 2020 в 14:18
  • Ну а что мешает при вставке/удалении или записи нового значения в какой-либо элемент выставить isZero=false?
    – Barmaley
    5 фев 2020 в 14:32
  • Ну вот есть массив 3 элемента { 1, 2, 3}. Дальше вызываем метод reset, который устанавливает isZero=true, get(0), get(1), get(2), теперь возвращает нули, дальше делам set(0, num), где выполняется isZero=false, теперь get(1) и get(2) снова возвращают 2 и 3, а должны 0
    – IR42
    5 фев 2020 в 14:37
  • А если это именно массив, не связной список? На операции вставки и удаления интервьюеру было всё равно, больше интересовало метод обнуления. И использовать он предлагал именно массив. Как в стандартном массиве использовать прием с boolean переменной? 5 фев 2020 в 22:12

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.