HACKEREARTH-DATA STRUCTURE

1.Challenge : Arrays – DS

An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0 <=i<N ), that can be referenced as A[i] (you may also see it written as Ai).

Given an array, A, N of integers, print each element in reverse order as a single line of space-separated integers.

Note: If you’ve already solved our C++ domain’s Arrays Introduction challenge, you may want to skip this.

Input Format

The first line contains an integer, N(the number of integers in A ).
The second line contains N space-separated integers describing A.

Constraints

1≤N≤10^{^3}
1≤A_i≤10^{^4} Where A_i is the i^th Integer in A

Output Format

Print all N integers in A in reverse order as a single line of space-separated integers.

Sample Input 1

Array: arr1432

4
1 4 3 2

Sample Output 1

2 3 4 1

Solution:

public class ArraysDS {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int arr[] = new int[n];
		for (int arr_i = 0; arr_i < n; arr_i++) {
			arr[arr_i] = in.nextInt();
		}
		for (int arr_i = n - 1; arr_i >= 0; arr_i--) {
			System.out.print(arr[arr_i] + " ");
		}
		in.close();
	}
}

2.Challenge:2D Array – DS

Given a 6*6 2D Array, arr :

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

We define an hourglass in A to be a subset of values with indices falling in this pattern in arr’s graphical representation:

a b c
  d
e f g

There are 16 hourglasses in arr, and an hourglass sum is the sum of an hourglass’ values. Calculate the hourglass sum for every hourglass in arr, then print the maximum hourglass sum.

For example, given the 2D array:

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

We calculate the following 16 hourglass values:

-63, -34, -9, 12, 
-10, 0, 28, 23, 
-27, -11, -2, 10, 
9, 17, 25, 18

Our highest hourglass value is 28 from the hourglass:

0 4 3
  1
8 6 6

Note: If you have already solved the Java domain’s Java 2D Array challenge, you may wish to skip this challenge.

Function Description

Complete the function hourglassSum in the editor below. It should return an integer, the maximum hourglass sum in the array.

hourglassSum has the following parameter(s):

arr: an array of integers

Input Format

Each of the 6 lines of inputs arr[i] contains 6 space-separated integers arr[i][j].

Constraints

Kodnest-2D Array

Output Format

Print the largest (maximum) hourglass sum found in arr.

Sample Input

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

Sample Output

Explanation

arr contains the following hourglasses:

The hourglass with the maximum sum (19) is:

2 4 4
  2
1 2 4

Solution:

import java.util.Scanner;

public class TwoDArrayDS {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int arr[][] = new int[6][6];
		for (int arr_i = 0; arr_i < 6; arr_i++) {
			for (int arr_j = 0; arr_j < 6; arr_j++) {
				arr[arr_i][arr_j] = in.nextInt();
			}
		}

		int maxsum = Integer.MIN_VALUE;
		for (int arr_i = 0; arr_i < 6; arr_i++) {
			for (int arr_j = 0; arr_j < 6; arr_j++) {

				if ((arr_j + 2) < 6 && (arr_i + 2) < 6) {
					int sum = arr[arr_i][arr_j] + arr[arr_i][arr_j + 1] + arr[arr_i][arr_j + 2]
							+ arr[arr_i + 1][arr_j + 1] + arr[arr_i + 2][arr_j] + arr[arr_i + 2][arr_j + 1]
							+ arr[arr_i + 2][arr_j + 2];
					if (sum > maxsum) {
						maxsum = sum;
					}
				}

			}
		}
		System.out.println(maxsum);
		in.close();
	}

}

3.Challenge: Dynamic Array

Create a lis seqList, of N empty sequences. where each sequence is indexed from 0 to N – 1. The elements within each of the N sequences also use 0-indexing.
Create an integer.lastAnswer.and initialize it to 0.
The 2 types of queries that can be performed on your list of sequences (seqList) are described below:
1. Query: lx y
  1. Find the sequence,seq, at index ( (x EB lastAnswer) 3 N ) in seqList.
  2. Append integer y to sequence seq.
2. Query: 2 x y
  1. Find the sequence,seq, at index ( (x EB lastAnswer) 3 N ) in seqList.
  2. Find the value of element y 3size in seq (where size is the size of seq) and assignit to last Answer.
  3. Print the new value of lastAnswe1·on a new line

Task

Given N , Q, and Q queries,execute each query.

Note: is the bitwise XOR operation,which corresponds to the ‘operator in most languages. Learn more about it on Wikipedia.

Input Format

The first line contains two space-separated integers, N (the number of sequences) and Q (the number of queries), respectively. Each of the Q subsequent lines contains a query in the format defined above

Constraints

Output Format

For each cype 2 query,print the updated value of lastArt.swer on a new line.

Sample Input

Sample Output

7
3

Explanation

Initial Values:

N = 2

lastAnswer = 0

So = []

S1= []

Query O: Append 5 to sequence ( (0 ⊕ 0) %2 ) = 0.

lastAnswer = 0

So = [5]

S1= []

Query 1:Append 7 to sequence ( (1 ⊕ 0) %2 ) = 1.

So = [5]

S1 =[7]

Query 2: Append 3to sequence ( (0 ⊕ 0) %2 ) = 0.

lastAnswer = 0

So = [5,3]

S1 = [7]

Query 3: Assign the value at index 0 of sequence ( (1 ⊕ 0) %2 ) = 1to last Answe1′.print lastAnswe1·. lastAnswer = 7

So = [5,3]

S1 = [7]

Query 4: Assign the value at index of sequence ( (1 ⊕ 7) %2 ) to lastAnswe1, printlastAnswe1 .
lastAnswe1=3
S0= [5, 3]
S1 = [7]

Solution:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class DynamicArray {

	List<Integer> list = new ArrayList<Integer>();
	List<List<Integer>> seqList = new ArrayList<List<Integer>>();
	int lastAns;

	public DynamicArray(int N) {
		for (int i = 0; i < N; i++) {
			list = new ArrayList<Integer>();
			seqList.add(list);
		}
	}

	void putValue(int x, int y, int N) {
		int rowIndex = (x ^ lastAns) % N;
		seqList.get(rowIndex).add(y);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		DynamicArray da = new DynamicArray(N);
		for (int i = 0; i < Q; i++) {
			int queryType = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (queryType == 1) {
				da.putValue(x, y, N);
			} else {
				da.getValue(x, y, N);
			}

		}
		sc.close();
	}

	private void getValue(int x, int y, int N) {
		int colIndex = 0;
		int rowIndex = (x ^ lastAns) % N;
		colIndex = y % seqList.get(rowIndex).size();
		lastAns = seqList.get(rowIndex).get(colIndex);
		System.out.println(lastAns);
	}

}

4.Challenge- Left Rotation

A left rotation operation on an array of size n 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 of integers and a number,d , perform d left rotations on the array. Then print the updated array as a single line of space-separated integers.

Input Format

The first line contains two space-separated integers denoting the respective values of n (the number of integers) and d (the number of left rotations you must perform).
The second line contains n space-separated integers describing the respective elements of the array’s initial state.

Constraints

KodNest 7

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 d=4 left rotations, the array undergoes the following sequence of changes:

Thus, we print the array’s final state as a single line of space-separated values, which is 5 1 2 3 4.

5.Challenge: Left Rotation

Consider an array of numeric strings where each string is a positive number with anywhere from to digits. Sort the array’s elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line.

Function Description

Complete the bigSorting function in the editor below. It should return the sorted string array.

bigSorting has the following parameter(s):

unsorted: an unsorted array of integers as strings

Input Format

The first line contains an integer, n , denoting the number of strings in unsorted .
Each of the n subsequent lines contains an integer string unsorted[i].

Constraints

1≤N≤2*10^{^5}
Each string is guaranteed to represent a positive integer without leading zeros.
The total number of digits across all strings in unsorted is between 1 and 10^{^6}
(inclusive).

Output Format

Print each element of the sorted array on a new line.

Sample Input 0

6
31415926535897932384626433832795
1
3
10
3
5

Sample Output 0

1
3
3
5
10
31415926535897932384626433832795

Explanation 0

The initial array of strings is . When we order each string by the real-world integer value it represents, we get:

We then print each value on a new line, from smallest to largest.

Sample Input 1

8
1
2
100
12303479849857341718340192371
3084193741082937
3084193741082938
111
200

Sample Output 1

1
2
100
111
200
3084193741082937
3084193741082938
12303479849857341718340192371

Solution:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BigSorting {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String[] unsorted = new String[n];
		for (int unsorted_i = 0; unsorted_i < n; unsorted_i++) {
			unsorted[unsorted_i] = in.next();
		}

		Arrays.sort(unsorted, new Comparator<String>() {

			public int compare(String s1, String s2) {
				return compareStrings(s1, s2);
			}
		});
		printArray(unsorted);
		in.close();
	}

	private static int compareStrings(String s1, String s2) {
		if (s1.length() < s2.length()) {
			return -1;
		} else if (s1.length() > s2.length()) {
			return 1;
		}
		for (int k = 0; k < s1.length(); k++) {
			if ((int) s1.charAt(k) < (int) s2.charAt(k))
				return -1;
			if ((int) s1.charAt(k) > (int) s2.charAt(k))
				return 1;

		}
		return 0;

	}

	private static void printArray(String[] unsorted) {

		for (String string : unsorted) {
			System.out.println(string);
		}

	}

}

6.Challenge-Sparse Arrays

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings.

For example, given input Strings=[‘ab’,’ab’,’abc’]and queries =[‘ab’,’abc’,’bc’], we find 2 instances of ‘ab’, 1 of ‘abc’ and 0 of ‘bc‘. For each query, we add an element to our return array, results=[2,1,0] .

Function Description

Complete the function matchingStrings in the editor below. The function must return an array of integers representing the frequency of occurrence of each query string in strings.

matchingStrings has the following parameters:

strings – an array of strings to search
queries – an array of query strings

Input Format

The first line contains and integer n, the size of strings.
Each of the next n lines contains a string strings[i].
The next line containsq , the size of queries .
Each of the next q lines contains a string q[i].

Constraints

KodNest 9

Output Format

Return an integer array of the results of all queries in order.

Sample Input 1

Array: strings [aba baba aba xzxb]

Array: queries [aba xzxb ab]

4
aba
baba
aba
xzxb
3
aba
xzxb
ab

Sample Output 1

2
1
0

Explanation 1

Here, “aba” occurs twice, in the first and third string. The string “xzxb” occurs once in the fourth string, and “ab” does not occur at all.

Sample Input 2

Array: strings [def de fgh] Array: queries[de lmn fgh]

3
def
de
fgh
3
de
lmn
fgh

Sample Output 2

1
0
1

Solution:

import java.util.Scanner;

public class SparseArrays {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int noOfStrings = sc.nextInt();

		String str[] = new String[noOfStrings];

		for (int i = 0; i < noOfStrings; i++) {
			str[i] = sc.next();
		}
		int queries = sc.nextInt();
		String strQ[] = new String[queries];

		for (int i = 0; i < queries; i++) {
			strQ[i] = sc.next();
		}
		int counter = 0;
		for (int i = 0; i < queries; i++) {
			for (int j = 0; j < noOfStrings; j++) {
				if (str[j].equals(strQ[i])) {
					counter++;
				}
			}
			System.out.println(counter);
			counter = 0;
		}
		sc.close();
	}

}

7.Challenge-Array Manipulation

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.

For example, the length of your array of zeros n=10. Your list of queries is as follows:

Add the values of k between the indices a and b inclusive:

index->	 1 2 3  4  5 6 7 8 9 10
	[0,0,0, 0, 0,0,0,0,0, 0]
	[3,3,3, 3, 3,0,0,0,0, 0]
	[3,3,3,10,10,7,7,7,0, 0]
	[3,3,3,10,10,8,8,8,1, 0]

The largest value is 10 after all operations are performed.

Function Description

Complete the function arrayManipulation in the editor below. It must return an integer, the maximum value in the resulting array.

arrayManipulation has the following parameters:

n – the number of elements in your array
queries – a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.

Input Format

The first line contains two space-separated integers m and n, the size of the array and the number of operations.
Each of the next m lines contains three space-separated integers a , b and k, the left index, right index and summand.

Constraints

KodNest 10

Output Format

Return the integer maximum value in the finished array.

Sample Input

Sample Output

Explanation

After the first update list will be 100 100 0 0 0.
After the second update list will be 100 200 100 100 100.
After the third update list will be 100 200 200 200 100.
The required answer will be 200.

Solution:

import java.util.Scanner;

ublic class ArrayManipulation {

	static long arrayManipulation(int n, int[][] queries) {

		long outputArray[] = new long[n + 2];
		for (int i = 0; i < queries.length; i++) {
			int a = queries[i][0];
			int b = queries[i][1];
			int k = queries[i][2];
			outputArray[a] += k;
			outputArray[b+1] -= k;
		}
		long max = getMax(outputArray);
		return max;
	}

	private static long getMax(long[] inputArray) {
		long max = Long.MIN_VALUE;
		long sum = 0;
		for (int i = 0; i < inputArray.length; i++) {
			sum += inputArray[i];
			max = Math.max(max, sum);
		}
		return max;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int queries[][] = new int[m][3];

		for (int i = 0; i < m; i++) {
			queries[i][0] = sc.nextInt();
			queries[i][1] = sc.nextInt();
			queries[i][2] = sc.nextInt();
		}
		long max = arrayManipulation(n, queries);
		System.out.println(max);
		sc.close();
	}
}

8.Challenge-Maximum Element

You have an empty sequence, and you will be given queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

Input Format

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints
KodNest 11
Output Format

For each type 3 query, print the maximum element in the stack on a new line.

Sample Input

