Design a persistent iterator over an array of elements


  • 1
    R

    This question was addressed to me at a Mozilla interview.
    A persistent iterator refers to an iterator that can traverse the elements of an array even though some of them can be deleted or inserted after the creation of the iterator. Take as example the following sequence of operations:

    array: 4, 5, 2
    create iterator1
    delete 2
    create iterator2
    delete 4
    add 7
    create iterator3
    iterator1.hasNext() returns true and iterator1.next() returns 4
    iterator1.hasNext() returns true and iterator1.next() returns 5
    iterator1.hasNext() returns true and iterator1.next() returns 2
    iterator1.hasNext() returns false
    iterator2.hasNext() returns true and iterator2.next() returns 4
    iterator2.hasNext() returns true and iterator2.next() returns 5
    iterator2.hasNext() returns false
    iterator3.hasNext() returns true and iterator3.next() returns 5
    iterator3.hasNext() returns true and iterator3.next() returns 7
    iterator3.hasNext() returns false
    

    If an element has been deleted and there isn't any existing iterator that references the element, the memory allocated for the element will be freed.
    The task is to design a vector-like data structure called PersistentArray that stores an array of elements ordered and exposes the PersistentIterator class as an inner class with the following interface:

    PersistentArray::PersistentIterator::PersistentIterator(vector<int>& arrray);
    int PersistentArray::PersistentIterator::next();
    bool PersistentArray::PersistentIterator::hasNext();
    PersistentArray::PersistentIterator::~PersistentIterator();
    

    The class PersistentArray has the following interface:

    PersistentArray::PersistentArray(vector<int>& array);
    PersistentArray::~PersistentArray();
    PersistentArray::add(int x);
    PersistentArray::delete(int x);
    

    Solution:
    Keep an internal timestamp for the PersistentArray that increments at every add() and delete() operation. Every element's timestamp will be the current PersistentArray timestamp at the element's addition. Also keep a reference count for every element that is shared with the iterators that are created. Once a PersistentIterator is created, it will keep internally the current timestamp of the PersistentArray. The PersistentIterator will only look for elements that have a timestamp less or equal to the iterator's timestamp and aren't marked as deleted, let's call them the visible elements for an iterator. Now, the iterator's constructor will increment the reference count for every visible element. Its destructor will decrement the reference count for every visible element. Once the reference count of an element reaches zero, its memory will be freed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.