John McD
BAN USERThis is the correct answer.
If you imagine an n by n matrix of the sums of each pairing of the arrays, the FJ algorithm can pick the Kth largest pair. It's that not easy to follow, but is described in section II of www dot ist.caltech.edu/~sthite/pubs/selectX+Y.pdf
If you dug in, you'd find that you can modify the algorithm, to keep track of which part of the n by n matrix that will have the K largest values, still in O(n) time.
Then you can iterate through the K values to compute and print them, which takes O(k) time, but because in this statement of the problem n==k, the overall runtime is O(n).
All of this said, most interviewers don't expect that you know or can derive this algorithm in an interview, but just that you can discuss possible solutions intelligently and pick up solutions with help.
This is actually the same as the result of F&J. Had the problem had different length arrays with the larger length m. The runtime to describe the K largest pairs has a run time O(m).
- John McD May 28, 2010