We all know that a binary search tree operations are of O(log n). But there can be a worst scenario where it can go up to O(n).

So you might expect quick question like,

When can binary search tree perform worst? What type of data can not be a good bet to use to form a Binary Search Tree? What can go wrong with Binary Search Tree? Binary search tree worst case scenario.

Answer is easy:

Explanation:

Unbalanced binary search tree can perform worst in a special case like sorted data.
If all the data are coming in a sorted order and forming BST then our tree will be unbalance and it will be form a linked list type of structure only as shown in the above figure. So this structure is equivalent to a singly linked list which makes the operation of search/remove/insert O(n).

It is asked in the coding challenge taken through Hacker Rank.

Goal: To determine if it is a even or odd string. Input: Number and Array of String containing lower case Output:
For each string compute:
[ Char[0]^Number X Char[1]^Number X …… (All character of String[0]) +

Char[0]^Number X Char[1]^Number X …… (All character of String[1]) +

…………… ] is Even Number or Odd Number ?

Here Char[i] is the ASCII value of character.

For example:
For input: abc bd and 2

= (97^2 X 98^2 X 99^2) + (98^2 X 100^2)

= ( 9409 X 9604 X 9801 ) + ( 9604 X 10000)

= 885657916836 + 96040000

= 885753956836

So it should return Even.

The catch here is not to compute complex mathematical formulas. There are very basic mathematical checks that needs to be followed to compute if this whole sum is even or odd.
1. Even^AnyNumber = Even & Odd^AnyNumber = Odd So you do not need to compute the powers.

2. Even X Any Number = Even
Odd X Odd = Odd So you just need to identify whether there is any even number present in the multiplication.

3. For sum: if Odd numbers occur odd times, final sum will be Odd. So you need to compute the odd count.

Below is the project structure and source code for the same:

Goal: Verify preorder sequence of Binary Search Tree (BST)

Problem:
You have an array of preorder traversal of Binary Search Tree ( BST). Your program should verify whether it is a correct sequence or not.

Input: Array of Integer [ Pre-order BST ] Output: String “Yes” or “No”

To solve above problem, you do not need to construct a Binary Tree from a given pre-order sequence.

The pre-order sequence of binary tree can form a sorted stack. So lets break it in a few “SIMPLE” steps as follows:

Iterate over each element and follow the steps below:

1. Push to stack till you get higher element than the topmost element of the stack. [i.e. you keep pushing till you hit the leftmost leaf]
2. If you find current value which is greater than the TOP of Stack, POP till you hit higher element, and also mark the last poped value, which is your variable (Left_Tree_Highest). This variable is used to check whether the order is correct or not.
3. In all the steps, if you find current element lesser than Left_Tree_Highest, then your tree is not a Binary Search Tree and it should return “NO”.

4. If all the element traversed, and you have not hit “NO”, means given sequence follows the Binary Search Tree rule.

Above step might be confusing, but take a pen and paper, try to follow the steps by taking stacks and Left_Tree_Highest values at each step. Once you are able to track it, you will able to co-relate it with the steps given above.

So the basic idea is that at any point, left subtree’s highest element should be lowest for the untraversed elements [Right Tree].

Below is the project structure and code for the same:

Code is as below:

import java.util.Stack;
public class PreorderBST {
public static void main(String args[]){
int[] inputPreOrderArray = {1,2,3};
System.out.println(checkBST(inputPreOrderArray));
int[] inputPreOrderArray1 = {3,2,1,5,4,6};
System.out.println(checkBST(inputPreOrderArray1));
int[] inputPreOrderArray2 = {3,4,5,1,2};
System.out.println(checkBST(inputPreOrderArray2));
}
public static String checkBST(int[] inOrderArray){
Stack<Integer> s = new Stack<Integer>();
int lower = -1;
for(int i=0;i<inOrderArray.length;i++){
if(lower>-1 && inOrderArray[i] < lower){
return "NO";
}
while(!s.isEmpty() && s.peek()<inOrderArray[i]){
lower = s.pop();
}
s.push(inOrderArray[i]);
}
return "YES";
}
}

Output:

For input:
1,2,3
3,2,1,5,4,6
3,4,5,1,2
Output:
YES
YES
NO

Below is the same code as above, with Hacker Rank Input style:

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class PreorderBST {
public static void main(String args[]){
Scanner in = new Scanner(System.in);
int testCaseNumber = Integer.parseInt(in.nextLine());
ArrayList<String> output = new ArrayList<String>();
while(testCaseNumber>0){
int size = Integer.parseInt(in.nextLine());
int[] preOrderArray = new int[size];
String[] numberStrArray = in.nextLine().split(" ");
for(int i=0;i<numberStrArray.length;i++){
preOrderArray[i] = Integer.parseInt(numberStrArray[i]);
}
output.add(checkBST(preOrderArray));
testCaseNumber--;
}
for(int i=0;i<output.size();i++){
System.out.println(output.get(i));
}
in.close();
}
public static String checkBST(int[] inOrderArray){
Stack<Integer> s = new Stack<Integer>();
int lower = -1;
for(int i=0;i<inOrderArray.length;i++){
if(lower>-1 && inOrderArray[i] < lower){
return "NO";
}
while(!s.isEmpty() && s.peek()<inOrderArray[i]){
lower = s.pop();
}
s.push(inOrderArray[i]);
}
return "YES";
}
}

