## Booking.com Interview Question for Software Engineer / Developers

• 2

Country: Netherlands
Interview Type: Phone Interview

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

Similar to DP problem , Minimum number of coins needed to make a given some.
Here instead of coin you have to take perfect square.

It will be like -
if n = 20
coins = {1,4,9,16}

By using minimum number of above coins you have to make a sum = 20

I will post code in other comment.

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

The solution code in java is here -

``````public class MinimumCoin {

public static int findMin(int[] prfct, int k) {

int[] arr = new int[k + 1];
arr[0] = 0;

for (int i = 1; i < arr.length; i++) {
arr[i] = Integer.MAX_VALUE;
for (int j = 0; j < prfct.length; j++) {

if (prfct[j] <= i) {
int temp = arr[i - prfct[j]] + 1;
arr[i] = arr[i] > temp ? temp : arr[i] ;

}
}
}

return arr[k];

}

public static int[] buildArray(int N) {
int l = (int) Math.sqrt(N);
int[] prfct = new int[l];

//System.out.println(prfct.length);
for(int i=1;i<=l;i++) {
prfct[i-1] = i*i;
}

return prfct;
}

public static void main(String[] args) {
int N = 20;
int[] prfct = buildArray(N); // Build the perfect square array

int output = findMin(prfct, N); // find  the minimum using Dynamic programming approach

System.out.println(output);
}

}``````

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

Dynamic programming question.
Let P(i, j) be the min number of sum of sq root numbers, where i ∈ [0, round(sqrt(N))], j ∈ [0, N]. P(i,j) = min(P[i-1, j], P[i, j-1] + 1)

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

Using Dynamic Programming

``````public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
scan.close();

if (n <= 3) {
System.out.println(n);
return;
}

int sqrt = (int)Math.sqrt(n);
if (sqrt*sqrt == n) {
// Number itself is perfect sqr
System.out.println(1);
return;
}

int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;

for (int i = 4; i <= n; i++) {
dp[i] = i;

for (int j = 1; j <= (int)Math.sqrt(i); j++) {
int temp = j*j;
if (temp > n) {
break;
}
dp[i] = Math.min(dp[i], 1+dp[i-temp]);
}
}

System.out.println(dp[n]);``````

}}

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

``````public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
scan.close();

if (n <= 3) {
System.out.println(n);
return;
}

int sqrt = (int)Math.sqrt(n);
if (sqrt*sqrt == n) {
// Number itself is perfect sqr
System.out.println(1);
return;
}

int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;

for (int i = 4; i <= n; i++) {
dp[i] = i;

for (int j = 1; j <= (int)Math.sqrt(i); j++) {
int temp = j*j;
if (temp > n) {
break;
}
dp[i] = Math.min(dp[i], 1+dp[i-temp]);
}
}

System.err.println(dp[n]);

}``````

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

``````public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
scan.close();

if (n <= 3) {
System.out.println(n);
return;
}

int sqrt = (int)Math.sqrt(n);
if (sqrt*sqrt == n) {
// Number itself is perfect sqr
System.out.println(1);
return;
}

int dp[] = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;

for (int i = 4; i <= n; i++) {
dp[i] = i;

for (int j = 1; j <= (int)Math.sqrt(i); j++) {
int temp = j*j;
if (temp > n) {
break;
}
dp[i] = Math.min(dp[i], 1+dp[i-temp]);
}
}
System.err.println(dp[n]);``````

}

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

``````unsigned minsum(unsigned v) {
if (v <= 1)
return v;
unsigned min = (unsigned)-1;
for (unsigned i = 1; i*i <= v; i++) {
unsigned cur = 1 + minsum(v-i*i);
if (cur < min)
min = cur;
}
return min;
}``````

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

``````public int numberOfMinSquareSum(int n)
{
int num = n;
int sqrt=0, carry=0;

if(num <= 3)
return num;
else
{
sqrt = (int) Math.sqrt(num);
carry = num-(sqrt*sqrt);

if(carry==0)
return 1;
else
return numberOfMinSquareSum(carry)+1;
}
}``````

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

Greedy does not work for sum of square.
Ex. if N = 12 your solution will give 9 + 1 + 1+ 1 (4 numbers) but ans should be 3(4 + 4 + 4). DP is expected solution here and TC would be N * sqrt(N)

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

Greedy does not work for sum of square.
Ex. if N = 12 your solution will give 9 + 1 + 1+ 1 (4 numbers) but ans should be 3(4 + 4 + 4). DP is expected solution here and TC would be N * sqrt(N)

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

