Re:Show HN: Learn to Code for Free
by ue_ on Wednesday November 23, 2016 @09:41AM
(#13022930)
I have no idea if this works (it did for 3 test cases), and I still end up reading through the array (but not the file) twice.
What way would you do it? I feel like I'm missing something.
[ Parent
| on HN ]
Re:Show HN: Learn to Code for Free
by pythonaut_16 on Wednesday November 23, 2016 @01:24PM
(#13024578)
I would probably keep a running total as I read through each line, then store `line_number: running_total` in a dictionary.
At the end, return the highest key in the dictionary for your total, and then run a reduce that returns the first key/value pair that is >= half the total
Thinking a little outside of the box - but if you could sort the lines by amount in ascending order, then total from both ends, take half after each addition, then shift a pointer to where "about half" would be based on where you were in the totaling (and which end) as you go.
I don't have any specific implementation - or if this idea would even work - but I do think sorting the lines first might be of help toward a better solution (I could be completely wrong on this). As well as tackling the totaling and checking from both ends of the list.
You'd have to keep track of everything, of course, in order to know at the end where in the -real list- (unsorted) the half-way total point is at. If this idea has any merit at least.