## Facebook Interview Question for SDE1s

Country: United States

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

@ChrisK, you are completely right, I just missed evidence that I can just calculate second term when I know n and first one. I even know such trick and used it already, but just forget in this case. Updated solution:

``````private static boolean isSumOfSquares(int n) {
for(long i=0;i*i<n;i++) {
double root = Math.sqrt(n-i*i);
if(Math.abs(root-Math.ceil(root))<1e-6)
return true;
}
return false;
}

public static void main(String[] args) {
System.out.println(isSumOfSquares(16)?"YES":"NO");  // YES
System.out.println(isSumOfSquares(17)?"YES":"NO");  // YES
System.out.println(isSumOfSquares(26)?"YES":"NO");  // YES
System.out.println(isSumOfSquares(15)?"YES":"NO");  // NO
System.out.println(isSumOfSquares(7)?"YES":"NO");  // NO
System.out.println(isSumOfSquares(63744256)?"YES":"NO");  // YES
}``````

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

Just precalculate all squares of numbers between 1 and SQRT(n). Space complexity: O(sqrt(n)), time complexity: O(n) (as it is O(sqrt(n)*sqrt(n)) = O(n)):

``````private static boolean isSumOfSquares(int n) {
List<Integer> squares = new ArrayList<Integer>();
for(long i=1;i*i<n;i++)
for(Integer a : squares)
for(Integer b: squares)
if(a+b==n) {
System.out.println(n+" = "+a+" + "+b);
return true;
}
return false;
}

public static void main(String[] args) {
System.out.println(isSumOfSquares(16)?"YES":"NO");
System.out.println(isSumOfSquares(17)?"YES":"NO");
System.out.println(isSumOfSquares(26)?"YES":"NO");
}
}``````

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

Here's my code in C. Time complexity O(sqrt(n)), space complexity O(1). Uses the sqrt() function though.

``````bool
target_is_sum_of_two_squares(int target)
{
long square = 1;
for (int i = 1; square < target; i++, square = i*i) {
double complement_sqrt = sqrt(target - square);
if (complement_sqrt - (long)complement_sqrt == 0) {
printf("Found sum of two squares: %d = %d*%d + %ld*%ld.\n", target, i, i, (long)complement_sqrt, (long)complement_sqrt);
return true;
}
}

return false;
}``````

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

@Matviy Ilyashenko:
I think you can do it in O(sqrt(n)) and avoid many expensive sqrt
note that your list doesn't really help you much (it safes you a n^2 - n multiplications for the cost of memory/cache access), you may as well want 4*4 + 0*0 = 16, so maybe we should start at 0. You could as well just repeat the loop of your sqaure calc:

``````for(long i=0;i*i<=n;i++)
for(long j=i;j*j<=n;i++)
if(i*i+j*j=n) return true;
return false;``````

But if you put i*i into a hash-set - I think you don't need to test all pairs and you can avoid sqrt calcs. Note sqrt calc is faster on modern CPUs than maintaining a hash-set.

``````unordered_set<int> s;
for(int i = 0; i*i <= n; ++i) {
s.insert(i*i);
if(s.count(n-i*i) > 0) return true;
}
return false;``````

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

This will print "all" the pair, without duplicates
O(n^0.5) < O(n)

``````public static void findSumSquares(int num) {

int n = (int)Math.sqrt(num)/2 + (int)Math.sqrt(num)%2;

for(int i = 0; i <= n; i++){
int asqr = num-(int)Math.pow(i,2);
int a = (int)Math.sqrt(asqr);
if((int)Math.pow(a,2) == asqr)
System.out.println("(+/-)"+a+" (+/-)"+i);
}

}``````

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

I think this is pretty easy question, twoSum problem but the follow up could be killer.

Determine if a number is a sum of any number of squares

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

@hprem991: no killer, it is, n-time the sum of 1^2 ;-)

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

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

int n = 17;
boolean ret = isSquareSum(n);
System.out.println(ret);
}

public static boolean isSquareSum(int n){
int m = (int)Math.sqrt(n);
int[] arr = new int[n+1];
for(int i = 0; i <= m; i++){
arr[(int)Math.pow(i, 2)] = 1;
}
for(int i = 0; i <= m; i++){
if(arr[i] > 0 && n-arr[i] >= 0 && arr[n-arr[i]] == 1)
return true;
}
return false;
}``````

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

As someone said, "Determine if a number is a sum of any number of squares" is not a real killer follow up since you can do 1^2 n times. One may think that "Determine the minimum amount of square numbers that sum up to n" gets worse, but that just transform the problem into a Dynamic Programming classic Coin Change problem where the values of the coins are all square numbers less or equal than n! That's amazing!

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

In Kotlin

Complexity of O(sqrt(n)) and space O(sqrt(n))

``````fun isSumOfSquares( value: Int ): Boolean{

if ( value < 2 ) return false

val maxSq = Math.ceil(Math.sqrt( value.toDouble() )).toInt()
val sqs = mutableSetOf<Int>()

(1 .. maxSq ).forEach {
val sq = it * it
val difference = value - sq
if ( sqs.contains( difference )){
println("Yes \$sq + \$difference")
return true
}
}

return false

}``````

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

``````import math

# determine whether a number is the sum of two squares, such as 17 = 16 +1

def is_square_root(n):
return math.pow(int(math.sqrt(n)), 2) == n

def is_two_square(n):
for i in range(0, int(n/2)):
if is_square_root(i) and is_square_root(n-i):
return i, n-i
return False

for i in range(100):
if (is_two_square(i)):
print("{} = {} + {}".format(i, *is_two_square(i)))``````

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

``````public class CheckSquare {

public static void main(String[] args) {

int in =17;

for(int n=0;n*n<=in;n++)
if(n*n <= in && (n+1)*(n+1)>in) System.out.println(in + " = " + n + "^2 + " + (in - n*n));
}
}``````

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

``````private static boolean isSumOfSquares2(int n) {
List<Integer> squares = new ArrayList<Integer>();
for(long i=0;i*i<=n;i++)
int low = 0;
int high = squares.size()-1;
while(low<high) {
if(squares.get(low)+squares.get(high) == n) {
// System.out.println(n+" = "+a+" + "+b);
return true;
} else if(squares.get(low)+squares.get(high)<n) {
low++;
} else {
high--;
}
}
return false;
}``````

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

``````def sum_of_squares(number):
SQUARES = set()

i = 1
while i * i < number:
square = i * i
if (number - square) in SQUARES:
return square, number - square
i += 1
return None, None``````

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.