0
$\begingroup$

Given $n$ cities, describe a data structure which supports the following functions:

Init$(n)$ - initializes the data structure in $O(1)$

Visit$(j,i)$ - adds "citizen from city $j$ would like to visit city $i$" in $O(1)$

Favorite($k$) - prints the $k$ most favorite cities in descending order in $O(k)$ (ignore ambiguity such as 2 cities with same amount)

I can't find how to do the last one in $O(k)$, hints would be appreciated.

$\endgroup$
17
  • 1
    $\begingroup$ Can you be a bit more precise in the description of the data structure operations? What's the role of $j$ in Visit($j$, $i$)? What do you mean by "the $k$ most favorite cities"? Is it legal to perform Visit($j$, $i$) more than once for the same pair $(j,i)$? $\endgroup$
    – Steven
    Nov 13, 2020 at 19:46
  • $\begingroup$ @Steven it is just a representation for a city, but I see your point. There are actually more functions which I didn't include due to irrelevance to my question, which use this information. If you think it would help i'll add them. $\endgroup$ Nov 13, 2020 at 20:06
  • $\begingroup$ @Steven Also, I mean the cities which have the biggest amount of people who want to visit them, and yes it is legal. $\endgroup$ Nov 13, 2020 at 20:12
  • $\begingroup$ Can you confirm that the time needed by Init$(n)$ must be $O(1)$ (and not $O(n)$)? The problem is easy to solve if you can spend $O(n)$ time. $\endgroup$
    – Steven
    Nov 13, 2020 at 20:15
  • 1
    $\begingroup$ Please don't provide clarifications in the comments (e.g., the definition of most favorite cities). Instead, edit your question to include all relevant information and to read well for someone who encounters it for the first time; and then flag as 'no longer needed' those comments. $\endgroup$
    – D.W.
    Nov 13, 2020 at 22:18

1 Answer 1

2
$\begingroup$

The idea is to keep a sorted list of non-empty "buckets". Each bucket $v$ is associated to a certain number $n_v$ of people that wish to visit some city and contains all the cities $c$ that wish to be visited by exactly $n_v$ people.

By keeping a suitable set of pointers cities can be moved from one bucket to the next in constant time. To perform a Favorite($k$) operation it suffices to look at the "last" buckets in the sorted list.


The data structure consists of:

  • A doubly-linked list $L$. Each node $v$ of $L$ is associated to an integer $\eta_v$ and to a (pointer) to an inner list $\ell_v$ of cities $c$ such that exactly $\eta_v > 0$ people want to visit $c$. The integers $\eta_v$ are appear in increasing order when traversing $L$.

  • An array $N$ of $n$ elements. The $i$-th element $n_i$ of $N$, if initialized, is the number of people that want to visit the $i$-th city.

  • An array $P^L$ of $n$ elements. The $i$-th element $p^L_i$ of $P^L$, if initialized, is a pointer to the node $v$ of $L$ such that $\eta_v = n_i$.

  • An array $P^\ell$ of $n$ elements. The $i$-th element $p^\ell_i$ of $P^\ell$, if initialized, is a pointer to the node containing the $i$-th city in the list $\ell_v$, where $v$ is the node of $L$ pointed by $p^L_i$.

Init$(n)$:

  • Create an empty list $L$. Allocate (but do not inizialize) the arrays $N$, $P^L$, and $P^\ell$ in $O(1)$ time.

Visit$(\cdot,i)$:

  • If $n_i$ is initialized, delete (in constant time) the node pointed by $p^\ell_i$ from the list $\ell_v$ where $v$ is the node of $L$ pointed by $p^L_i$. If $\ell_v$ is empty, delete $v$ from $L$. Increment $n_i$.

  • Otherwise, if $n_i$ is not initialized, set $\eta_i=1$.

  • Find the node $v'$ of $L$ such that such that $\eta_{v'}=n_i$, if it exists. Notice that $v'$ can only be the node of $L$ following (the possibly just deleted) node $p^L_i$ in $L$.

  • If $v'$ did not exists, then create it (in constant time).

  • Add city $i$ to a new node $z$ of $\ell_{v'}$.

  • Make $p^L_i$ point to $v'$.

  • Make $p^\ell_i$ point to $z$.

Favorite$(k)$:

  • Let $v$ be last node of $L$.
  • While $k>0$ and $v$ exists:
    • Let $x$ be a pointer to the first node of $\ell_v$
    • While $k > 0$ and $x$ exists:
      • Return the city stored in $x$.
      • Set $x$ to the vertex following $x$ in $\ell_v$ (possibly none).
      • Decrement $k$
    • Set $v$ to the vertex preceding $v$ in $L$ (possibly none).
$\endgroup$
6
  • $\begingroup$ I think you confused $p_i^{\ell}$ and $p_i^L$ at the end of the visit explanation? I think I understand your design, I'll be sure to accept this answer later. $\endgroup$ Nov 14, 2020 at 8:28
  • $\begingroup$ Can you point me to the specific line where the mistake is? (I can't seem to find it) $\endgroup$
    – Steven
    Nov 14, 2020 at 9:40
  • $\begingroup$ Never mind my bad $\endgroup$ Nov 14, 2020 at 10:08
  • 1
    $\begingroup$ It seems right to me, since $v'$ is a node in $L$, and therefore it should be pointed to by the pointer $p_i^L$ while $z$ is a node in the list $\ell_{v'}$ therefore it should be pointed to by the pointer to the inner list $p_i^|ell$. $\endgroup$
    – Steven
    Nov 14, 2020 at 10:09
  • 1
    $\begingroup$ @paxtibimarce, $L$ is a doubly-linked list and you can keep pointers both to the first and last nodes of $L$ (and traverse $L$ in either direction). $\endgroup$
    – Steven
    Nov 14, 2020 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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