ds

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

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:

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

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

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>();
}
}
void putValue(int x, int y, int N) {
int rowIndex = (x ^ lastAns) % N;
}
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 Output Format Print a single line of nspace-separated integers denoting the final state of the array after performing d left rotations.

5 4
1 2 3 4 5

5 1 2 3 4


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.

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>();
}
}
void putValue(int x, int y, int N) {
int rowIndex = (x ^ lastAns) % N;
} 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 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]

• 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 1and 10^6
•  (inclusive).

Print each element of the sorted array on a new line. 6 31415926535897932384626433832795 1 3 10 3 5 Sample Output 0 1 3 3 5 10 31415926535897932384626433832795 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 18 1 2 100 12303479849857341718340192371 3084193741082937 3084193741082938 111 200</sp

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

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 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: [2222(]).
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 FormatThe 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.

ConstraintsOutput Format

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

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

5


Explanation

• Initially, the stacks look like this:

• 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).

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

• 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.
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.
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 : 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
Output Format
Your function should return a single integer denoting the height of the binary tree.
Sample Input
Sample Output
3

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:
     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>();
while (!q.isEmpty()) {
Node currentNode = q.poll();
System.out.print(currentNode.data + " ");
if (currentNode.left != null)
if (currentNode.right != null)
}
}
}

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
, 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 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.
5 383 484 392 975 321 321 975 392 484 383 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) {
} else {
}
}
}

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

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

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

• 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
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) {
return newNode;
} else {
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;
}
}
}
}

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
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) {
} else {
while (current != null) {
if (++counter == position) {
prev.next = current.next;
break;
}
prev = current;
current = current.next;
}
}
}
}

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

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
1
5
1
2
3
4
5
Sample Output5 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)
Node remaing = Reverse(head.next);
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
, 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;
}
while (headA != null && headB != null) {
return 0;
} else {
}
}
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
, 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;
}
if (headA == null && headB == null)
return null;
else if (headA != null && headB == null)
else if (headA == null && headB != null)
} else {
}
}
}


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

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

Hackerearth-General Programming

1. Challenge: Solve Me First Complete the function solveMeFirst to compute the sum of two integers. Function prototype: int solveMeFirst(int a, int b); where, a is the…

Hackerearth-Algorithm

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

Hackerearth-Java

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

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…

Java Programming Question

1. Wap to print Fibonnaci series eg 1 1 2 3 5 8 …. up to a given number 2. Wap to check if…

Ask Us How You Can Get Your First Dream Job

Fill in the form below to book a 30 min no-obligation consulting session.