1
$\begingroup$

I have just started learning algorithms and data structures and I came by an interesting problem.
I need some help in solving the problem.

There is a data set given to me. Within the data set are characters and a number associated with each of them. I have to evaluate the sum of the largest numbers associated with each of the present characters. The list is not sorted by characters however groups of each character are repeated with no further instance of that character in the data set. Moreover, the largest number associated with each character in the data set always appears at the largest position of reference of that character in the data set. We know the length of the entire data set and we can get retrieve the data by specifying the line number associated with that data set.
For Eg.
C-7
C-9
C-12
D-1
D-8
A-3
M-67
M-78
M-90
M-91
M-92
K-4
K-7
K-10
L-13
length=15
get(3)= D-1(stores in class with character D and value 1)
The answer for the above should be 13+10+92+3+8+12 as they are the highest numbers associated with L,K,M,A,D,C respectively.
The simplest solution is, of course, to go through all of the elements but what is the most efficient algorithm(reading the data set lesser than the length of the data set)?

$\endgroup$
  • 2
    $\begingroup$ If there are much more data elements than letters you can do a kind of binary search to find the last occurrence of each letter. $\endgroup$ – Hendrik Jan Sep 11 '17 at 12:22
  • $\begingroup$ The thing is we don't know what the elements are. Plus here we are not simply getting rid of some part of the data set. $\endgroup$ – user77108 Sep 11 '17 at 12:53
  • $\begingroup$ @HendrikJan Letters are not sorted $\endgroup$ – paparazzo Sep 11 '17 at 19:58
3
$\begingroup$

Say you have $n$ entries, $m$ distinct letters, and the $i$-th letter occurs $k_i$ times. You can find the last occurrence of the $i$-th letter using a variant of binary search: Double your step size until you find a different letter (or run out of the array), do binary search between your last and second-to-last step. This takes about $2\log k_i$ many steps. So in total you need about

$$\sum_{i=1}^m \log k_i = \log \prod_{i=1}^{m} k_i$$

many steps. That product is biggest when all terms are equal, so you have something like $m\log (n/m)$ many steps.

Naively implemented, this is not always better than looking at all elements though. If you work out all the details, you'll see that for example when $m=n$ you have to be a bit careful.

$\endgroup$
  • $\begingroup$ The number of searches to the database matters here, so in order to determine the step size, itself will consume searches to the database. Don't you think so? $\endgroup$ – user77108 Sep 11 '17 at 19:45

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.