2
$\begingroup$

A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers)

No two postal codes are alike, yet a postal code can contain many different mailboxes.

At any given postal code, all mailboxes have different numbers.

Display a data structure that supports the following methods in best complexity:

$Insert(z,p)$: insert a new person into the structure, who's postal code is $z$ and mailbox number is $p$.

$Delete(z,p)$: delete a person with postal code $z$ and mailbox number $p$ .

$Median(z)$: at postal code $z$, who has a mailbox that is the median? (half of people at postal code $z$ have mailbox with lower number)

$Max(z_1,z_2)$: out of the people living in the range $z_1 \rightarrow z_2$, who has the maximal mailbox number?

$HowMany(x)$: how many postal codes have exactly $x$ mailboxes?

The DS I've come up with was an AVL tree, where each key is a postal code and each node has a pointer to another AVL tree which represents the mailboxes in that postal code. That solves $insert/delete$ in

$O(max\{log$(amount of postal codes)$, log$(amount of mailboxes in postal code z)$\})$

which seems pretty efficient.

From this point forward I'm not sure how to continue, Median seems like $O(log$(amount of postal codes)$)$ to me since the mailboxes are in an AVL tree, so we can keep track of how many mailboxes we got, if number of mailboxes is uneven, the median is at the root, else we can find the heavier subtree and claim the median is the mean of the root and the root of said subtree, yet I'm not sure that works.

About $max$ and $howmany$, I still can't think of a solution that yields anything better than $O(n)$ where $n=$number of postal codes so far.

What would be some efficient data structure for my situation?

$\endgroup$
5
  • $\begingroup$ I am puzzled by the requirement "in best complexity". There is a number of queries to implement, and a priori fulfilling all of them efficiently might not be possible, there could be tradeoffs. So either there is a wonderful data structure that easily solves everything, or the question is ill-posed. In which case are we ? $\endgroup$ Apr 20 at 6:53
  • $\begingroup$ Are there constraints on the size and preprocessing time of the data structure ? $\endgroup$ Apr 20 at 6:57
  • $\begingroup$ There are no constraints space-wise, I'm asked to find the data structure that is able to perform according to the requirements above in the best time complexity possible, yet the question does not state what the goal time complexity is. I couldent think of a better time data structure that would result in better complexity than the one I've explained in my purposed solution. $\endgroup$
    – Aishgadol
    Apr 20 at 9:42
  • 1
    $\begingroup$ For the HowMany query, you can use a separate hashmap that keeps the number of mailboxes per postal code (histogram); it is easy to update it upon Insert or Delete; also keep in a hashmap the number of postal codes per different numbers of mailboxes (reverse histogram). Upon Insert or Delete, you get a new $x$ (incremented or decremented) and you update the postal codes counts for the old $x$ and the new one. All this takes amortized $O(1)$ time. $\endgroup$ Apr 20 at 9:54
  • $\begingroup$ much appriciated! $\endgroup$
    – Aishgadol
    Apr 20 at 16:38

1 Answer 1

2
$\begingroup$

Your idea of using a tree of tree representation seems good. Let $n$ be the current number of postal codes and $m$ be the current maximum number of mailboxes in any postal code. Then the insert and delete implementation takes $O(\log n + \log m) = O(\log nm)$.

To implement median, you can make the mailbox tree of each postal code to be an order statistic tree. This will give you a bound of $O(\log nm)$ running-time.

To implement max, first augment each postal code node $z$, so it will store the current maximum mailbox number of its mailbox tree as $z.max$. Also, let $z.maxT$ be a pointer to the node that has the largest $max$ value in $z$'s subtree. Note that it's possible for $z.maxT$ be equal to $z$. The $maxT$ of each nodes must be updated accordingly after every insert and delete. Now, find $z_1$. As you do the search, check the $max$ attribute of all nodes $z$ in the search path such that $z_1 \le z \le z_2$ and remember the node $z_1'$ with the maximum $max$ attribute. Next, find $z_2$ similarly to also find $z'_2$. Finally, compare the $max$ attributes of $z_1'$, $z_1.right.maxT$, $z_2'$, and $z_2.left.maxT$ to find the overall maximum in the range $[z_1, z_2]$. The $left$ and $right$ attributes are pointers to the left and right child of a node. Since this procedure performs 2 searches in you postal code tree, it takes $O(\log n)$.

As for howmany, the only idea I have to prevent checking all postal codes is to create another AVL tree such that the key of each node is a number $m'$ representing the number of mailboxes and the value of the node is the number of postal codes with $m'$ mailboxes. Think of this as a reverse look-up map, such that given a number of mailboxes, it returns the number of postal codes that have such mailboxes. In the worst-case, each postal code will have different number mailboxes, so the size of this tree is $n$. Performing a howmany operation is just a search in the tree, which takes $O(\log n)$ time. However, an insert or delete operation will requires adding/deleting/updating of this tree, which also incurs an additional $O(\log n)$ time to insert and delete. But since its just an additive increase, it does not affect the overall asymptotic running-time of the two operations.

$\endgroup$
3
  • $\begingroup$ Interesting approach, if I were to use other DS except BST, what would be your recommendation to solve this problem? $\endgroup$
    – Aishgadol
    Apr 19 at 9:16
  • $\begingroup$ Is there any particular reason why BST is out of your option $\endgroup$
    – Russel
    Apr 19 at 9:54
  • $\begingroup$ BSTs are not out of my options, it's just that I'm limited to Splay/2-3/AVL BSTs, Heaps (binary, binomial) and priority queues, just that I'm not completely sure if the way I decided to use AVL trees to solve this problem is the most efficient approach, or there might be a more efficient approach that will solve some (if not all) the methods within better time complexity. $\endgroup$
    – Aishgadol
    Apr 19 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.