Sample Output

26
91

Solution:

import java.util.Scanner;

public class MaximumElement {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a[] = new int[N];
		int b[] = new int[N];
		int top = -1;
		int bTop = -1;

		for (int i = 0; i < N; i++) {
			int op = sc.nextInt();
			switch (op) {
			case 1:
				int item = sc.nextInt();
				a[++top] = item;
				if (bTop >= 0) {
					if (item >= b[bTop])
						b[++bTop] = item;
				} else {
					b[++bTop] = item;
				}

				break;
			case 2:
				item = a[top];
				a[top--] = -1;
				if (item == b[bTop])
					b[bTop--] = -1;
				break;

			case 3:

				System.out.println(b[bTop]);
				break;
			}
		}
		sc.close();
	}
}

9.Challenge-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, ].

By this logic, we say a sequence of brackets is 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, return YES. Otherwise, return NO.

Function Description

Complete the function isBalanced in the editor below. It must return a string: YES if the sequence is balanced or NO if it is not.

isBalanced has the following parameter(s):

s: a string of brackets

Input Format

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

Constraints

1≤N≤10^{^3}

1≤|s|≤10^{^3}, where |s| is the length of the sequence.

All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or 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 pair { and } are not balanced: [(]).

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

10. Challenge-Equal Stacks

You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times.

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they’re all the same height, then print the height. The removals must be performed in such a way as to maximize the height.

Note: An empty stack is still a stack.

Input Format

The first line contains three space-separated integers,n1 ,n2 , and n3 , describing the respective number of cylinders in stacks 1, 2, and 3. The subsequent lines describe the respective heights of each cylinder in a stack from top to bottom:

The second line contains n1 space-separated integers describing the cylinder heights in stack 1. The first element is the top of the stack.
The third line contains n2 space-separated integers describing the cylinder heights in stack 2. The first element is the top of the stack.
The fourth line contains n3 space-separated integers describing the cylinder heights in stack 3. The first element is the top of the stack.

Constraints

KodNest 12.1

Output Format

Print a single integer denoting the maximum height at which all stacks will be of equal height.

Sample Input

Sample Output

Explanation

Initially, the stacks look like this:

initial stacks

Observe that the three stacks are not all the same height. To make all stacks of equal height, we remove the first cylinder from stacks 1 and 2, and then remove the top two cylinders from stack 3(shown below).

modified stacks

As a result, the stacks undergo the following change in height:

KodNest 12.2

All three stacks now have hieght=5. Thus, we print 5 as our answer.

Solution:

import java.util.Scanner;
import java.util.Stack;

public class EqualStacks {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n1 = in.nextInt();
		int n2 = in.nextInt();
		int n3 = in.nextInt();
		int h1[] = new int[n1];
		for (int h1_i = 0; h1_i < n1; h1_i++) {
			h1[h1_i] = in.nextInt();
		}
		int h2[] = new int[n2];
		for (int h2_i = 0; h2_i < n2; h2_i++) {
			h2[h2_i] = in.nextInt();
		}
		int h3[] = new int[n3];
		for (int h3_i = 0; h3_i < n3; h3_i++) {
			h3[h3_i] = in.nextInt();
		}

		Stack<Long> st1 = new Stack<Long>();
		Stack<Long> st2 = new Stack<Long>();
		Stack<Long> st3 = new Stack<Long>();
		long sum1 = 0, sum2 = 0, sum3 = 0;
		for (int i = h1.length - 1; i >= 0; i--) {
			sum1 += h1[i];
			st1.push(sum1);
		}
		for (int i = h2.length - 1; i >= 0; i--) {
			sum2 += h2[i];
			st2.push(sum2);
		}
		for (int i = h3.length - 1; i >= 0; i--) {
			sum3 += h3[i];
			st3.push(sum3);
		}

		boolean found = false;
		if (n1 <= n2 && n1 <= n3) {
			while (!st1.isEmpty()) {
				long top = st1.pop();
				if (st2.contains(top) && st3.contains(top)) {
					System.out.println(top);
					found = true;
					break;
				}
			}

		} else if (n2 <= n3 && n2 <= n1) {
			while (!st2.isEmpty()) {
				long top = st2.pop();
				if (st1.contains(top) && st3.contains(top)) {
					System.out.println(top);
					found = true;
					break;
				}
			}

		} else if (n3 <= n1 && n3 <= n2) {
			while (!st3.isEmpty()) {
				long top = st3.pop();
				if (st2.contains(top) && st1.contains(top)) {
					System.out.println(top);
					found = true;
					break;
				}
			}
		}
		if (!found) {
			System.out.println("0");
		}
		in.close();
	}
}

11.Challenge-Largest Rectangle

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join k adjacent buildings, they will form a solid rectangle of area .

For example, the heights array h=[3,2,3]. A rectangle of height h=2 and length k=3 can be constructed within the boundaries. The area formed is h.k=3.2=6.

Function Description

Complete the function largestRectangle int the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.

largestRectangle has the following parameter(s):

h: an array of integers representing building heights

Input Format

The first line contains n, the number of buildings.
The second line contains n space-separated integers, each representing the height of a building.

Constraints

Output Format

Print a long integer representing the maximum area of rectangle formed.

Sample Input

5
1 2 3 4 5

Sample Output

Explanation

An illustration of the test case follows.

12.Challenge-Tree: Preorder Traversal

Complete the preOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s preorder traversal as a single line of space-separated values.

Input Format

Our hidden tester code passes the root node of a binary tree to your preOrder function.

Constraints

1≤ Nodes in the tree≤500

Output Format

Print the tree’s preorder traversal as a single line of space-separated values.

Sample Input

Sample Output

1 2 5 3 4 6

13.Challenge-Tree: Inorder Traversal

Complete the inOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s inorder traversal as a single line of space-separated values.

Input Format

Our hidden tester code passes the root node of a binary tree to your inOrder function.

Constraints

1≤ Nodes in the tree≤500

Output Format

Print the tree’s inorder traversal as a single line of space-separated values.
Sample Input
     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  
Sample Output

1 2 3 4 5 6

Solution:
import java.util.Stack;

public class InorderTraversal {

	class Node {
		int data;
		Node left;
		Node right;
	}

	void inOrder(Node root) {
		Stack<Node> st = new Stack<Node>();
		while (true) {
			while (root != null) {
				st.push(root);
				root = root.left;
			}
			if (st.empty())
				return;
			root = st.pop();
			System.out.print(root.data + " ");
			root = root.right;
		}
	}
}

14.Challenge-Tree: Postorder Traversal

Complete the postOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree’s postorder traversal as a single line of space-separated values.

Input Format

Our hidden tester code passes the root node of a binary tree to your postOrder function.

Constraints

1≤ Nodes in the tree≤500

Output Format

Print the tree’s postorder traversal as a single line of space-separated values.

Sample Input

Sample Output

4 3 6 5 2 1

Solution:

public class PostorderTraversal {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void postOrder(Node root) {
		if (root != null) {
			postOrder(root.left);
			postOrder(root.right);
			System.out.print(root.data + " ");

		}
	}
}

15.Challenge-Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree’s root and its furthest leaf. For example, the following binary tree is of height :

Function Description

Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer.

getHeight or height has the following parameter(s):

root: a reference to the root of a binary tree.

Note -The Height of binary tree with single node is taken as zero.

Input Format

The first line contains an integer n, the number of nodes in the tree.
Next line contains n space separated integer where i th integer denotes node[i].data.

Note: Node values are inserted into a binary search tree before a reference to the tree’s root node is passed to your function. In a binary search tree, all nodes on the left branch of a node are less than the node value. All values on the right branch are greater than the node value.

Constraints

KodNest 15

Output Format

Your function should return a single integer denoting the height of the binary tree.

Sample Input

Sample Output

Explanation

The longest root-to-leaf path is shown below:

There are 4 nodes in this path that are connected by 3 edges, meaning our binary tree’s hieght=3.

Solution:

public class HeightOfABinaryTree {
	class Node {
		int data;
		Node left;
		Node right;
	}

	int height(Node root) {
		if (root == null)
			return 0;
		return (Math.max(height(root.left), height(root.right)) + 1);

	}

}

16.Challenge-Tree: Level Order Traversal

You are given a pointer to the root of a binary tree. You need to print the level order traversal of this tree. In level order traversal, we visit the nodes level by level from left to right. You only have to complete the function. For example:

For the above tree, the level order traversal is 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Input Format

You are given a function,

void levelOrder(Node * root) {

}

Constraints

1 Nodes in the tree 500

Output Format

Print the values in a single line separated by a space.

Sample Input

Sample Output

1 2 5 3 6 4

Explanation

We need to print the nodes level by level. We process each level from left to right.
Level Order Traversal: 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Solution:

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrderTraversal {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void levelOrder(Node root) {

		Queue<Node> q = new LinkedList<Node>();
		q.add(root);

		while (!q.isEmpty()) {

			Node currentNode = q.poll();
			System.out.print(currentNode.data + " ");
			if (currentNode.left != null)
				q.add(currentNode.left);
			if (currentNode.right != null)
				q.add(currentNode.right);
		}

	}
}

17. Challenge-Tree: Top View

You are given a pointer to the root of a binary tree. Print the top view of the binary tree.
Top view means when you look the tree from the top the nodes, what you will see will be called the top view of the tree. See the example below.
You only have to complete the function.
For example :

Top View : 1 -> 2 -> 5 -> 6

Input Format

You are given a function,

void topView(node * root) {

}

Constraints

1 <=Nodes in the tree <=500

Output Format

Print the values on a single line separated by space.

Sample Input

Sample Output

1 2 5 6

Explanation

From the top only nodes 1,2,5,6 will be visible.

Solution:

public class TopView {
	class Node {
		int data;
		Node left;
		Node right;
	}

	void topView(Node root) {
		Node rootNode = root;

		if (rootNode == null)
			return;
		printLeft(rootNode.left);
		System.out.print(rootNode.data + " ");
		printright(rootNode.right);

	}

	void printLeft(Node rootNode) {
		if (rootNode == null)
			return;
		printLeft(rootNode.left);
		System.out.print(rootNode.data + " ");
	}

	void printright(Node rootNode) {
		if (rootNode == null)
			return;
		System.out.print(rootNode.data + " ");
		printright(rootNode.right);

	}

}

18. Challenge-Print the Elements of a Linked List

If you’re new to linked lists, this is a great exercise for learning about them. Given a pointer to the head node of a linked list, print its elements in order, one element per line. If the head pointer is null (indicating the list is empty), don’t print anything.

Input Format

The first line of input contains n, the number of elements in the linked list.
The next n lines contain one element each, which are the elements of the linked list.

Note: Do not read any input from stdin/console. Complete the printLinkedList function in the editor below.

Constraints

KodNest 18 , where List_i is the ith element of the linked list.

Output Format

Print the integer data for each element of the linked list to stdout/console (e.g.: using printf, cout, etc.). There should be one element per line.

Sample Input

2
16
13

Sample Output

16
13

Explanation

There are two elements in the linked list. They are represented as 16 -> 13 -> NULL. So, the printLinkedList function should print 16 and 13 each in a new line.

Solution:

class PrintTheElementsOfALinkedList {

	class Node {
		int data;
		Node next;
	}

	void Print(Node head) {
		Node current = head;
		while (current != null) {
			System.out.println(current.data);
			current = current.next;
		}

	}
}

19. Challenge-Insert a node at the head of a linked list

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the head of the linked list and return the new head node. The head pointer given may be null meaning that the initial list is empty.

Input Format

You have to complete the SinglyLinkedListNode Insert(SinglyLinkedListNode head, int data) method which takes two arguments – the head of the linked list and the integer to insert. You should NOT read any input from stdin/console.

The input is handled by code in the editor and is as follows:

The first line contains an integer n, denoting the number of elements to be inserted at the head of the list.
The next n lines contain an integer each, denoting the element to be inserted.

Constraints

KodNest 19

Output Format

Insert the new node at the head and return the head of the updated linked list. Do NOT print anything to stdout/console.

The output is handled by the code in the editor and it is as follows:

Print the elements of linked list from head to tail, each in a new line.

Sample Input

Sample Output

Explanation

Intially the list in NULL. After inserting 383, the list is 383 -> NULL.
After inserting 484, the list is 484 -> 383 -> NULL.
After inserting 392, the list is 392 -> 484 -> 383 -> NULL.
After inserting 975, the list is 975 -> 392 -> 484 -> 383 -> NULL.
After inserting 321, the list is 321 -> 975 -> 392 -> 484 -> 383 -> NULL.

20. Challenge-Insert a Node at the Tail of a Linked List

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty.

Input Format

You have to complete the SinglyLinkedListNode insertAtTail(SinglyLinkedListNode head, int data) method. It takes two arguments: the head of the linked list and the integer to insert at tail. You should not read any input from the stdin/console.

The input is handled by code editor and is as follows:
The first line contains an integer n, denoting the elements of the linked list.
The next n lines contain an integer each, denoting the element that needs to be inserted at tail.

Constraints

KodNest 20

Output Format

Insert the new node at the tail and just return the head of the updated linked list. Do not print anything to stdout/console.

The output is handled by code in the editor and is as follows:
Print the elements of the linked list from head to tail, each in a new line.

Sample Input

Sample Output

Explanation

First the linked list is NULL. After inserting 141, the list is 141 -> NULL.
After inserting 302, the list is 141 -> 302 -> NULL.
After inserting 164, the list is 141 -> 302 -> 164 -> NULL.
After inserting 530, the list is 141 -> 302 -> 164 -> 530 -> NULL. After inserting 474, the list is 141 -> 302 -> 164 -> 530 -> 474 -> NULL, which is the final list.

21. Challenge-Insert a node at a specific position in a linked list

You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node.

A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

As an example, if your list starts as 1->2->3 and you want to insert a node at position 2 with data=4, your new list should be 1_>2->4->3

Function Description Complete the function insertNodeAtPosition in the editor below. It must return a reference to the head node of your finished list.

insertNodeAtPosition has the following parameters:

head: a SinglyLinkedListNode pointer to the head of the list
data: an integer value to insert as data in your new node
position: an integer position to insert the new node, zero based indexing

Input Format

The first line contains an integer n, the number of elements in the linked list.
Each of the next n lines contains an integer SinglyLinkedListNode[i].data.
The last line contains an integer position.

Constraints

, where is the element of the linked list.

Output Format

Return a reference to the list head. Locked code prints the list for you.

Sample Input

Sample Output

16 13 1 7

Explanation

The initial linked list is 16 13 7. We have to insert 1 at the position 2 which currently has 7 in it. The updated linked list will be 16 13 1 7

Solution:

public class InsertANodeAtASpecificPositionInALinkedList {

	class Node {
		int data;
		Node next;
	}

	Node InsertNth(Node head, int data, int position) {
		Node newNode = new Node();
		newNode.data = data;
		Node current = head;
		Node prev = current;
		int counter = 0;

		if (position == 0) {
			newNode.next = head;
			return newNode;

		} else {
			current = head.next;
			while (current != null) {
				if (++counter == position) {
					newNode.next = prev.next;
					prev.next = newNode;
					break;
				}
				prev = current;
				current = current.next;
			}

			if (current == null) {
				newNode.next = prev.next;
				prev.next = newNode;
			}
		}
		return head;

	}

}

22. Challenge-Delete a Node

You’re given the pointer to the head node of a linked list and the position of a node to delete. Delete the node at the given position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The list may become empty after you delete the node.

Input Format

You have to complete the deleteNode(SinglyLinkedListNode* llist, int position) method which takes two arguments – the head of the linked list and the position of the node to delete. You should NOT read any input from stdin/console. position will always be at least 0 and less than the number of the elements in the list.

The first line of input contains an integer n, denoting the number of elements in the linked list.
The next n lines contain an integer each in a new line, denoting the elements of the linked list in the order.
The last line contains an integer position denoting the position of the node that has to be deleted form the linked list.

Constraints

, where is the element i th of the linked list.

Output Format

Delete the node at the given position and return the head of the updated linked list. Do NOT print anything to stdout/console.

The code in the editor will print the updated linked list in a single line separated by spaces.

Sample Input

Sample Output

20 6 2 7 4 15 9

Explanation

The given linked list is 20->6->2->19->7->4->15->9. We have to delete the node at position 3, which is 19. After deleting that node, the updated linked list is: 20->6->2->7->4->15->9

public class DeleteANode {

	class Node {
		int data;
		Node next;
	}

	Node Delete(Node head, int position) {

		Node current = head;
		Node prev = current;
		int counter = 0;

		if (head == null && position == 0) {
			return null;
		}
		if (position == 0 && head != null) {
			head = head.next;
			return head;
		} else {

			current = head.next;
			while (current != null) {

				if (++counter == position) {
					prev.next = current.next;
					break;
				}
				prev = current;
				current = current.next;
			}

		}
		return head;

	}

}

23. Challenge-Print in Reverse

You are given the pointer to the head node of a linked list and you need to print all its elements in reverse order from tail to head, one element per line. The head pointer may be null meaning that the list is empty – in that case, do not print anything!

Input Format

You have to complete the void reversePrint(SinglyLinkedListNode* head) method which takes one argument – the head of the linked list. You should NOT read any input from stdin/console.

The first line of input contains t , the number of test cases.
The input of each test case is as follows:

The first line contains an integer n, denoting the number of elements in the list.
The next n lines contain one element each, denoting the elements of the linked list in the order.

Constraints

, where is the i th element in the list.

Output Format

Complete the reversePrint function in the editor below and print the elements of the linked list in the reverse order, each in a new line.

Sample Input

Sample Output

Explanation

There are three test cases.
The first linked list has  elements: 16 -> 12 -> 4 -> 2 -> 5. Printing this in reverse order will produce: 5 -> 2 -> 4 -> 12 -> 16.
The second linked list has  elements: 7 -> 3 -> 9. Printing this in reverse order will produce: 9 -> 3 -> 7.
The third linked list has  elements: 5 -> 1 -> 18 -> 3 -> 13. Printing this in reverse order will produce: 13 -> 3 -> 18 -> 1 -> 5.

24. Challenge-Reverse a linked list

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Input Format

You have to complete the SinglyLinkedListNode reverse(SinglyLinkedListNode head) method which takes one argument – the head of the linked list. You should NOT read any input from stdin/console.

The input is handled by the code in the editor and the format is as follows:

The first line contains an integer , denoting the number of test cases.
Each test case is of the following format:

The first line contains an integer , denoting the number of elements in the linked list.
The next lines contain an integer each, denoting the elements of the linked list.

Constraints

, where is the i th element in the list.

Output Format

Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.

The output is handled by the code in the editor. The output format is as follows:

For each test case, print in a new line the elements of the linked list after reversing it, separated by spaces.

Sample Input

Sample Output

5 4 3 2 1

Explanation

The initial linked list is: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

The reversed linked list is: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

25. Challenge-Compare two linked lists

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format

You have to complete the int CompareLists(Node* headA, Node* headB) method which takes two arguments – the heads of the two linked lists to compare. You should NOT read any input from stdin/console.

The input is handled by the code in the editor and the format is as follows: The first line contains , the number of test cases. The format for each test case is as follows:

The first line contains an integer n, denoting the number of elements in the first linked list.
The next n lines contain an integer each, denoting the elements of the first linked list.
The next line contains an integer m, denoting the number of elements in the second linked list.
The next m lines contain an integer each, denoting the elements of the second linked list.

Constraints

, where is the i th element in the list.

Output Format

Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

The output is handled by the code in the editor and it is as follows:

For each test case, in a new line, print 1 if the two lists are equal, else print 0.

Sample Input

Sample Output

0
1

Explanation

In the first case, linked lists are: 1 -> 2 -> NULL and 1 -> NULL

In the second case, linked lists are: 1 -> 2 -> NULL and 1 -> 2 -> NULL

Solution:

26. Challenge-Merge two sorted linked lists

You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format

You have to complete the SinglyLinkedListNode MergeLists(SinglyLinkedListNode headA, SinglyLinkedListNode headB) method which takes two arguments – the heads of the two sorted linked lists to merge. You should NOT read any input from stdin/console.

The input is handled by the code in the editor and the format is as follows:

The first line contains an integer t, denoting the number of test cases.
The format for each test case is as follows:

The first line contains an integer n, denoting the length of the first linked list.
The next n lines contain an integer each, denoting the elements of the linked list.
The next line contains an integer m, denoting the length of the second linked list.
The next m lines contain an integer each, denoting the elements of the second linked list.

Constraints

, where is the i th element of the list.

Output Format

Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Do NOT print anything to stdout/console.

The output is handled by the editor and the format is as follows:

For each test case, print in a new line, the linked list after merging them separated by spaces.

Sample Input

Sample Output

1 2 3 3 4

Explanation

The first linked list is: 1 -> 2 -> 3 -> NULL

The second linked list is: 3 -> 4 -> NULL

Hence, the merged linked list is: 1 -> 2 -> 3 -> 3 -> 4 -> NULL

27. Challenge-Get Node Value

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Input Format

You have to complete the int getNode(SinglyLinkedListNode* head, int positionFromTail) method which takes two arguments – the head of the linked list and the position of the node from the tail. positionFromTail will be at least 0 and less than the number of nodes in the list. You should NOT read any input from stdin/console.

The first line will contain an integer t, the number of test cases.
Each test case has the following format:
The first line contains an integer n, the number of elements in the linked list.
The next n lines contains, an element each denoting the element of the linked list.
The last line contains an integer PositionFromTail denoting the position from the tail, whose value needs to be found out and returned.

Constraints

, where is the i th element of the linked list.

Output Format

Find the node at the given position counting backwards from the tail. Then return the data contained in this node. Do NOT print anything to stdout/console.

The code in the editor handles output.
For each test case, print the value of the node, each in a new line.

Sample Input

Sample Output

1
3

Explanation

In first case, there is one element in linked list with value 1. Hence, last element is 1.

In second case, there are 3 elements with values 3, 2 and 1 (3 -> 2 -> 1). Hence, element with position of 2 from tail is 3.

Solution:

public class GetNodeValue {
	class Node {
		int data;
		Node next;
	}

	int GetNode(Node head, int n) {
		Node p1 = head;
		Node p2 = head;

		for (int i = 0; i < n; i++) {
			p1 = p1.next;
		}

		while (p1.next != null) {
			p2 = p2.next;
			p1 = p1.next;
		}
		return p2.data;

	}

}

28. Challenge-Delete duplicate-value nodes from a sorted linked list

You’re given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete as few nodes as possible so that the list does not contain any value more than once. The given head pointer may be null indicating that the list is empty.

Input Format

You have to complete the SinglyLinkedListNode* removeDuplicates(SinglyLinkedListNode* head) method which takes one argument – the head of the sorted linked list. You should NOT read any input from stdin/console.

The input is handled by the code in the editor and the format is as follows:

The first line contains an integer , denoting the number of test cases. The format for each test case is as follows:

The first line contains an integer , denoting the number of elements in the linked list.
The next lines contain an integer each, denoting the elements of the linked list.

Constraints

KodNest 24

Output Format

Delete as few nodes as possible to ensure that no two nodes have the same data. Adjust the next pointers to ensure that the remaining nodes form a single sorted linked list. Then return the head of the sorted updated linked list. Do NOT print anything to stdout/console.

The output is handled by the code in the editor and the format is as follows: For each test case, print in a new line, the data of the linked list after removing the duplicates separated by space.

Sample Input

Sample Output

1 2 3 4

Explanation

The initial linked list is: 1 -> 2 -> 2 -> 3 -> 4 -> NULL

The final linked list is: 1 -> 2 -> 3 -> 4 -> NULL

29. Challenge-Cycle Detection

A linked list is said to contain a cycle if any node is visited more than once while traversing the list.

Complete the function provided for you in your editor. It has one parameter: a pointer to a Node object named head that points to the head of a linked list. Your function must return a boolean denoting whether or not there is a cycle in the list. If there is a cycle, return true; otherwise, return false.

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

Input Format

Our hidden code checker passes the appropriate argument to your function. You are not responsible for reading any input from stdin.

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 Inputs

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.

30. Challenge-Find Merge Point of Two Lists

In the diagram below, the two lists converge at Node x:

