Sappient : Star Pattern problem

Question: WAP to print the number in the below format.

star pattern for size :7

    1

   232

  34543

 4567654

  34543

   232

    1

Answer :

 

Maximum size square sub-matrix with all 1s

 Approach: Think how you what information you are getting while traversing  the matrix. I find that while traversing the matrix i try to store that how many ones i have encountered  in past. So that is the key of solve the problem, just use your memory/result to get the result. Maximum size square can find as maximum number in the result matrix.

it can used to print the small matrix, but in actual there can be multiple places where you can find the square size coordinates.so returning the maximum size can solve the problem. To get the coordinates we in count how many max size matrix we have then we can try to use it.that coordinates with max square sum.

complexity space:(m*n) time: O(m*n)

Print different views of Tree like a Top, Bottom, Left, Right?

Question: Print different views of Tree like a Top, Bottom, Left, Right?

Problem link: https://www.hackerrank.com/challenges/tree-top-view/problem

Answer 

I am using Recursive approach to solve this Question, As it is easier to understand and explain, but it can lend up in stack overflow problem in case of a huge tree. It is good if we have some idea about the iterative approach. Followup Question may be asked that is the internal working of TreeMap and its data structure and its time complexity of inserting the data and traversing it.

1. TopView

 

To solve this Question, First, start thinking about how we can traverse the tree.

We can use recursion with the base condition that starts traversing left part of the tree and then right part. Here we got the hit that if we maintain horizontal distance from the root node that can give us the Top/Bottom view tree. 

To get the particular tree we use the level to get the specific Top/Bottom view tree.

Pair is a class that holds the two number that is node value and its level.

Time Complexity: O(n)

Space Complexity: O(n)

2. Bottom View

Only this below condition is changed.In order to get the bottom view of tree.

!map.containsKey(dist) || level >= map.get(dist).level

Time Complexity: O(n)

Space Complexity: O(n)

3. Left View 

now, this becomes easier as here we just need to maintain the max level till now while doing pre-order traversal.

Time Complexity: O(n)

Space Complexity: O(1)

4.Right View

now, this becomes easier as here we just need to maintain the max level till now while doing post-order traversal.

Time Complexity: O(n)

Space Complexity: O(1)

Code Solution :

Console 

6

1 2 5 3 6 4

Tree:  

  1

    \

     2

      \

       5

      /  \

     3    6

      \

       4

Top View: 

1 2 5 6 

Bottom View: 

1 3 4 6 

Left View: 

1 2 5 3 4 

Right View: 

1 2 5 6 4 

Google Code jam 2019 | Qualification Round | Foregone Solution

Problem: Someone just won the Code Jam lottery, and we owe them N jamcoins! However, when we tried to print out an oversized check, we encountered a problem. The value of N, which is an integer, includes at least one digit that is a 4... and the 4 key on the keyboard of our oversized check printer is broken.

Fortunately, we have a workaround: we will send our winner two checks for positive integer amounts A and B, such that neither A nor B contains any digit that is a 4, and A + B = N. Please help us find any pair of values A and B that satisfy these conditions.

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with an integer N.

Output

For each test case, output one line containing Case #x: A B, where x is the test case number (starting from 1), and A and B are positive integers as described above.

It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2019 contest.)

Solution :
Problem link: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231?show=progress

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:

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:

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: