Создайте компактный набор моментальных снимков

Я получил этот вопрос интервью, который я не знал, как решить.

Разработайте функциональность набора снимков.

После создания моментального снимка итератор класса должен возвращать только те значения, которые присутствовали в функции.

Класс должен обеспечивать функциональность add, remove и contains. Итератор всегда возвращает элементы, которые присутствовали в моментальном снимке, даже если элемент может быть удален из набора после моментального снимка.

Снимок набора делается при вызове функции итератора.

interface SnapshotSet {
  void add(int num);
  void remove(num);
  boolean contains(num);
  Iterator<Integer> iterator(); // the first call to this function should trigger a snapshot of the set
}

Интервьюер сказал, что потребность в пространстве заключается в том, что мы не можем создать копию (моментальный снимок) всего списка ключей при вызове итератора.

Первый шаг заключается в обработке только одного создаваемого итератора за раз. Следующий вопрос: как справиться со сценарием нескольких итераторов?

Пример:

SnapshotSet set = new SnapshotSet();
set.add(1);
set.add(2);
set.add(3);
set.add(4);
Iterator<Integer> itr1 = set.iterator(); // iterator should return 1, 2, 3, 4 (in any order) when next() is called.
set.remove(1);
set.contains(1); // returns false; because 1 was removed.
Iterator<Integer> itr2 = set.iterator(); // iterator should return 2, 3, 4 (in any order) when next() is called.

Я придумал решение для пространства O (n), в котором я создал копию всего списка ключей при вызове итератора. Интервьюер сказал, что это недостаточно эффективно.

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

Требуется ли время для итератора? Не могли бы вы записать свою структуру в виде реестра, а вашему итератору нужно отслеживать только начало реестра до того момента, когда итератор был создан, позволяя добавлять новые записи в реестр во время его итерации? Конечно, итератор будет медленным (ему нужно будет проверить всю книгу, чтобы убедиться, что элемент, который был added, не является removed), но он займет всего O(1) места на итератор.

Welbog 13.02.2023 03:57

Если подумать, у вас может быть набор для каждого итератора без копирования. Вы начинаете с набора, добавляете и удаляете как обычно. После создания итератора для этого набора создается новый набор для всех последующих добавлений и удалений. Следующий итератор — это итератор для первого и второго наборов. Каждый набор является подмножеством того, что содержит структура. Итак, все вместе наборы равны O(n), но каждый отдельный набор меньше. Хитрость будет заключаться в отслеживании удалений из разных наборов, но это решаемо, если разрешить операции contains быть медленными.

Welbog 13.02.2023 04:02

@Welbog Я думаю, что хорошо иметь решение, которое фокусируется на сокращении пространства за счет временной сложности (но временная сложность все равно должна быть максимально эффективной).

user21200640 13.02.2023 06:53
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
3
61
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

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

Сначала нам нужно рассмотреть идею списка пропуска. Без функции моментального снимка.

Что мы делаем, так это начинаем со связанного списка внизу, который всегда будет храниться в отсортированном порядке. Нарисуйте это в линию. Половина значений выбираются случайным образом, чтобы также быть частью другого связанного списка, который вы рисуете над первым. Затем половина из них выбирается для включения в другой связанный список и так далее. Если нижний слой имеет размер n, вся структура обычно требует около 2n узлов. (Потому что 1 + 1/2 + 1/4 + 1/8 + ... = 2.) Каждый узел во всей двумерной структуре имеет следующие данные:

value: the value of the node
height: the height of the node in the skip list
next: the next node at the current level (is null at the end)
down: the same value node, one level down (is null at height 0)

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

Вот основная картинка:

  set
   |
start(3)   ->    2
   |             |
start(2)   ->    2      ->      5        ->         9
   |             |              |                   |
start(1)   ->    2   ->    4 -> 5        ->         9
   |             |         |    |                   |
start(0) -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Теперь предположим, что я хочу найти, входит ли 8 в набор. Что я делаю, так это начинаю с набора, нахожу самое верхнее начало, затем:

while True:
    if node.next is null or 8 < node.next.value:
        if node.down is null:
            return False
        else:
            node = node.down
    elif 8 == node.next.value:
        return True
    else:
        node = node.next

