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
O(1) additional space

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

- Sergey September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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){
				arr_negetive.add(arr[i] * arr[i]);
			}
			else{
				arr_positive.add(arr[i] * arr[i]);
			}
		}
		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)

- Sahib December 09, 2016 | Flag
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;
}

- Bobosas September 26, 2016 | Flag Reply
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))

- Anonymous dude September 22, 2016 | Flag Reply
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()

- tomkowz October 05, 2016 | Flag Reply
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;
    }

- Scavi September 21, 2016 | Flag Reply
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.Add((int) squaredValue);
	squareListOfInt.Sort();

}

- Gunjan Parmar September 21, 2016 | Flag Reply
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.Add((int) squaredValue);
squareListOfInt.Sort();
}

- Anonymous September 21, 2016 | Flag Reply
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.Add((int) squaredValue);
	squareListOfInt.Sort();
}

- Gunjan Parmar September 21, 2016 | Flag Reply
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);
}}}

- super September 21, 2016 | Flag Reply
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);
    }

- super September 21, 2016 | Flag Reply
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

- super September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- super September 21, 2016 | Flag Reply
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);
    }

- Anonymous September 21, 2016 | Flag Reply
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)
                {
                    negatives.Add(inp[i] * inp[i]);
                }
                else
                {
                    positives.Add(inp[i] * inp[i]);
                }
            }

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

- Andrea September 21, 2016 | Flag Reply
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])

- Anonymous September 22, 2016 | Flag Reply
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])

- AT September 22, 2016 | Flag Reply
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;
	}

- Hangman September 22, 2016 | Flag Reply
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;
	}

- Hangman September 22, 2016 | Flag Reply
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;
	}

- Hangman September 23, 2016 | Flag Reply
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;
	}

- Hangman September 23, 2016 | Flag Reply
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;
	}

- Hangman September 23, 2016 | Flag Reply
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;
	}

- Hangman September 23, 2016 | Flag Reply
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) {
            pq.add(BigInteger.valueOf(data[i]).pow(2).intValue());
        }
        return pq;
    }

- cheeyim September 25, 2016 | Flag Reply
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

- fdevillamil September 25, 2016 | Flag Reply
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;
}

- Bobosa September 26, 2016 | Flag Reply
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;
}

- hnatsu September 26, 2016 | Flag Reply
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;
}
}
}

- Roc September 29, 2016 | Flag Reply
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)

- TEst September 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is very simple.

- Anonymous October 09, 2016 | Flag Reply
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--;

		}
	}

- Anonymous October 20, 2016 | Flag Reply
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--;

		}
	}

- Anonymous October 20, 2016 | Flag Reply
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];
	}
}

- Killbill October 20, 2016 | Flag Reply
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--]); } } } } }} - libertythecoder October 21, 2016 | Flag Reply
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()
        }

- Andy Clark October 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Trivial Answer in Kotlin

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
        }

    }
}

- Andy Clark October 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(n) answer in Kotlin

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 {

                positiveIndex >= positiveSq.size -> final.add(negativeSq[negativeIndex--])

                negativeIndex < 0 -> final.add(positiveSq[positiveIndex++])

                positiveSq[positiveIndex] > negativeSq[negativeIndex] -> final.add(negativeSq[negativeIndex--])

                else -> final.add(positiveSq[positiveIndex++])

            }


        }

        return final

    }

}

- Andy C October 26, 2016 | Flag Reply
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(", "))
}

- otherman October 28, 2016 | Flag Reply
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(", "))
}

- otherman October 28, 2016 | Flag Reply
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(", "))

}

- otherman October 28, 2016 | Flag Reply
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(", "))
}

- otherman October 28, 2016 | Flag Reply
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;
}

- Ignacio November 05, 2016 | Flag Reply
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;

}

- Long November 06, 2016 | Flag Reply
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]))

- yangmillstheory November 12, 2016 | Flag Reply
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;
	}

}

- Anonymous November 13, 2016 | Flag Reply
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;
}

- ttsou December 06, 2016 | Flag Reply
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

- Nitish Garg January 02, 2017 | Flag Reply
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;
    }

- Anonymous February 20, 2017 | Flag Reply
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

- Zahid March 31, 2017 | Flag Reply
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)

- Jay November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More