[List #1] a--->b--->c
                     \
                      x--->y--->z--->NULL
                     /
     [List #2] p--->q

Complete the int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) method so that it finds and returns the data value of the Node where the two lists merge.

Input Format

Do not read any input from stdin/console.

The findMergeNode(SinglyLinkedListNode,SinglyLinkedListNode) method has two parameters, head1 and head2, which are the non-null head Nodes of two separate linked lists that are guaranteed to converge.

Constraints

The lists will merge.
KodNest 30

Output Format

Do not write any output to stdout/console.

Each Node has a data field containing an integer. Return the integer data for the Node where the two lists merge.

Sample Input

The diagrams below are graphical representations of the lists that input Nodes headA and headB are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those 2 Nodes and must explore the rest of the Nodes using some algorithm of your own design.

Test Case 0

 1
  \
   2--->3--->NULL
  /
 1

Test Case 1

1--->2
      \
       3--->Null
      /
     1

Sample Output

2
3

Explanation

Test Case 0: As demonstrated in the diagram above, the merge Node’s data field contains the integer 2.
Test Case 1: As demonstrated in the diagram above, the merge Node’s data field contains the integer 3.

Solution:

public class FindMergePointOfTwoLists {
	class Node {
		int data;
		Node next;
	}

	int FindMergeNode(Node headA, Node headB) {
		Node currentA = headA;
		Node currentB = headB;

		int lenA = 0, lenB = 0, d;

		while (currentA != null) {
			lenA++;
			currentA = currentA.next;
		}
		while (currentB != null) {
			lenB++;
			currentB = currentB.next;
		}

		if (lenA > lenB) {
			d = lenA - lenB;
		} else {
			d = lenB - lenA;
		}

		currentA = headA;
		currentB = headB;
		for (int i = 0; i < d; i++) {
			if (lenA > lenB) {
				currentA = currentA.next;
			} else {
				currentB = currentB.next;
			}

		}

		while (currentA != currentB) {
			currentA = currentA.next;
			currentB = currentB.next;
		}

		return currentA.data;
	}
}

31. Challenge-Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer, data, create a new DoublyLinkedListNode object having data value data and insert it into a sorted linked list while maintaining the sort.

Function Description

Complete the sortedInsert function in the editor below. It must return a reference to the head of your modified DoublyLinkedList.

sortedInsert has two parameters:

head: A reference to the head of a doubly-linked list of DoublyLinkedListNode objects.
data: An integer denoting the value of the data field for the DoublyLinkedListNode you must insert into the list.

Note: Recall that an empty list (i.e., where head=null) and a list with one element are sorted lists.

Input Format

The first line contains an integer t, the number of test cases.

Each of the test case is in the following format:

The first line contains an integer n, the number of elements in the linked list.
Each of the next n lines contains an integer, the data for each node of the linked list.
The last line contains an integer data which needs to be inserted into the sorted doubly-linked list.

Constraints

KodNest 31

Output Format

Do not print anything to stdout. Your method must return a reference to the head of the same list that was passed to it as a parameter.

The ouput is handled by the code in the editor and is as follows:
For each test case, print the elements of the sorted doubly-linked list separated by spaces on a new line.

Sample Input

Sample Output

1 3 4 5 10

Explanation

The initial doubly linked list is: .

The doubly linked list after insertion is:

Solution:

public class InsertingANodeIntoASortedDoublyLinkedList {

	class Node {
		int data;
		Node next;
		Node prev;
	}

	Node SortedInsert(Node head, int data) {
		Node header = head;
		Node newNode = new Node();
		newNode.data = data;
		newNode.prev = null;
		Node current = head;
		Node previous = current;

		if (header == null) {
			newNode.next = null;
			newNode.prev = null;
			header = newNode;
			return header;

		} else if (header.data > data) {
			newNode.next = header;
			header.prev = newNode;
			newNode.prev = null;
			header = newNode;
			return header;

		} else {
			while (current.next != null) {

				if (current.data < data) {

					previous = current;
					current = current.next;
					continue;
				}
				newNode.next = current;
				current.prev = newNode;
				previous.next = newNode;
				newNode.prev = previous;

			}

			if (current.next == null && current.data > data) {

				newNode.next = current;
				current.prev = newNode;
				previous.next = newNode;
				newNode.prev = previous;
			} else {
				newNode.next = null;
				current.next = newNode;
				newNode.prev = current;
			}

		}
		return header;
	}
}

32. Challenge-Reverse a doubly linked list

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty. Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list.

Function Description

Complete the reverse function in the editor below. It should return a reference to the head of your reversed list.

reverse has the following parameter(s):

head: a reference to the head of a DoublyLinkedList

Input Format

The first line contains an integer t, the number of test cases.

Each test case is of the following format:

The first line contains an integer n, the number of elements in the linked list.
The next n lines contain an integer each denoting an element of the linked list.

Constraints

KodNest 32

Output Format

Return a reference to the head of your reversed list. The provided code will print the reverse array as a one line of space-separated integers for each test case.

Sample Input

Sample Output

4 3 2 1

Explanation

The initial doubly linked list is:

The reversed doubly linked list is:

public class ReverseADoublyLinkedList {
	class Node {
		int data;
		Node next;
		Node prev;
	}

	Node Reverse(Node head) {
		Node current = head;

		Node temp = new Node();

		while (current != null) {

			temp = current.prev;
			current.prev = current.next;
			current.next = temp;
			head = current;
			current = current.prev;
		}

		return head;
	}
}

33. Challenge-Contacts

We’re going to make our own Contacts application! The application must perform two types of operations:

add name, where name is a string denoting a contact name. This must store name as a new contact in the application.
find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting with partial and print the count on a new line.

Given n sequential add and find operations, perform each operation in order.

Input Format

The first line contains a single integer, n, denoting the number of operations to perform.
Each line i of the n subsequent lines contains an operation in one of the two forms defined above.

Constraints

KodNest 33

It is guaranteed that name and partial contain lowercase English letters only.
The input doesn’t have any duplicate name for the add operation.

Output Format

For each find partial operation, print the number of contact names starting with partial on a new line.

Sample Input

4
add hack
add hackerrank
find hac
find hak

Sample Output

2
0

Explanation

We perform the following sequence of operations:

Add a contact named hack.
Add a contact named hackerrank.
Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we print 2 on a new line.
Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print 0 on a new line.

Solution:

public class Contacts {

	public static void main(String[] args) {
		TST<Integer> tst = new TST<Integer>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String op = sc.next();
			String name = sc.next();
			if (op.equals("add")) {
				tst.put(name, i);
			} else {
				System.out.println(tst.keyWithPrefix(name).size());
			}
		}
		sc.close();
	}

}

class TST<Value> {
	private Node root;

	private class Node {
		private Value val;
		private char c;
		private Node left, mid, right;
	}

	public void put(String key, Value val) {
		root = put(root, key, val, 0);
	}

	
	private Node put(Node x, String key, Value val, int d) {
		char c = key.charAt(d);
		if (x == null) {
			x = new Node();
			x.c = c;
		}
		if (c < x.c)
			x.left = put(x.left, key, val, d);
		else if (c > x.c)
			x.right = put(x.right, key, val, d);
		else if (d < key.length() - 1)
			x.mid = put(x.mid, key, val, d + 1);
		else
			x.val = val;
		return x;
	}

	
	private Node get(Node x, String key, int d) {
		if (x == null)
			return null;
		char c = key.charAt(d);
		if (c < x.c)
			return get(x.left, key, d);
		else if (c > x.c)
			return get(x.right, key, d);
		else if (d < key.length() - 1)
			return get(x.mid, key, d + 1);
		else
			return x;
	}

	/**
	 * @param root2
	 * @param string
	 * @param queue
	 */
	private void collect(Node x, StringBuilder prefix, Queue<String> q) {
		if (x == null)
			return;
		collect(x.left, prefix, q);
		if (x.val != null)
			q.offer(prefix.toString() + x.c);
		collect(x.mid, prefix.append(x.c), q);
		prefix.deleteCharAt(prefix.length() - 1);
		collect(x.right, prefix, q);
	}

	public Queue<String> keyWithPrefix(String prefix) {
		Queue<String> queue = new LinkedList<String>();
		Node x = get(root, prefix, 0);
		if (x == null)
			return queue;
		if (x.val != null)
			queue.offer(prefix);
		collect(x.mid, new StringBuilder(prefix), queue);
		return queue;
	}

}

34. Challenge-No Prefix Set

Given N strings. Each string contains only lowercase letters from a-j(both inclusive). The set of N strings is said to be GOOD SET if no string is prefix of another string else, it is BAD SET. (If two strings are identical, they are considered prefixes of each other.)

For example, aab, abcde, aabcd is BAD SET because aab is prefix of aabcd.

Print GOOD SET if it satisfies the problem requirement.
Else, print BAD SET and the first string for which the condition fails.

Input Format
First line contains N, the number of strings in the ith set.
Then next N lines follow, where ith line contains string.

Constraints

KodNest 34

Output Format
Output GOOD SET if the set is valid.
Else, output BAD SET followed by the first string for which the condition fails.

Sample Input00

7
aab
defgab
abcde
aabcde
cedaaa
bbbbbbbbbb
jabjjjad

Sample Output00

BAD SET
aabcde

Sample Input01

4
aab
aac
aacghgh
aabghgh

Sample Output01

BAD SET
aacghgh

Explanation
aab is prefix of aabcde. So set is BAD SET and it fails at string aabcde.

class TSTPrefix {

	static class TrieNode {
		char ch;
		int count;
		TrieNode[] children;
		boolean isCompleted = false;

		TrieNode(char ch) {
			this.ch = ch;
			children = new TrieNode[12];
		}

	}

	public boolean add(TrieNode root, String in) {
		TrieNode curr = root;
		for (int i = 0; i < in.length(); i++) {
			char c = in.charAt(i);
			int index = c - 'a';
			if (curr.children[index] == null)
				curr.children[index] = new TrieNode(c);
			if (curr.isCompleted)
				return false;
			curr.count++;
			curr = curr.children[index];
		}
		curr.isCompleted = true;
		return ++curr.count <= 1;

	}

}

public class NoPrefixSet {
	public static void main(String[] args) {
		TSTPrefix tst = new TSTPrefix();
		boolean found = false;
		TrieNode root = new TrieNode(' ');
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			String str = sc.next();
			if (!tst.add(root, str)) {
				System.out.println("BAD SET \n" + str);
				found = true;
				break;
			}

		}
		System.out.println(!found ? "GOOD SET" : "");
		sc.close();
	}
}

35. Challenge-Queue using Two Stacks

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

Enqueue: add a new element to the end of the queue.
Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process q queries, where each query is one of the following 3 types:

1 x: Enqueue element x into the end of the queue.
2: Dequeue the element at the front of the queue.
3: Print the element at the front of the queue.

Input Format

The first line contains a single integer, q, denoting the number of queries.
Each line i of the q subsequent lines contains a single query in the form described in the problem statement above. All three queries start with an integer denoting the query type, but only query 1 is followed by an additional space-separated value, x, denoting the value to be enqueued.

Constraints

KodNest 35

It is guaranteed that a valid answer always exists for each query of type .

Output Format

For each query of type 3, print the value of the element at the front of the queue on a new line.

Sample Input

Sample Output

14
14

public class QueueUsingTwoStacks {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		QueueWithTwoStack q = new QueueWithTwoStack();
		for (int i = 0; i < N; i++) {
			int qType = sc.nextInt();
			switch (qType) {
			case 1:
				q.enqueue(sc.nextInt());
				break;
			case 2:
				q.dequeue();
				break;
			case 3:
				q.front();
				break;

			default:
				break;
			}

		}
		sc.close();
	}

}

class QueueWithTwoStack {
	Stack<Integer> s1;
	Stack<Integer> s2;

	public QueueWithTwoStack() {
		super();
		this.s1 = new Stack<Integer>();
		this.s2 = new Stack<Integer>();
	}

	public void enqueue(int data) {
		s1.push(data);
	}

	public int dequeue() {
		if (s2.isEmpty()) {
			while (!s1.isEmpty()) {
				s2.push(s1.pop());
			}
		}
		return s2.pop();

	}

	public void front() {
		if (s2.isEmpty()) {
			while (!s1.isEmpty()) {
				s2.push(s1.pop());
			}
		}
		System.out.println(s2.peek());
	}

}

36. Challenge-QHEAP1

This question is designed to help you get a better understanding of basic heap operations.
You will be given queries of types:

“ 1v” – Add an element v to the heap.
“2 v ” – Delete the element v from the heap.
“3” – Print the minimum of all the elements in the heap.

NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.

Input Format

The first line contains the number of queries,Q .
Each of the next Q lines contains a single query of any one of the 3 above mentioned types.

Constraints
KodNest 36

Output Format

For each query of type 3, print the minimum value on a single line.

Sample Input

Sample Output

4  
9

Explanation

After the first queries, the heap contains {}. Printing the minimum gives as the output. Then, the query deletes from the heap, and the query gives as the output.

public class QHEAP1 {
	static int a[];
	static int c = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		a = new int[10];
		for (int i = 0; i < n; i++) {
			int q = sc.nextInt();
			int y;
			switch (q) {
			case 1:
				y = sc.nextInt();
				insert(y);
				break;
			case 2:
				y = sc.nextInt();
				delete(y);
				break;
			case 3:
				printMin();
				break;

			}
		}
		sc.close();
	}

	private static void delete(int y) {
		int k = 0;
		boolean found = false;
		for (int i = 0; i < a.length; i++) {
			if (y == a[i]) {
				k = i;
				found = true;
				break;
			}
		}
		if (found) {
			exch(k, c--);
			if (k == 1 || a[k] > a[k / 2]) {
				sink(k);
			} else {
				swim(k);
			}
			a[c + 1] = -1;
		}
	}

	private static void sink(int k) {
		while (2 * k <= c) {
			int j = 2 * k;
			if (j < c && less(j + 1, j))
				j++;
			if (less(k, j))
				break;
			exch(k, j);
			k = j;
		}

	}

	private static void insert(int y) {
		if (c == a.length - 1)
			resize();
		a[++c] = y;
		swim(c);
	}

	private static void resize() {
		int b[] = Arrays.copyOf(a, a.length * 2);
		a = b;
	}

	private static void swim(int k) {
		while (k > 1 && less(k, k / 2)) {
			exch(k, k / 2);
			k = k / 2;
		}

	}

	private static boolean less(int i, int j) {
		return a[i] < a[j];
	}

	private static void exch(int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	private static void printMin() {
		System.out.println(a[1]);
	}

}

37. Challenge-Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with:

sweetness =(1x Least sweet cookie +2x 2nd least sweet cookie).

He repeats this procedure until all the cookies in his collection have a sweetness >=K.
You are given Jesse’s cookies. Print the number of operations required to give the cookies a sweetness >=K. Print -1 if this isn’t possible.

Input Format

The first line consists of integers N, the number of cookies and K, the minimum required sweetness, separated by a space.
The next line contains N integers describing the array A where Ai is the sweetness of the cookie in Jesse’s collection.

Constraints

Output Format

Output the number of operations that are needed to increase the cookie’s sweetness >=K.
Output -1 if this isn’t possible.

Sample Input

6 7
1 2 3 9 10 12

Sample Output

Solution:

public class JesseAndCookies {
	static int A[];
	static int c;
	static int N = 0;
	static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int K = sc.nextInt();
		c = 0;
		A = new int[N + 1];
		A[1] = sc.nextInt();
		c++;
		for (int i = 2; i <= N; i++) {
			int item = sc.nextInt();
			insert(item);
		}
		boolean found = false;
		for (int i = 1; i <= N; i++) {
			if (A[1] < K) {
				count++;
				int m1 = getMin();
				delete(1);
				int m2 = getMin();
				delete(1);
				int m3 = m1 + 2 * m2;
				insert(m3);
			} else {
				found = true;
				break;
			}

		}
		System.out.println(found ? count : -1);
		sc.close();
	}

	private static int getMin() {
		return A[1];
	}

	private static void delete(int k) {
		exch(1, c--);
		sink(1);

	}

	private static void sink(int k) {
		while (2 * k <= c) {
			int j = 2 * k;
			if (j < c && A[j] > A[j + 1])
				j++;
			if (A[k] < A[j])
				break;
			exch(j, k);
			k = j;

		}

	}

	private static void insert(int item) {
		if (c == A.length - 1)
			resize();
		A[++c] = item;
		swim(c);
	}

	private static void swim(int k) {
		while (k > 1 && A[k] < A[k / 2]) {
			exch(k, k / 2);
			k = k / 2;
		}
	}

	private static void exch(int i, int j) {
		int t = A[i];
		A[i] = A[j];
		A[j] = t;
	}

	private static void resize() {
		int[] b = Arrays.copyOf(A, A.length * 2);
		A = b;
	}

}

