Tag Archives: java

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:

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

HackerRankProjectStructure

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:
GitHub-Mark-32px 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:

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

HackerRankProjectStructure

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>();
			al.add(0);
			
			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{
				a.add(a.get(a.size()-1) + x);
				printAllPermutations(a);
				a1.add(a1.get(a1.size()-1) + y);
				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:

GitHub-Mark-32px 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.

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

 

HackerRankProjectStructure

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])){
					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

You can have above code from GIT.

GitHub-Mark-32px 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.

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

HackerRankProjectStructure

 

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)){
					hSet.add(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.

GitHub-Mark-32px 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.

GitHub-Mark-32px 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);
		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

You can have above code from GIT.

GitHub-Mark-32px 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.

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

HackerRankProjectStructure

 

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>();
		reduceArrayList.add(A[0]);
		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){
				reduceArrayList.add(A[i]);
			}
		}
		
		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.

GitHub-Mark-32px 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.

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

 

Project Structure in Eclipse:

HackerRankProjectStructure

 

 

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);
		System.out.println("Please Enter Your String");
		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

Please Enter Your String
({({()})})
Pass

Please Enter Your String
(((((((
Fail

Please Enter Your String
)))))(((((
Fail

Please Enter Your String
))))))
Fail


You can have above code from GIT.

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

Stack implementation using Array

Stack is an abstract data type.
Basic operation of stack can be:

1. Push :
Push object on top of stack.
Throw exception if stack is full.

2. Pop :
Take out(remove) object that is on top of stack .
Throw exception if stack is empty.

3. Top:
Read the object that is on top of stack.
Throw exception if stack is empty.

Now we need to implement these all operation in Java using Object Array.

Below is my eclipse folder structure. You may find this common but keeping all beginners in mind so please bare with me.

ArrayStack

Lets define an interface for a stack:

package datastructure.stack;

public interface Stack {

	//accessor method stack
	public int size();
	public boolean isEmpty();
	public Object top() throws Exception;
	
	//update method stack
	public void push(Object element) throws Exception;
	public Object pop() throws Exception;
}

 

 

 

Now we need to implement these functionality. So will be implementing this interface by our class called ArrayStack.java.

package datastructure.stack;

public class ArrayStack implements Stack {
	
	private Object stack[];
	private int capacity;
	private int currentPos=-1;
	
	public ArrayStack(int capacity){
		this.capacity = capacity;
		stack = new Object[capacity];
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return this.capacity;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		if(currentPos<0){
			return true;
		}
		return false;
	}

	@Override
	public Object top() throws Exception {
		// TODO Auto-generated method stub	
		if(currentPos<0){
			throw new Exception(" Stack is Empty");
		}
		return stack[currentPos];
	}

	@Override
	public void push(Object element) throws Exception {
		// TODO Auto-generated method stub
		if(currentPos==capacity){
			throw new Exception();
		}
		stack[++currentPos] = element;
	}

	@Override
	public Object pop() throws Exception {
		// TODO Auto-generated method stub
		if(currentPos<0){
			throw new Exception();
		}
		return stack[currentPos--] = null;
	}

}

 

 

As you can see in the ArrayStack.java,
we define constructor to initialize the size of our stack. This size will set the limit on number of element in stack.
So let me just briefly explain about class variable and methods.

Object stack[] : An array which is going to be our stack(element holder)
int capacity : Max size of Stack
int currentPos : It is pointer of top element of stack. We will need to increment it when any element is pushed, decrement it when we do the pop operation. Initially we kept it -1 as first element will have index 0. So if there is no element it should be -1.

public int size()                                 : Gives you the capacity of Stack, which was set at the time of initialization.
public boolean isEmpty()                : Gives you true/false based on currentPos pointer.
public Object top()                            : Return the object that is there on top of stack. It does not remove it. And if there is no element that it will                                                                        throw exception.
public void push(Object element) :  Push the object specified as the parameter. If stack is full than it will throw exception.
public Object pop()                           :  Remove the element that is there on top of stack. If stack is empty it will throw the exception.

So thats all everyone. Below is some basic operation that I ran and the output of it.

import datastructure.stack.ArrayStack;

public class MainPractise {

	public static void main(String[] args) {		
		
		ArrayStack as = new ArrayStack(10);  // Stack can have at max 10 element
		try{
			System.out.println("Stack size:"+as.size());
			as.push("Nirav"); // push String object in stack
			as.pop(); // pop Nirav out of stack 🙁
			as.push("Nihar");
			String topString = (String)as.top(); // chek out nihar 😛
			System.out.println(topString); /* U will see stubborn nihar string object 
			                                print out bt the object will still be there */
			
			as.pop(); // Now There is no element in stack
			as.pop(); // it will throw exception as stack is empty
		}catch(Exception e){
			System.out.println("Exception message:"+e.getMessage());
		}
		
	}
}

The output of above code is:

Stack size:10
Nihar
Exception message:Stack is Empty

This is it.

You can have above code from GIT.

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

If you have any question mail us on
snippetexample@gmail.com or Post comments or join us on facebook.