HACKEREARTH-CRACKING THE CODING INTERVIEW

prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given p integers, determine the primality of each integer and print whether it is Prime or Not prime on a new line.

Note: If possible, try to come up with an KodNest 1 primality algorithm, or see what sort of optimizations you can come up with for an O(n) algorithm. Be sure to check out the Editorial after submitting your code!

Function Description

Complete the primality function in the editor below. It should return Prime if n is prime, or Not prime.

primality has the following parameter(s):

  • n: an integer to test for primality

Input Format

The first line contains an integer, p, denoting the number of integers to check for primality. 
Each of the p subsequent lines contains an integer, n, the number you must test for primality.

Constraints

KodNest 1.2

Output Format

For each integer, print whether n is Prime or Not prime on a new line.

Sample Input

3
12
5
7

Sample Output

Not prime
Prime
Prime

Explanation

We check the following p=3 integers for primality:

  1. n=12 is divisible by numbers other than 1 and itself (i.e.: 2,3 ,4 ,6 ), so we print Not prime on a new line.
  2. n=5 is only divisible 1 and itself, so we print Prime on a new line.
  3. n=7 is only divisible 1 and itself, so we print Prime on a new line.

Solution:

public class Primality {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int p = in.nextInt();
		boolean found = false;
		for (int a0 = 0; a0 < p; a0++) {
			int n = in.nextInt();
			if (n == 1) {
				System.out.println("Not prime");
			} else {
				for (int i = 2; i <= Math.sqrt(n); i++) {
					if (n % i == 0) {
						found = true;
						break;
					}
				}
				System.out.println(found ? "Not prime" : "Prime");
				found = false;
			}
		}
		in.close();
	}
}

The Fibonacci Sequence

The Fibonacci sequence appears in nature all around us, in the arrangement of seeds in a sunflower and the spiral of a nautilus for example.

The Fibonacci sequence begins with fibonacci(0)=0 and fibonacci(1)=1 as its first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements.

Programmatically:

KodNest 2

Given n, return the nth number in the sequence.

As an example, n=5. The Fibonacci sequence to 6 is fs=[0,1,1,2,3,5,8]. With zero-based indexing, fs[5]=5.

Function Description

Complete the recursive function fibonacci in the editor below. It must return the nth element in the Fibonacci sequence.

fibonacci has the following parameter(s):

  • n: the integer index of the sequence to return

Input Format

The input line contains a single integer, n.

Constraints

KodNest 2.1

Output Format

Locked stub code in the editor prints the integer value returned by the Fibonacci function.

Sample Input

3  

Sample Output

2

Solution:

public class FibonacciNumber {

	/**
	 * This method is used to generate the nth fibonacci number
	 * 
	 * @param n
	 * @return a nth fibonacci number
	 */
	public static int fibonacci(int n) {
		if (n == 0 || n == 1)
			return n;
		return fibonacci(n - 1) + fibonacci(n - 2);

	}

