1
$\begingroup$

Regarding this question:

You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$. Suggest a data structure that allows to answer in $O(1)$ steps the number of keys in the range $a$ to $b$ (note that $a, b$ are not necessarily integers). The construction of data structure should cost at most $O(n)$ steps.

  1. Describe in few sentences the data structure.
  2. Write a pseudocode for constructing the data structure.
  3. Write a pseudocode for the numberKeys(NewDataStructure,a,b).
  4. Give a short explanation of the time and space complexity of (2) and (3).

Can someone please explain me what "the number of keys in the range $a$ to $b$" means?

$\endgroup$
5
1
$\begingroup$

It probably means "the number of array elements whose value is between $a$ and $b$".

For the solution, it is crucial that the number of possible values of array elements is $O(1)$.

$\endgroup$
5
  • $\begingroup$ I see, so building a BST that holds key values? Something like that? $\endgroup$ – Oliver May 16 at 16:29
  • $\begingroup$ That’s an overkill. $\endgroup$ – Yuval Filmus May 16 at 16:39
  • $\begingroup$ BST that holds key values [is] overkill in conceptual and implementation effort while meeting answer in $O(1)$ steps by plugging $10n$ (or $n$?) $\in O(1)$ - bold. $\endgroup$ – greybeard May 16 at 19:58
  • $\begingroup$ @YuvalFilmus What do you mean by overkill? Is that good? $\endgroup$ – Math4me May 25 at 8:51
  • $\begingroup$ Look it up in the dictionary. $\endgroup$ – Yuval Filmus May 25 at 9:25

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