Greedy does not work for sum of square.
Ex. if N = 12 your solution will give 9 + 1 + 1+ 1 (4 numbers) but ans should be 3(4 + 4 + 4). DP is expected solution here and TC would be N * sqrt(N)

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

``````int number(int N)
{
if(N<=0)
{
return 0;
}

int numbers=0;
while(N>0)
{
N=N-(int)(Math.Sqrt(N))*(int)(Math.Sqrt(N));
numbers++;
}

return numbers;``````

}

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

-(int)minimumSquareRoot:(int) number {
int count = 0;
int num = number;
while (num > 0) {
int flor = floor(sqrt(num));
num = num - (flor*flor);
count += 1;
}
}

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

-(int)minimumSquareRoot:(int) number {
int count = 0;
int num = number;
while (num > 0) {
int flor = floor(sqrt(num));
num = num - (flor*flor);
count += 1;
}
}

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

``````def check(N):
import math
lk = []
count = 0
for i in range(N, 0, -1):
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
lk.append(i)
count += 1
N = N - 1
print lk
print count``````

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

def check(N) {
import math
lk = []
count = 0
for i in range(N, 0, -1):
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
lk.append(i)
count += 1
N = N - 1
print lk
print count
}

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

``````def check(N):
import math
lk = []
count = 0
for i in range(N, 0, -1):
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N:
lk.append(i)
count += 1
N = N - 1
print lk
print count``````

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

import math
lk =[]
count = 0
for i in range(N, 0, -1){
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
lk.append(i)
count += 1
N = N - 1
}
}

print lk
print count

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

``````import math
lk =[]
count = 0
for i in range(N, 0, -1){
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
lk.append(i)
count += 1
N = N - 1
}
}

print lk
print count``````

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

{{
import math
lk =[]
count = 0
for i in range(N, 0, -1){
if int(math.sqrt(i) + 0.5) ** 2 == i and sum(lk) + i <= N {
lk.append(i)
count += 1
N = N - 1
}
}

print lk
print count}}}

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

int newPerfect( int n)
{
vector<int> arr(n+1);
if(n <= 3)
return n;
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
for(int i=4; i<= n; i++ )
{
int min = INT_MAX;
int max = floor(sqrt(i));
for (int j =1; j <= max; j++ )
{
int val = arr[i - (j * j)] + 1;
if ( val < min)
min = val;
}

arr[i] = min;
}

return arr[n];
}

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

``````int newPerfect( int n)
{
vector<int> arr(n+1);
if(n <= 3)
return n;
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
for(int i=4; i<= n; i++ )
{
int min = 9999;
int max = floor(sqrt(i));
for (int j =1; j <= max; j++ )
{
int val = arr[i - (j * j)] + 1;
if ( val < min)
min = val;
}

arr[i] = min;
}

return arr[n];
}``````

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

``````def numSquares(n):
if n < 2:
return n
lst = []
i = 1
while i * i <= n:
lst.append( i * i )
i += 1
print(lst)
cnt = 0
toCheck = {n}
while toCheck:
cnt += 1
temp = set()
for x in toCheck:
for y in lst:
if x == y:
return cnt
if x < y:
break
toCheck = temp
print(toCheck)
return cnt

numSquares(12)``````

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

I solve this problem by recursive function.
f(n) = min(1+f(n-root^2), n//(root-1)^2+f(n%(root-1)^2)
f(0...4) = 0...4

``````import math
import sys

def find_no_of_perfect_square(n):
if n<0:
return sys.maxsize
if n<4:
return n
elif n==4:
return 1

root = int(math.sqrt(n))
if root>=2:
return min(
1+find_no_of_perfect_square(n-pow(root, 2)),
n//pow(root-1,2) + find_no_of_perfect_square(n%pow(root-1,2))
)
else:
return n

if __name__=='__main__':
data = [
[5, 2],
[7, 4],
[12, 3],
[20, 2],
]
for d in data:
print('the least no of perfect square for', d[0], 'is', find_no_of_perfect_square(d[0]), 'expected', d[1])``````

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

static int getMinSquares(int n)
{
// base cases
if (n <= 3)
return n;

// getMinSquares rest of the table using recursive
// formula
int res = n; // Maximum squares required is
// n (1*1 + 1*1 + ..)

// Go through all smaller numbers
// to recursively find minimum
for (int x = 1; x <= n; x++) {
int temp = x * x;
if (temp > n)
break;
else
res = Math.min(res, 1 + getMinSquares(n - temp));
}
return res;
}

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

``````fun sumOfPerfectSquares(target: Int) : Int {
var targetCache = target-1
var sum = target
var count = 0
while(targetCache > 0){
if(isPerfectSquare(targetCache)){
if(sum-targetCache == 0){
// zero
count++
break
} else if(sum-targetCache < 0) {
// negative
targetCache--
} else {
// positive
count++
sum -= targetCache
}
} else {
targetCache--
}
}
return count
}

fun isPerfectSquare(num : Int) : Boolean {
val lastDigit = num%10
val sumOfDigits = sumOfDigits(num)
return true
}
return false
}