В этом случае мы идем от set к start(3) наверх 2, вниз на один к 2, вперед к 5, вниз 2 раза к 5, затем идем 6, 7 и находим 8.

Это contains. Для remove мы следуем той же идее поиска, но если мы находим это node.next.value == 5, то мы присваиваем node.next = node.next.next, а затем продолжаем поиск.

Для add мы случайным образом выбираем height (может быть int(-log(random())/log(2))). И затем мы ищем вперед, пока не достигнем этой высоты в узле, чье node.next должно быть нашим желаемым новым значением. Затем делаем что-то сложное.

prev_added = null
while node is not null:
    if node.next is null or new_value < node.next.value:
        if node.height <= desired_height:
            adding_node = Node(new_value, node.height, node.next, null)
            node.next = adding_node
            if prev_added is not null:
                prev_added.down = adding_node
            prev_added = adding_node
        node = node.down
    else:
        node = node.next

Вы можете убедиться, что ожидаемая производительность всех трех операций равна O(log(n)).

Итак, как мы добавим к этому моментальные снимки?

Сначала мы добавляем version к структуре данных set. Это будет привязано к моментальному снимку. Затем мы заменяем каждый отдельный указатель связанным списком указателей и версий. И теперь вместо прямого изменения указателей, если верхний имеет более старую версию, чем мы сейчас вставляем, вы добавляете в начало списка и оставляете более старую версию.

И СЕЙЧАС мы можем реализовать снимок следующим образом.

set.version = set.version+1
node = set.start
while node.down is not null:
    node = node.down
snapshot = Snapshot(set, set.version, node)

Теперь снэпшот делается очень быстро. И чтобы пройти определенную предыдущую версию набора (включая просто итерацию по снимку) для любого указателя, нам нужно пройти назад, пока мы не пройдем все слишком новые указатели и не найдем достаточно старый. Оказывается, любой заданный указатель будет иметь довольно небольшое количество указателей, поэтому это имеет лишь скромные накладные расходы.

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

И теперь у нас есть версия со всеми снэпшотами, доступными навсегда. Можно добавить сборку мусора, чтобы уменьшить масштаб проблемы. Но это описание уже достаточно длинное.

Спасибо! Не могли бы вы добавить анализ к своему ответу о наихудшей временной сложности для вызова iterator.next для моментального снимка, особенно когда многие элементы были удалены?

user21200640 13.02.2023 20:47

Худший случай для iterator.next — это O(edits). Худший случай повторения всего снимка — это O(size + edits). Если вы переключитесь со связанных списков для указателей на древовидную структуру, вы можете сделать наихудший случай для одного вызова iterator.next на O(log(versions)), но средний случай и вся итерация ухудшится.

btilly 13.02.2023 21:39

Это совсем другой, но в конечном итоге гораздо лучший ответ, чем тот, который я дал вначале. Идея состоит в том, чтобы просто иметь структуру данных в виде достаточно хорошо сбалансированного отсортированного дерева, доступного только для чтения. Поскольку он доступен только для чтения, его легко перебирать.

Но как тогда делать модификации? Ну, вы просто создаете новую копию дерева от модификации до корня. Это будут O(log(n)) новые узлы. Более того, O(log(n)) старые узлы, которые были заменены, могут быть тривиально удалены сборщиком мусора, если они не используются.

Все операции обозначаются O(log(n)), кроме итерации, которая обозначается O(n). Я также включил как явный итератор с использованием обратных вызовов, так и неявный с использованием генераторов Python.

Ради интереса я написал код на Python.