Input/Output Patter:

3 //Number of test case
3 //Number of Element for test case 1
1 2 3
6 //Number of Element for test case 2
3 2 1 5 4 6
5 //Number of Element for test case 3
3 4 5 1 2
Output:
YES
YES
NO

Calculate Fibonacci number in java using recursion and also using multi-threading in O(log n) steps in java.

Input: Index value of Fibonacci series.

Output: Fibonacci value

To solve above problem, the very basic definition of Fibonacci is that F_{i} = F_{i-1} + F_{i-2}.

Each F is our function. So let’s look at the basic solution.

1. Simple Recursion:

Here at each recursive call to method computeFib(int n), you simple needs to compute sum of two previous number. So for i^{th} step, you need to compute F_{i-1} + F_{i-2} . So each iteration we will have 2 recursive call one for F_{i-1}and other one for F_{i-2} . The ending of recursion is when your value of n is less or equal to 2.

So below is the screen shot of my project structure and code to achieve the same:

Code as is follows:

public class FibRecursion {
public static void main(String args[]){
int inputNum = 8;
System.out.println("Fibonacci number at "+inputNum+" position is:"+computeFib(inputNum));
}
public static int computeFib(int n){
if(n==0) return 0;
if( n==1 || n ==2) return 1;
/*
* recursion call with previous number
*/
return computeFib(n-1)+computeFib(n-2);
}
}

Output of above code:

Fibonacci number at 8 position is:21
Fibonacci number at 0 position is:0
Fibonacci number at 10 position is:55

2. Multithreaded Version of above which will compute it in O(log n).

Here, we will spawn a new thread for each recursion call, which will create a tree. So each step you will be spawning new thread which will continue to spawn another threads till it reached its leaf (i.e n <=2) .

Multithreaded code is as below:

public class FibMultiThreading extends Thread {
private int x;
public int answer;
public FibMultiThreading(int x) {
this.x = x;
}
public void run() {
if (x == 0){
answer = 0;
}else if( x == 1 || x == 2 ) {
answer = 1;
}else {
try {
/*
* Below we are invoking 2 threads to compute separate values
* This will for a tree structure
*/
FibMultiThreading f1 = new FibMultiThreading(x-1);
FibMultiThreading f2 = new FibMultiThreading(x-2);
f1.start();
f2.start();
f1.join();
f2.join();
answer = f1.answer + f2.answer;
}catch(InterruptedException ex) {
ex.printStackTrace();
}
}
}
public static void main(String[] args){
try {
int inputNum = 8;
FibMultiThreading f = new FibMultiThreading(inputNum);
f.start();
f.join();
System.out.println("Fibonacci number at "+inputNum+" position is:"+f.answer);
}
catch(Exception e) {
e.printStackTrace();
}
}
}

The output for the above is:

Fibonacci number at 8 position is:21
Fibonacci number at 0 position is:0
Fibonacci number at 10 position is:55

Output: print each iteration by subtracting the smallest elements till array becomes empty

For example:
For input array: 4, 3, 5, 8, 12

At each iteration, find minimum number and subtract it from element and print non zero elements
1 2 5 9 (Subtracted 3 from each elements)
1 4 8 (Subtracted 1 from each elements)
3 7 (Subtracted 1 from each elements)
4 (Subtracted 3 from each elements)

For the above problem, naive approach is to find the minimum in each iteration, subtracting it and copy it in new memory.

There are 2 place where you can improve on memory as well as the time complexity (less iteration).

1. Identify minimum value while subtracting the minimum value

2. Do not copy element to another array, just simple store the last index value and decrease it in recursive call.

Below is the screen shots of my project directory and the code for the above solution:

You can also clone the repository from GIT using the link below:

public class SliceDown {
public static void main(String args[]){
SliceDown sd = new SliceDown();
int a[] = {15,12,10,5,3};
printArray(a, a.length);
int smallestIndex = findSmallest(a);
sd.sliceDown(a,a.length,smallestIndex);
}
/*
* recursively call this method by passing the index value of
* min number and the range that needs to be sliced down
*/
public void sliceDown(int a[],int range, int smallestIndex){
int new_range = 0;
int new_smallestIndex = -1;
int smallNumber = a[smallestIndex];
for(int i=0;i<range;i++){
// To skip the number which is going to be slice down
if(a[i]!=smallNumber){
a[new_range] = a[i] - smallNumber;
//To initialize & find the new minimum number for next iteration
if(new_smallestIndex<0){
new_smallestIndex = new_range;
}else if(a[new_range] < a[new_smallestIndex]){
new_smallestIndex = new_range;
}
new_range++;
}
}
printArray(a,new_range);
if(new_range>1){
sliceDown(a, new_range,new_smallestIndex);
}
}
//This method will be called only once for the first iteration
private static int findSmallest(int a[]){
int smallestIndex = 0;
for(int i=1;i<a.length;i++){
if(a[smallestIndex]>a[i]){
smallestIndex = i;
}
}
return smallestIndex;
}
public static void printArray(int a[],int range){
for(int i=0;i<range;i++){
System.out.print(a[i]+" ");
}
System.out.println("");
}
}

