Booking.com Interview Question for Software Engineer / Developers


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.

- azambhrgn February 01, 2017 | Flag Reply
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);
	}

}

- azambhrgn February 02, 2017 | Flag Reply
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)

- Marcello Ghali February 02, 2017 | Flag Reply
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]);

}}

- Tasneem March 14, 2017 | Flag Reply
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]);
		
	}

- Tasneem March 14, 2017 | Flag Reply
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]);

}

- Tasneem March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the answer is only about the length of sum:

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;
}

- harvos.arsen July 25, 2017 | Flag Reply
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;
		}
	}

- Nitesh August 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Brajesh February 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Brajesh February 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Brajesh February 03, 2019 | Flag
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;

}

- Anonymous November 28, 2017 | Flag Reply
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;
}
}

- Ravi September 30, 2018 | Flag Reply
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;
}
}

- Anonymous September 30, 2018 | Flag Reply
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

- amit barnwal December 27, 2018 | Flag Reply
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
}

- amit barnwal December 27, 2018 | Flag Reply
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

- amit barnwal December 27, 2018 | Flag Reply
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

- amit barnwal December 27, 2018 | Flag Reply
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

- amit barnwal December 27, 2018 | Flag Reply
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}}}

- Anonymous December 27, 2018 | Flag Reply
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){
   // sqList.add(fstsq * fstsq);

      //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);

    }

    }

- Uday February 05, 2017 | Flag Reply
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){
// sqList.add(fstsq * fstsq);

//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);

}

}

- Uday February 05, 2017 | Flag Reply
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){
   // sqList.add(fstsq * fstsq);

      //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);

    }

    }

- UdayJoshi February 05, 2017 | Flag Reply
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){
   // sqList.add(fstsq * fstsq);

      //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);

    }

    }

- UdayJoshi February 05, 2017 | Flag Reply
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);
}

}}}

- Sharif Malik April 04, 2017 | Flag Reply
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);
		}

	}

- virtualSharif April 04, 2017 | Flag Reply
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];
	}

- koustav.adorable July 25, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More