38. Challenge-Jesse and Cookies

People connect with each other in a social network. A connection between Person I and Person J is represented as MIJ. When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to.

At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected 2 and 3 later and connected, then 1,2, and 3 will belong to the same community.

There are two type of queries:

communities containing person and merged (if they belong to different communities).
print the size of the community to which person belongs.

Input Format

The first line of input will contain integers N and Q, i.e. the number of people and the number of queries.
The next Q lines will contain the queries.

Constraints :
KodNest 38

Output Format

The output of the queries.

Sample Input

Sample Output

Explanation

Initial size of each of the community is 1.

Solution:

public class MergingCommunities {

	int[] id, sz;

	MergingCommunities(int n) {
		id = new int[n];
		sz = new int[n];
		for (int i = 0; i < id.length; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}

	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}

	private int find(int p) {
		int q = p;
		while (q != id[q]) {
			q = id[q];
		}
		id[p] = q;
		return q;
	}

	public void union(int p, int q) {
		int pId = find(p);
		int qId = find(q);

		if (pId == qId) {
			return;
		} else {
			if (sz[pId] >= sz[qId]) {
				id[qId] = pId;
				sz[pId] = sz[pId] + sz[qId];

			} else if (sz[pId] < sz[qId]) {
				id[pId] = qId;
				sz[qId] = sz[qId] + sz[pId];
			}

		}
	}

	public int countFreq(int[] a, int n) {
		int nRoot = find(n);
		return sz[nRoot];
	}

	public static void main(String[] args) throws FileNotFoundException {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		MergingCommunities c = new MergingCommunities(N + 1);
		while (Q-- != 0) {
			String s = sc.next();
			char ch = s.charAt(0);

			if (ch == 'Q') {
				int q = sc.nextInt();
				System.out.println(c.countFreq(c.id, q));
			} else {
				int p = sc.nextInt();
				int q = sc.nextInt();
				if (!c.connected(p, q)) {
					c.union(p, q);

				}

			}
		}
		sc.close();
	}
}

39.Challenge-Find the Running Median

If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set {1,2,3},2 is the median.
If your set contains an even number of elements, the median is the average of the two middle elements of the sorted sample. In the sorted set {1,2,3,4}, is the median.

Given an input stream of integers, you must perform the following task for each integer:

Add the ith integer to a running list of integers.
Find the median of the updated list (i.e., for the first element through the ith element).
Print the list’s updated median on a new line. The printed value must be a double-precision number scaled to 1 decimal place (i.e.12.3, format).

Input Format

The first line contains a single integer, n, denoting the number of integers in the data stream.
Each line i of the n subsequent lines contains an integer,ai , to be added to your list.

Constraints

KodNest 40

Output Format

After each new integer is added to the list, print the list’s updated median on a new line as a single double-precision number scaled to 1 decimal place (i.e.12.3, format).

Sample Input

Sample Output

12.0
8.0
5.0
4.5
5.0
6.0

Solution:

public class ComponentsInAGraph {

	int[] id, sz;
	int count;

	ComponentsInAGraph(int n) {
		id = new int[n];
		sz = new int[n];
		count = n;
		for (int i = 0; i < id.length; i++) {
			id[i] = i;
			sz[i] = 1;
		}

	}

	public int getCount() {
		return count;
	}

	public void decrementCount() {
		count--;
	}

	public boolean connected(int p, int q) {
		return id[p] == id[q];

	}

	public void union(int p, int q) {
		int pId = id[p];
		int qId = id[q];

		if (pId == qId) {
			return;
		} else {
			for (int i = 0; i < id.length; i++) {
				if (id[i] == pId)
					id[i] = qId;

			}
		}
		this.decrementCount();
	}

	public void printMinMax(int[] a) {
		HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
		for (int i = 0; i < a.length; i++) {

			if (hmap.containsKey(a[i])) {
				hmap.put(a[i], hmap.get(a[i]) + 1);
			} else {
				hmap.put(a[i], 1);
			}

		}
		int min = Integer.MAX_VALUE, max = 0;
		for (Map.Entry<Integer, Integer> e : hmap.entrySet()) {
			if ((e.getValue()) > 1) {
				int temp = e.getValue();
				if (temp > max) {
					max = temp;
				}
				if (temp < min) {
					min = temp;
				}
			}
		}
		System.out.println(min + " " + max);
	}

	public static void main(String[] args) throws FileNotFoundException {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		ComponentsInAGraph c = new ComponentsInAGraph(2 * N + 1);
		while (N-- != 0) {
			int p = sc.nextInt();
			int q = sc.nextInt();

			if (!c.connected(p, q)) {
				c.union(p, q);
			}

		}
		c.printMinMax(c.id);
		sc.close();
	}

}

40. Challenge : Priority Queue

In computer science, a priority queue is an abstract data type which is like a regular queue, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. – Wikipedia

In this problem we will test your knowledge on Java Priority Queue.

There are a number of students in a school who wait to be served. Two types of events, ENTER and SERVED, can take place which are described below.

ENTER: A student with some priority enters the queue to be served.
SERVED: The student with the highest priority is served (removed) from the queue.

A unique id is assigned to each student entering the queue. The queue serves the students based on the following criteria (priority criteria):

The student having the highest Cumulative Grade Point Average (CGPA) is served first.
Any students having the same CGPA will be served by name in ascending case-sensitive alphabetical order.
Any students having the same CGPA and name will be served in ascending order of the id.

Create the following two classes:

The Student class should implement:
- The constructor Student(int id, String name, double cgpa).
- The method int getID() to return the id of the student.
- The method String getName() to return the name of the student.
- The method double getCGPA() to return the CGPA of the student.
The Priorities class should implement the method List getStudents(List events) to process all the given events and return all the students yet to be served in the priority order.

Input Format

The first line contains an integer, n, describing the total number of events. Each of the n subsequent lines will be of the following two forms:

ENTER name CGPA id: The student to be inserted into the priority queue.
SERVED: The highest priority student in the queue was served.

The locked stub code in the editor reads the input and tests the correctness of the Student and Priorities classes implementation.

Constraints

2 ≤ n ≤ 1000
0 ≤ CGPA ≤ 4.00
1 ≤ id≤ 10⁵
2 ≤ |name| ≤ 30

Output Format

The locked stub code prints the names of the students yet to be served in the priority order. If there are no such student, then the code prints EMPTY.

Sample Input 0

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

Sample Output 0

Dan
Ashley
Shafaet
Maria

Solution:

public class JavaPriorityQueue {
	static class Student {
		private int token;
		private String fname;
		private double cgpa;

		public Student(int id, String fname, double cgpa) {
			super();
			this.token = id;
			this.fname = fname;
			this.cgpa = cgpa;
		}

		public int getToken() {
			return token;
		}

		public String getFname() {
			return fname;
		}

		public double getCgpa() {
			return cgpa;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		PriorityQueue data = new PriorityQueue(new Comparator() {
			@Override
			public int compare(Student o1, Student o2) {
				if (o1.getCgpa() < o2.getCgpa()) {
					return 1;
				} else if (o1.getCgpa() > o2.getCgpa()) {
					return -1;
				} else {
					if (o1.getFname().compareTo(o2.getFname()) == 0) {
						if (o1.getToken() > o2.getToken()) {
							return 1;
						} else if (o1.getToken() < o2.getToken()) {
							return -1;
						} else {
							return 0;
						}

					} else {
						return o1.getFname().compareTo(o2.getFname());
					}
				}
			}
		});
		for (int i = 0; i < t; i++) {
			String op = sc.next();
			switch (op) {
			case "ENTER":
				String name = sc.next();
				double cgpa = sc.nextDouble();
				int id = sc.nextInt();
				Student s = new Student(id, name, cgpa);
				data.add(s);
				break;
			case "SERVED":
				if (data.isEmpty()) {
					break;
				}
				data.remove();

			}
		}
		if (data.isEmpty())
			System.out.println("EMPTY");
		else {
			while (!data.isEmpty()) {
				Student st = data.poll();
				System.out.println(st.getFname());
			}
		}
		sc.close();
	}
}

41. Challenge : Java 1D Array (Part 2)

Let’s play a game on an array! You’re standing at index 0 of an n-element array named game. From some index i(where 0 ≤ i ≤ n), you can perform one of the following moves:

Move Backward: If cell i – 1 exists and contains a 0, you can walk back to cell i – 1.
Move Forward:
- If cell i + 1 contains a zero, you can walk to cell i + 1.
- If cell i + leap contains a zero, you can jump to cell i + leap.
- If you’re standing in cell n – 1 or the value of i + leap ≥ n, you can walk or jump off the end of the array and win the game.

In other words, you can move from index i to index i + 1, i – 1, or i + leap as long as the destination index is a cell containing a 0. If the destination index is greater than n – 1, you win the game.

Given leap and game, complete the function in the editor below so that it returns true if you can win the game (or false if you cannot).

Input Format

The first line contains an integer, q, denoting the number of queries (i.e., function calls).
The 2 . q subsequent lines describe each query over two lines:

The first line contains two space-separated integers describing the respective values of n and leap.
The second line contains n space-separated binary integers (i.e., zeroes and ones) describing the respective values of game_0,game₁,…,game_n-1.

Constraints

1 ≤ q ≤ 5000
2 ≤ n ≤ 100
0 ≤ leap ≤ 100
It is guaranteed that the value of game[0] is always 0.

Output Format

Return true if you can win the game; otherwise, return false.

Sample Input

4
5 3
0 0 0 0 0
6 5
0 0 0 1 1 1
6 3
0 0 1 1 1 0
3 1
0 1 0

Sample Output

YES
YES
NO
NO

Solution:

public class Java1DArrayPart2 {
	public static boolean canWin(int leap, int[] game) {

		return canWin(leap, game, 0);
	}

	public static boolean canWin(int leap, int[] g, int i) {
		if (i < 0 || g[i] == 1) {
			return false;
		}
		if (i + leap >= g.length || i == g.length - 1) {
			return true;
		}
		g[i] = 1;

		return canWin(leap, g, i + 1) || canWin(leap, g, i + leap) || canWin(leap, g, i - 1);

	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int q = scan.nextInt();
		while (q-- > 0) {
			int n = scan.nextInt();
			int leap = scan.nextInt();

			int[] game = new int[n];
			for (int i = 0; i < n; i++) {
				game[i] = scan.nextInt();
			}

			System.out.println((canWin(leap, game)) ? "YES" : "NO");
		}
		scan.close();
	}
}

42. Challenge : Java Inheritance I

Using inheritance, one class can acquire the properties of others. Consider the following Animal class:

class Animal{
    void walk(){
        System.out.println("I am walking");
    }
}

This class has only one method, walk. Next, we want to create a Bird class that also has a fly method. We do this using extendskeyword:

class Bird extends Animal {
    void fly() {
        System.out.println("I am flying");
    }
}

Finally, we can create a Bird object that can both fly and walk.

public class Solution{
   public static void main(String[] args){

      Bird bird = new Bird();
      bird.walk();
      bird.fly();
   }
}

The above code will print:

I am walking
I am flying

This means that a Bird object has all the properties that an Animal object has, as well as some additional unique properties.

The code above is provided for you in your editor. You must add a sing method to the Bird class, then modify the main method accordingly so that the code prints the following lines:

I am walking
I am flying
I am singing

Solution:

class Animal{
	void walk(){
		System.out.println("I am walking");
	}
}


class Bird extends Animal{
	void fly(){
		System.out.println("I am flying");
	}
	//code need to be added
    void sing(){
        System.out.println("I am singing");
    }
}


public class JavaInheritanceI {
	public static void main(String args[]){

		  Bird bird = new Bird();
		  bird.walk();
		  bird.fly();
	      bird.sing();
		
	   }
	}

43. Challenge : Java Inheritance II

Write the following code in your editor below:

A class named Arithmetic with a method named add that takes 2 integers as parameters and returns an integer denoting their sum.
A class named Adder that inherits from a superclass named Arithmetic.

Your classes should not be public .

Input Format

You are not responsible for reading any input from stdin; a locked code stub will test your submission by calling the addmethod on an Adder object and passing it 2 integer parameters.

Output Format

You are not responsible for printing anything to stdout. Your add method must return the sum of its parameters.

Sample Output

The main method in the Solution class above should print the following:

My superclass is: Arithmetic
42 13 20

Solution:

class Arithmetic {
	int add(int a, int b) {
		return a + b;
	}
}

class Adder extends Arithmetic {

}

public class JavaInheritanceII {
	public static void main(String[] args) {
		// Create a new Adder object
		Adder a = new Adder();

		// Print the name of the superclass on a new line
		System.out.println("My superclass is: " + a.getClass().getSuperclass().getName());

		// Print the result of 3 calls to Adder's `add(int,int)` method as 3
		// space-separated integers:
		System.out.print(a.add(10, 32) + " " + a.add(10, 3) + " " + a.add(10, 10) + "\n");
	}
}

44. Challenge : Java Abstract Class

A Java abstract class is a class that can’t be instantiated. That means you cannot create new instances of an abstract class. It works as a base for subclasses. You should learn about Java Inheritance before attempting this challenge.

Following is an example of abstract class:

abstract class Book{
    String title;
    abstract void setTitle(String s);
    String getTitle(){
        return title;
    }
}

If you try to create an instance of this class like the following line you will get an error:

Book new_novel=new Book();

You have to create another class that extends the abstract class. Then you can create an instance of the new class.

Notice that setTitle method is abstract too and has no body. That means you must implement the body of that method in the child class.

In the editor, we have provided the abstract Book class and a Main class. In the Main class, we created an instance of a class called MyBook. Your task is to write just the MyBook class.

Your class mustn’t be public.

Sample Input

A tale of two cities

Sample Output

The title is: A tale of two cities

Solution:

abstract class Book {
	String title;

