2
$\begingroup$

I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$
and it can be occupied or not.

Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, Queues, Binary Trees.

$O(n)$ Space complexity available.

Using AVL OR B-Tree is a must.

I have to support these functions:

1) $\text{Init(n)}$ : Initializes the data structure with $n$ unoccupied rooms, the indexing of the rooms is $1-n$
this has to work at $O(n)$ time complexity

For the next functions: $l$ and $r$ do not have to be a number of an occupied room-

2) $\text{GetUnOcc(l,r)}$ : Gets $l$ -Left and $r$ - Right (Does not have to be an occupied room number) , 2 numbers that defined a range of numbers and I need to count how many hotel rooms are not occupied between them (Including). Has to work at $O(\log_2{n})$ Time complexity

3) $\text{GetMinUnOcc(l,r})$ : Gets $l$-Left and $r$-Right, 2 numbers that define a range of numbers, this one adds the person to the hotel at the smallest room that is not yet occupied between $l-r$ (Including).
Has to work at $O(\log_2{n})$ Time complexity

4) $\text{GetOut(r)}$ : It gets a room number and deletes the person from that Room/Hotel, making room number $r$ unoccupied.
Has to work at $O(\log_2{n})$ Time complexity

My Go:

Init: I thought about using an AVL tree with a boolean array.
We initialize it $O(n)$ by just making an array of False (Unoccupied) which takes $O(n)$

GetUnOcc(l,r) : I thought about this formula:
$\text{#UnOcc} = r - l + 1 - \text{Occupied}$ so we need to find how many rooms are occupied between $l-r$ but I am not sure how to do so in $O(\log_2{n})$

GetMinUnOcc is much harder because I cannot determine which value is the smallest, let's say $l=3$ and $r=10$ and every room between $3-8$ and room $10$ are occupied, and I need to return $9$ (because it is the smallest which is not occupied)

Let's say I have this tree (as Steven suggested to build an AVL of unoccupied rooms) so in this matter it is $\text{Init(10)}$ And Now I want to do $\text{GetMinUnOcc(5,7)}$ so it should delete $5$ from the tree as it will become occupied. But in what you suggest, we find the successor of $l=5$ which is his parent, $6$ and delete it, but, $5$ is not occupied and we want to return the minimum so we need to actually delete $5$, where am I wrong? Thank you!
enter image description here

I would appreciate your help / hints to solve this hard question! Thank you!

$\endgroup$
2
  • $\begingroup$ There might be a typo. Did you want to say that GetUnOcc($l$,$r$) returns the number of unoccupied rooms between $l$ and $r$? $\endgroup$ – Steven May 25 '20 at 12:09
  • $\begingroup$ @Steven Yes you are correct. I will fix it $\endgroup$ – MathAsker May 25 '20 at 12:21
3
$\begingroup$

Maintain an AVL tree $T$ containing the indices of the unoccupied rooms. For each vertex $v$ of the tree additionally maintain the number $\eta(v)$ of vertices in the subtree of $T$ rooted at $v$.

1) Init: create an AVL tree with keys $\{1, \dots, n\}$. This requires $O(n)$ time.

2) GetUnOcc($l$, $r$): Find the vertex $u$ associated with the successor of $l$ in $T$ (possibly $l$ itself). Find the vertex $v$ associated with the predecessor of $r$ in $T$ (possibly $r$ itself). If the key of $u$ is larger than the key of $v$ return $0$. Otherwise find the least common ancestor $w$ of $l$ and $r$. Initialize the number $x$ of unoccupied rooms to $0$. Walk from $u$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=u$ or the previous vertex in the walk was the left child of $z$, let $z'$ be the right child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$). Walk from $v$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=v$ or the previous vertex in the walk was the right child of $z$, let $z'$ be the left child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$). Return $1+x$.

3) GetMinUnOcc($l$, $r$): Search for the vertex $u$ associated with the successor of $l$ in $T$ (where the successor of $l$ might be $l$ itself). If the key of $u$ is at most $r$, delete $u$ from the tree subtract $1$ from the values $\eta(z)$ of all proper ancestors $z$ of $u$. Otherwise all rooms between $l$ and $r$ are already occupied.

