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≤Ai≤10^4 Where Ai is the ith 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

19

Explanation

 arr contains the following hourglasses:

image

 

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

KodNest 5

Output Format 

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

 Sample Input

2 5
1 0 5
1 1 7
1 0 3
2 1 0
2 1 1

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]

3                 

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

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:

KodNest 7.1

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

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

 

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 KodNest 8.1. When we order each string by the real-world integer value it represents, we get:

KodNest 8.2

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:

    a b k
    1 5 3
    4 8 7
    6 9 1

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

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

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

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

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

  1. The string {[()]} meets both criteria for being a balanced string, so we print YES on a new line.
  2. The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).
  3. The string {{[[(())]]}} meets both criteria for being a balanced string, so we print YES on a new line.
Solution:
import java.util.Scanner;
import java.util.Stack;
public class BalancedBrackets {
	private static String matchParenthisis(String str) {
		Stack<Character> st = new Stack<Character> ();
		char[] ch = str.toCharArray();
		for (char c : ch) {
			if (c == '{' || c == '[' || c == '(') {
				st.push(c);
			} else {
				if (c == ']' && !st.isEmpty() && st.pop() == '[') {
					continue;
				} else if (c == '}' && !st.isEmpty() && st.pop() == '{') {
					continue;
				} else if (c == ')' && !st.isEmpty() && st.pop() == '(') {
					continue;
				} else {
					return "NO";
				}
			}
		}
		if (!st.isEmpty()) {
			return "NO";
		}
		return "YES";
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int a0 = 0; a0 < t; a0++) {
			String s = in.next();
			System.out.println(matchParenthisis(s));
		}
		in.close();
	}
}

 

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

5 3 4
3 2 1 1 1
4 3 2
1 1 4 1

Sample Output

5

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 KodNest 13.1. If you join k adjacent buildings, they will form a solid rectangle of area KodNest 13.2.

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

9

Explanation

An illustration of the test case follows. 
image

Solution:
import java.util.Scanner;
import java.util.Stack;
public class LargestRectangle {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Integer> st = new Stack<Integer>();
		int n = sc.nextInt();
		int maxArea = 0;
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		for (int i = 0; i <= a.length; i++) {
			int h = (i == a.length) ? 0 : a[i];
			if (st.isEmpty() || a[st.peek()] <= h) {
				st.push(i);
			} else {
				int tp = st.pop();
				maxArea = Math.max(maxArea, a[tp] * (st.isEmpty() ? i : i - st.peek() - 1));
				i--;
			}
		}
		System.out.println(maxArea);
		sc.close();
	}
}

 

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

     1
       2
         5
        /
       3    6
         4

Sample Output

1 2 5 3 4 6 
Solution:
class PreorderTraversal {
	class Node {
		int data;
		Node left;
		Node right;
	}
	void preOrder(Node root) {
		if (root == null)
			return;
		System.out.print(root.data + " ");
		preOrder(root.left);
		preOrder(root.right);
	}
}

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

     1
       2
         5
        /
       3    6
         4

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 :

image 
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

image

Sample Output

3

Explanation

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

image

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:

     1
       2
         5
        /
       3    6
         4

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

     1
       2
         5
        /
       3    6
         4

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 :

   1
     2
       5
      /
     3    6
       4

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

   1
     2
       5
      /
     3    6
       4

Sample Output

1 2 5 6

Explanation

   1
     2
       5
      /
     3    6
       4

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 Listi 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 printfcout, 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

5
383
484
392
975
321

Sample Output

321
975
392
484
383

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.

Solution:
public class InsertANodeAtHeadOfAList {
	class Node {
		int data;
		Node next;
	}
	Node Insert(Node head, int x) {
		Node newNode = new Node();
		newNode.data = x;
		newNode.next = null;
		if (head == null) {
			head = newNode;
		} else {
			newNode.next = head;
			head = newNode;
		}
		return head;
	}
}

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

5
141
302
164
530
474

Sample Output

141
302
164
530
474

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.

Solution:
public class InsertANodeAtTheTailOfALinkedList {
	class Node {
		int data;
		Node next;
	}
	Node Insert(Node head, int data) {
		Node current = head;
		Node newNode = new Node();
		newNode.data = data;
		newNode.next = null;
		while (current.next != null) {
			current = current.next;
		}
		current.next = newNode;
		return head;
	}
}

 

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

KodNest 21.1, where KodNest 21.2 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

3
16
13
7
1
2

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

  •  
  • KodNest 22 1, 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

8
20
6
2
19
7
4
15
9
3

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

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

  •  
  • KodNest 22 1, 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

3
5
16
12
4
2
5
3
7
3
9
5
5
1
18
3
13

Sample Output

5
2
4
12
16
9
3
7
13
3
18
1
5

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.

