# Tag Archives: Interview Question

## Verify preorder sequence of Binary Search Tree (BST) Interview Question – Hacker Rank

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]);
}
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```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Calculate Fibonacci number in java using Recursion and Multi Threading

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 Fi = Fi-1 + Fi-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 ith step, you need to compute Fi-1 + Fi-2 . So each iteration we will have 2 recursive call one for Fi-1 and other one for Fi-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) .

```public class FibMultiThreading extends Thread {
private int x;

this.x = x;
}

public void run() {
if (x == 0){
}else if( x == 1 || x == 2 ) {
}else {
try {
/*
* Below we are invoking 2 threads to compute separate values
* This will for a tree structure
*/
f1.start();
f2.start();
f1.join();
f2.join();
}catch(InterruptedException ex) {
ex.printStackTrace();
}
}
}

public static void main(String[] args){
try {
int inputNum = 8;
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```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Slice Down problem in Java (Hacker Rank Interview Questions)

Input: array of integer value

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:

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Code is as 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

## Print all the possible permutations by adding X and Y (Hacker Rank Interview Question)

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:

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

```import java.util.ArrayList;

public class PossiblePermutations {

int x=1;
int y=2;
int permutSize = 5;
int length;

public static void main(String args[]){
PossiblePermutations pd = new PossiblePermutations();
ArrayList<Integer> al = new ArrayList<Integer>();

pd.printAllPermutations(al);
}

public void printAllPermutations(ArrayList<Integer> a){
ArrayList<Integer> a1 = new ArrayList<Integer>(a);

if(a.size() == permutSize){
System.out.println(a);
}else{
printAllPermutations(a);
printAllPermutations(a1);
}
}

public void printArray(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("");
}
}
```

The output of above code:

```Input:
X = 1
Y = 2
N = 5

Output:
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 5]
[0, 1, 2, 4, 5]
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 5]
[0, 1, 3, 4, 6]
[0, 1, 3, 5, 6]
[0, 1, 3, 5, 7]
[0, 2, 3, 4, 5]
[0, 2, 3, 4, 6]
[0, 2, 3, 5, 6]
[0, 2, 3, 5, 7]
[0, 2, 4, 5, 6]
[0, 2, 4, 5, 7]
[0, 2, 4, 6, 7]
[0, 2, 4, 6, 8]
```

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

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Count Duplicate Pairs of Integer in a given array (Hacker Rank Interview Questions)

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.

Step 2: Loop over each element in the given array

Now, for each element:

a. Check whether element is in the Hash set

b. If yes, then add it to duplicate set

c. If no, then add it to normal hash set

Step 3: output the size of duplicate hash set

Below is the code in java for the above problem.

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Below is the code:

```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])){
}else{
}
}

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```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Find unique pairs with k difference (KDiff) (Hacker Rank Interview Question)

Input: Integer array
Diff: Integer difference

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.

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

```import java.util.HashSet;
import java.util.Iterator;

public class KDiff {

public static void main(String args[]){

int pairCount = 0;
Integer elements[] = {1,3,4,5,8,8};
int kDiff = 2;

if(elements.length>1 && kDiff>=1 && elements.length == elements.length){

HashSet<Integer> hSet = new HashSet<Integer>();

for(int i=0;i<elements.length;i++){
int inputElement = elements[i];
if(!hSet.contains(inputElement)){
}
}

Iterator<Integer> itSet = hSet.iterator();

while (itSet.hasNext()) {

Integer value = itSet.next();
Integer subtractValue =  value+kDiff;

if(hSet.contains(subtractValue)){
System.out.println("Pair Found:"+value+" & "+subtractValue);
pairCount++;
}
}
}else{
pairCount=0;
}

System.out.println("Total Pairs:"+pairCount);
}
}
```

Sample output of above code:

```Input:
elements[] = {1,3,4,5,8,8};
int kDiff = 2;

Output:
Pair Found:1 & 3
Pair Found:3 & 5
Total Pairs:2```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Total Number of Perfect Squares (Hacker Rank Interview Question)

Problem: Finding the number of perfect squares between two integer range.

Input: first integer and last integer ->  int startInteger, int endInteger

Output: total number of perfect squares including this number -> int count

The worst approach would be to loop over each element and check whether it is an integer.

The best approach would be to determine the floor of root of first integer and ceil of root of last integer.

So lets take an example of 10, 100.

The expected answer would be: 7

So first compute the floor of the square root of 10 that would be 3.

And then compute the ceil of the square root of 100 that would be 10.

10 – 3 = 7 will be the output. It will be O(1) .

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

```import java.util.Scanner;

