We have a universe $U = {0,1, …,u-1}$ and a set $S subseteq U$ of size
$n$. We will create a hash table containing all the elements of $S .$ Additionally, the hash table will contain every $prefix$ of the binary representation of every element in the set. We will create a doubly linked list of all the elements of S which are arranged in increased order of their values. Finally, with each $prefix$ $p$ in the hash table, store a minimum and a maximum: Among all the elements of $S$ which have $p$ as a $prefix$, minimum (resp., maximum) of $p$ will be the element with the minimum (resp., maximum) value.
- What is the space occupied by this data structure?
- How to perform insertion of a new element in $O(log u)$ time?
- Given a query $x in U$, the longest common prefix (lcp) operation will report that prefix in the
hash table which has the longest common prefix with $x$. How do you perform this operation by querying the hash table only $O(log log u)$ times? - Assume that the lcp operation can be performed in $O(log log u)$ time. Using the lcp operation,
how to perform predecessor search operation in $O(log log u)$ time?
My Take on the Problem:
For example, consider $u = 16.$ Then representing each integer in the universe will require four bits. If, say, $14$ is in $S$, then its binary representation is $1110$, and hence, all its prefixes $1, 11, 111, 1110$ will be stored in the hash table.
For the number $3$, an example, if $x = 110111$, and
hash table has two strings $y = 110100$ and $z = 111100$, then $y$ has a common prefix of length
four with $x$, while $z$ has a common prefix of length only two with $x$. Every element in
$U$ in binary representation requires $O(log u)$ bits. I have come up to this point.
Please provide a short description or pseudo code for number $2$ and $3$ and a solution for $4$ .
Thanks in advance!