Facebook Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 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
  }

- Matviy Ilyashenko November 14, 2017 | Flag Reply
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++)
      squares.add((int)(i*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");
  }
}

- Matviy Ilyashenko November 14, 2017 | Flag Reply
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;
}

- tng November 14, 2017 | Flag Reply
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;

- ChrisK November 14, 2017 | Flag Reply
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);
        }

    }

- incarose November 14, 2017 | Flag Reply
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

- hprem991 November 14, 2017 | Flag Reply
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 ;-)

- ChrisK November 14, 2017 | Flag Reply
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;
  }

- sudip.innovates November 14, 2017 | Flag Reply
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!

- Anonymous November 15, 2017 | Flag Reply
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
        sqs.add( sq )
        val difference = value - sq
        if ( sqs.contains( difference )){
            println("Yes $sq + $difference")
            return true
        }
    }

    return false

}

- Andy C November 15, 2017 | Flag Reply
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)))

- rz November 16, 2017 | Flag Reply
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));
        }
}

- thatfernando@yahoo.com November 20, 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