	abstract void setTitle(String s);

	String getTitle() {
		return title;
	}
}

// Write MyBook class here
class MyBook extends Book {

	void setTitle(String s) {
		super.title = s;
	}
}

public class JavaAbstractClass {
	public static void main(String[] args) {
		// Book new_novel=new Book(); This line prHMain.java:25: error: Book is
		// abstract; cannot be instantiated
		Scanner sc = new Scanner(System.in);
		String title = sc.nextLine();
		MyBook new_novel = new MyBook();
		new_novel.setTitle(title);
		System.out.println("The title is: " + new_novel.getTitle());
		sc.close();

	}
}

45. Challenge : Java Interface

A Java interface can only contain method signatures and fields. The interface can be used to achieve polymorphism. In this problem, you will practice your knowledge on interfaces.

You are given an interface AdvancedArithmetic which contains a method signature int divisor_sum(int n). You need to write a class called MyCalculator which implements the interface.

divisorSum function just takes an integer as input and return the sum of all its divisors. For example divisors of 6 are 1, 2, 3 and 6, so divisor_sum should return 12. The value of n will be at most 1000.

Read the partially completed code in the editor and complete it. You just need to write the MyCalculator class only. Your class shouldn’t be public.

Sample Input

Sample Output

I implemented: AdvancedArithmetic
12

Solution:

interface AdvancedArithmetic {
	int divisor_sum(int n);
}

// Write your code here
class MyCalculator implements AdvancedArithmetic {
	public int divisor_sum(int n) {
		int sum = 0, i = 1;
		while (n != 0 && i <= n) {
			if (n % i == 0) {
				sum += i;
			}
			i++;
		}
		return sum;
	}
}

public class JavaInterface {
	public static void main(String[] args) {
		MyCalculator my_calculator = new MyCalculator();
		System.out.print("I implemented: ");
		ImplementedInterfaceNames(my_calculator);
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.print(my_calculator.divisor_sum(n) + "\n");
		sc.close();
	}

	/*
	 * ImplementedInterfaceNames method takes an object and prints the name of the
	 * interfaces it implemented
	 */
	static void ImplementedInterfaceNames(Object o) {
		Class[] theInterfaces = o.getClass().getInterfaces();
		for (int i = 0; i < theInterfaces.length; i++) {
			String interfaceName = theInterfaces[i].getName();
			System.out.println(interfaceName);
		}
	}
}

46. Challenge : Java Method Overriding

When a subclass inherits from a superclass, it also inherits its methods; however, it can also override the superclass methods (as well as declare and implement new ones). Consider the following Sports class:

class Sports{
    String getName(){
        return "Generic Sports";
    }
    void getNumberOfTeamMembers(){
        System.out.println( "Each team has n players in " + getName() );
    }
}

Next, we create a Soccer class that inherits from the Sports class. We can override the getName method and return a different, subclass-specific string:

class Soccer extends Sports{
    @Override
    String getName(){
        return "Soccer Class";
    }
}

Note: When overriding a method, you should precede it with the @Override annotation. The parameter(s) and return type of an overridden method must be exactly the same as those of the method inherited from the supertype.

Task
Complete the code in your editor by writing an overridden getNumberOfTeamMembers method that prints the same statement as the superclass’ getNumberOfTeamMembers method, except that it replaces n with 11 (the number of players on a Soccer team).

Output Format

When executed, your completed code should print the following:

Generic Sports
Each team has n players in Generic Sports
Soccer Class
Each team has 11 players in Soccer Class

Solution:

class Sports {

	String getName() {
		return "Generic Sports";
	}

	 // Write your overridden getNumberOfTeamMembers method here
	void getNumberOfTeamMembers() {
		System.out.println("Each team has n players in " + getName());
	}
}

class Soccer extends Sports {
	@Override
	String getName() {
		return "Soccer Class";
	}

}

public class JavaMethodOverriding {
	public static void main(String[] args) {
		Sports c1 = new Sports();
		Soccer c2 = new Soccer();
		System.out.println(c1.getName());
		c1.getNumberOfTeamMembers();
		System.out.println(c2.getName());
		c2.getNumberOfTeamMembers();
	}
}

47. Challenge : Java Method Overriding 2

When a method in a subclass overrides a method in superclass, it is still possible to call the overridden method using superkeyword. If you write super.func() to call the function func(), it will call the method that was defined in the superclass.

You are given a partially completed code in the editor. Modify the code so that the code prints the following text:

Hello I am a motorcycle, I am a cycle with an engine.
My ancestor is a cycle who is a vehicle with pedals.

Solution:

class BiCycle {
	String define_me() {
		return "a vehicle with pedals.";
	}
}

class MotorCycle extends BiCycle {
	String define_me() {
		return "a cycle with an engine.";
	}

	MotorCycle() {
		System.out.println("Hello I am a motorcycle, I am " + define_me());
		String temp = super.define_me(); // Fix this line
		System.out.println("My ancestor is a cycle who is " + temp);
	}

}

public class JavaMethodOverriding2SuperKeyword {
	public static void main(String[] args) {
	 new MotorCycle();
	}
}

48. Challenge : Java Instaneof Keyword

The Java instanceof operator is used to test if the object or instance is an instanceof the specified type.

In this problem we have given you three classes in the editor:

Student class
Rockstar class
Hacker class

In the main method, we populated an ArrayList with several instances of these classes. count method calculates how many instances of each type is present in the ArrayList. The code prints three integers, the number of instance of Student class, the number of instance of Rockstar class, the number of instance of Hacker class.

But some lines of the code are missing, and you have to fix it by modifying only 3 lines! Don’t add, delete or modify any extra line.

To restore the original code in the editor, click on the top left icon in the editor and create a new buffer.

Sample Input

5
Student
Student
Rockstar
Student
Hacker

Sample Output

3 1 1

Solution:

class Student {
}

class Rockstar {
}

class Hacker {
}

public class JavaInstanceofkeyword {

	static String count(ArrayList mylist) {
		int a = 0, b = 0, c = 0;
		for (int i = 0; i < mylist.size(); i++) {
			Object element = mylist.get(i);
			if (element instanceof Student)
				a++;
			if (element instanceof Rockstar)
				b++;
			if (element instanceof Hacker)
				c++;
		}
		String ret = Integer.toString(a) + " " + Integer.toString(b) + " " + Integer.toString(c);
		return ret;
	}

	public static void main(String[] args) {
		ArrayList mylist = new ArrayList();
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			String s = sc.next();
			if (s.equals("Student"))
				mylist.add(new Student());
			if (s.equals("Rockstar"))
				mylist.add(new Rockstar());
			if (s.equals("Hacker"))
				mylist.add(new Hacker());
		}
		System.out.println(count(mylist));
		sc.close();
	}
}

49. Challenge : Java Iterator

Java Iterator class can help you to iterate through every element in a collection. Here is a simple example:

import java.util.*;
public class Example{

    public static void main(String []args){
        ArrayList mylist = new ArrayList();
        mylist.add("Hello");
        mylist.add("Java");
        mylist.add("4");
        Iterator it = mylist.iterator();
        while(it.hasNext()){
            Object element = it.next();
            System.out.println((String)element);
        }
    }
}

In this problem you need to complete a method func. The method takes an ArrayList as input. In that ArrayList there is one or more integer numbers, then there is a special string “###”, after that there are one or more other strings. A sample ArrayListmay look like this:

element[0]=>42
element[1]=>10
element[2]=>"###"
element[3]=>"Hello"
element[4]=>"Java"

You have to modify the func method by editing at most 2 lines so that the code only prints the elements after the special string “###”. For the sample above the output will be:

Hello
Java

Note: The stdin doesn’t contain the string “###”, it is added in the main method.

To restore the original code in the editor, click the top left icon on the editor and create a new buffer.

Solution:

public class JavaIterator {
	static Iterator func(ArrayList mylist) {
		Iterator it = mylist.iterator();
		while (it.hasNext()) {
			Object element = it.next();
			if (element instanceof String)// Hints: use instanceof operator
				break;
		}
		return it;

	}

	@SuppressWarnings({ "unchecked" })
	public static void main(String[] args) {
		ArrayList mylist = new ArrayList();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < n; i++) {
			mylist.add(sc.nextInt());
		}

		mylist.add("###");
		for (int i = 0; i < m; i++) {
			mylist.add(sc.next());
		}

		Iterator it = func(mylist);
		while (it.hasNext()) {
			Object element = it.next();
			System.out.println((String) element);
		}
		sc.close();
	}
}

50. Challenge : Java Exception Handling (Try-Catch)

Exception handling is the process of responding to the occurrence, during computation, of exceptions – anomalous or exceptional conditions requiring special processing – often changing the normal flow of program execution. (Wikipedia)

Java has built-in mechanism to handle exceptions. Using the try statement we can test a block of code for errors. The catchblock contains the code that says what to do if exception occurs.

This problem will test your knowledge on try-catch block.

You will be given two integers x and y as input, you have to compute x/y. If x and y are not 32 bit signed integers or if y is zero, exception will occur and you have to report it. Read sample Input/Output to know what to report in case of exceptions.

Sample Input 0:

10
3

Sample Output 0:

Sample Input 1:

10
Hello

Sample Output 1:

java.util.InputMismatchException

Sample Input 2:

10
0

Sample Output 2:

java.lang.ArithmeticException: / by zero

Sample Input 3:

23.323
0

Sample Output 3:

java.util.InputMismatchException

Solution:

public class JavaExceptionHandlingTryCatch {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		try {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int z = x / y;
			System.out.println(z);
		} catch (ArithmeticException e) {
			System.out.println(e);
		} catch (InputMismatchException e) {
			System.out.println(e.getClass().getName());
		} finally {
			sc.close();
		}
	}
}

51. Challenge : Java Varargs – Simple Addition

You are given a class Solution and its main method in the editor.
Your task is to create the class Add and the required methods so that the code prints the sum of the numbers passed to the function add.

Note: Your add method in the Add class must print the sum as given in the Sample Output

Input Format

There are six lines of input, each containing an integer.

Output Format

There will be only four lines of output. Each line contains the sum of the integers passed as the parameters to add in the mainmethod.

Sample Input

Sample Output

1+2=3
1+2+3=6
1+2+3+4+5=15
1+2+3+4+5+6=21

Solution:

public class JavaVarargsSimpleAddition {
	public void add(int... a) {
		String b = "";
		int c = 0;
		for (int i : a) {
			b += i + "+";
			c += i;
		}
		System.out.print(b.substring(0, b.length() - 1));
		System.out.println("=" + c);

	}
}

52. Challenge : Java Reflection – Attributes

JAVA reflection is a very powerful tool to inspect the attributes of a class in runtime. For example, we can retrieve the list of public fields of a class using getDeclaredMethods().

In this problem, you will be given a class Solution in the editor. You have to fill in the incompleted lines so that it prints all the methods of another class called Student in alphabetical order. We will append your code with the Student class before running it. The Student class looks like this:

class Student{
    private String name;
    private String id;
    private String email;

    public String getName() {
        return name;
    }
    public void setId(String id) {
        this.id = id;
    }
    public void setEmail(String email) {
        this.email = email;
    }
    public void anothermethod(){  }
    ......
    ......
    some more methods
    ......
}

You have to print all the methods of the student class in alphabetical order like this:

anothermethod
getName
setEmail
setId
......
......
some more methods
......

There is no sample input/output for this problem. If you press “Run Code”, it will compile it, but it won’t show any outputs.

Hint: See the oracle docs for more details about JAVA Reflection Methods and Fields

Solution:

class Student {
	private String name;
	private String id;
	private String email;

	public String getName() {
		return name;
	}

	public void setId(String id) {
		this.id = id;
	}

	public void setEmail(String email) {
		this.email = email;
	}

	public void anothermethod() {
	}
}

public class JavaReflectionAttributes {
	public static void main(String[] args) {
		Class student = new Student().getClass();
		Method[] methods = student.getDeclaredMethods();
		ArrayList methodList = new ArrayList<>();
		for (Method m : methods) {
			methodList.add(m.getName());
		}
		Collections.sort(methodList);
		for (String name : methodList) {
			System.out.println(name);
		}
	}

}

53. Challenge : Can you Access?

You are given a class Solution and an inner class Inner.Private. The main method of class Solution takes an integer num as input. The powerof2 in class Inner.Private checks whether a number is a power of 2. You have to call the method powerof2 of the class Inner.Private from the main method of the class Solution.

Constraints

1 ≤ num ≤ 2³⁰

Sample Input

Sample Output

8 is power of 2
An instance of class: Solution.Inner.Private has been created

Solution:

public class CanYouAccess {
	public static void main(String[] args) throws Exception {
		DoNotTerminate.forbidExit();

		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int num = Integer.parseInt(br.readLine().trim());
			Object o;// Must be used to hold the reference of the instance of the class
						// Solution.Inner.Private

			// Inner i= new Inner();
			// Private p=new Private();
			/**main code starts from here*/
			CanYouAccess.Inner si = new CanYouAccess.Inner();
			o = si.new Private();
			System.out.println(num + " is " + ((CanYouAccess.Inner.Private) o).powerof2(num));
			/**main code end  here*/

			System.out.println("An instance of class: " + o.getClass().getCanonicalName() + " has been created");

		} // end of try