	/**
	 * Unit tests the {@code FibonacciNumber}
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		scanner.close();
		System.out.println(fibonacci(n));
	}
}

Davis has a number of staircases in his house and he likes to climb each staircase 1, 2, or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase.

Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase, module (10^9) +7 on a new line.

For example, there is s=1 staircase in the house that is n=5 steps high. Davis can step on the following sequences of steps:

1 1 1 1 1
1 1 1 2
1 1 2 1 
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2

There are 13 possible ways he can take these 5 steps. 13%1000000007=13

Function Description

Complete the stepPerms function in the editor below. It should recursively calculate and return the integer number of ways Davis can climb the staircase, modulo 10000000007.

stepPerms has the following parameter(s):

  • n: an integer, the number of stairs in the staircase

Input Format

The first line contains a single integer, s, the number of staircases in his house. 
Each of the following s lines contains a single integer, n, the height of staircase i.

Constraints

KodNest 3

Subtasks

KodNest 3.1 of the maximum score.

Output Format

For each staircase, return the number of ways Davis can climb it as an integer.

Sample Input

3
1
3
7

Sample Output

1
4
44

Explanation

Let’s calculate the number of ways of climbing the first two of the Davis’ s=3 staircases:

  1. The first staircase only has n=1 step, so there is only one way for him to climb it (i.e., by jumping 1 step). Thus, we print 1 on a new line.
  2. The second staircase has n=3 steps and he can climb it in any of the four following ways: 

KodNest 3.3

Thus, we print 4 on a new line.

Solution:

import java.util.Scanner;
public class DavisStaircase {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int s = in.nextInt();

		for (int a0 = 0; a0 < s; a0++) {
			int n = in.nextInt();
			if (n < 2) {
				System.out.println(n);
			} else {
				int a[] = new int[n + 1];
				a[1] = 1;
				a[2] = 2;
				a[3] = 4;
				for (int i = 4; i < n; i++) {
					a[i] = a[i - 1] + a[i - 2] + a[i - 3];
				}
				System.out.println(printNoOfStaircases(n, a));
			}
		}
		in.close();
	}

	
	private static int printNoOfStaircases(int n, int a[]) {
		if (n <= 2)
			return a[n];
		if (n == 3)
			return a[n];

		return a[n] = a[n - 1] + a[n - 2] + a[n - 3];
	}
}

Consider an array of integers where all but one of the integers occur in pairs. In other words, every element occurs exactly twice except for one unique element. Find the unique element.

For example, given the array arr=[1,1,2,3,2], you would return 3.

Function Description

Complete the findLonely function in the editor below. It should return the unique integer in arr.

findLonely has the following parameter(s):

  • arr: an array of integers

Input Format

The first line contains a single integer, n, denoting the number of integers in arr
The second line contains n space-separated integers, each an element, arr[i].

Constraints

KodNest 4

Output Format

Print the unique number in arr on a new line.

Sample Input 0

1
1

Sample Output 0

1

Explanation 0 
The array only contains a single 1, so we print 1 as our answer.

Sample Input 1

3
1 1 2

Sample Output 1

2

Explanation 1 
We have two 1‘s and one 2. We print 2, because that’s the only unique element in the array.

Sample Input 2

5
0 0 1 2 1

Sample Output 2

2

Explanation 2 
We have two 0‘s, two 1‘s, and one 2. We print 2, because that’s the only unique element in the array.

 
Solution:
import java.util.Scanner;

public class LonelyInteger {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int res = 0;
		for (int i = 0; i < n; i++) {
			res ^= sc.nextInt();
		}
		System.out.println(res);
		sc.close();
	}
}

Given a number of dollars and an array of denominations of coins, determine how many ways you can make change. For example, making change for n=10 dollars from coin denominations coins=[1,2,5,10], there are  15 ways to make change:

1 1 1 1 1 1 1 1 1 1 1 	1 1 5 5			1 1 1 1 1 1 1 5
1 1 1 1 1 1 1 1 1 1 2	2 5 5
1 1 1 1 1 1 1 1 2 2	1 1 10
1 1 1 1 1 1 2 2 2	2 10
1 1 1 1 2 2 2 2		2 2 2 1 5
1 1 2 2 2 2 2       	2 2 1 1 1 5
2 2 2 2 2 2          	2 1 1 1 1 1 5

Hints:

  • You can solve this problem recursively, but you must optimize your solution to eliminate overlapping subproblems using Dynamic Programming if you wish to pass all test cases. More specifically, think of ways to store the checked solutions and use the stored values to avoid repeatedly calculating the same values.
  • Think about the degenerate cases:
    • How many ways can you make change for 0 dollars?
    • How many ways can you make change for less than 0 dollars if you have no coins?
  • If you are having trouble defining the storage for your precomputed values, then think about it in terms of the base case (n=0).

Function Description

Complete the function makeChange in the editor below. It should return the integer representing the number of ways change can be made.

makeChange has the following parameter(s):

  • n: an integer, the amount to change
  • coins: an array of integers representing coin denominations

Input Format

The first line contains two space-separated integers, n and m, the amount to make change for and the number of denominations of coin. 
The second line contains m space-separated integers describing the denominations of each coins(i).

Constraints

  • The list of coins contains m distinct integers where each integer denotes the dollar value of a coin available in an infinite quantity.

Output Format

Print a single integer denoting the number of ways we can make change for n dollars using an infinite supply of our m types of coins.

Sample Input 0

4 3
1 2 3 

Sample Output 0

4

Explanation 0 
For  and  there are four solutions:

KodNest 4.1

Thus, we print 4 on a new line.

Solution:
import java.util.HashMap;
import java.util.Scanner;

public class DPCoinChange {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int coins[] = new int[m];
		for (int coins_i = 0; coins_i < m; coins_i++) {
			coins[coins_i] = in.nextInt();
		}
//	        approach1(n, coins);
//	        approach2(n, coins);
		approach3(n, coins);
//	        approach4(n, coins);
		in.close();
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach4(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecursionWithMemo2(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach3(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingDP(coins, n);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach2(int n, int[] coins) {
		long memo[][] = new long[n + 1][coins.length + 1];
		memo[0][0] = 1;
		long result = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, 0, memo);
		System.out.println(result);
	}

	/**
	 * @param n
	 * @param coins
	 */
	private static void approach1(int n, int[] coins) {
		long result = noOfWaysToGetChangeUsingRecusion(coins, n, 0);
		System.out.println(result);
	}

