Sorting squares of an integer array

Question

I had this question in an interview recently. Given a sorted array of integers, return a list of those integers squared, with the squares sorted. So given an array of these numbers:

-5, -3, 1, 2, 4 

the result should be this:

1 4 9 16 25 

I came up with this solution using Java 8 streams, but is there a way to do this without the call to Array.sort?

public static int[] sortedSquares(int[] arr) { arr = Arrays.stream(arr).map(i -> i * i).toArray(); Arrays.sort(arr); return arr; } 

Answer 1

One way to be more concise is to use the Stream.sorted() method right in the stream:

public static int[] sortedSquares(int[] arr) { arr = Arrays.stream(arr).map(i -> i * i).sorted().toArray(); return arr; } 

Answer 2

For an interview, this is bad code. It is \$O(n \log n)\$. But it can be done in \$O(n)\$ time. Your code does not show your skills in that direction. Also, many interviewers (justifiably) will be unhappy for using streams. Streams may look cute but at scale like Gmail, they cause performance problems.