Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
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
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
//start with the largest, look for perfect squares
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
}
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;
}
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;
}
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 )
}
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;
}
Quick algorithm sketch to solve this:
- Killedsteel January 08, 20171. 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