You don't have to come up with the O(nlogn) solution. The naive approach (comparing every two points) in to nested for loops is good enough. explaining the O(nlogn) solution (divide and conquer) is a bonus, I don't think that anyone really expects you to be able to write an implementation during an interview.