www.google.com Mountain View, CA 5000+ Employees
Work in HR? Complete Your Profile

# Interview Question for Software Engineer at Google: Jul 31, 2012

## Write a Square Root function for a computer without floating point calculations

Yes | No
Inappropriate?

2 of 3 people found this helpful

Aug 5, 2012
Perhaps using binary search will work.
Yes | No
Inappropriate?

Aug 8, 2012
By approximation.

Star with a = 1 and check if a*a is > N. If so you return a-1 else a++ and move forward.

The fact that here we cannot use the floating point calculation makes everything trivial and not much accurate.

Anyway convert this strategy into an accurate one using floating point it's easy as well.
Yes | No
Inappropriate?

1 of 1 people found this helpful

Aug 18, 2012
Use fractions (=2 integers) and the Babylonian/Newtonian approach:
X(n+1) = (X(n)^2 + N) / (2 * X(n))
Yes | No
Inappropriate?

3 of 3 people found this helpful

Aug 24, 2012
Use the babylonian method
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method