fun endsWithPerfectSum(num: Int) =
num == 0 || num == 1 || num == 4 || num == 5 || num == 6|| num == 9

num == 1 || num == 4 || num == 7 || num == 9

fun sumOfDigits(num: Int) : Int {
var sum = 0
var numCache = num
while(numCache != 0){
sum += numCache%10
numCache = numCache/10
}
return sum
}``````

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

// k√k 0-1 knapsack
int solve(int k) {
int dp[k + 1];
dp[0] = 0;

for (int i = 1; i <= k; ++i) {
dp[i] = i;
for (int j = 1; j <= sqrt(i); ++j) {
dp[i] = min(dp[i], 1 + dp[i - j * j]);
}
}

return dp[k];
}

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

``````// k√k 0-1 knapsack
int solve(int k) {
int dp[k + 1];
dp[0] = 0;

for (int i = 1; i <= k; ++i) {
dp[i] = i;
for (int j = 1; j <= sqrt(i); ++j) {
dp[i] = min(dp[i], 1 + dp[i - j * j]);
}
}

return dp[k];
}``````

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

``````public static void squareSum(int n){
ArrayList<Integer> sqList = new ArrayList<Integer>();
sqrtmeth(n);
}
public static void sqrtmeth(int k){

int fstsq = (int) Math.sqrt(k);
int temp = k - (fstsq * fstsq);
if(temp==0){

//System.out.println(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
}
else {
sqrtmeth(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

}

}``````

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

public static void squareSum(int n){
ArrayList<Integer> sqList = new ArrayList<Integer>();
sqrtmeth(n);
}
public static void sqrtmeth(int k){

int fstsq = (int) Math.sqrt(k);
int temp = k - (fstsq * fstsq);
if(temp==0){

//System.out.println(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
}
else {
sqrtmeth(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

}

}

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

``````public static void squareSum(int n){
ArrayList<Integer> sqList = new ArrayList<Integer>();
sqrtmeth(n);
}
public static void sqrtmeth(int k){

int fstsq = (int) Math.sqrt(k);
int temp = k - (fstsq * fstsq);
if(temp==0){

//System.out.println(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
}
else {
sqrtmeth(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

}

}``````

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

Used recursion :

``````public static void squareSum(int n){
ArrayList<Integer> sqList = new ArrayList<Integer>();
sqrtmeth(n);
}
public static void sqrtmeth(int k){

int fstsq = (int) Math.sqrt(k);
int temp = k - (fstsq * fstsq);
if(temp==0){

//System.out.println(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);
}
else {
sqrtmeth(temp);
System.out.println("Nums : " + fstsq + " Square is " + fstsq * fstsq);

}

}``````

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

Here is the solution for the problem :
{{
public static void main(String a[]) {
System.out.println(totalNoOfPerfectSquareRequiredToSum(10010000));
}

public static int totalNoOfPerfectSquareRequiredToSum(int k) {

int sqrt = (int) Math.sqrt(k);
int temp = k - (sqrt * sqrt);
if (temp == 0) {
return 1;
} else {
return 1 + totalNoOfPerfectSquareRequiredToSum(temp);
}

}}}

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

``````public static void main(String a[]) {
System.out.println(totalNoOfPerfectSquareRequiredToSum(10010000));
}

public static int totalNoOfPerfectSquareRequiredToSum(int k) {

int sqrt = (int) Math.sqrt(k);
int temp = k - (sqrt * sqrt);
if (temp == 0) {
return 1;
} else {
return 1 + totalNoOfPerfectSquareRequiredToSum(temp);
}

}``````

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

``````public static void main(String args[]) throws Exception {
System.out.println(minSumOfSquares(37));
}

public static int minSumOfSquares(int N) {
int arr[] = new int[N + 1];
Arrays.fill(arr, Integer.MAX_VALUE);
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
for (int i = 3; i <= N; i++) {
double sqrt = Math.sqrt(i);
int x = (int) sqrt;
if (Math.pow(sqrt, 2) == Math.pow(x, 2)) {
arr[i] = 1;
continue;
}
for (int j = 1; j <= Math.sqrt(i); j++) {
arr[i] = Math.min(arr[i], arr[(int) (i - Math.pow(j, 2))] + arr[(int) Math.pow(j, 2)]);
}
}
System.out.println(Arrays.toString(arr));
return arr[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.