Microsoft Interview Question SDE1s
Country: United States
Interview Type: In-Person
t=raw_input()
t=int(t)
d={}
for i in range(2,t):
while t%i == 0:
d[i]=d.get(i,0)+1
t=t/i
if t>1:
d[t]=d.get(t,0)+1
print d
f=1
ans=1
for k in d:
if d[k]%2 !=0:
print 'not a square of any number'
f=0
break
else:
ans=ans*(k**(d[k]/2))
if f==1:
print 'square of some number'
print 'that number is',ans
#include<stdio.h>
int main(){
int n,sqroot,i,j;
printf("Enter the number: \n");
scanf("%d", &n);
if(n>10000){
printf("Invalid Entry number should be less than 10000\n");
//return ;
}
else{
for(i=1;i<=100;i++){
if(i *i == n){
sqroot = i;
break;
}
}
if(sqroot == i){
printf("Number is perfect square and square root is %d :", sqroot);
}else{
printf("Not perfect square");
}
}
return 0;
}
A number can be square only if its last digit is from set: {1,4,9,6,5}
Lets take example of 1024.
So, if num%10 is not part of this set, num cannot be perfect square.
num<10000 indicates that square root will be 2-digit number.
Now, lets check for unit place digit. If it is 4 then there only 2 possibilities for unit place of its its square-root can have only 2 or 8 (becoz (2^2)%10 =4 and (8^2)%10 = 4)
Now we need to check remaining 2 right-most digits of number: (i.e. 10 in 1024) Check where you can insert this number in squares-set : a[] = {1,4,9,16,25,36,49,64,81,100}
we get 3 so right-digit in square-root = 3
So, only 2 possibilities for number either 32 or 38.
Now, calculate both numbers' square and check which one matches with 1024.
A number can be square only if its last digit is from set: {1,4,9,6,5,0}
(remember last digits in squares of 1 to 10?).
Lets take example of 1024.
So, if num%10 is not part of this set, num cannot be perfect square.
num<10000 indicates that square root will be 2-digit number.
Now, lets check for unit place digit. If it is 4 then there only 2 possibilities for unit place of its its square-root can have only 2 or 8 (becoz (2^2)%10 =4 and (8^2)%10 = 4)
Now we need to check remaining 2 right-most digits of number: (i.e. 10 in 1024) Check where you can insert this number in squares-set : a[] = (1,4,9,16,25,36,49,64,81,100)
we get 3 so right-digit in square-root = 3
So, only 2 possibilities for number either 32 or 38.
Now, calculate both numbers' square and check which one matches with 1024.
Well, you gave a fixed upper limit, which means this can be done rather simply in O(1) because we have a O(1) preprocessing step (with no chance to go beyond a set limit, its considered constant)
To preprocess, take each value x from 0...n and add it to a lookup table in the format <x^2, x> unless x^2 is greater than 10000
in python:
def pre_process(upper_limit):
sqr_table = {}
for i in range(0, upper_limit):
if i**2 <= upper_limit:
sqr_table[i**2] = i
else:
break
return sqr_table
def lookup_sqr_root(val, sqr_table):
if sqr_table.get(val, None):
return sqr_table.get(val, None)
else:
return False
import java.util.ArrayList;
class SolutionFindGivenNumberIsPerfectSquareOrNot {
public boolean findWhetherPerfectSquareOrNotMethod1(int num) {
if (num == 1 || num == 0) {
System.out.println("Perfect Square: " + num);
return true;
} else if (num < 0) {
System.out.println("Not Perfect Square");
return false;
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
list.add(1);
int m = 1;
while (m * m <= num) {
m = m * 10;
}
for (int i = 2; i <= m; i++) {
list.add(i * i);
if (i * i >= num) {
break;
}
}
if (list.indexOf(num) == -1) {
System.out.println("Not Perfect Square");
return false;
}
System.out.println("Perfect Square: " + list.indexOf(num));
return true;
}
public boolean findWhetherPerfectSquareOrNotMethod2(int num) {
if (num == 1 || num == 0) {
System.out.println("Perfect Square: " + num);
return true;
} else if (num < 0) {
System.out.println("Not Perfect Square");
return false;
}
int m = 1;
int out = 0;
while (m * m <= num) {
m = m * 10;
}
for (int i = 2; i <= m; i++) {
if (i * i >= num) {
out = i;
break;
}
}
if (out == 0 || (out * out) != num) {
System.out.println("Not Perfect Square");
return false;
}
System.out.println("Perfect Square: " + out);
return true;
}
}
public class FindGivenNumberIsPerfectSquareOrNot {
public static void main(String[] args) {
SolutionFindGivenNumberIsPerfectSquareOrNot mSol = new SolutionFindGivenNumberIsPerfectSquareOrNot();
mSol.findWhetherPerfectSquareOrNotMethod1(1024);
mSol.findWhetherPerfectSquareOrNotMethod1(1025);
mSol.findWhetherPerfectSquareOrNotMethod2(1024);
mSol.findWhetherPerfectSquareOrNotMethod2(1025);
}
}
Factorize the number. Check if any factor has odd number of appearances. If so, return false. Also, keep a helper variable which would contain the root.
int root(int n) {
int current_root = 1;
int current_factor = 2;
while (current_factor < n/2) {
if (n %% current_factor == 0) {
n /= current_factor;
current_root *= current_factor;
if (n %% current_factor == 0) {
n /= current_factor;
} else {
// the number is not a perfect square
return -1;
}
} else {
current_factor++;
}
}
return current_root;
}
O(log n) solution.
function sqrt(num) { // will return 0 if not perfect square
// binary search for the number for which n^2 = num
var low = 0;
var high = num;
while(low+1<high) {
var mid = Math.floor((low+high)/2);
var sq = mid*mid;
if(num<sq) {
high = mid;
}
else {
low = mid;
}
}
// if low^2 = num, we found the number. Otherwise it's not a perfect square
return low*low==num?low:0;
}
Idea is to use bitwise operations. Number n is a perfect square if and only if n & (n-1) == 0. For example, 8 & 7 == 0, but 9 & 8 != 0. Code in C:
#include<stdio.h>
int main() {
unsigned n;
scanf("%u", &n);
if((n & (n-1)) == 0)
printf("Yes\n");
else
printf("No\n");
return 0;
}
This logic is used to find if n is a power of 2. Perfect square does not mean n has to be a power of 2.
Preprocessing step:
- oOZz April 19, 2015Calculate squares of numbers from 1 to 100 (Note that we'll query the numbers that are less than 10000) and put the number and the square to a hashmap/hashtable value = the numbers from 1 to 100 and the keys are the corresponding square of that number, e.g.,
<1, 1>
<4, 2>
<9, 3>
...
<10000, 100>
Time complexity of the preprocess = TO(N), but since N is constant which is equal to 100, then time complexity is constant time - O(1)
Query Step:
Once the hashtable is created in the preprocessing step, all the queries can be done in in O(1) time. Of course, assuming that the hashmap/hashtable used has O(1) for get, put, containsKey operations.
Time complexity of the queries: O(1)