Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

One may think, that since the input array is sorted, we could return the squared elements in same order, but that's not always going to work.

Consider the list [-3, -1, 0, 2, 4], which contains negative numbers, squaring the values would return [9, 1, 0, 2, 4], that isn't sorted.

It's possible to sort the squared values in O(n log n) time, but we can do better. We are not using the fact that the input array is sorted yet!

Lets split the list in two (maybe empty) halves, say L and R. L contains all the values from input array that are negative, and R contains the ones that are greater or equal than 0. It can be observed, that absolute-wise, values from L grow from right to left, and left to right in R. That's, L.reverse() and R are non-decreasing absolute-wise.

Using that x^2 = |x|^2, we can merge L.reverse() and R in O(n), like MergeSort does, taking the absolute of values from L, and then square the result, which will lead to a O(n) time solution.

- Anonymous October 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

The given input array might contain both negative and positive integers. Therefore, the idea is use two pointers.
1) One pointer at the left end (low =0)and another pointer on the right end(high = arr.length-1) index of array.
2)Resulting array of squares is filled from right to left (arr.length-1 to 0) i.e largest square to smallest square.
3)Compare the absolute value of the element pointed by the two pointers whichever is greater the result array takes the square of that element.
4)Every element in the array is processed at least once
Time Complexity : O(n)

Note : But the key here is that when an large integer is squared it might overflow the integer bounds. So either a custom class to handle that situation or Long or BigInteger class in java should be used to handle that.

The below code is not doing that but is rather a simple method to do the required.

public class GetSortedSquares {

	public static void main(String[] args) {
		int[] arr = {-6,-3,2,3,4};
		int[] arr1= {1,2,3,4};
		
		int[] result = getSortedSquares(arr);
		int[] result1 = getSortedSquares(arr1);
		
		printArr(result);
		printArr(result1);
		
	}
// The function to get the Squares in Sorted order
	private static int[] getSortedSquares(int[] arr) {
		int[] result = new int[arr.length];
		int low =0 , high = arr.length-1, i = arr.length-1;
			while(low <= high && i >= 0){
				if(Math.abs(arr[low]) >= Math.abs(arr[high])){ // absolute value of array element on the left is greater than the array element on right
					result[i]= arr[low]*arr[low];
					i--;
					low++;
				}else if (Math.abs(arr[low]) < Math.abs(arr[high])){
					result[i]= arr[high]*arr[high];
					i--;
					high--;
				}		
			}
		
		return result;
	}

	private static void printArr(int[] result) {
		for(int n : result)
			System.out.println(n);
		
	}

}

- Shilpi_Roy October 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function square(array) {
	return array.map(x=> x*x)
}

square([1,5,8,10]) // => [ 1, 25, 64, 100 ]

- Anonymous October 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can find the index in the array, where positive numbers start, and expand from the index to periphery.

vector<uint64_t> Square(vector<int32_t> const &a)
{
	vector<uint64_t> out;

	size_t i = 0;
	while (i < a.size() &&
			a[i] < 0)
	{
		++i;
	}

	size_t j = (i <= a.size()) ? i - 1 : a.size() - 1;

	while (i < a.size() ||
		j < a.size())
	{
		if (i >= a.size() ||
			(j < a.size() && a[i] > - a[j]))
		{
			out.push_back((int64_t)a[j] * a[j]);
			--j;
		} else {
			out.push_back((int64_t)a[i] * a[i]);
			++i;
		}
	}
	return out;
}

- Alex October 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity - O(logn) + n

