## Facebook Interview Question for Software Engineer / Developers

Team: Emerging Markets
Country: United States
Interview Type: Phone Interview

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

This solution is similar to the 2-sum algorithm, used to see whether any two values of a sorted array sum to a specific number.

In this case, however, the lower bound is zero, while the upper bound is the square root of N. We set a cursor on the lower bound, and it only moves in +1 steps. Also, we set another cursor on the upper bound, and it only moves in -1 steps.

Whenever the sum of squares is greater than N, we need to decrease the sum. In order to do so, we move the upper cursor down (j = j-1). Whenever the sum is lower than N, we move the lower cursor up (i = i+1). Else, when we find a match, we move both.

``````import sys
import math

n = int(sys.argv)

root = math.sqrt(n)
floor = int(root)

i = 0
j = floor

while i <= j:
sqsum = i**2 + j**2
if sqsum == n:
print i, j
i = i + 1
j = j - 1
elif sqsum > n:
j = j - 1
else:
i = i + 1``````

This algorithm is O(n) loose, which is way better than the naive approach of two nested fors.

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

+1
In fact, this is O(sqrt(n))-time algorithm.

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

Excellent solution. It is also important to clarify whether we deal with primitive integer types or the input can be unbound integer. Because if unbound, it will not fit into one CPU operation and squaring itself will not be constant, possible O(i) where i is number to square. Why is this important. Let's say when we talk about complexity of prime factorization problem, we assume unbound numbers that cannot be divided or multiplied in one CPU operation.

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

``````public static int doublequare(int num)
{
int temp = (int)Math.ceil(Math.sqrt(num/2));
int count= 0;
for(int i = 0; i<= temp; i++)
{
int x = num- i*i;
if( perfectsquare(x))
count++;
}
return count;
}

public static boolean perfectsquare(int num)
{
double x = Math.sqrt(num);
int y = (int) Math.sqrt(num);
if(x == (double)y)
return true;
return false;
}``````

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

Here is another solution. Using the input 1215306625 you should get 64.

The algorithm is O(n/2).

``````public static int countPerfctSquare(int n) {
int count = 0;
for(int y=0; y*y <= n/2; y++) {
double x = Math.sqrt(n - y*y);
if (x % 1 == 0) {
count++;
}
}
return count;
}``````

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

Isn't this O(sqrt(n))? If n= 16 then this algo would only run 4 times because y = 3 on the 4th iteration so 9 <= 8 is false.

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

1. When talking about complexity, it makes no sense to say O(n/2), because 1/2 is a constant.
2. `x % 1` tells you if an integer's last bit is 1 (aka even or odd): `14 % 1 is 0`
3 `sqrt` is not O(1), so your code runs in ~ O(n * o_sqrt), where o_sqrt is the complexity run time of sqrt implementation
4. Your code gives 4 solution for n = 25

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

Try inserting this line of code before `count++`:

``System.out.println(String.format("%d = %d ^2 + %d ^2", n, (int) x, y));``

Then, using 25 as input, you should get this:

25 = 5 ^2 + 0 ^2
25 = 4 ^2 + 3 ^2
The number of combinations for 25 is: 2

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

if a number is double square, the function below will return list of tuples.

``````def dSq(n):
lst = []
for i in range(n+1):
for j in range(n+1):
if (i**2 + j**2) == n:
lst.append((i, j))

return lst``````

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

void fun(int num)
{
int sum,sqr,i,j,c=0;
sqr=sqrt(num);
for(i=1;i<=sqr-2;i++)
{
for(j=i+1;j<=sqr;j++)
{
sum=i*i+j*j;
if(sum>num)
break;
if(sum==num)
{
c++;
printf("%d %d",i,j);
}
}
}
if(c==0)
printf("NO ANY NUMBer are found");

}

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

``````Objective c solution,
int x = 100;
__block int doublesCount = 0;
NSMutableArray *squaresArray = [NSMutableArray new];
for (int j = 1; j<sqrt(x); j++) {
}
[squaresArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
for (NSUInteger j = idx; j<squaresArray.count; j++) {
if (([obj integerValue] + [squaresArray[j] integerValue]) == x) {
doublesCount++;
}
}
}];``````

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

``````public static int doubleSquare(int num)
{
int temp = (int)Math.ceil(Math.sqrt(num));
int count= 0;
for(int i = 1; i< temp; i++)
{
int x = num- i*i;
if( isPerfectSquare(x))
count++;
}
return count;
}

public static boolean isPerfectSquare(int num){
double x = Math.sqrt(num);
int y = (int)Math.sqrt(num);
if(x == y){
return true;
}
return false;
}``````

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

``````package codepunt;

import java.util.Scanner;

public class CodePunt {
public static void main(String[] args) {

System.out.println("Enter a number");
Scanner sc = new Scanner(System.in);
int ans = sc.nextInt();
int result = 0;

for(int i = 1; i < ans; i++)
{
int count = i * i;

for(int j = 2; j < ans; j++)
{
int count1 = j*j;
if((count + count1) == ans )
{
result++;
}
}
}
System.out.println("Result is : "+result);
}

}``````

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

``````public int findNumberOfWays (int n, double m){
int ways = 0 ;
int k = (int)Math.sqrt(n) ;
for (double i = 1 , j = k ; i < j ;) {
if (Math.pow(i, 2) + Math.pow(j, 2) == n) {
ways++;
i++;
j--;
} else if (Math.pow(i, 2) + Math.pow(j, 2) > n) {
j-- ;
} else {
i++ ;
}
}

return ways ;``````

}

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

``````#include <stdio.h>
/// return the number of pairs (a,b) of which a^2+b^2==sum
///
/// Time Complexity O(n)
/// Space Complexity O(n^0.5)
///
int double_sqrt_count(int sum) {
int l=0, h=0;
int elements[sum];

/// these are the numbers whose sqrt is smaller or equal to sum.
for (int i=0;i<sum;++i) {
if (i*i >sum)
break;
elements[h++] = i;
}

/// h points to the last valid element.
h = h-1;

int count=0;
while (l<h) {
int curr = elements[l]*elements[l] + elements[h]*elements[h];
if (curr == sum) {
/// found a solution. need to increase a and decrease
/// b at the same time. as only increasing a or decreasing
/// b is going to find a bigger or smaller sum respectively.
++count;
++l;
--h;
continue;
}
else if (curr > sum) {
/// need to have a smaller b.
--h;
continue;
} else {
/// need to have a bigger a.
++l;
continue;
}
}
return count;
}

int main() {
printf("%d\n", double_sqrt_count(1393940););
return 0;
}``````

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

khbkj

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

Here is the C++ solution.
Running time is O( N ) or O (N/2).

``````#include <iostream>
#include<math.h>

using namespace std;

bool is_double_square(int x)
{
for (int i = 1; i < x/2; i++)
{
double squared = sqrt(i);
int whole = (int)squared;
if ( squared == whole)
{
int left = x - i;
squared = sqrt(left);
whole = (int)squared;
if (squared == whole)
{
cout << "found = " << i << ", " << left<< endl;
return true;
}
}
}
return false;
}``````

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.