gsarda
BAN USERYaa true reading from end shall work. But still someone has to parse the file till end. Whether it is done by you in code or the API of the language you are using.
Doubt, if that will be acceptable, otherwise anyone will think that as first solution but no one will post that..
Yup that's correct that choice of algorithm will depend on the file structure and line structure too.
But looking to the problem given, it seems to be simple text file which can be read from starting only. If data is coming from the network or its in a disk based files, problem will completely change. We shall have different problems for the specific scenarios.
Looking towards a simple and best solution, its easy to maintain two pointers. Let's not complex the problem without the need :) Else it will be like confusing the interviewer :P
Nice to see the brainstorming the problem!!
1) Sort the sets on the basis of second number. Set (a,b) should be sorted on 'b'
- gsarda December 02, 20132) Then, take the series satisfying second condition, that is, out of sets (a,b) & (c,d) b should be less than c.
For example,
(4,5) (7,9) (1,2) (11,15) (3,18)
After sorting it becomes:
(1,2)
(4,5)
(7,9)
(11,15)
(3,18)
It is being assured that in (a,b) a is always less than b.
Now, we can choose elements with respect to second condition as out of two sets, (a,b) & (c,d) b should be less than c.