Tag Archives: hacker rank interview question

Even or Odd String Interview Question – Hacker Rank

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:

ProjectStructure

Code is as below:

public class OddStrings {

	public static void main(String args[]){
		
		String data[] = {"aceace","ceceaa","abdbdbdbakjkljhkjh"};
		System.out.println(checkComputation(data));
		
		String data2[] = {"azbde","abcher","acegk"};
		System.out.println(checkComputation(data2));
				
	}
	
	public static  boolean checkComputation(String data[] ){
		
		boolean isStringEvenArray[] = new boolean[data.length] ;
		int tempVal;
		boolean isEvenPresent = false;
		
		for(int i=0; i<data.length;i++){
			isEvenPresent= false;
			
			for(int j=0; j<data[i].length();j++ ){
				tempVal = (int) data[i].charAt(j);
				if(tempVal%2==0){
					isEvenPresent = true;
				}
			}			
			isStringEvenArray[i] = isEvenPresent;			
		}
		
		int oddCount=0;		
		for(int i=0; i<data.length; i++){			
			if(!isStringEvenArray[i])
				oddCount++;			
		}
		
		if(oddCount%2!=0)return false;
		else return true;
		
	}
	
}

The output of the above code:

Input:
"aceace","ceceaa","abdbdbdbakjkljhkjh"

Output:
true

Input:
"azbde","abcher","acegk"

Output:
false

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

 


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:
ProjectStructure

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

 

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git