class TreeNode:
    def __init__ (self, value, left=None, right=None):
        self.value = value
        count = 1
        if left is not None:
            count += left.count
        if right is not None:
            count += right.count
        self.count = count
        self.left = left
        self.right = right

    def left_count (self):
        if self.left is None:
            return 0
        else:
            return self.left.count

    def right_count (self):
        if self.right is None:
            return 0
        else:
            return self.right.count

    def attach_left (self, child):
        # New node for balanced tree with self.left replaced by child.
        if id(child) == id(self.left):
            return self
        elif child is None:
           return TreeNode(self.value).attach_right(self.right)
        elif child.left_count() < child.right_count() + self.right_count():
            return TreeNode(self.value, child, self.right)
        else:
            new_right = TreeNode(self.value, child.right, self.right)
            return TreeNode(child.value, child.left, new_right)

    def attach_right (self, child):
        # New node for balanced tree with self.right replaced by child.
        if id(child) == id(self.right):
            return self
        elif child is None:
            return TreeNode(self.value).attach_left(self.left)
        elif child.right_count() < child.left_count() + self.left_count():
            return TreeNode(self.value, self.left, child)
        else:
            new_left = TreeNode(self.value, self.left, child.left)
            return TreeNode(child.value, new_left, child.right)

    def merge_right (self, other):
        # New node for balanced tree with all of self, then all of other.
        if other is None:
            return self
        elif self.right is None:
            return self.attach_right(other)
        elif other.left is None:
            return other.attach_left(self)
        else:
            child = self.right.merge_right(other.left)
            if self.left_count() < other.right_count():
                child = self.attach_right(child)
                return other.attach_left(child)
            else:
                child = other.attach_left(child)
                return self.attach_right(child)

    def add (self, value):
        if value < self.value:
            if self.left is None:
                child = TreeNode(value)
            else:
                child = self.left.add(value)
            return self.attach_left(child)
        elif self.value < value:
            if self.right is None:
                child = TreeNode(value)
            else:
                child = self.right.add(value)
            return self.attach_right(child)
        else:
            return self

    def remove (self, value):
        if value < self.value:
            if self.left is None:
                return self
            else:
                return self.attach_left(self.left.remove(value))
        elif self.value < value:
            if self.right is None:
                return self
            else:
                return self.attach_right(self.right.remove(value))
        else:
            if self.left is None:
                return self.right
            elif self.right is None:
                return self.left
            else:
                return self.left.merge_right(self.right)

    def __str__ (self):
        if self.left is None:
            left_lines = []
        else:
            left_lines = str(self.left).split("\n")
            left_lines.pop()

            left_lines = ["  " + l for l in left_lines]

        if self.right is None:
            right_lines = []
        else:
            right_lines = str(self.right).split("\n")
            right_lines.pop()

            right_lines = ["  " + l for l in right_lines]

        return "\n".join(left_lines + [str(self.value)] + right_lines) + "\n"

    # Pythonic iterator.
    def __iter__ (self):
        if self.left is not None:
            yield from self.left
        yield self.value
        if self.right is not None:
            yield from self.right



class SnapshottableSet:
    def __init__ (self, root=None):
        self.root = root

    def contains (self, value):
        node = self.root
        while node is not None:
            if value < node.value:
                node = node.left
            elif node.value < value:
                node = node.right
            else:
                return True
        return False

    def add (self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self.root = self.root.add(value)

    def remove (self, value):
        if self.root is not None:
            self.root = self.root.remove(value)

    # Pythonic built-in approach
    def __iter__ (self):
        if self.root is not None:
            yield from self.root

    # And explicit approach
    def iterator (self):
        nodes = []
        if self.root is not None:
            node = self.root
            while node is not None:
                nodes.append(node)
                node = node.left
        def next_value ():
            if len(nodes):
                node = nodes.pop()
                value = node.value
                node = node.right
                while node is not None:
                    nodes.append(node)
                    node = node.left
                return value
            else:
                raise StopIteration
        return next_value

s = SnapshottableSet()
for i in range(10):
    s.add(i)
it = s.iterator()
for i in range(5):
    s.remove(2*i)

print("Current contents")
for v in s:
    print(v)

print("Original contents")
while True:
    print(it())

Другие вопросы по теме

Похожие вопросы

Неправильный вывод алгоритма Дейкстры с использованием C#
Задача интервью с массивом целых чисел, представляющих блочные башни, необходимо создать ступенчатый шаблон за минимальное количество ходов
Временная и пространственная сложность нарезки списка Python внутри рекурсивных вызовов
Идея решения для динамического программирования
Как написать функцию Python, чтобы максимизировать сумму N X N верхней левой подматрицы из заданной матрицы 2N X 2N?
Как убрать скобки из строки?
JS - Как рассчитать все возможные +, -, ÷, × математические операции для 4 конкретных чисел?
Минимальный набор непересекающихся путей вершин, покрывающих заданный набор вершин
Как динамически размещать атомы на атомных орбиталях с заданным набором желаемых расположений?
Объединить два отсортированных массива с использованием цикла for, в котором отсутствует последний элемент