Paytm : Throttling on java method

Problem: Throw Exception when you method hit goes above a certain limit.

Approach: Try to implement the leaky bucket algorithm Here.

Solution:

Paytm : Print "P" "T" "M" using 3 threads.

Question: Create 3 thread and ask them to print the alphabet P by thread 1, T by thread 2 and P by thread 3.

Approach:
1.create 3 threads with a there run method and shared variable.
2. update the shared variable after the execution of actual logic.


Solution :

Output: PTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTMPTM

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.

Print the Post order of a binary tree given its Pre-Order and In-Order in two different arrays.

Given two arrays representing the In-Order/Pre-Order of the binary tree elements;

you need to print the post order of the tree.

For Example:

Input1: { 4, 2, 5, 1, 3, 6 };

Input2: { 1, 2, 4, 5, 3, 6 };

Output:{ 4, 5, 2, 6, 3, 1 };

Explanation:

--We will use the below two facts for solving our problem

----1-The First element in the Pre-Order array will always be the root of the tree. 

    AND

----2-The left part in the In-Order always consists of the elements in the left subtree of the root element and similarly for right subtree.

Basic Algo:

--Store the root of the tree/sub-tree from the first element of the Pre-Order array.

--Find that root in the in-order array to segregate the left subtree and the right tree.

--Now have faith that if you call your method again i.e recursively for left subtree and right subtree then you will get your result for left subtree and right subtree.

--After getting the answer Print the root element.

NOTE: For calculating the post order of left subtree and right subtree,

Be careful that you would need to pass correct array indexes for both subtrees.

CALCULATION of Array Indexes for Subtrees

-- For Calculation, first of all, find the position of the root element in In-Order array (as per the above algo)

---LEFT SUBTREE INDEX CALCULATION

-- Starting Index of Left Sub Tree in original In-Order Array: It is same as In-Order starting index (and for the full-tree/first-call it is 0).

-- Ending Index of Left Sub Tree in original In-Order Array: Position of root in In-Order minus 1 (pos-1)

-- Starting Index of Left Sub Tree in original Pre-Order Array: It is one more than original Pre-Order starting index.

-- Ending Index of Left Sub Tree in original Pre-Order Array: It is the addition of starting index of Pre-Order Array and the size of the left subtree.

 --For calculating the size of the Left subtree you know that it should be the number of elements from the starting index of In-Order array and

the position of the root.

---RIGHT SUBTREE INDEX CALCULATION

-- Starting Index of RIGHT Sub Tree in original In-Order Array: Position of root in In-Order add 1 (pos+1)

-- Ending Index of RIGHT Subtree in original In-Order Array: End index of the In-Order Array.

-- Starting Index of RIGHT Sub Tree in original Pre-Order Array: It is one more than the sum of starting index of Pre-Order array and size of the left subtree

-- Ending Index of RIGHT Tree in original Pre-Order Array: It is the end index of the Pre-Order Array

SPECIAL CONDITION:

--If the root does not have a left/right subtree then don't call the method again

--When you get the position of the root element at the starting index of In-Order Array, it means that it does not have left subtree.

--When you get the position of the root element at the ending index of In-Order Array, it means that it does not have right subtree.

CODE:

package binarytree;

public class PrintPostWithPreAndIn

     {

     public static void main(String[] args)

          {

               int in[] = { 4, 2, 5, 1, 3, 6 };

               int pre[] = { 1, 2, 4, 5, 3, 6 };

               printPostOrder(in, pre, 0, 5, 0, 5);

          }

     public static void printPostOrder(int in[], int pre[], int isi, int iei,int psi, int pei)

          {

               if (isi >= iei || psi >= pei)

               {

                    System.out.print(in[isi]+” “);

                    return;

               }

               int root = pre[psi];

               // root is always the first element in preorder

               int pos = search(in, isi, iei, root);

               int startIndexOfLSTIO = isi;

               int endIndexOfLSTIO = pos - 1;

               int startIndexofLSTPRO = psi + 1;

               int lsize = pos - isi;

               int endIndexofLSTPRO = psi + lsize;

               // printPostOrderFromLeftSubTree

               if(pos!=isi)

               {

                    printPostOrder(in, pre, startIndexOfLSTIO,endIndexOfLSTIO,startIndexofLSTPRO, endIndexofLSTPRO);

               }

               

               // printPostOrderFromRightSubTree

               int startIndexOfRSTIO = pos + 1;

               int endIndexOfRSTIO = iei;

               int startIndexOfRSTPRO = psi + lsize+1;

               int endIndexOfRSTPRO = pei;

               if(pos!=iei)

               {

                    printPostOrder(in, pre, startIndexOfRSTIO, endIndexOfRSTIO,startIndexOfRSTPRO, endIndexOfRSTPRO);

               }

               System.out.println(root);

          }

     public static int search(int[] ar, int si, int ei, int val)

          {

               for (int i = si; i <= ei; i++)

               {

                    if (ar[i] == val)

                    {

                         return i;

                    }

               }

          return -1;

          }

     }

OUTPUT: 4 5 2 6 3 1