Solution:
public class PrintInReverse {
	class Node {
		int data;
		Node next;
	}
	void ReversePrint(Node head) {
		if (head != null) {
			ReversePrint(head.next);
			System.out.println(head.data);
		}
	}
}

 

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

KodNest 24, 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

1
5
1
2
3
4
5

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

Solution:
public class ReverseALinkedList {
	class Node {
		int data;
		Node next;
	}
	Node Reverse(Node head) {
		if (head == null || head.next == null)
			return head;
		Node remaing = Reverse(head.next);
		head.next.next = head;
		head.next = null;
		return remaing;
	}
} 

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

KodNest 24, 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

2
2
1
2
1
1
2
1
2
2
1
2

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:
public class CompareTwoLinkedLists {
	class Node {
		int data;
		Node next;
	}
	int CompareLists(Node headA, Node headB) {
		while (headA != null && headB != null) {
			if (headA.data != headB.data) {
				return 0;
			} else {
				headA = headA.next;
				headB = headB.next;
			}
		}
		if ((headA == null) && (headB == null)) {
			return 1;
		} else {
			return 0;
		}
	}
}

 

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

KodNest 24, 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

1
3
1
2
3
2
3
4

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

Solution:
public class MergeTwoSortedLinkedLists {
	class Node {
		int data;
		Node next;
	}
	Node MergeLists(Node headA, Node headB) {
		if (headA == null && headB == null)
			return null;
		else if (headA != null && headB == null)
			return headA;
		else if (headA == null && headB != null)
			return headB;
		else if (headA.data < headB.data) {
			headA.next = MergeLists(headA.next, headB);
			return headA;
		} else {
			headB.next = MergeLists(headA, headB.next);
			return headB;
		}
	}
}

 

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

KodNest 26, 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

2
1
1
3
3
2
1
2

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

1
5
1
2
2
3
4

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

Solution:
public class DeleteDuplicateValueNodesFromASortedLinkedList {
	class Node {
		int data;
		Node next;
	}
	Node RemoveDuplicates(Node head) {
		Node current = head;
		while (current.next != null) {
			if (current.data == current.next.data) {
				current.next = current.next.next;
				continue;
			} else {
				current = current.next;
			}
		}
		return head;
	}
}

 

 

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

KodNest 29

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

  1. The first list has no cycle, so we return false and the hidden code checker prints 0 to stdout.
  2. The second list has a cycle, so we return true and the hidden code checker prints 1 to stdout.
Solution:
public class CycleDetection {
	class Node {
		int data;
		Node next;
	}
	int HasCycle(Node head) {
		Node p1 = head, p2 = head;
		while (p1 != null && p1.next != null && p2 != null) {
			p1 = p1.next;
			p2 = p2.next.next;
			{
				if (p1 == p2)
					return 1;
			}
		}
		return 0;
	}
}

30. Challenge-Find Merge Point of Two Lists

Given pointers to the head nodes of 2 linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.

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:

  1. head: A reference to the head of a doubly-linked list of DoublyLinkedListNode objects.
  2. 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

1
4
1
3
4
10
5

Sample Output

1 3 4 5 10

Explanation

The initial doubly linked list is: KodNest 31.1 .

The doubly linked list after insertion is: KodNest 31.2

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

1
4
1
2
3
4

Sample Output

4 3 2 1

Explanation

The initial doubly linked list is: KodNest 32.1

The reversed doubly linked list is: KodNest 31.2 1

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

  1. add name, where name is a string denoting a contact name. This must store name as a new contact in the application.
  2. 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

Explanation

We perform the following sequence of operations:

  1. Add a contact named hack.
  2. Add a contact named hackerrank.
  3. 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.
  4. 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, aababcdeaabcd 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.

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

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. 1 x: Enqueue element x into the end of the queue.
  2. 2: Dequeue the element at the front of the queue.
  3. 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

10
1 42
2
1 14
3
1 28
3
1 60
1 78
2
2

Sample Output

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

5
1 4
1 9
3
2 4
3

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.

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

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

  1.  communities containing person  and  merged (if they belong to different communities).

  2.  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

3 6
Q 1
M 1 2
Q 2
M 2 3
Q 3
Q 2

Sample Output

1
2
3
3

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

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then:
  • 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},  KodNest 40.1is the median.

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

  1. Add the ith integer to a running list of integers.
  2. Find the median of the updated list (i.e., for the first element through the ith element).
  3. 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

6
12
4
5
3
8
7

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

 

 

Related Articles

Core Java

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

Hackerearth-Java

     1. Challenge : Welcome to Java! Welcome to the world of Java! In this challenge, we practice printing to stdout. The code stubs…

Hackerearth-Algorithm

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

Responses

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

KodNest Training New Batch is starting on 21st September 2020. Attend one week free demo classes.Register Now

New Report

Close