	/**
	 * method1 with recursion
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecusion(int[] coins, int n, int index) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		return noOfWaysToGetChangeUsingRecusion(coins, n - coins[index], index)
				+ noOfWaysToGetChangeUsingRecusion(coins, n, index + 1);
	}

	/**
	 * method2 with recursion with memorization
	 * 
	 * @param coins
	 * @param n
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingRecursionWithMemo(int[] coins, int n, int index, long[][] memo) {
		if (n == 0)
			return 1;
		if (n < 0 || index >= coins.length)
			return 0;
		if (memo[n][index] != 0)
			return memo[n][index];
		return memo[n][index] = noOfWaysToGetChangeUsingRecursionWithMemo(coins, n - coins[index], index, memo)
				+ noOfWaysToGetChangeUsingRecursionWithMemo(coins, n, index + 1, memo);
	}

	
	private static long noOfWaysToGetChangeUsingRecursionWithMemo2(int[] coins, int n) {
		return makeChange(coins, n, 0, new HashMap<String, Long>());
	}

	private static long makeChange(int[] coins, int money, int index, HashMap<String, Long> memo) {
		if (money == 0)
			return 1;
		if (index >= coins.length)
			return 0;

		String key = money + "-" + index;
		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		int amountWithCoin = 0;
		long ways = 0;
		while (amountWithCoin <= money) {
			int remaining = money - amountWithCoin;
			ways += makeChange(coins, remaining, index + 1, memo);
			amountWithCoin += coins[index];
		}
		memo.put(key, ways);
		return ways;
	}

	/**
	 * method4 using dynamic programming approach
	 * 
	 * @param coins
	 * @param n
	 * @param i
	 * @return
	 */
	private static long noOfWaysToGetChangeUsingDP(int[] coins, int n) {
		long dp[] = new long[n + 1];
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= n; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[n];
	}
}

left rotation operation on an array shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2].

Given an array a of n integers and a number, d, perform d left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

Function Description

Complete the function rotLeft in the editor below. It should return the resulting array of integers.

rotLeft has the following parameter(s):

  • An array of integers .
  • An integer , the number of rotations.

Input Format

The first line contains two space-separated integers n and d, the size of a and the number of left rotations you must perform. 
The second line contains n space-separated integers a[i].

Constraints

KodNest 6.1

 

Output Format

Print a single line of n space-separated integers denoting the final state of the array after performing d left rotations.

Sample Input

5 4
1 2 3 4 5

Sample Output

5 1 2 3 4

Explanation

When we perform  left rotations, the array undergoes the following sequence of changes:

KodNest 6.2
Solution:
import java.util.Scanner;

public class LeftRotation {
	public static void main(String[] args) {
		/*
		 * Enter your code here. Read input from STDIN. Print output to STDOUT. Your
		 * class should be named Solution.
		 */

		Scanner sc = new Scanner(System.in);
		int arraySize = sc.nextInt();
		int key = sc.nextInt();
		int a[] = new int[arraySize];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		leftRotate(a, 0, key - 1);
		leftRotate(a, key, arraySize - 1);
		leftRotate(a, 0, arraySize - 1);

		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		sc.close();
	}

	static void leftRotate(int a[], int start, int end) {
		while (start < end) {
			int temp = a[start];
			a[start++] = a[end];
			a[end--] = temp;

		}

	}
}

Alice is taking a cryptography class and finding anagrams to be very useful. We consider two strings to be anagrams of each other if the first string’s letters can be rearranged to form the second string. In other words, both strings must contain the same exact letters in the same exact frequency For example, bacdc and dcbac are anagrams, but bacdc and dcbad are not.