public static void main(String[] args){
  
    int[] arr = {-3, -1, 0, 2, 4};
    int p = find(arr, 0, arr.length-1);
    sort(arr, p);
  }
  
  
  public static void sort(int[] arr, int p){
  	int n = arr.length;
    
    int i = p;
    int j = p+1;
    
    while(i >= 0 && j < n){
      int pos = Math.abs(arr[i]);
      if(pos <= arr[j]){
      	System.out.print((int)(Math.pow(pos, 2)) + " ");
        i--;
      }else if(pos > arr[j]){
      	System.out.print((int)(Math.pow(arr[j], 2)) + " ");
        j++;
      }
    }
    while(i >= 0){
    	int pos = Math.abs(arr[i]);
        System.out.print((int)(Math.pow(pos, 2)) + " ");
        i--;
    }
    while(j < n){
     	System.out.print((int)(Math.pow(arr[j], 2)) + " ");
        j++;
    }
  }
  
  public static int find(int[] arr, int l, int h){
  	
    int n = arr.length;
    
    while(l < h){
      int mid = (h-l)/2 + l;
      if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < 0 && arr[mid+1] >= 0)
        return mid;
      else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < 0 && arr[mid+1] < 0)
        l = mid+1;
      else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] > 0 && arr[mid+1] > 0)
        h = mid-1;  
    }
    return -1;
  }

- sudip.innovates October 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have seen a tons of response for this simple question. I dont think this question is intended to provide sorted square of integer inputs. Interviewer wanna check how much candidate knows about Integer implementation.

As we square up high value integer, it wont fit in another integer so unless you come up with a custom class which able to do so, all above responses are wrong. Specially when a candidate is interviewing top companies

- hprem991 October 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@hprem991 - For me to learn -
Can you please explain "As we square up high value integer, it wont fit in another integer", why would we try to fit a higher value in a lower one?
Can you explain your understanding?

- sudip.innovates October 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> d{ -5, -2, -1, 4, 5, 6, };

	vector<int> sqr;
	sqr.reserve(d.size());

	auto ip = lower_bound(d.begin(), d.end(), 0);
	auto in = ip;

	while (ip != d.end() || in != d.begin()) {
		if (in == d.begin() || (ip != d.end() && abs(*prev(in)) > abs(*ip))) {
			int v = *(ip++);
			sqr.emplace_back(v * v);
		}
		else {
			int v = *(--in);
			sqr.emplace_back(v * v);
		}
	}

- john700 October 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"""
Assume array is in ascending order. First we check if the first
int in the list is >=0. If yes, then we square each element and
leave it in the result in the same order (trivial case)
Else we have negative values in the array.
Find position of the abs minimum in the list.
Square this value and move to the result.
Keep two pointers to the left and right of the min value found earlier.
We now compare the abs values of the values pointed to by these pointers
and square the smaller value and move it to the result. Keep doing this
till you exhaust the list
"""
def squareSortedIntArray(list):
    result = []
    if list[0] >= 0:
        result = [i * i for i in list]
    else:
        m = list.index (min(list, key=abs))
        result.append(list[m] * list[m])
        low = m - 1
        high = m + 1
        #print (f"low={low}, high={high}")
        while (low > -1  and  high < len(list)):
            if (abs(list[low]) < abs(list[high])):
                result.append(list[low] * list[low])
                low -=1
            elif (abs(list[low]) == abs(list[high])):
                v = list[low] * list[low]
                result.append(v)
                result.append(v)
                low -=1
                high += 1
            else:
                result.append(list[high] * list[high])
                high += 1
        # append rest of the list squared to the result
        while ( low >-1):
            result.append(list [low]  * list [low])
            low-=1
        while ( high < len  (list)):
            result.append (list [high]  * list [high])
            high+=1
    return result

def main():
    list = [-5, -4, -3, -3, -3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8]
    print(f"squared & sorted array of \n\t{list} \nis \n\t{squareSortedIntArray(list)}")
    """
    Prints
    [0, 1, 4, 4, 9, 9, 9, 9, 16, 16, 25, 25, 36, 49, 64]
    """


if (__name__ == '__main__'):
    main()

- Makarand October 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@hprem991: Well, @Alex's solution will not fail and it got down-voted for no obvious or stated reason.

