This discussion is archived
1 2 Previous Next 29 Replies Latest reply: Dec 16, 2010 4:45 PM by EJP RSS

Collection Question in ArrayList

824049 Newbie
Currently Being Moderated
Plz find the question below:-

There is a table "STUDENT"

id marks name
**** ****** ************
1 20 stud1
2 25 stud2
3 25 stud3
4 18 stud4
5 25 stud11
6 20 stud17

Now consider that there is a java class called "Student" whose attributes are "id", "marks" and "name" .
So think each row in the table as one "Student" object and all of them are added into the ArrayList.

Therefore ArrayList will contain group of "Student" objects as above.

Question
**********

Given the above ArrayList, what would be the optimistic way of finding the names of those students whose marks are 2nd highest.

Plz help me in finding the answer for this ArrayList Problem in an optimized way by using any sort of Collection mechanism.
  • 1. Re: Collection Question in ArrayList
    EJP Guru
    Currently Being Moderated
    I would think speaking in Java that a PriorityQueue would be close to optimum. It imposes a partial ordering which is completed per item removed, and you can stop removing items once you get to the third level of marks, so you're not paying for a total ordering.
  • 2. Re: Collection Question in ArrayList
    802316 Pro
    Currently Being Moderated
    If you just need the two highest marks (or just the second highest) the fastest approach would be to have a single look which keeps track of the two highest entries and return the second highest as the solution.
    This way you don't need to re-organies the collection or create another collection.
  • 3. Re: Collection Question in ArrayList
    DrClap Expert
    Currently Being Moderated
    Peter Lawrey wrote:
    If you just need the two highest marks (or just the second highest) the fastest approach would be to have a single look which keeps track of the two highest entries and return the second highest as the solution.
    But the requirement is to return the students who received the second-highest score. In the example there are two of them, and there could be many in other examples. Just a quick scan to determine that the second-highest score is 20 doesn't produce that information.
  • 4. Re: Collection Question in ArrayList
    796440 Guru
    Currently Being Moderated
    Another approach would be to define a Comparator that uses marks to compare. Call Collections.sort() using that Comparator, start on the end where the high scores are, and do the rest like you wouuld do it "manually." That is, start walking toward the lower scores. When the score changes, you've found the second highest score. When it changes again, you're done with the students that have that second highest score. In the mean time, as you're walking, each student that matches that second highest score gets added to a second list. Once you hit the second change of score, you've found all the students with the second highest and put them in that second list, and you're done.
  • 5. Re: Collection Question in ArrayList
    EJP Guru
    Currently Being Moderated
    Sorting the array completely can't be more efficient than my suggestion.
  • 6. Re: Collection Question in ArrayList
    796440 Guru
    Currently Being Moderated
    EJP wrote:
    Sorting the array completely can't be more efficient than my suggestion.
    Never suggested that it was. Just offering it as an alternative. It seems a more natural fit, to me, and it's unlikely that for this particular use case any performance benefits of the priority queue will be noticed or needed.

    Although I in all honesty, now that I think about it, I don't see how your solution will be any more efficient. Collections.sort() is O(n log(n)) IIRC. You're suggesting putting all the elements into a priority queue, and then pulling off the queue until we've hit the 3rd priority tier, right? My understanding is that adding one element to the queue is an O(log(n)) operation, because it's effectively a binary search, and for n elements, the overall approach is O(n log(n)), and it is a full ordering.

    Or am I missing something?
  • 7. Re: Collection Question in ArrayList
    EJP Guru
    Currently Being Moderated
    But we're not processing N elements. We're only constructing a partial ordering over N, then extracting a full ordering over the M elements that terminates when we get to the third level, then we stop. M <= N.
  • 8. Re: Collection Question in ArrayList
    802316 Pro
    Currently Being Moderated
    DrClap wrote:
    Peter Lawrey wrote:
    If you just need the two highest marks (or just the second highest) the fastest approach would be to have a single look which keeps track of the two highest entries and return the second highest as the solution.
    But the requirement is to return the students who received the second-highest score.
    When I said entries, I meant students.
    In the example there are two of them, and there could be many in other examples.
    There could be a lot of things if the requirements changed, but in this case there only two you need to keep track of.
    Just a quick scan to determine that the second-highest score is 20 doesn't produce that information.
    It wouldn't match your requirement, but having "the two highest entries" would do what the OP requires the quickest.
  • 9. Re: Collection Question in ArrayList
    802316 Pro
    Currently Being Moderated
    @EJP, I assume you mean, find the highest entry and remove it, find the second highest entry and return it.

    I would assume that a single pass of the students would be quicker as the loop/comparison time is small and the locality of data will be your main cost (bringing the student records into cache) Once its in cache, the second pass is quick, only provided all you student fit into cache.
  • 10. Re: Collection Question in ArrayList
    802316 Pro
    Currently Being Moderated
    In any case we are talking about small amounts of data. For say 1000 student records, any decent approach is likely to perform fast enough, so the simplest approach might be best. IMHO I would just use Arrays.sort() which will take less than 1 ms longer, but will be more efficient on my time and anyone reading the code. (I picked 1000 because the students have to have a common assessment which is worth comparing, so while universities have more student you would compare all their marks across all subjects)

    Note: In any large sample of students, there is highly likely to be duplicate scores, esp if there are only 101 possible grades. (0% to 100%) You are likely to find say 3 students have the same top grade and there is no obviously fair way to pick who is the second highest grader. Its reasons like this that developers spend a relatively small amount of time writing the final code, and much more time gathering requirements and understanding the problem. ;) My estimate/guess is that if you typed the final code for a real program again from a print out it would take about 10% of the time it took the first time. (If you were no tempted to "improve it" as you went)
  • 11. Re: Collection Question in ArrayList
    EJP Guru
    Currently Being Moderated
    @EJP, I assume you mean, find the highest entry and remove it, find the second highest entry and return it.
    No. I mean retrieve and remove the head of the PriorityQueue, which by definition is the highest entry. PriorityQueue.poll(). Then do that again. And again. When the key changes for the first time, start collecting, as you are now on the 2nd rank. When the key changes for the second time, stop iterating, as you are now on the 3rd rank.
    I would assume that a single pass of the students would be quicker as the loop/comparison time is small and the locality of data will be your main cost (bringing the student records into cache) Once its in cache, the second pass is quick, only provided all you student fit into cache.
    I don't understand what you mean by 'a single pass'. You need an ordering so you can find the 2nd-ranking students and that implies at least a partial sort. You can't accomplish that in a single pass as far as I can see, or at least if you can it hasn't been suggested yet.
  • 12. Re: Collection Question in ArrayList
    EJP Guru
    Currently Being Moderated
    In any case we are talking about small amounts of data.
    In any case we have zero evidence about the size of the dataset, and in any case the OP asked for the optimal solution. Personally I would probably just use Collections.sort() as jverd suggested, as I personally wouldn't care about the optimal solution over a small dataset. But that doesn't answer the OP's question.
  • 13. Re: Collection Question in ArrayList
    824049 Newbie
    Currently Being Moderated
    Hi,

    Thanks for ur immediate reply. Cud u plz give ur code as for me its very difficult to understand the vocabulary.
  • 14. Re: Collection Question in ArrayList
    824049 Newbie
    Currently Being Moderated
    Hi,

    Thanks for ur quick response.Cud u plz give ur code as for me its very difficult to understand the vocabulary.
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points