Facebook | Design a data structure for History Set

Design a data structure for History Set with following operations:

  1. Add(element) : Adds an element to the Set and returns a SequenceId
  2. Discard(element): Discards an element from the Set and returns a SequenceId
  3. Member(sequenceId): Return the state of historySet at a given sequenceId

Example:
seq1 = add("a")
seq2 = add("b")
seq3 = add("c")
seq4 = discard("b")

member(seq3) = ("a", "b", "c")
member(seq1) = ("a")
member(seq4) = ("a", "c")

Comments (11)