The output of the above code:

15 12 10 5 3
12 9 7 2
10 7 5
5 2
3

Again you can find the above code on git repo: https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Input:
X and Y are integer values, where X < Y
N is the length of permutation
Output:
To print all the possible permutations in sorted order, in given form, starting from zero.

i.e 0 , 0 + X (or Y)

For example:
X = 1, Y = 2
N = 3.

output should be:
0 1 2
0 1 3
0 2 3
0 2 4

To solve this problem, we can use recursion by passing the value of X and Y with the current state array.
At each recursion step, we will call the method by passing values of X or Y in order. The end of the recursion would be the length of array reaching the value of N.

Here is the code:

You can also clone the repository from GIT using the link below:

Input: Integer array with 0 or more repeated values.
Output: Total number of duplicate numbers present in the given array

The use of Hash set can be done in order to solve this by traversing each element and adding it into the set, later on they are checked for repetitive addition (i.e. we make sure that the numbers were not included already!)

Step 1: Create 2 hash sets. 1 is for all the elements and the other is for the duplicate elements.

import java.util.HashSet;
public class CountDuplicates {
static int countDuplicates(int[] numbers) {
HashSet<Integer> set = new HashSet<Integer>();
HashSet<Integer> duplicateSet = new HashSet<Integer>();
for(int i=0;i<numbers.length;i++){
if(set.contains(numbers[i])){
duplicateSet.add(numbers[i]);
}else{
set.add(numbers[i]);
}
}
return duplicateSet.size();
}
public static void main(String p[]){
int a[]={20,20,20,30,40,50,60,90,80,90,100};
System.out.println("Total Number having duplicate Count:"+countDuplicates(a));
}
}

The output of the above code:

Input:
{20,20,20,30,40,50,60,90,80,90,100};
Output:
Total Number having duplicate Count:2

Output: Total number of unique pairs having difference provided in the input.

Here in this problem, the input will be an array of integer and also the difference value. So it will ask to out put either the total unique pairs of elements from the array having difference or just total count of that pairs.

So, with the use of hash set, it will be achieved in O(n) where n is the total number of elements in array.

Step to solve this question:
Step 1: Create a Set of all the elements.

Step 2: Iterate over each element in set

Check whether number (element value + diff) is in hashset.

Below is the java implementation and sample output.

import java.util.Scanner;
public class PerfectSquare {
public static void main(String args[]){
Scanner in = new Scanner(System.in);
System.out.println("Please Enter Your Lower Limit");
int low = in.nextInt();
System.out.println("Please Enter Your Upper Limit");
int high = in.nextInt();
in.close();
int smallestNumber = (int)Math.ceil(Math.sqrt(low));
int highestNumber = (int)Math.floor(Math.sqrt(high));
System.out.println("Total Number of Perfect square are:"+(highestNumber-smallestNumber+1));
}
}

The output of above code is as below:

Please Enter Your Lower Limit
10
Please Enter Your Upper Limit
100
Total Number of Perfect square are:7
Please Enter Your Lower Limit
2
Please Enter Your Upper Limit
12
Total Number of Perfect square are:2
Please Enter Your Lower Limit
45
Please Enter Your Upper Limit
500
Total Number of Perfect square are:16

Here, you will have fixed size array with integer elements called catter pillars. For example: [2,4,5] and you have integer value of totalLeaves. For example 10, so it will have values from 1 to 10.

Now the question will be like, how many leaves will be left if it will be eaten in a way where (Leaf % catterpillar == 0).

So for our example,

we have leaves [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Caterpillar 2 can eat: 2, 4, 6, 8, 10

Caterpillar 4 can eat: 4, 8

Caterpillar 5 can eat: 5, 10

So the left leaves will be: 1,3,7,9

Total of 4 leaves will be left.

Here the naïve approach would be to loop over all the leaves and also loop over all the caterpillars and discard those leaves that are divisible by it. It will have 0 (n^{2}) complexity.

Approach 1. Here the first improvement can be achieved, if you look at the caterpillar array. Here you have [2,4,5]. The easiest catch is the discard those caterpillars which are divisible by other. So which will make our caterpillar array [2,4]. It is because the leaves that are eaten by 4 can also be eaten by 2. So we do not need to loop over all the caterpillars. This way we can save many iterations by reducing unnecessary caterpillar.