		catch (DoNotTerminate.ExitTrappedException e) {
			System.out.println("Unsuccessful Termination!!");
		}
	}// end of main

	static class Inner {
		private class Private {
			private String powerof2(int num) {
				return ((num & num - 1) == 0) ? "power of 2" : "not a power of 2";
			}
		}
	}// end of Inner

}// end of Solution

class DoNotTerminate { // This class prevents exit(0)

	public static class ExitTrappedException extends SecurityException {

		private static final long serialVersionUID = 1L;
	}

	public static void forbidExit() {
		final SecurityManager securityManager = new SecurityManager() {
			@Override
			public void checkPermission(Permission permission) {
				if (permission.getName().contains("exitVM")) {
					throw new ExitTrappedException();
				}
			}
		};
		System.setSecurityManager(securityManager);
	}
}

54. Challenge : Java Factory Pattern

According to Wikipedia, a factory is simply an object that returns another object from some other method call, which is assumed to be “new”.

In this problem, you are given an interface Food. There are two classes Pizza and Cake which implement the Food interface, and they both contain a method getType().

The main function in the Main class creates an instance of the FoodFactory class. The FoodFactory class contains a method getFood(String) that returns a new instance of Pizza or Cake according to its parameter.

You are given the partially completed code in the editor. Please complete the FoodFactory class.

Sample Input 1

cake

Sample Output 1

The factory returned class Cake
Someone ordered a Dessert!

Sample Input 2

pizza

Sample Output 2

The factory returned class Pizza
Someone ordered Fast Food!

Solution:

interface Food {
	public String getType();
}

class Pizza implements Food {
	public String getType() {
		return "Someone ordered a Fast Food!";
	}
}

class Cake implements Food {

	public String getType() {
		return "Someone ordered a Dessert!";
	}
}

class FoodFactory {
	public Food getFood(String order) {

		/**
		 * main code starts from here
		 */

		if (order.equalsIgnoreCase("Pizza")) {
			return new Pizza();
		} else if (order.equalsIgnoreCase("Cake")) {
			return new Cake();
		}
		return null;

		/** main code end herer */

	}// End of getFood method

}// End of factory class

public class JavaFactoryPattern {

	public static void main(String args[]) {
		Do_Not_Terminate.forbidExit();
		Scanner sc = null;
		try {

			sc = new Scanner(System.in);
			// creating the factory
			FoodFactory foodFactory = new FoodFactory();

			// factory instantiates an object
			Food food = foodFactory.getFood(sc.nextLine());

			System.out.println("The factory returned " + food.getClass());
			System.out.println(food.getType());
		} catch (Do_Not_Terminate.ExitTrappedException e) {
			System.out.println("Unsuccessful Termination!!");
		} finally {
			sc.close();
		}
	}

}

class Do_Not_Terminate {

	public static class ExitTrappedException extends SecurityException {

		private static final long serialVersionUID = 1L;
	}

	public static void forbidExit() {
		final SecurityManager securityManager = new SecurityManager() {
			@Override
			public void checkPermission(Permission permission) {
				if (permission.getName().contains("exitVM")) {
					throw new ExitTrappedException();
				}
			}
		};
		System.setSecurityManager(securityManager);
	}
}

55. Challenge : Java Singleton Pattern

“The singleton pattern is a design pattern that restricts the instantiation of a class to one object. This is useful when exactly one object is needed to coordinate actions across the system.”
– Wikipedia: Singleton Pattern

Complete the Singleton class in your editor which contains the following components:

A private Singleton non parameterized constructor.
A public String instance variable named .
Write a static method named getSingleInstance that returns the single instance of the Singleton class.

Once submitted, our hidden Solution class will check your code by taking a String as input and then using your Singleton class to print a line.

Input Format

You will not be handling any input in this challenge.

Output Format

You will not be producing any output in this challenge.

Sample Input

hello world

Sample Output

Hello I am a singleton! Let me say hello world to you

Solution:

public class JavaSingletonPattern {
	public String str = "";
	private static final JavaSingletonPattern instance=null;

	private JavaSingletonPattern() {

	}

	public static JavaSingletonPattern getSingleInstance() {
		if (instance == null)
			return new JavaSingletonPattern();
		return instance;
	}

}

56. Challenge : Covariant Return Types

Java allows for Covariant Return Types, which means you can vary your return type as long you are returning a subclass of your specified return type.

Method Overriding allows a subclass to override the behavior of an existing superclass method and specify a return type that is some subclass of the original return type. It is best practice to use the @Override annotation when overriding a superclass method.

Implement the classes and methods detailed in the diagram below:

You will be given a partially completed code in the editor where the main method takes the name of a state (i.e., WestBengal, or AndhraPradesh) and prints the national flower of that state using the classes and methods written by you.

Note: Do not use access modifiers in your class declarations.

Resources
Covariant Return Type
Java Covariant Type

Input Format

The locked code reads a single string denoting the name of a subclass of State (i.e., WestBengal, Karnataka, or AndhraPradesh), then tests the methods associated with that subclass. You are not responsible for reading any input from stdin.

Output Format

Output is handled for you by the locked code, which creates the object corresponding to the input string’s class name and then prints the name returned by that class’ national flower’s whatsYourName method. You are not responsible for printing anything to stdout.

Sample Input 0

AndhraPradesh

Sample Output 0

Lily

Solution:

public class CovariantReturnTypes {
/**
 * main code starts from here** */
	class Flower{
	    
	    public String whatsYourName(){
	        return "I have many names and types.";
	    }
	}
	class Jasmine extends Flower{
	    public String whatsYourName(){
	        return "Jasmine";
	    }
	}
	class Lily extends Flower{
	    public String whatsYourName(){
	        return "Lily";
	    }
	}
	class Lotus extends Flower{
	    public String whatsYourName(){
	        return "Lotus";
	    }
	}
	class State{
	    Flower yourNationalFlower(){
	        return new Flower();
	    }
	}
	class WestBengal extends State{
	    Jasmine yourNationalFlower(){
	        return new Jasmine();
	    }
	}
	class Karnataka extends State{
	    Lotus yourNationalFlower(){
	        return new Lotus();
	    }
	}
	class AndhraPradesh extends State{
	    Lily yourNationalFlower(){
	        return new Lily();
	    }
	    /**
	     * main code ends here  */
	}
}

57. Challenge : Prime Checker

You are given a class Solution and its main method in the editor. Your task is to create a class Prime. The class Prime should contain a single method checkPrime.

The locked code in the editor will call the checkPrime method with one or more integer arguments. You should write the checkPrime method in such a way that the code prints only the prime numbers.

Please read the code given in the editor carefully. Also please do not use method overloading!

Note: You may get a compile time error in this problem due to the statement below:

  BufferedReader br=new BufferedReader(new InputStreamReader(in));

This was added intentionally, and you have to figure out a way to get rid of the error.

Input Format

There are only five lines of input, each containing one integer.

Output Format

There will be only four lines of output. Each line contains only prime numbers depending upon the parameters passed to checkPrime in the main method of the class Solution. In case there is no prime number, then a blank line should be printed.

Sample Input

Sample Output

Solution:

public class PrimeChecker {
	public void checkPrime(int... num) {
		String str = "";
		for (int n : num) {
			boolean found = true;
			if (n <= 3 && n > 1) {
				str += n + " ";
			} else {
				for (int i = 2; i <= Math.sqrt(n); i++) {
					if (n % i == 0) {
						found = false;
						break;
					}
				}
				if (found && n != 1) {
					str += n + " ";
				}
			}
		}
		System.out.println(str);
	}
}

58. Challenge : Java Annotations

Java annotation can be used to define the metadata of a Java class or class element. We can use Java annotation at the compile time to instruct the compiler about the build process. Annotation is also used at runtime to get insight into the properties of class elements.

Java annotation can be added to an element in the following way:

@Entity
Class DemoClass{

}

We can also set a value to the annotation member. For example:

@Entity(EntityName="DemoClass")
Class DemoClass{

}

In Java, there are several built-in annotations. You can also define your own annotations in the following way:

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface FamilyBudget {
   String userRole() default "GUEST";
}

Here, we define an annotation FamilyBudget, where userRole is the only member in that custom annotation. The userRole takes only String type values, and the default is “GUEST”. If we do not define the value for this annotation member, then it takes the default. By using @Target, we can specify where our annotation can be used. For example, the FamilyBudget annotation can only be used with the method in a class. @Retention defines whether the annotation is available at runtime. To learn more about Java annotation, you can read the tutorial and oracle docs.

Take a look at the following code segment:

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface FamilyBudget {
    String userRole() default "GUEST";
}

class FamilyMember {

    public void seniorMember(int budget, int moneySpend) {
        System.out.println("Senior Member");
        System.out.println("Spend: " + moneySpend);
        System.out.println("Budget Left: " + (budget - moneySpend));
    }

