## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
10
of 10 vote

1 approach

1) sort array by abs(x) as key (e.g. [1,2,3,-4,5,-6])
2) return [x**2 for x in array]

O(n log n) time

2 approach

1) do sqr for all negative and reverse list, do sqr for positive
2) merge 2 arrays like in merge sort but only 1 iteration needed

O(n) time
O(n) additional space (because of merge)

Actually it IS possible to do merge in linear time and constant extra space. By algorithm is not trivial :)

Google for it: Bing-Chao Huang, Michael A. Langston, “Practical In-Place Merging” (1988).

So best solution will be:
O(n) time
O(1) extra space

Comment hidden because of low score. Click to expand.
0

``````public Integer[] sqArray(int[] arr)
{
ArrayList<Integer> arr_negetive = new ArrayList<Integer>();
ArrayList<Integer> arr_positive = new ArrayList<Integer>();
for(int i=0;i<arr.length;i++){
if(arr[i] < 0){
}
else{
}
}
Integer[] array_result = new Integer[arr.length];
int n = arr_negetive.size()-1;//negetive counter
int p = 0;//positive counter
int count = 0;
while(count < arr.length)
{
System.out.println(p+","+n);
if(n < 0 && p < arr_positive.size())
{
array_result[count] = (arr_positive.get(p));
p++;
}
else if (p == arr_positive.size() && n >= 0)
{
array_result[count]=(arr_negetive.get(n));
n--;
}
else if(arr_negetive.get(n) < arr_positive.get(p))
{
array_result[count]=(arr_negetive.get(n));
n--;
}
else
{
array_result[count]=(arr_positive.get(p));
p++;
}
count++;

}
if(arr_negetive.size() == 0)
{
return arr_positive.toArray(new Integer[arr_positive.size()]);
}
else if( arr_positive.size() == 0)
{
return arr_negetive.toArray(new Integer[arr_negetive.size()]);
}
else
{
return array_result;
}

}``````

This is the best solution as it will run O(n)

Comment hidden because of low score. Click to expand.
6
of 6 vote

O(n) - single pass

``````int[] sortedSquare(int[] sortedArray)
{
var sortedSquare = new int[sortedArray.Length];
int front = 0;
int back = sortedArray.Length - 1;
int currentPos = sortedArray.Length - 1;
while(front <= back)
{
int frontSq = sortedArray[front] * sortedArray[front];
int backSq = sortedArray[back] * sortedArray[back];

if(frontSq <= backSq)
{
sortedSquare[currentPos--] = backSq;
--back;
}
else
{
sortedSquare[currentPos--] = frontSq;
++front;
}
}

return sortedSquare;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Notice that a sorted array with negative integers can be thought of as two sorted lists, one sorted from greatest abs value to lowest abs value, and the other sorted from lowest abs value to greatest abs value.

1) Use a merge method working from the start of the array for negative numbers, and the end of the array for positive numbers. Square the largest numbers, and use the resulting values when building a new array from largest to smallest value.

``````def sortedSquaredArray(sortedArray):
sqSortedArray = []
negIndex = 0
posIndex = len(sortedArray) - 1
while negIndex <= posIndex:
if (sortedArray[negIndex])**2 > (sortedArray[posIndex])**2:
sqSortedArray =  [(sortedArray[negIndex])**2] + sqSortedArray
negIndex += 1
else:
sqSortedArray = [(sortedArray[posIndex])**2] + sqSortedArray
posIndex -= 1

if negIndex >= len(sortedArray) or sortedArray[negIndex] >= 0:
break
elif posIndex <= 0 or sortedArray[posIndex] <= 0:
break

if negIndex > posIndex:
return sqSortedArray
elif negIndex >= len(sortedArray) or sortedArray[negIndex] >= 0:
while posIndex >= negIndex:
sqSortedArray = [(sortedArray[posIndex])**2] + sqSortedArray
posIndex -= 1
return sqSortedArray
elif posIndex <= 0 or sortedArray[posIndex] <= 0:
while negIndex <= posIndex:
sqSortedArray = [(sortedArray[negIndex])**2] + sqSortedArray
negIndex += 1
return sqSortedArray

