Fidelity Problem 4: More commonly it is known as the Longest String Chain Problem.

Description: You are provided a dictionary of words in a form of a list of size n.You have to find Longest String Chain Length as per following explanation:

From the dictionary, you pick up a word and in each step, you remove a single letter from it and check whether the remaining word is still in the dictionary. If the remaining word is present in the dictionary you increase the chain length by one. You perform the same operations until you are left with the last remaining word present in the dictionary.

Mind it, you have to remove every possible character in the string and check the remaining word for chain length.
Input :
a
b
ba
bca
bda
bdca
Output: 4

Fidelity Question3: You are given an array of random positive and negative numbers.

You need to find the largest difference among all differences between two numbers in such a way that: 0<=i<n ; i<=j<n; ar[j]>ar[i] and the difference is ar[j]-ar[i].

For example: in array {2,3,1,5,4,7,9}

For 3 :{1} , max of set :1

For 1 :{} , empty as 1 is not bigger than any element in left

For 5 :{3,2,4} , max of set=4

For 4 :{2,1,3} , max of set=3

For 7 :{5,4,6,2,3} , max of set=6

For 9 :{7,6,8,4,5,2}, max of set=8

So the answer is the max of all above results{1,4,3,6,8} i.e 8.

If if you cannot get the required result return -1;

PS: (The question description is made easier than the original one)

Implementation:

	package hackerrankQuestion.fidelity;
	import java.util.Scanner;
	public class Solution3
	{
	public static void main(String[] args)
	{
	Scanner sc = new Scanner(System.in);
	int numberOfElements= sc.nextInt();
	int ar[]= new int[numberOfElements];
	for(int i=0;i<numberOfElements;i++)
	{
	ar[i]=sc.nextInt();
	}
	int maxDifference=getMaxDifference(ar);
	System.out.println("The resultant maximum difference is "+maxDifference);
	}
	public static int getMaxDifference(int ar[])
	{
	int curMin = ar[0];
	int resMin = -1;
	for (int i = 1; i < ar.length; i++)
	{
	if (ar[i] < curMin)
	{
	curMin = ar[i];
	continue;
	} else if (ar[i] > curMin)
	{
	int res = ar[i] - curMin;
	if (res > resMin)
	{
	resMin = res;
	}
	}
	}
	return resMin;
	}
	}

view raw Solution3.java hosted with ❤ by GitHub

Output:

7

2

3

4

1

5

7

9

The resultant maximum difference is 8

Fidelity Question2: 

You are given an array which you need to sort.

But Sorting here means different.Here by sorting we mean that if an array for example has following values:{3,4,2,9}, the resultant can be :

{4,2,3,9} OR {2,4,3,9} OR {4,2,9,3} OR {2,4,9,3}.

There are in total four different valid sorting resultants.

You need to find out the minimum number of moves to make an array sorted.

PS: (The question description is made easier than the original one)

Explanation: The question, in fact, needs that you move all the even elements on the left side of the array and all the odd elements on the right side but with the minimum number of moves.

Implementation:

	package hackerrankQuestion.fidelity;
	import java.util.Scanner;
	public class Solution2
	{
	public static void main(String[] args)
	{
	Scanner sc = new Scanner(System.in);
	int numberOfElements = sc.nextInt();
	int ar[] = new int[numberOfElements];
	for (int i = 0; i < numberOfElements; i++)
	{
	ar[i] = sc.nextInt();
	}
	int numberOfMoves = minMoves(ar);
	System.out.println("The minimum number of moves is " + numberOfMoves);
	for (int i : ar)
	{
	System.out.println(i);
	}
	}
	public static int minMoves(int ar[])
	{
	int beg = 0;
	int end = ar.length - 1;
	int count = 0;
	while (beg <= end)
	{
	if (ar[beg] % 2 != 0 && ar[end] % 2 == 0)
	{
	int x = ar[beg];
	ar[beg] = ar[end];
	ar[end] = x;
	beg++;
	end--;
	count++;
	}
	if (ar[beg] % 2 == 0)
	{
	beg++;
	}
	if (ar[end] % 2 != 0)
	{
	end--;
	}
	}
	return count;
	}
	}

view raw Solution2.java hosted with ❤ by GitHub

Fidelity Questions: 

Problem 1:

Simple Question based on Inheritance and methods related to java.lang.Math class.

Description:

You have to implement 2 classes named Point2D and Point3D.

The purpose of the two classes is to find out the distance between two 2D points and two 3D points respectively.

The Structure of the classes should be as follows:

Point2D:

-- Two instance level properties x and y which depicts the x and y coordinate of a point in two-dimensional space.

--A parameterized constructor which takes two parameters and initializes its instance variables with it.

--A method double distanceFrom(Point2D p) which returns the distance between two points in 2-Dimensional space.

--A method void printDistance(double d) which outputs the distance in a single digit format of the largest number than it if the distance is not an integer literal.

Point3D:

--The class extends Point2D

-- Three instance level properties x, y, and z which depicts the x, y and z coordinate of a point in three-dimensional space.

--A parameterized constructor which takes three parameters and initializes its instance variables with it.

--A method double distanceFrom(Point3D p) which returns the distance between two points in 3-Dimensional space.

--A method void printDistance(double d) which outputs the distance in a single digit format of the largest number than it if the distance is not an integer literal.

Implementation:

	package hackerrankQuestion.fidelity;
	import java.util.Scanner;
	public class Solution
	{
	// The following code is already present.
	public static void main(String[] args)
	{
	Scanner sc = new Scanner(System.in);
	int x1 = sc.nextInt();
	int y1 = sc.nextInt();
	int z1 = sc.nextInt();
	int x2 = sc.nextInt();
	int y2 = sc.nextInt();
	int z2 = sc.nextInt();
	Point2D p1 = new Point2D(x1, y1);
	Point2D p2 = new Point2D(x2, y2);
	Point3D p3D1 = new Point3D(x1, y1, z1);
	Point3D p3D2 = new Point3D(x2, y2, z2);
	double twoDdistance = p1.distanceFrom(p2);
	double threeDdistance = p3D1.distanceFrom(p3D2);
	p1.printDistance(twoDdistance);
	p3D1.printDistance(threeDdistance);
	}
	}
	//we need to implement the following classes
	class Point2D
	{
	int x, y;
	public Point2D(int x, int y)
	{
	this.x = x;
	this.y = y;
	}
	public double distanceFrom(Point2D p)
	{
	int subx = p.x - this.x;
	int suby = p.y - this.y;
	return Math.sqrt(((subx * subx) + (suby * suby)));
	}
	public void printDistance(double d)
	{
	System.out.println("2D distance=" + (int) Math.ceil(d));
	}
	}
	class Point3D extends Point2D
	{
	int z;
	public Point3D(int x, int y, int z)
	{
	super(x, y);
	this.z = z;
	}
	public double distanceFrom(Point3D p)
	{
	int subx = p.x - this.x;
	int suby = p.y - this.y;
	int subz = p.z - this.z;
	return Math.sqrt(((subx * subx) + (suby * suby) + (subz * subz)));
	}
	public void printDistance(double d)
	{
	System.out.println("3D distance=" + (int) Math.ceil(d));
	}
	}

view raw Solution.java hosted with ❤ by GitHub

Recursion In Maze Game

Question: Print all possible path in the 2D array from source to destination. Allowed motion is Horizontal right and vertical down.