B'day Gift

Isaac has to buy a new HackerPhone for his girlfriend Amy. He is exploring the shops in the town to compare the prices whereupon he finds a shop located on the first floor of a building, that has a unique pricing policy. There are N steps leading to the shop. A numbered ball is placed on each of the steps.
The shopkeeper gives Isaac a fair coin and asks him to toss the coin before climbing each step. If the result of the toss is a 'Heads', Isaac should pick up the ball, else leave it and proceed to the next step.

The shopkeeper then asks Isaac to find the sum of all the numbers he has picked up (let's say S). The price of the HackerPhone is then the expected value of S. Help Isaac find the price of the HackerPhone. 

Example:

Input:  balls_count = 3, balls = {1, 1, 2}
Output: 2.0

Approach

Java

public class BdayGift {
    public static void main(String[] args) {

        int balls_count = 3;
        int balls[] = { 1, 1, 2 };
        System.out.println(solve(balls));

    }

    static double solve(int[] balls) {
        double sum = 0;
        for (int i : balls) {
            sum += i;
        }
        return (sum / 2);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

double solve(vector<int> balls)
{
    double sum = 0;
    for (auto i : balls)
    {
        sum += i;
    }
    return (sum / 2);
}

int main()
{
    int balls_count = 3;
    vector<int> balls = {1, 1, 2};
    double result = solve(balls);

    cout << fixed << setprecision(1) << result << "\n";

    return 0;
}

Diwali Lights

On the eve of Diwali, Hari is decorating his house with a serial light bulb set. The serial light bulb set has N bulbs placed sequentially on a string which is programmed to change patterns every second. If at least one bulb in the set is on at any given instant of time, how many different patterns of light can the serial light bulb set produce?

Note: Lighting two bulbs *-* is different from **-

Example:

Input:  n = 4
Output: 15

Approach

Java

public class DiwaliLights {
    public static void main(String[] args) {

        int n = 4;

        System.out.println(lights(n));

    }

    static long mod = 100000;

    static long power(long a, long n) {
        // Base Case
        if (n == 0)
            return 1;
        long res = power(a, n / 2) % mod;
        if (n % 2 == 1)
            return (res * res * a) % mod;
        else
            return (res * res) % mod;
    }

    static long lights(long n) {
        return (power(2, n) % mod - 1);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

#define mod 100000
long power(long a, long n)
{
    //Base Case
    if (n == 0)
        return 1;
    long res = power(a, n / 2) % mod;
    if (n & 1)
        return (res * res * a) % mod;
    else
        return (res * res) % mod;
}

long lights(long n)
{
    return (power(2, n) % mod - 1);
}

int main()
{

    int n = 4;

    cout << lights(n) << "\n";
    return 0;
}

Read Interview Questions

Exception Handling Interview Questions

DBMS Interview Questions Set -1

DBMS Interview Questions Set -2

SQL Interview Question Set -1

SQL Interview Question Set -2

JPA Interview Questions Set -1

JPA Interview Question Set -2

Hibernate Interview Questions

Spring Boot Interview Questions Set 1

Spring Boot Interview Questions Set 2

Most Distant

Keko has N dots in a 2-D coordinate plane. He wants to measure the gap between the most distant two dots. To make the problem easier, Keko decided to change each dot's x or y coordinate to zero.

Help Keko calculate the distance!

Example:

Input: n = 4, coordinates = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}
Output: 2.0000000000

Approach

Java

public class MostDistant {
    public static void main(String[] args) {

        int n = 4;

        double[][] coordinates = { { -1, 0 }, { 1, 0 }, 
                     { 0, 1 }, { 0, -1 } };

        double mnx = 0, mxx = 0, mny = 0, mxy = 0;

        for (int i = 0; i < n; i++) {
            double a = coordinates[i][0];
            double b = coordinates[i][1];
            if (a == 0) {
                mny = Math.min(mny, b);
                mxy = Math.max(mxy, b);
            } else {
                mnx = Math.min(mnx, a);
                mxx = Math.max(mxx, a);
            }
        }
        double mx = Math.max(Math.abs(mxx - mnx),
          Math.abs(mny - mxy));
        double q1 = Math.sqrt(mxx * mxx + mxy * mxy);
        double q2 = Math.sqrt(mnx * mnx + mxy * mxy);
        double q3 = Math.sqrt(mnx * mnx + mny * mny);
        double q4 = Math.sqrt(mxx * mxx + mny * mny);

        System.out.println(String.format("%.10f", 
     Math.max(mx, Math.max(q1, Math.max(q2, 
    Math.max(q3, q4))))));

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{

    int n = 4;

    vector<vector<double>> coordinates = {{-1, 0},
                                          {1, 0},
                                          {0, 1},
                                          {0, -1}};

    double mnx, mxx, mny, mxy;

    for (int i = 0; i < n; i++)
    {
        double a = coordinates[i][0];
        double b = coordinates[i][1];
        if (a == 0)
        {
            mny = min(mny, b);
            mxy = max(mxy, b);
        }
        else
        {
            mnx = min(mnx, a);
            mxx = max(mxx, a);
        }
    }
    double mx = max(abs(mxx - mnx), abs(mny - mxy));
    double q1 = sqrt(mxx * mxx + mxy * mxy);
    double q2 = sqrt(mnx * mnx + mxy * mxy);
    double q3 = sqrt(mnx * mnx + mny * mny);
    double q4 = sqrt(mxx * mxx + mny * mny);

    printf("%.10f", max(mx, max(q1, max(q2, max(q3, q4)))));

    return 0;
}

Points On a Line

Given n two-dimensional points in space, determine whether they lie on some vertical or horizontal line. If yes, print YES; otherwise, print NO.

Example:

Input:  n = 5, arr = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}}
Output: YES

Approach

Java

import java.util.HashSet;

public class PointsOnLine {
    public static void main(String[] args) {

        int n = 5;

        int[][] arr = { { 0, 1 }, { 0, 2 }, { 0, 3 }, 
         { 0, 4 }, { 0, 5 } };
        HashSet<Integer> xset = new HashSet<Integer>();
        HashSet<Integer> yset = new HashSet<Integer>();

        for (int i = 0; i < n; i++) {
            int a = arr[i][0], b = arr[i][1];

            xset.add(a);
            yset.add(b);
        }

        if (xset.size() == 1 || yset.size() == 1)
            System.out.println("YES");
        else
            System.out.println("NO");

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 5;

    vector<vector<int>> arr = {{0, 1},
                               {0, 2},
                               {0, 3},
                               {0, 4},
                               {0, 5}};
    set<int> xset, yset;

    for (int i = 0; i < n; i++)
    {
        int a = arr[i][0], b = arr[i][1];

        xset.insert(a);
        yset.insert(b);
    }

    if (xset.size() == 1 || yset.size() == 1)
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

Number Groups

The positive odd numbers are sorted in ascending order as (1,3,5,7,9...), and grouped as (1),(3,5),(7,9,11), and so on.

Thus, the first group is (1), the second group is (3,5), the third group is (7,9,11), etc. In general, the kth group contains the next k elements of the sequence.

Given k, find the sum of the elements of the kth group. For example, for k = 3, the answer is : 7+9+11 = 27

Find the sum of the elements of the th group.

Explanation:

For a number k, the result will be k*k*k, which is the cube of the number k.

So, simply return the cube of the given number.

Example:

Input:  k = 3
Output: 27

Approach

Java

public class NumberOfGroups {
    public static void main(String[] args) {

        int k = 3;

        System.out.println(sumOfGroup(k));

    }

    static long sumOfGroup(long k) {
        long res = k * k * k;
        return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long sumOfGroup(long long k)
{
    long long res = k * k * k;
    return res;
}

int main()
{

    int k = 3;

    cout << sumOfGroup(k) << "\n";

    return 0;
}

Sumar and the Floating Rocks

Famous wizard Sumar moonji kumaru is stuck in a huge room and has to save Hermione Granger from a monster. Kumaru is at location P1 given by integral coordinates (x1,y1) and Hermione is at location P2 given by integral coordinates (x2,y2). Sadly P1 and P2 are the only points at which floating rocks are present. The rest of the room is without a floor and underneath is hot lava.

Kumaru has to go from P1 to P2 but there are no floating rocks to walk on. Kumaru knows a spell that can make the rocks appear but only on the integral coordinates on the straight line joining P1 and P2.

How many rocks can appear at locations (x,y) on the line segment between P1 and P2 (excluding P1 and P2) which satisfy the condition that both x and y are integers?

Example:

Input: x1 = 2, y1 = 2, x2 = 5, y2 = 5
Output: 2

Approach

Java

public class FloatingRocks {
    public static void main(String[] args) {

        int x1 = 2, y1 = 2;
        int x2 = 5, y2 = 5;

        System.out.println(solve(x1, y1, x2, y2));

    }

    static int solve(int x1, int y1, int x2, int y2) {
        return Math.abs(gcd(y1 - y2, x1 - x2)) - 1;
    }

    static int gcd(int i, int j) {
        if (j == 0)
            return i;
        return gcd(j, i % j);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int solve(int x1, int y1, int x2, int y2)
{
    return abs(__gcd(y1 - y2, x1 - x2)) - 1;
}

int main()
{

    int x1 = 2, y1 = 2;
    int x2 = 5, y2 = 5;

    cout << solve(x1, y1, x2, y2) << "\n";

    return 0;
}

Halloween party

Alex is attending a Halloween party with his girlfriend, Silvia. At the party, Silvia spots the corner of an infinite chocolate bar (two-dimensional, infinitely long in width and length).

If the chocolate can be served only as 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Example:

Input: k = 5
Output: 6

Approach

Java

public class HalloweanParty {
    public static void main(String[] args) {

        int k = 5;

        System.out.println(halloweenParty(k));

    }

    static long halloweenParty(int k) {
        long y1 = k / 2, y2;
        if (k % 2 == 0)
            y2 = k / 2;
        else
            y2 = k / 2 + 1;
        return y1 * y2;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long halloweenParty(int k)
{
    long y1 = k / 2, y2;
    if (k % 2 == 0)
        y2 = k / 2;
    else
        y2 = k / 2 + 1;
    return y1 * y2;
}

int main()
{
    int k = 5;

    cout << halloweenParty(k) << "\n";

    return 0;
}