4) GetOut(r): Insert a new vertex $z$ with key $r$ into the tree with $\eta(z)=1$. Increment by $1$ the values $\eta(z')$ of all the proper ancestors $z'$ of $z$.

$\endgroup$
22
  • $\begingroup$ Hey, Thank you very much for your answer! but isn't initializing an AVL tree takes $O(n log_2 n)$ Time complexity? $\endgroup$ – MathAsker May 25 '20 at 12:33
  • $\begingroup$ It takes $O(n \log n)$ time but, in particular, it takes $O(n)$ time (recall that $O(n)$ is a subset of $O(n \log n)$ ). You do not need to initialize the tree by iteratively adding one element at a time. Just construct a BST on $n$ nodes that is complete up to the penultimate level. This is also an AVL tree since the balance factor of each node must be in $\{-1, 0, 1\}$. $\endgroup$ – Steven May 25 '20 at 12:37
  • $\begingroup$ So let's say that we have 4 rooms available then we have a tree like this: 2 1 .. 3 .........4 which are not occupied yet except 2 . Then we want to insert between [2-4] then it must take 3 (We know that 1 isnt occupied but its not between 2-4) but in the function you said to mark 2 as occupied which it is and then it returns the predecessor and marks it as occupied, no? $\endgroup$ – MathAsker May 25 '20 at 12:42
  • $\begingroup$ If $2$ is occupied then $2$ is not in the tree. The three only contains unoccupied rooms. If you search for $2$ in a tree containing \{1, 3, 4\} you'll either 1) find $1$, in which case you'll look at the successor of $1$ in the tree, which is $3$, and mark $3$ as occupied or 2) find $3$, which you'll mark as occupied. In any case the operation works as expected. $\endgroup$ – Steven May 25 '20 at 12:49
  • 1
    $\begingroup$ Otherwise let $x$ be the $2^{k-1}$-th element in $S$. Define $S^- = \{y \in S : y<x\}$ and $S^+=\{y \in S : y>x\}$ so that $|S^-|=|S^+|=2^{k-1}-1$. Recursively apply the algorithm on $S^-$ and $S^+$ to obtain two BSTs $T^-$ and $T^+$, respectively. Create a vertex $u$ with key $x$, let $T^-$ be the left subtree of $u$ and $T^+$ be the right subtree of $u$. The time complexity of this algorithm can be found by solving the recurrence equation $T(n) <= 2T(n/2) + O(1)$. By the master theorem we know that $T(n) = O(n)$. $\endgroup$ – Steven May 27 '20 at 14:58
0
$\begingroup$

This can be done using a simple array.

Note that the complexity depends on the total number of rooms, and not on the number of (un)occupied rooms. So we might as well store all rooms. The trick to do the counting of free rooms is basically the same as in the case of AVL trees in the other answer. On top of the linear list of arraus we build a complete binary tree, such that each node stores the number of free rooms in the interval of rooms below.

We can find the number of free rooms in an interval by looking for the rooms $\ell$ and $r$ in the tree, and start counting from the node where the two paths diverge. Then for $\ell$ we count the free rooms to the right, for $r$ the free rooms to the left.

The next free room from position $\ell$ is found as follows. First go up in the tree untill we find a node where we came from left, and the right subtree has an unuccupied room. Then go down to the first free spot.

Going up and down, left and right is done using bit-matic. I strore the rooms in the odd indices. The ndes above are even. The number of trailing zeroes in the binary index indicates the level of the node. Left nodes end with "01" and then zeroes, right nodes have "11" and zeroes.

Picture below depicts eight rooms, stored at positions 1,3,5,...,13,15. Numbers in the tree indicate free rooms. So in this situation leaves 3,5,9,11,15 are occupied, indicating rooms 2,3,5,6 and 8.

enter image description here

Storing the complete tree as an array is also done for binary heaps. However, the representation is different. For the heap the root is the first node in the array. Kind of upside down from this one.

$\endgroup$
2
  • $\begingroup$ But was is the name for this representation, using intervals? I have seen it, but cannot remember the name. $\endgroup$ – Hendrik Jan May 27 '20 at 12:16
  • $\begingroup$ Ah. In might be a Fenwick-tree, also known as binary indexed tree? Pictures on wikipedia are not helpful, Found more intuitive ones on topcoder. $\endgroup$ – Hendrik Jan May 27 '20 at 15:23

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.