Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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);
}
}
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;
}
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;
}
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
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);
}
}
"""
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()
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);
}
}
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;
}
}
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);
}
}
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;
}
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;
}
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.
- Anonymous October 19, 2017Consider 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.