Alice decides on an encryption scheme involving two large strings where encryption is dependent on the minimum number of character deletions required to make the two strings anagrams. Can you help her find this number?

Given two strings, a and b, that may or may not be of the same length, determine the minimum number of character deletions required to make a and b anagrams. Any characters can be deleted from either of the strings.

For example, if a=cde and b=dcf, we can delete e from string a and f from string b so that both remaining strings are cd and dc which are anagrams.

Function Description

Complete the makeAnagram function in the editor below. It must return an integer representing the minimum total characters that must be deleted to make the strings anagrams.

makeAnagram has the following parameter(s):

  • a: a string
  • b: a string

Input Format

The first line contains a single string,a 
The second line contains a single string,b .

Constraints

KodNest 7 1

  • The strings  a and b consist of lowercase English alphabetic letters ascii[a-z].

Output Format

Print a single integer denoting the number of characters you must delete to make the two strings anagrams of each other.

Sample Input

cde
abc

Sample Output

4

Explanation

We delete the following characters from our two strings to turn them into anagrams of each other:

  1. Remove d and e from cde to get c.
  2. Remove a and b from abc to get c.

We must delete 4 characters to make both strings anagrams, so we print 4 on a new line.

Solution:

import java.util.HashMap;
import java.util.Scanner;

public class MakingAnagrams {
	public static int numberNeeded(String first, String second) {
		HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
		int length = 0;
		for (int i = 0; i < first.length(); i++) {
			char c = first.charAt(i);
			if (hmap.containsKey(c)) {
				hmap.put(c, hmap.get(c) + 1);
			} else {
				hmap.put(c, 1);
			}
		}

		for (int i = 0; i < second.length(); i++) {
			char c = second.charAt(i);
			if (hmap.containsKey(c) && hmap.get(c) != 0) {
				hmap.put(c, hmap.get(c) - 1);
				length += 2;
			}
		}
		return (first.length() + second.length() - length);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String a = in.next();
		String b = in.next();
		System.out.println(numberNeeded(a, b));
		in.close();
	}
}

Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use only whole words available in the magazine. He cannotuse substrings or concatenation to create the words he needs.

Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

For example, the note is “Attack at dawn”. The magazine contains only “attack at dawn”. The magazine has all the right words, but there’s a case mismatch. The answer is NO.

Function Description

Complete the checkMagazine function in the editor below. It must print YES if the note can be formed using the magazine, or NO.

checkMagazine has the following parameters:

  • magazine: an array of strings, each a word in the magazine
  • note: an array of strings, each a word in the ransom note

Input Format

The first line contains two space-separated integers, m and n, the numbers of words in the magazine and note the .. 
The second line contains m space-separated strings, each magazine(i). 
The third line contains n space-separated strings, each note(i).

Constraints

KodNest 8

  • Each word consists of English alphabetic letters (i.e., a to z and A to Z).

Output Format

Print Yes if he can use the magazine to create an untraceable replica of his ransom note. Otherwise, print No.

Sample Input 0

6 4
give me one grand today night
give one grand today

Sample Output 0

Yes

Sample Input 1

6 5
two times three is not four
two times two is four

Sample Output 1

No

Explanation 1

‘two’ only occurs once in the magazine.

Sample Input 2

7 4
ive got a lovely bunch of coconuts
ive got some coconuts

Sample Output 2

No

Explanation 2

Harold’s magazine is missing the word some.

