Я получил этот вопрос интервью, который я не знал, как решить.
Разработайте функциональность набора снимков.
После создания моментального снимка итератор класса должен возвращать только те значения, которые присутствовали в функции.
Класс должен обеспечивать функциональность 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), в котором я создал копию всего списка ключей при вызове итератора. Интервьюер сказал, что это недостаточно эффективно.
Я думаю, что хорошо иметь решение, которое фокусируется на сокращении пространства за счет временной сложности (но временная сложность все равно должна быть максимально эффективной).
Если подумать, у вас может быть набор для каждого итератора без копирования. Вы начинаете с набора, добавляете и удаляете как обычно. После создания итератора для этого набора создается новый набор для всех последующих добавлений и удалений. Следующий итератор — это итератор для первого и второго наборов. Каждый набор является подмножеством того, что содержит структура. Итак, все вместе наборы равны O(n), но каждый отдельный набор меньше. Хитрость будет заключаться в отслеживании удалений из разных наборов, но это решаемо, если разрешить операции contains быть медленными.
@Welbog Я думаю, что хорошо иметь решение, которое фокусируется на сокращении пространства за счет временной сложности (но временная сложность все равно должна быть максимально эффективной).
Вот решение, которое делает все операции достаточно быстрыми. Так что это похоже на набор, у которого есть вся история, все время.
Сначала нам нужно рассмотреть идею списка пропуска. Без функции моментального снимка.
Что мы делаем, так это начинаем со связанного списка внизу, который всегда будет храниться в отсортированном порядке. Нарисуйте это в линию. Половина значений выбираются случайным образом, чтобы также быть частью другого связанного списка, который вы рисуете над первым. Затем половина из них выбирается для включения в другой связанный список и так далее. Если нижний слой имеет размер 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 для моментального снимка, особенно когда многие элементы были удалены?
Худший случай для iterator.next
— это O(edits)
. Худший случай повторения всего снимка — это O(size + edits)
. Если вы переключитесь со связанных списков для указателей на древовидную структуру, вы можете сделать наихудший случай для одного вызова iterator.next
на O(log(versions))
, но средний случай и вся итерация ухудшится.
Это совсем другой, но в конечном итоге гораздо лучший ответ, чем тот, который я дал вначале. Идея состоит в том, чтобы просто иметь структуру данных в виде достаточно хорошо сбалансированного отсортированного дерева, доступного только для чтения. Поскольку он доступен только для чтения, его легко перебирать.
Но как тогда делать модификации? Ну, вы просто создаете новую копию дерева от модификации до корня. Это будут 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())
Требуется ли время для итератора? Не могли бы вы записать свою структуру в виде реестра, а вашему итератору нужно отслеживать только начало реестра до того момента, когда итератор был создан, позволяя добавлять новые записи в реестр во время его итерации? Конечно, итератор будет медленным (ему нужно будет проверить всю книгу, чтобы убедиться, что элемент, который был
add
ed, не являетсяremove
d), но он займет всего O(1) места на итератор.