# Hackerearth-Cracking the coding interview

## 1.Challenge: Time Complexity: Primality

A *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 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**

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

- 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. - n=5 is only divisible 1 and itself, so we print
`Prime`

on a new line. - 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(); } }

## 2.Challenge:Recursion: Fibonacci Numbers

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

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

**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)); } }

## 3.Challenge:Recursion: Davis’ Staircase

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

**Subtasks**

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:

- 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.
- The second staircase has n=3 steps and he can climb it in any of the four following ways:

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

## 4.Challenge:Bit Manipulation: Lonely Integer

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

**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(); } }

## 5.Challenge:DP: Coin Change

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:

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

## 6.Challenge:Arrays: Left Rotation

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

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

**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; } } }

## 7.Challenge:Arrays: Left Rotation

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

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

- Remove
`d`

and`e`

from`cde`

to get`c`

. - 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(); } }

## 8.Challenge:Hash Tables: Ransom Note

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 *cannot*use 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**

- 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(); } }

## 9.Challenge:Linked Lists: Detect a Cycle

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.

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

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

**Sample Output**

```
0
1
```

**Explanation**

- The first list has no cycle, so we return
*false*and the hidden code checker prints 0 to stdout. - 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; } }

## 10.Challenge:Stacks: Balanced Brackets

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

, 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**

- The string
`{[()]}`

meets both criteria for being a balanced string, so we print`YES`

on a new line. - 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. - 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(); } }

## Responses