sortedData = [-3, -1, 0, 2, 5, 7]
sqSortedData = sortedSquaredArray(sortedData)
print('Orig: ' + str(sortedData))
print('Sqst: ' + str(sqSortedData))``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Swift:

``````let array = [-3, 1, 5]
let result = array.map({ \$0 * \$0 }).sorted()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int[] squareOfSortedData(final int[] data) {
if (data == null || data.length == 0) {
return data;
}
for (int i = 0; i < data.length; ++i) {
data[i] = BigInteger.valueOf(data[i]).pow(2).intValue();
}
return data;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var intList = new List<int>() {-1, 2, -3, 4, -5, 6};
intList.Sort();
var squareListOfInt = new List<int>();
foreach (var t in intList)
{
var squaredValue = Math.Pow(t, 2);
squareListOfInt.Sort();``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

var intList = new List<int>() {-1, 2, -3, 4, -5, 6};
intList.Sort();
var squareListOfInt = new List<int>();
foreach (var t in intList)
{
var squaredValue = Math.Pow(t, 2);
squareListOfInt.Sort();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var intList = new List<int>() {-1, 2, -3, 4, -5, 6};
intList.Sort();
var squareListOfInt = new List<int>();
foreach (var t in intList)
{
var squaredValue = Math.Pow(t, 2);
squareListOfInt.Sort();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ public Long[] getSquareOfNumbers(Long[] numbers) {
if (numbers == null || numbers.length == 0) {
return numbers;
}
return Stream.of(numbers).map(number -> number * number).toArray(Long[]::new);
}}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Long[] getSquareOfNumbers(Long[] numbers) {
if (numbers == null || numbers.length == 0) {
return numbers;
}
return Stream.of(numbers).map(number -> number * number).toArray(Long[]::new);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Long[] getSquareOfNumbers(Long[] numbers) {
if (numbers == null || numbers.length == 0) {
return numbers;
}
return Stream.of(numbers).map(number -> number * number).toArray(Long[]::new);
}
and``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Long[] getSquareOfNumbers(Long[] numbers) {
if (numbers == null || numbers.length == 0) {
return numbers;
}
return Stream.of(numbers).map(number -> number * number).toArray(Long[]::new);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C#, O(n) time, using List<>, could use arrays and still keep it to O(n) time

``````public static int[] SortedSquare(int[] inp)
{
List<int> negatives = new List<int>();
List<int> positives = new List<int>();
List<int> r = new List<int>();
for (int i = 0; i < inp.Length; i++)
{
if (inp[i] < 0)
{
}
else
{
}
}

int p = 0;
int n = 0;
bool keepGoing = true;
while (keepGoing)
{
if (n < negatives.Count())
{
if (p < positives.Count())
{
if (negatives[n] < positives[p])
{
n += 1;
}
else
{
p += 1;
}
}
else
{
{
n += 1;
}
}
}
else
{
if (p < positives.Count())
{
p += 1;
}
else
{
keepGoing = false;
}
}
}
return r.ToArray();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// Given sorted array of integers return squares of those integers
func sortedSquaredArray(arr: [Int]) -> [Int] {
let array = arr.map({ (a) -> Int in
return a * a
})
return array.sorted()
}

sortedSquaredArray(arr: [-2,1,3,5])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// Given sorted array of integers return squares of those integers
func sortedSquaredArray(arr: [Int]) -> [Int] {
let array = arr.map({ (a) -> Int in
return a * a
})
return array.sorted()
}

sortedSquaredArray(arr: [-2,1,3,5])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer solution - 1st pointer points to the first +ve integer, second pointer points to the last -ve integer
* Implement merge routine like algorithm
* @param nums
* @return
*/
private int[] go(int[] nums){
int[] res = new int[nums.length];
int pos = Integer.MAX_VALUE;
int neg = -1;
for(int i=0;i<nums.length;i++){
if(nums[i] >= 0){
pos = Math.min(pos, i);
}
else{
neg = i;
}
}
int fill = 0;
while(neg >=0 || pos < nums.length){
if(neg >=0 && pos < nums.length){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
else{
res[fill++] = nums[pos]*nums[pos];
pos++;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer solution - 1st pointer points to the first +ve integer, second pointer points to the last -ve integer
* Implement merge routine like algorithm
* @param nums
* @return
*/
private int[] go(int[] nums){
int[] res = new int[nums.length];
int pos = Integer.MAX_VALUE;
int neg = -1;
for(int i=0;i<nums.length;i++){
if(nums[i] >= 0){
pos = Math.min(pos, i);
}
else{
neg = i;
}
}
int fill = 0;
while(neg >=0 || pos < nums.length){
if(neg >=0 && pos < nums.length){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
else{
res[fill++] = nums[pos]*nums[pos];
pos++;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* Two pointer
* increment for positive, decrement for negative
*/
public int[] sort(int[] nums){
int len = nums.length;
int pos = Integer.MAX_VALUE;
int neg = -1;
int[] res = new int[len];
for(int i=0;i<nums.length;i++){
if(nums[i] >=0){
pos = i; //first +ve index
break;
}
else{
neg = i; //last -ve index
}
}
int fill = 0;
//similar to merge routine
while(neg >= 0 || pos < len){
if(neg >= 0 && pos < len){
if(Math.abs(nums[neg]) > nums[pos]){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else{
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
else if(pos < len){
res[fill++] = nums[pos]*nums[pos];
pos++;
}
else if(neg >= 0){
res[fill++] = nums[neg]*nums[neg];
neg--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String args[]) {

final int[] numbers = {-9,-1,1,3,5};

PriorityQueue pq = squareOfSortedData(numbers);

while (!pq.isEmpty())
System.out.println(pq.poll() + ",");
}

public static PriorityQueue squareOfSortedData(final int[] data) {
PriorityQueue pq = new PriorityQueue();

if (data == null || data.length == 0) {
return pq;
}
for (int i = 0; i < data.length; ++i) {
}
return pq;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Ruby:

``````def square_sorted_array arr
arr.map! { |int| int ** 2 }.sort!
end``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution
Use two pointers, back and front.
Increment front if sqaure > sqaure of back else decrement back. Fill the array from behind

``````int[] sortedSquare(int[] sortedArray)
{
var sortedSquare = new int[sortedArray.Length];
int front = 0;
int back = sortedArray.Length - 1;
int currentPos = sortedArray.Length - 1;
while(front <= back)
{
int frontSq = sortedArray[front] * sortedArray[front];
int backSq = sortedArray[back] * sortedArray[back];

if(frontSq <= backSq)
{
sortedSquare[currentPos--] = backSq;
--back;
}
else
{
sortedSquare[currentPos--] = frontSq;
++front;
}
}

return sortedSquare;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Like mentiones previosly con be solved in O(n) is an example of join two sorted lists

``````public static int[] GetSortedArrayOfSquares(int[] a)
{
if (a == null || a.Length == 0)
return a;

// Set I at the begining of positive numbers and J in the last negative number
int i=0;
while (a[i] < 0)
i++;
int j = i - 1;

int index = 0;
int[] result = new int[a.Length];

// Join both sorted lists
while (j >=0 && i < a.Length)
{
int n1 = a[i] * a[i];
int n2 = a[j] * a[j];

if (n1 <= n2)
{
result[index] = n1;
i++;
}
else
{
result[index] = n2;
j--;
}

index++;
}

// Copy the remainder
while (j >=0)
{
result[index] = a[j] * a[j];;
j--;
index++;
}

while (i < a.Length)
{
result[index] = a[i] * a[i];
i++;
index++;
}

return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

// this is O(n) solution

void compute_sorted_squares(int *sqrs, int * arr, int num)
{
if ( !arr || (num < 1)) return;

int begin = 0;
int end = num - 1;
int change = -1;
int val;
int prev_val = arr[0];
for (int i = 0; i < num; i++) {
val = arr[i];
if ( prev_val < 0 && val > 0){
change = i;
}
prev_val = val;
}

/* all -ve or all +ve */
if (change == -1) {
for(int i = 0; i < num; i++) {
sqrs[i] = arr[i] * arr[i];
}
return;
}

int fwd = change;
int bwd = change - 1;
int pos = 0;
int dir = 0;
int dir_start = -1;
while ( pos < num ) {
int fwd_sqr = arr[fwd] * arr[fwd];
int bwd_sqr = arr[bwd] * arr[bwd];
if (bwd_sqr > fwd_sqr) {
sqrs[pos] = fwd_sqr;
fwd++;
} else {
sqrs[pos] = bwd_sqr;
bwd--;
}
pos++;
if ( bwd == -1 ) {
dir = 1;
dir_start = fwd;
break;
}
if ( fwd == num ) {
dir = -1;
dir_start = bwd;
break;
}
}

if ( dir != 0) {
for (int i = pos; i < num; i++) {
sqrs[i] = arr[dir_start] * arr[dir_start];
dir_start = dir_start + dir;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't you binary search to find the first positive number. Store this as stopping point, stp.

Create two pointers, one starting off at the 0th index(neg_idx), and the other starting at stp(pos_idx).

Then implement a merge like routine where you selct the minimum of the elements corresponding values. Insert the square of that in a new list, and increment the corresponding pointer.

Do this while the neg_idx < stp and pos_idx<arr.length;

This would run in O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

this is very simple.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In-place O(n) solution-

``````public static void sortedSq(){
int[] a = {-7,-6,-2,0,3,4,6,8};
int r = a.length-1;
while(r>=0){
if(r == 0) {
a[r] = a[r]*a[r];
}
else if(a[0]*a[0] < a[r]*a[r]) {
a[r] = a[r]*a[r];
}else if(a[0]*a[0] >= a[r]*a[r]) {
int t = a[r];
a[r] = a[0]*a[0];
a[0] = t;
if(r>1 && Math.abs(a[1]) > a[0]) {
int tmp = a[0];
a[0] = a[1];
a[1] = tmp;
}
}
r--;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void sortedSq(){
int[] a = {-7,-6,-2,0,3,4,5,8};
int r = a.length-1;
while(r>=0){
if(r == 0) {
a[r] = a[r]*a[r];
}
else if(a[0]*a[0] < a[r]*a[r]) {
a[r] = a[r]*a[r];
}else if(a[0]*a[0] >= a[r]*a[r]) {
int t = a[r];
a[r] = a[0]*a[0];
a[0] = t;
if(r>1 && Math.abs(a[1]) > a[0]) {
int tmp = a[0];
a[0] = a[1];
a[1] = tmp;
}
}
r--;

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Complexity:

O(n) time
O(1) space

``````class SquareOfSortedArray {

public static void main(String args[]) {

int []num = {-5,-4,-3,0,1,6,7,8};
//int []num = {-5,-3,-3,3};
//int []num = {1,2,3,4,5};
//int []num = {-5,-4,-3,-2, -1, 1,6,7,8};
//int []num = {-5};

squareSortedArrayConstantSpace(num);
for(int i: num) {
System.out.println(i);
}
}

static void squareSortedArrayConstantSpace(int []n) {
int len = n.length;
if(len <= 0)
return;

int i = 0;
int j = 0;
while(i < len) { //square all negative numbers, if any
n[i] = n[i] * n[i];
i++;
if(j == 0 && n[i] >= 0)
j = i; // Get the mid point from negative to positive

} // O(n)
i = j - 1; // Two pointer starting from mid (negative to positive)
int index = 0;

while(i >= 0  && i > index && j < len) {
if(n[j] > n[i]) {
swap(n, index, i);
i--;
} else {
swap(n, index, j);
j++;
}
index ++;

}

if(index < n.length && j < n.length) { // At this point all items till index are sorted, just compare n swap the remaining items starting from index

while(index < j) {
if(n[index] > n[j]) {
swap(n, index, j);
}
index++;
j--;
}
} // O(n) including the above while loop

}

static void swap(int []num, int i, int j) {
num[i] ^= num[j];
num[j] ^= num[i];
num[i] ^= num[j];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
O(n) time. What I do is iterate to the left and the right of the first positive number, taking the minimum absolute number of the positive and negative numbers: {{{ public int[] sortedSquares(int[] array){ int size = array.length; int positive = 0; while(positive < size && array[positive] < 0){ positive++; } int negative = positive - 1; //No positive numbers in the array if(array[positive] < 0){ negative = positive; positive++; } int[] result = int[size]; for(int i = 0; i < size; i++){ if(negative < 0){ result[i] = Math.sqrt(array[positive++]); }else{ if(positive >= size){ result[i] = Math.sqrt(array[negative--]); }else{ if(array[positive] < Math.abs(array[negative])) result[i] = Math.sqrt(array[positive++]); else result[i] = Math.sqrt(array[negative--]); } } } } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

Very simplistic O (n log n) in Kotlin

``````fun toOrderedListOfSquares( originalArray: List<Int> ) {

val returnArray = originalArray.map { it * it  }.toMutableList()

return returnArray.sort()
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Exersises {

companion object {

@JvmStatic fun main(args: Array<String> ){

val input = listOf(-4,-2,-1,2,4,10)
print ( toOrderedListOfSquares( input ))

}

fun toOrderedListOfSquares( originalArray: List<Int> ) : List<Int> {

val returnArray = originalArray.map { it * it  }.toMutableList()
returnArray.sort()
return returnArray
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class SortedSquares {

companion object {

@JvmStatic fun main(args: Array<String>) {

val original = listOf(-10, -6, -2, 1, 5, 12)

println(SortedSquares().sort(original))

}
}

private fun sort(original: List<Int>): List<Int> {

val (positive, negative) = original.partition { it > 0 }

val positiveSq = positive.map { it * it }
val negativeSq = negative.map { it * it }

val final = mutableListOf<Int>()

var positiveIndex = 0
var negativeIndex = negativeSq.size - 1

while (positiveIndex < positiveSq.size || negativeIndex >= 0) {

when {

}

}

return final

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })

val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }

var negInd: Int = 0
var posSqr: Int = 0

while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}

fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })

val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }

var negInd: Int = 0
var posSqr: Int = 0

while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}

fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })

val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }

var negInd: Int = 0
var posSqr: Int = 0

while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}

fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* I guess the idea is to achieve O(n) execution time
* Approach: Split, Map, Merge
*/
fun squareSort(array: Array<Int>): Array<Long> {
val result: Array<Long> = Array(array.size, { i -> 0.toLong() })

val negativeSquared = array.filter { it < 0 }.reversed().map { it.toLong() * it }
val positiveSquared = array.filter { it >= 0 }.map { it.toLong() * it }

var negInd: Int = 0
var posSqr: Int = 0

while (negInd < negativeSquared.size || posSqr < positiveSquared.size) {
if (negInd == negativeSquared.size) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else if (posSqr == positiveSquared.size) {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
} else if (positiveSquared[posSqr] < negativeSquared[negInd]) {
result[negInd + posSqr] = positiveSquared[posSqr]
posSqr++
} else {
result[negInd + posSqr] = negativeSquared[negInd]
negInd++
}
}
return result
}

fun main(arg: Array<String>) {
print(squareSort(arrayOf(-9, -3, -2, 0, 1, 4, 6)).joinToString(", "))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution with 2 pointers in O(N)

``````public int[] getSortedPowers(int[] nums] {
int[] sorted = new int[nums.length];
int i=0, j=nums.length-1, index = nums.length-1;

while (index >= 0) {
int left = Math.abs(nums[i]), right = Math.abs(nums[j]);
if (left > right) {
sorted[index] = left * left;
i++;
} else {
sorted[index] = right * right;
j--;
}
index--;
}

return sorted;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static int[] power(int[] sortedArray) {
int start = -1;
for (int i = 0; i < sortedArray.length; i++) {
if (sortedArray[i] > 0) {
start = i;
break;
}
}
if (start < 0) {
start = sortedArray.length - 1;
}
int result[] = new int[sortedArray.length];
int left = start - 1;
int right = start;
int i = 0;
while (left >= 0 || right < sortedArray.length) {
if (left >= 0) {
int leftValue = -sortedArray[left];
if (right < sortedArray.length) {
int rightValue = sortedArray[right];
if (leftValue < rightValue) {
result[i++] = leftValue * leftValue;
left--;
} else {
result[i++] = rightValue * rightValue;
right++;
}
} else {
result[i++] = leftValue * leftValue;
left--;
}
} else {
if (right >= sortedArray.length) {
break;
} else {
int rightValue = sortedArray[right];
result[i++] = rightValue * rightValue;
right++;
}
}
}
return result;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function getSortedSquares(numbers) {
if (!numbers) {
return []
} else if (numbers[0] >= 0) {
return numbers.map(aNumber => aNumber * aNumber)
}
const squares = []
// find the first positive index, guaranteed to be > 0
let j = 0
while (numbers[j] < 0) {
j++
}
let i = j - 1
while (i >= 0 || j < numbers.length) {
if (i < 0) {
squares.push(numbers[j] * numbers[j])
j++
} else if (j === numbers.length) {
squares.push(numbers[i] * numbers[i])
i--
} else if (Math.abs(numbers[i]) < Math.abs(numbers[j])) {
squares.push(numbers[i] * numbers[i])
i--
} else {
squares.push(numbers[j] * numbers[j])
j++
}
}
return squares
}

console.log(getSortedSquares([-4, -2, 1, 3, 5]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SquareOfSortedArray {

public static void main(String[] arg) {

int[] arr = { -5,-4,-3, -2, 1, 4, 5 ,7,8};
int positivePointer = Integer.MAX_VALUE;
int negativePointer = -1;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] > 0)) {
positivePointer = Math.min(positivePointer, i);
} else {
negativePointer = i;
}

arr[i] = arr[i] * arr[i];

}
int m = 0;
int n = negativePointer;

while (m < n) {
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
m++;
n--;
}
//Arrays.sort(arr);
arr = merge(arr,0,positivePointer);
for (int i = 0; i < arr.length; i++) {

System.out.println(arr[i]);
}
}

public static int[] merge(int[]arr,int l , int h){

int[] temp = new int[arr.length];
int k = l;
int low = l;
int high = h;

while (low<h && high<arr.length){

if(arr[low]<arr[high]){
temp[k] = arr[low];
low++;
k++;
}else{
temp[k] = arr[high];
high++;
k++;
}
}

while(low <h){
temp[k] = arr[low];
low++;
k++;
}
while(high<arr.length){
temp[k] = arr[high];
high++;
k++;
}

return temp;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Beating the horse...

Obvious naive solution is to square and sort, which is O(nlogn) time and O(1) assuming the sorting is performed in place.

Better solution is a play on merge sort to reach O(n) time and O(n) space because of the spare array.

Insane solution performs merge in place (someone posted the reference above) for O(1) space, but you'd be insane to implement the algorithm during an interview (or even outside of an interview).

Straight C version

``````static void merge(int *a, int len, int split, int *b)
{
int j = split;
int k = split+1;

for (int i = 0; i < len; i++)
a[i] = a[i] * a[i];

for (int i = 0; i < len; i++) {
if (j < 0)
b[i] = a[k++];
else if (k >= len)
b[i] = a[j--];
else if (a[k] < a[j])
b[i] = a[k++];
else
b[i] = a[j--];
}
}

static void squaresort(int *a, int len, int *b)
{
if (a[0] >= 0)
return merge(a, len, 0, b);

for (int i = 0; i < len-1; i++) {
if (a[i] < 0 && a[i+1] >= 0)
return merge(a, len, i, b);
}

return merge(a, len, len-1, b);
}

#include <stdio.h>

int main(int argc, char **argv)
{
int len = 8;
int a[8] = { -6, -5, -4, -3, 0, 1, 2, 3, };
int b[8];

squaresort(a, len, b);

for (int i = 0; i < len; i++)
printf("%i    %i\n", i, b[i]);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````from collections import deque
a = [-3, -1, 2, 4]

neg =  deque()
pos =  deque()
for x in a:
if x < 0: neg.append(x**2)
else: pos.appendleft(x**2)

final = []
while neg or pos:
if not pos: final.append(neg.pop())
elif not neg: final.append(pos.pop())
elif neg[-1] > pos[-1]: final.append(pos.pop())
else: final.append(neg.pop())

print final``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int[] squared(int[] arr) {
if (arr == null || arr.length == 0)
return arr;

int[] sq = new int[arr.length];
int i=0, j=arr.length-1;
int k=j;
while( i <= j ) {
if( Math.abs(arr[i] ) <= Math.abs( arr[j] ) ) {
sq[k--]= arr[j]*arr[j];
j--;
}else{
sq[k--]= arr[i]*arr[i];
i++;
}
}
return sq;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach:
1. Initialised an array, append all absolute values in new array
2. Performed a quick sort of array
3. Returned the squares of the sorted array

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just split the array to two half, one half < 0, one half > 0
Then square them, and merge them
Time Complexity: O(n)
Space Complexity: O(1)

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.