    public void juniorUser(int budget, int moneySpend) {
        System.out.println("Junior Member");
        System.out.println("Spend: " + moneySpend);
        System.out.println("Budget Left: " + (budget - moneySpend));
    }
}

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int testCases = Integer.parseInt(in.nextLine());
        while (testCases > 0) {
            String role = in.next();
            int spend = in.nextInt();
            try {
                Class annotatedClass = FamilyMember.class;
                Method[] methods = annotatedClass.getMethods();
                for (Method method : methods) {
                    if (method.isAnnotationPresent(FamilyBudget.class)) {
                        FamilyBudget family = method
                                .getAnnotation(FamilyBudget.class);
                        String userRole = family.userRole();
                        int budgetLimit = family.budgetLimit();
                        if (userRole.equals(role)) {
                            if(spend<=budgetLimit){
                                method.invoke(FamilyMember.class.newInstance(),
                                        budgetLimit, spend);
                            }else{
                                System.out.println("Budget Limit Over");
                            }
                        }
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
            testCases--;
        }
    }
}

Here, we partially define an annotation,FamilyBudget and a class, FamilyMember. In this problem, we give the user role and the amount of money that a user spends as inputs. Based on the user role, you have to call the appropriate method in the FamilyMember class. If the amount of money spent is over the budget limit for that user role, it prints Budget Limit Over.

Your task is to complete the FamilyBudget annotation and the FamilyMember class so that the Solution class works perfectly with the defined constraints.

Note: You must complete the 5 incomplete lines in the editor. You are not allowed to change, delete or modify any other lines. To restore the original code, click on the top-left button on the editor and create a new buffer.

Input Format

The first line of input contains an integer N representing the total number of test cases. Each test case contains a string and an integer separated by a space on a single line in the following format:

UserRole MoneySpend

Constraints

2 ≤ N ≤ 10

0 ≤ MoneySpend ≤ 200

|UserRole| = 6

Name contains only lowercase English letters.

Output Format

Based on the user role and budget outputs, output the contents of the certain method. If the amount of money spent is over the budget limit, then output Budget Limit Over.

Sample Input

3
SENIOR 75
JUNIOR 45
SENIOR 40

Sample Output

Senior Member
Spend: 75
Budget Left: 25
Junior Member
Spend: 45
Budget Left: 5
Senior Member
Spend: 40
Budget Left: 60

Solution:

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface FamilyBudget {
	String userRole() default "GUEST";

	int moneySpend() default 100;
}

class FamilyMember {
	@FamilyBudget(userRole = "SENIOR")
	public void seniorMember(int budget, int moneySpend) {
		System.out.println("Senior Member");
		System.out.println("Spend: " + moneySpend);
		System.out.println("Budget Left: " + (budget - moneySpend));
	}

	@FamilyBudget(userRole = "JUNIOR", moneySpend = 50)
	public void juniorUser(int budget, int moneySpend) {
		System.out.println("Junior Member");
		System.out.println("Spend: " + moneySpend);
		System.out.println("Budget Left: " + (budget - moneySpend));
	}
}

public class JavaAnnotations {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int testCases = Integer.parseInt(in.nextLine());
		while (testCases > 0) {
			String role = in.next();
			int spend = in.nextInt();
			try {
				Class annotatedClass = FamilyMember.class;
				Method[] methods = annotatedClass.getMethods();
				for (Method method : methods) {
					if (method.isAnnotationPresent(FamilyBudget.class)) {
						FamilyBudget family = method.getAnnotation(FamilyBudget.class);
						String userRole = family.userRole();
						int budgetLimit = family.moneySpend();
						if (userRole.equals(role)) {
							if (budgetLimit >= spend) {
								method.invoke(FamilyMember.class.newInstance(), budgetLimit, spend);
							} else {
								System.out.println("Budget Limit Over");
							}
						}
					}
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
			testCases--;
		}
		in.close();
	}
}

59. Challenge : Java Lambda Expressions

This Java 8 challenge tests your knowledge of Lambda expressions!

Write the following methods that return a lambda expression performing a specified action:

PerformOperation isOdd(): The lambda expression must return true if a number is odd or false if it is even.
PerformOperation isPrime(): The lambda expression must return true if a number is prime or false if it is composite.
PerformOperation isPalindrome(): The lambda expression must return true if a number is a palindrome or false if it is not.

Input Format

Input is handled for you by the locked stub code in your editor.

Output Format

The locked stub code in your editor will print T lines of output.

Sample Input

The first line contains an integer, T (the number of test cases).

The T subsequent lines each describe a test case in the form of 2 space-separated integers:
The first integer specifies the condition to check for (1 for Odd/Even,2 for Prime, or 3 for Palindrome). The second integer denotes the number to be checked.

Sample Output

EVEN
PRIME
PALINDROME
ODD
COMPOSITE

Solution:

interface PerformOperation {
	boolean check(int a);
}

class MyMath {
	public static boolean checker(PerformOperation p, int num) {
		return p.check(num);
	}

	// Write your code here
	public static PerformOperation isOdd() {
		return n -> ((n & 1) == 1);
	}

	public static PerformOperation isPrime() {
		return n -> {
			if (n < 2) {
				return false;
			} else {
				int k = (int) Math.sqrt(n);
				for (int i = 2; i <= k; i++) {
					if (n % i == 0)
						return false;
				}
				return true;
			}
		};
	}

	public static PerformOperation isPalindrome() {
		return n -> {
			String org = n + "";
			String newString = new StringBuffer(org).reverse().toString();
			return org.equals(newString);
		};
	}
}

public class JavaLambdaExpressions {
	public static void main(String[] args) throws IOException {
		MyMath ob = new MyMath();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		PerformOperation op;
		boolean ret = false;
		String ans = null;
		while (T-- > 0) {
			String s = br.readLine().trim();
			StringTokenizer st = new StringTokenizer(s);
			int ch = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			if (ch == 1) {
				op = ob.isOdd();
				ret = ob.checker(op, num);
				ans = (ret) ? "ODD" : "EVEN";
			} else if (ch == 2) {
				op = ob.isPrime();
				ret = ob.checker(op, num);
				ans = (ret) ? "PRIME" : "COMPOSITE";
			} else if (ch == 3) {
				op = ob.isPalindrome();
				ret = ob.checker(op, num);
				ans = (ret) ? "PALINDROME" : "NOT PALINDROME";

			}
			System.out.println(ans);
		}
	}
}

60. Challenge : Java MD5

MD5 (Message-Digest algorithm 5) is a widely-used cryptographic hash function with a 128-bit hash value. Here are some common uses for MD5:

To store a one-way hash of a password.
To provide some assurance that a transferred file has arrived intact.

MD5 is one in a series of message digest algorithms designed by Professor Ronald Rivest of MIT (Rivest, 1994); however, the security of MD5 has been severely compromised, most infamously by the Flame malware in 2012. The CMU Software Engineering Institute essentially considers MD5 to be “cryptographically broken and unsuitable for further use”.

Given an alphanumeric string, s, denoting a password, compute and print its MD5 encryption value.

Input Format

A single alphanumeric string denoting s.

Constraints

6 ≤ |s| ≤ 20
String s consists of English alphabetic letters (i.e., [a – zA – Z] and/or decimal digits (i.e., 0 through 9) only.

Output Format

Print the MD5 encryption value of s on a new line.

Sample Input 0

HelloWorld

Sample Output 0

68e109f0f40ca72a15e05cc22786f8e6

Sample Input 1

Javarmi123

Sample Output 1

2da2d1e0ce7b4951a858ed2d547ef485

Solution:

public class JavaMD5 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		System.out.println(getMD5(s));
		sc.close();
	}

	private static String getMD5(String s) {
		StringBuffer sb = new StringBuffer();
		try {
			MessageDigest md = MessageDigest.getInstance("MD5");
			byte[] result = md.digest(s.getBytes());
			for (int i = 0; i < result.length; i++) {
				String hex = Integer.toHexString(0xff & result[i]);
				if (hex.length() == 1)
					sb.append('0');
				sb.append(hex);

			}
		} catch (NoSuchAlgorithmException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return sb.toString();
	}

}

61. Challenge : Java SHA-256

Cryptographic hash functions are mathematical operations run on digital data; by comparing the computed hash (i.e., the output produced by executing a hashing algorithm) to a known and expected hash value, a person can determine the data’s integrity. For example, computing the hash of a downloaded file and comparing the result to a previously published hash result can show whether the download has been modified or tampered with. In addition, cryptographic hash functions are extremely collision-resistant; in other words, it should be extremely difficult to produce the same hash output from two different input values using a cryptographic hash function.

Secure Hash Algorithm 2 (SHA-2) is a set of cryptographic hash functions designed by the National Security Agency (NSA). It consists of six identical hashing algorithms (i.e., SHA-256, SHA-512, SHA-224, SHA-384, SHA-512/224, SHA-512/256) with a variable digest size. SHA-256 is a 256-bit (32 byte) hashing algorithm which can calculate a hash code for an input of up to 264 – 1 bits. It undergoes 64 rounds of hashing and calculates a hash code that is a 64 -digit hexadecimal number.

Given a string, s, print its SHA-256 hash value.

Input Format

A single alphanumeric string denoting s.

Constraints

6 ≤ |s| ≤ 20
String s consists of English alphabetic letters (i.e., [a – zA – Z] and/or decimal digits (i.e., 0 through 9) only.

Output Format

Print the SHA-256 encryption value of s on a new line.

Sample Input 0

HelloWorld

Sample Output 0

872e4e50ce9990d8b041330c47c9ddd11bec6b503ae9386a99da8584e9bb12c4

Sample Input 1

Javarmi123

Sample Output 1

f1d5f8d75bb55c777207c251d07d9091dc10fe7d6682db869106aacb4b7df678

Solution:

public class JavaSHA256 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		System.out.println(getSHAHEX(s));
		sc.close();
	}

	private static String getSHAHEX(String s) {
		StringBuffer sb = new StringBuffer();
		try {
			MessageDigest digest = MessageDigest.getInstance("SHA-256");
			byte[] result = digest.digest(s.getBytes());
			for (int i = 0; i < result.length; i++) {
				String hex = Integer.toHexString(0xff & result[i]);
				if (hex.length() == 1)
					sb.append('0');
				sb.append(hex);
			}

		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}

		return sb.toString();
	}

}

62. Challenge : Java Visitor Pattern

Note: In this problem you must NOT generate any output on your own. Any such solution will be considered as being against the rules and its author will be disqualified. The output of your solution must be generated by the uneditable code provided for you in the solution template.

An important concept in Object-Oriented Programming is the open/closed principle, which means writing code that is open to extension but closed to modification. In other words, new functionality should be added by writing an extension for the existing code rather than modifying it and potentially breaking other code that uses it. This challenge simulates a real-life problem where the open/closed principle can and should be applied.

A Tree class implementing a rooted tree is provided in the editor. It has the following publicly available methods:

getValue(): Returns the value stored in the node.
getColor(): Returns the color of the node.
getDepth(): Returns the depth of the node. Recall that the depth of a node is the number of edges between the node and the tree’s root, so the tree’s root has depth 0 and each descendant node’s depth is equal to the depth of its parent node +1.

In this challenge, we treat the internal implementation of the tree as being closed to modification, so we cannot directly modify it; however, as with real-world situations, the implementation is written in such a way that it allows external classes to extend and build upon its functionality. More specifically, it allows objects of the TreeVis class (a Visitor Design Pattern) to visit the tree and traverse the tree structure via the accept method.

There are two parts to this challenge.

Part I: Implement Three Different Visitors

Each class has three methods you must write implementations for:

getResult(): Return an integer denoting the result, which is different for each class:
- The SumInLeavesVisitor implementation must return the sum of the values in the tree’s leaves only.
- The ProductRedNodesVisitor implementation must return the product of values stored in all red nodes, including leaves, computed modulo 10⁹+ 7. Note that the product of zero values is equal to 1.
- The FancyVisitor implementation must return the absolute difference between the sum of values stored in the tree’s non-leaf nodes at even depth and the sum of values stored in the tree’s green leaf nodes. Recall that zero is an even number.
visitNode(TreeNode node): Implement the logic responsible for visiting the tree’s non-leaf nodes such that the getResultmethod returns the correct result for the implementing class’ visitor.
visitLeaf(TreeLeaf leaf): Implement the logic responsible for visiting the tree’s leaf nodes such that the getResultmethod returns the correct result for the implementing class’ visitor.

Part II: Read and Build the Tree

Read the n-node tree, where each node is numbered from 1 to n. The tree is given as a list of node values (), a list of node colors (), and a list of edges. Construct this tree as an instance of the Tree class. The tree is always rooted at node number .

Your implementations of the three visitor classes will be tested on the tree you built from the given input.

Input Format

The first line contains a single integer, , denoting the number of nodes in the tree. The second line contains space-separated integers describing the respective values of x_1,x₂,…,x_n. The third line contains n space-separated binary integers describing the respective values of c_1,c₂,…,c_n. Each c_i denotes the color of the i^th node, where 0 denotes red and 1 denotes green.
Each of the n – 1 subsequent lines contains two space-separated integers, u_i and v_i , describing an edge between nodes u_iand v_i .

Constraints

2 ≤ n ≤ 10⁵
1 ≤ x_i ≤ 10³
c_i ∈ {0,1}
1 ≤ v_i,u_i ≤ n
It is guaranteed that the tree is rooted at node 1.

Output Format

Do not print anything to stdout, as this is handled by locked stub code in the editor. The three getResult() methods provided for you must return an integer denoting the result for that class’ visitor (defined above). Note that the value returned by ProductRedNodesVisitor‘s getResult method must be computed modulo 10⁹+ 7.

Sample Input

Sample Output

24
40
15

Solution:

enum Color {
	RED, GREEN
}

abstract class Tree {

	private int value;
	private Color color;
	private int depth;

	public Tree(int value, Color color, int depth) {
		this.value = value;
		this.color = color;
		this.depth = depth;
	}

	public int getValue() {
		return value;
	}

	public Color getColor() {
		return color;
	}

	public int getDepth() {
		return depth;
	}

	public abstract void accept(TreeVis visitor);
}

class TreeNode extends Tree {

	private ArrayList children = new ArrayList<>();

	public TreeNode(int value, Color color, int depth) {
		super(value, color, depth);
	}

	public void accept(TreeVis visitor) {
		visitor.visitNode(this);

		for (Tree child : children) {
			child.accept(visitor);
		}
	}

	public void addChild(Tree child) {
		children.add(child);
	}
}

class TreeLeaf extends Tree {

	public TreeLeaf(int value, Color color, int depth) {
		super(value, color, depth);
	}

	public void accept(TreeVis visitor) {
		visitor.visitLeaf(this);
	}
}

abstract class TreeVis {
	public abstract int getResult();

	public abstract void visitNode(TreeNode node);

	public abstract void visitLeaf(TreeLeaf leaf);

}

class SumInLeavesVisitor extends TreeVis {
	private int result = 0;

	public int getResult() {
		return result;
	}

	public void visitNode(TreeNode node) {
		// do nothing
	}

	public void visitLeaf(TreeLeaf leaf) {
		result += leaf.getValue();
	}
}

class ProductOfRedNodesVisitor extends TreeVis {
	private long result = 1;
	private final int M = 1000000007;

	public int getResult() {
		return (int) result;
	}

	public void visitNode(TreeNode node) {
		if (node.getColor() == Color.RED) {
			result = (result * node.getValue()) % M;
		}
	}

	public void visitLeaf(TreeLeaf leaf) {
		if (leaf.getColor() == Color.RED) {
			result = (result * leaf.getValue()) % M;
		}
	}
}

class FancyVisitor extends TreeVis {
	private int nonLeafEvenDepthSum = 0;
	private int greenLeavesSum = 0;

	public int getResult() {
		return Math.abs(nonLeafEvenDepthSum - greenLeavesSum);
	}

	public void visitNode(TreeNode node) {
		if (node.getDepth() % 2 == 0) {
			nonLeafEvenDepthSum += node.getValue();
		}
	}

	public void visitLeaf(TreeLeaf leaf) {
		if (leaf.getColor() == Color.GREEN) {
			greenLeavesSum += leaf.getValue();
		}
	}
}

public class JavaVisitorPattern {
	static int[] values;
	static Color[] colors;
	static ArrayList[] edges;
	// each edges[i] holds arrayList of all nodes connnected to node i

	@SuppressWarnings("unchecked")
	public static Tree solve() {
		int n;
		TreeNode root;
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		values = new int[n];
		colors = new Color[n];
		for (int i = 0; i < n; i++)
			values[i] = sc.nextInt();
		for (int i = 0; i < n; i++)
			colors[i] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;

		// initialize arraylists
		edges = (ArrayList[]) new ArrayList[n + 1];
		for (int i = 1; i <= n; i++)
			edges[i] = new ArrayList();

		// read the n- 1 edges and store them in both directions
		for (int i = 0; i < n - 1; i++) {
			int edgeNode1 = sc.nextInt();
			int edgeNode2 = sc.nextInt();
			edges[edgeNode1].add(edgeNode2);
			edges[edgeNode2].add(edgeNode1);
		}
		sc.close();
		root = new TreeNode(values[0], colors[0], 0); // root is always internal
		addChildren(root, 1);
		return root;
	}

	public static void addChildren(Tree node, Integer nodeNumber) {
		// for all edges coming out of this node
		for (Integer otherNodeNumber : edges[nodeNumber]) {
			Tree otherNode;
			if (edges[otherNodeNumber].size() > 1)
				// new internal node
				otherNode = new TreeNode(values[otherNodeNumber - 1], colors[otherNodeNumber - 1], node.getDepth() + 1);
			else
				// new leaf
				otherNode = new TreeLeaf(values[otherNodeNumber - 1], colors[otherNodeNumber - 1], node.getDepth() + 1);
			((TreeNode) node).addChild(otherNode);
			edges[otherNodeNumber].remove(nodeNumber); // remove reverse edge
			if (otherNode instanceof TreeNode)
				addChildren(otherNode, otherNodeNumber);
		}
	}

	public static void main(String[] args) {
		Tree root = solve();
		SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
		ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
		FancyVisitor vis3 = new FancyVisitor();

		root.accept(vis1);
		root.accept(vis2);
		root.accept(vis3);

		int res1 = vis1.getResult();
		int res2 = vis2.getResult();
		int res3 = vis3.getResult();

		System.out.println(res1);
		System.out.println(res2);
		System.out.println(res3);
	}
}

Task

Input Format

Sample Output

So = []

Solution:

Part I: Implement Three Different Visitors

Part II: Read and Build the Tree

Related Articles

Responses