- Chris October 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class Solution {
	
	public static void Squares(int arr[]){
		int length = arr.length;
		int arr1[] = new int[length];
		int j=0;
		for(int i=0;i<length;i++){
			arr1[j] = arr[i] * arr[i];
			j++;
		}
		Arrays.sort(arr1);
		for(j=0;j<arr1.length;j++){
			System.out.println(arr1[j]);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {-3,-1,0,2,4};
		Squares(arr);
	}

}

- Sameer October 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
public class SquaredSortedList
{
	public static void main(String args[])
	{
		SquaredSortedList s = new SquaredSortedList();
		int[] nums = {-7, -2, -1, 1, 6};
		int[] res = s.getSquaredSortedList(nums);
		System.out.println(Arrays.toString(res));
	}

	public int[] getSquaredSortedList(int[] nums)
	{
		int lo = 0;
		int hi = nums.length-1;

		int[] res = new int[nums.length];
		int k = nums.length-1;
		while(lo <= hi)
		{
			long lo2 = nums[lo] * nums[lo];
			long hi2 = nums[hi] * nums[hi];

			if(lo2>=hi2)
			{
				res[k] = (int)lo2;
				lo++;
				k--;
 			}
 			else if(lo2<hi2)
 			{
 				res[k] = (int)hi2;
 				hi--;
 				k--;
 			}
		}
		return res;
	}

}

- noob October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class MyClass {
public static void main(String args[]) {
int[] a = {-4, -1, 0, 2, 3, 4, 5};
int fp = 0;
for(int i=0; a[i] < 0; i++) fp = i;

for(; fp>=0; fp--){
int temp = Math.abs(a[fp]);
int l = fp+1 ;
while(l < a.length && temp >= a[l]){
a[l-1] = a[l];
a[l] = temp;
l++;
}
}

for(int ta:a) System.out.println(ta*ta);
}
}

- mo November 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
System.out.println(square(Arrays.asList(-2, -1, 0, 1, 2)));
}

static List<Integer> square(List<Integer> input) {
int startIdx = 0;
while (startIdx < input.size()) {
if (input.get(startIdx) >= 0) {
break;
}
startIdx++;
}

List<Integer> rv = new ArrayList<>();
int negIdx = startIdx - 1;
int posIdx = startIdx;
while (negIdx >= 0 && posIdx < input.size()) {
int negSq = input.get(negIdx) * input.get(negIdx);
int posSq = input.get(posIdx) * input.get(posIdx);
if (negSq < posSq) {
rv.add(negSq);
negIdx--;
continue;
}
rv.add(posSq);
posIdx++;
}

while (negIdx >= 0) {
rv.add(input.get(negIdx) * input.get(negIdx));
negIdx--;
}

while (posIdx < input.size()) {
rv.add(input.get(posIdx) * input.get(posIdx));
posIdx++;
}

return rv;
}

- Anonymous January 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        System.out.println(square(Arrays.asList(-2, -1, 0, 1, 2)));
    }

    static List<Integer> square(List<Integer> input) {
        int startIdx = 0;
        while (startIdx < input.size()) {
            if (input.get(startIdx) >= 0) {
                break;
            }
            startIdx++;
        }

        List<Integer> rv = new ArrayList<>();
        int negIdx = startIdx - 1;
        int posIdx = startIdx;
        while (negIdx >= 0 && posIdx < input.size()) {
            int negSq = input.get(negIdx) * input.get(negIdx);
            int posSq = input.get(posIdx) * input.get(posIdx);
            if (negSq < posSq) {
                rv.add(negSq);
                negIdx--;
                continue;
            }
            rv.add(posSq);
            posIdx++;
        }

        while (negIdx >= 0) {
            rv.add(input.get(negIdx) * input.get(negIdx));
            negIdx--;
        }

        while (posIdx < input.size()) {
            rv.add(input.get(posIdx) * input.get(posIdx));
            posIdx++;
        }

        return rv;
    }

- modernphysics January 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

arr.map(val => Math.pow(val,2)).sort((a,b) => a - b);

- marlon October 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

arr.map(val => Math.pow(val,2)).sort((a,b) => a - b);

- marlon October 19, 2017 | Flag Reply


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