## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

Quick algorithm sketch to solve this:
1. Find all prime factors of x (using the Sieve of Eratosthenes, for example) and store each factor's power in an array prime_power[]
3. Initialize product = 1
2. Iterate over each of the prime factors and do for each prime p: product *= ((prime_power[p]%2 == 0) ? 1 : p)
3. return product

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

``````def primes(n):
primfac = []
d = 2
while d * d <= n:
factor = False
pow=0
while (n % d) == 0:
factor = True  # supposing you want multiple factors repeated
n /= d
pow+=1
if factor:
primfac.append((d,pow))
d += 1
if n > 1:
primfac.append(n)
return primfac

def make_perfect_square(n):
prime_factors=primes(n)
smallest=1
for (prime,pow) in prime_factors:
#pow is odd
if pow &1 :
smallest*=prime

return smallest``````

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

In Go. The trial division could be optimized.

``````package main

import (
"fmt"
"math"
"sort"
)

func main() {
fmt.Println(findNumber(1))     //1/1 = 1
fmt.Println(findNumber(2))     //2/2 = 1
fmt.Println(findNumber(3))     //3/3 = 1
fmt.Println(findNumber(288))   //288 / 2 = 144 (12*12)
fmt.Println(findNumber(49392)) //49392 / 7 = 7056 (84*84)
}

func findNumber(x int) int {
divs := []int{1, x}

//find all divisors
d := 2
for d*d < x {
if x%d == 0 {
divs = append(divs, d)
divs = append(divs, x/d)
}
d++
}

sort.Ints(divs) //sort factors

for i := len(divs) - 1; i >= 0; i-- {
sq := math.Sqrt(float64(divs[i]))
if sq == float64(int64(sq)) {
return x / divs[i] //return the other factor
}
}
return -1 //will never happen, x/x is 1, which is a perfect square
}``````

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

The number is 1/x so x/1/x= x^2

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

the number is 1/x so x/1/x = x^2

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

``````public int smallestSquareNumber(int x) {
// y^2 < x < (y+1)^2
// find n and y such that y^2 = (x/n)
for (int i = x; i > 0; i--) {
double newSquare = Math.pow(i, 2);
if (newSquare < x) {
if (x % newSquare == 0) {
return (int) (x / newSquare);
}
} else if (newSquare == x) {
return 1;
}
}
// should never get here.
return -1;
}``````

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

``````public int smallestSquareNumber(int x) {
// y^2 < x < (y+1)^2
// find n and y such that y^2 = (x/n)
for (int i = x; i > 0; i--) {
double newSquare = Math.pow(i, 2);
if (newSquare < x) {
if (x % newSquare == 0) {
return (int) (x / newSquare);
}
} else if (newSquare == x) {
return 1;
}
}
// should never get here.
return -1;
}``````

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

This should do it:

``````// ZoomBA
def find_square_complement(n){
if ( n == 0 || n == 1 ) return n
#(primes,factor) = fold ( [2:n+1] , [set(),1] ) -> {
cur_primes = \$.p.0 ; cur_no = \$.o
continue ( exists ( cur_primes ) :: {  \$.o /? cur_no } )
\$.p.0 += cur_no ; power = 0 ; x = n
while ( cur_no /? x ){ power +=1 ; x /= cur_no }
if ( !(2 /? power ) ){ \$.p.1 *= cur_no }
\$.p
}
return ( ( n @ primes ) ? n : factor )
}``````

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

``````public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}``````

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

``````public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}``````

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

``````public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}``````

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

public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}

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

``````public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}``````

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

``````public static int perfectSquare(int x)
{
int i=1;
while(i<=x)
{

if((x % i==0) && (Math.sqrt(x/i)-(long)(Math.sqrt(x/i))==0))
{
return i;

}
else
{

i++;
}

}

return x;
}``````

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

``````int find(int n) {
int rt = (int)sqrt(n);
if (rt*rt == n) return 1;
// You can start from bigger to smaller number so that number of iterations become less. For example, 16*16 would have covered 2*2,4*4 and 8*8 when loop reaches 8,4 or 2.. so it will be fast.
for (int i=rt;i>=2;i--) {
if (n%(i*i) == 0)
n  /= (i*i);
}
return n;
}``````

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

``````int find(int n) {
int rt = (int)sqrt(n);
if (rt*rt == n) return 1;
for (int i=rt;i>=2;<blank>) {
if (n%(i*i) == 0)
{ n  /= (i*i); i = (int)sqrt(n);} // If n is divided by i, directly reduce i to current num's sqrt and start downwards from there.
else
{ i--;}
}
return n;
}``````

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.