Solution:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class HashTablesRansomNote {

	public static boolean isMessageReplicable(String[] magazine, String[] ransom) {
		Map<String, Integer> magazineWords = new HashMap<String, Integer>();

		for (int i = 0; i < magazine.length; i++) {
			Integer wordCount = magazineWords.get(magazine[i]);
			if (wordCount == null) {
				magazineWords.put(magazine[i], 1);
			} else {
				magazineWords.put(magazine[i], wordCount + 1);
			}
		}

		for (int i = 0; i < ransom.length; i++) {
			Integer wordCount = magazineWords.get(ransom[i]);
			if (wordCount == null || wordCount == 0) {
				return false;
			} else {
				magazineWords.put(ransom[i], wordCount - 1);
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		String magazine[] = new String[m];
		for (int magazine_i = 0; magazine_i < m; magazine_i++) {
			magazine[magazine_i] = in.next();
		}
		String ransom[] = new String[n];
		for (int ransom_i = 0; ransom_i < n; ransom_i++) {
			ransom[ransom_i] = in.next();
		}
		String result = isMessageReplicable(magazine, ransom) ? "Yes" : "No";
		System.out.println(result);
		in.close();
	}
}

A linked list is said to contain a cycle if any node is visited more than once while traversing the list. For example, in the following graph there is a cycle formed when node 5 points back to node 3.

image

Function Description

Complete the function has_cycle in the editor below. It must return a boolean true if the graph contains a cycle, or false.

has_cycle has the following parameter(s):

  • head: a pointer to a Node object that points to the head of a linked list.

Note: If the list is empty,  head will be null.

Input Format

There is no input for this challenge. A random linked list is generated at runtime and passed to your function.

Constraints

KodNest 9 1

Output Format

If the list contains a cycle, your function must return true. If the list does not contain a cycle, it must return false. The binary integer corresponding to the boolean value returned by your function is printed to stdout by our hidden code checker.

Sample Input

The following linked lists are passed as arguments to your function:

image

image

Sample Output

0
1

Explanation

  1. The first list has no cycle, so we return false and the hidden code checker prints 0 to stdout.
  2. The second list has a cycle, so we return true and the hidden code checker prints 1 to stdout.
Solution:
public class DetectACycle {
	class Node {
		int data;
		Node next;
	}

	boolean hasCycle(Node head) {
		Node p1 = head, p2 = head;

		while (p1 != null && p1.next != null && p2 != null) {
			p1 = p1.next;
			p2 = p2.next.next;
			{
				if (p1 == p2)
					return true;

			}

		}
		return false;

	}

}

A bracket is considered to be any one of the following characters: (){}[, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., ([, or {) occurs to the left of a closing bracket (i.e., )], or }of the exact same type. There are three types of matched pairs of brackets: []{}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

Some examples of balanced brackets are []{}()[({})]{}() and ({(){}[]})[].

By this logic, we say a sequence of brackets is considered to be balanced if the following conditions are met:

  • It contains no unmatched brackets.
  • The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given n strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, print YES on a new line; otherwise, print NO on a new line.

Input Format

The first line contains a single integer, n, denoting the number of strings. 
Each line i of the n subsequent lines consists of a single string, s, denoting a sequence of brackets.

Constraints

KodNest 10 1, where  is the length of the sequence.

  • Each character in the sequence will be a bracket (i.e., {}()[, and ]).

Output Format

For each string, print whether or not the string of brackets is balanced on a new line. If the brackets are balanced, print YES; otherwise, print NO.

Sample Input

3
{[()]}
{[(])}
{{[[(())]]}}

Sample Output

YES
NO
YES

Explanation

  1. The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.
  2. The string {[(])} is not balanced, because the brackets enclosed by the matched pairs [(] and (]) are not balanced. Thus, we print NO on a new line.
  3. The string {{[[(())]]}} meets both criteria for being a balanced string, so we print YES on a new line.
Solution:
import java.util.Scanner;
import java.util.Stack;

public class BalancedBrackets {
	private static String matchParenthisis(String str) {
		Stack<Character> st = new Stack<Character>();
		char[] ch = str.toCharArray();
		for (char c : ch) {

			if (c == '{' || c == '[' || c == '(') {
				st.push(c);
			} else {

				if (c == ']' && !st.isEmpty() && st.pop() == '[') {
					continue;

				} else if (c == '}' && !st.isEmpty() && st.pop() == '{') {
					continue;
				} else if (c == ')' && !st.isEmpty() && st.pop() == '(') {
					continue;
				} else {
					return "NO";
				}

			}
		}
		if (!st.isEmpty()) {
			return "NO";
		}

		return "YES";

	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int a0 = 0; a0 < t; a0++) {
			String s = in.next();
			System.out.println(matchParenthisis(s));
		}
		in.close();
	}
}

Related Articles

Core Java

1. What are primitive types in Java ? byte, short, int, long, float, double, char, boolean… 2. What are tokens? Name the 5 types of tokens available in Java with an example…

Hackerearth-Algorithm

      1. Challenge: Quicksort 1 – Partition The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running…

JavaScript

Explain event delegation Event delegation is a technique involving adding event listeners to a parent element instead of adding them to the descendant elements. The…

Responses

Your email address will not be published. Required fields are marked *

×