public class PerfectSquare {

public static void main(String args[]){
Scanner in = new Scanner(System.in);
int low = in.nextInt();
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
100
Total Number of Perfect square are:7

2
12
Total Number of Perfect square are:2

45
500
Total Number of Perfect square are:16```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## The caterpillar problem (Hacker Rank Interview Questions)

The caterpillar problem.

Input:

1. int[] caterPillar = {2,4,5}
2. int totalLeaves = 10

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 (n2) 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.

Below code is implementation of above approach.

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

```import java.util.ArrayList;

public class EatenLeaves {

public static void main(String args[]){
int inputArray[] = {2,4,5,10,12};
System.out.println("Survived Leaves Count:"+returnCountLeaves(10,inputArray));
}

static int returnCountLeaves(int N, int[] A ){

ArrayList<Integer> reduceArrayList = new ArrayList<Integer>();
boolean reduceFlag = false;

for(int i=1;i<A.length;i++){
reduceFlag = false;
for(int j=0;j<reduceArrayList.size();j++){
if(A[i]%reduceArrayList.get(j)==0){
reduceFlag = true;
break;
}
}

if(!reduceFlag){
}
}

System.out.println("Reduced Caterpillars:"+reduceArrayList);

int survivedLeaves = 0;
for(int m = 1;m<=N;m++){
for(int j=0;j<reduceArrayList.size();j++){
if(m%reduceArrayList.get(j) == 0){
survivedLeaves++;
break;
}
}
}

return N-survivedLeaves;
}
}```

The output of above code is as below:

```Input:
Total Leaves N = 10
Caterpillars: 2,4,5,10,12

Output:
Reduced Caterpillars:[2, 5]
Survived Leaves Count:4

Input:
Total Leaves N = 20
Caterpillars: 2,3,4,5

Output:
Reduced Caterpillars:[2, 3, 5]
Survived Leaves Count:6

Input:
Total Leaves N = 20
Caterpillars: 2,4,5,10,12

Output:
Reduced Caterpillars:[2, 5]
Survived Leaves Count:8
```

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

## Parentheses / Brackets Check (Hacker Rank Interview Questions)

Match the braces and verify weather all the opening braces has the closing braces in right order.

Input: String of braces only: “[{}]()[{{()}}()]”
Output: Yes

Input: String of braces only: “[{}]({{()}}()]”
Output: No

So the basic approach would be to use stack to verify the correct order of braces.

Iterate over each braces from start to end and do the below step at each iteration.

Step 1.  When you find opening bracket: Do Push.
Step 2.  When you find closing bracket: Do pop and check whether closing and opening bracket match. If yes, then continue, if not then break and return NO.

Below is the Screenshots of the project structure followed by the source code:

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

Project Structure in Eclipse:

Below is the code:

```import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class BracesCheck {

public static void main(String args[]){
Scanner in = new Scanner(System.in);
String inputString = in.nextLine();
System.out.println(checkBraces(inputString));
in.close();
}

static String checkBraces(String value){
Stack<Character> specialCharStack = new Stack<Character>();
String response = "Fail";
char tempChar;
Character[] openingBraces = {'[','(','{'};
Character[] closingBraces = {']',')','}'};
List<Character> openingBracesList = Arrays.asList(openingBraces);
List<Character> closingBracesList = Arrays.asList(closingBraces);

if(value == null){
return response;
}else if(value.length()==0){
response = "Pass";
}else{

for(int i=0; i < value.length(); i++) {
tempChar = value.charAt(i);

if(openingBracesList.contains(tempChar)){
specialCharStack.push(tempChar);
}else if(closingBracesList.contains(tempChar)){
if(!specialCharStack.isEmpty()){
if(tempChar==')' && '(' != specialCharStack.pop()){
return response;
}else if(tempChar=='}' && '{' !=specialCharStack.pop()){
return response;
}else if(tempChar==']' && '[' != specialCharStack.pop()){
return response;
}
}else{
return response;
}
}else{
return response;
}
}

}

if( specialCharStack.isEmpty()){
response = "Pass";
return response;
}else{
return response;
}
}
}
```

The output of the above code

```Please Enter Your String
()
Pass

({({()})})
Pass

(((((((
Fail