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 spaceseparated 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 spaceseparated integers describing A.
Constraints
 1≤N≤10^{^3}
 1≤A_{i}≤10^{^4} Where A_{i} is the i^{th} Integer in A
Output Format
Print all N integers in A in reverse order as a single line of spaceseparated 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 spaceseparated 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 0indexing.
 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:
 Query: lx y
 Find the sequence,seq, at index ( (x EB lastAnswer) 3 N ) in seqList.
 Append integer y to sequence seq.
 Query: 2 x y
 Find the sequence,seq, at index ( (x EB lastAnswer) 3 N ) in seqList.
 Find the value of element y 3size in seq (where size is the size of seq) and assignit to last Answer.
 Print the new value of lastAnswe1·on a new line
 Query: lx y
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 spaceseparated 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>(); seqList.add(list); } } void putValue(int x, int y, int N) { int rowIndex = (x ^ lastAns) % N; seqList.get(rowIndex).add(y); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); DynamicArray da = new DynamicArray(N); for (int i = 0; i < Q; i++) { int queryType = sc.nextInt(); int x = sc.nextInt(); int y = sc.nextInt(); if (queryType == 1) { da.putValue(x, y, N); } else { da.getValue(x, y, N); } } sc.close(); } private void getValue(int x, int y, int N) { int colIndex = 0; int rowIndex = (x ^ lastAns) % N; colIndex = y % seqList.get(rowIndex).size(); lastAns = seqList.get(rowIndex).get(colIndex); System.out.println(lastAns); } }
4.Challenge Left Rotation
A left rotation operation on an array of size n shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array[1,2,3,4,5] , then the array would become[3,4,5,1,2]. Given an array of integers and a number,d , perform d left rotations on the array. Then print the updated array as a single line of spaceseparated integers.Input Format The first line contains two spaceseparated 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 spaceseparated integers describing the respective elements of the array’s initial state. Constraints Output Format Print a single line of nspaceseparated 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 spaceseparated 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>(); 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 nondecreasing, 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 realworld 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
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.ChallengeSparse Arrays
 strings – an array of strings to search
 queries – an array of query strings
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.ChallengeArray Manipulation
a b k
1 5 3
4 8 7
6 9 1
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]
 n – the number of elements in your array
 queries – a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.
5 3
1 2 100
2 5 100
3 4 100
200
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.ChallengeMaximum Element
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.
10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
26
91
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.ChallengeBalanced Brackets
(
, )
, {
, }
, [
, 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.
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
 1≤N≤10^{^3}
 1≤s≤10^{^3}, where s is the length of the sequence.
 All chracters in the sequences ∈ { {, }, (, ), [, ] }.
YES
or NO
.3
{[()]}
{[(])}
{{[[(())]]}}
YES
NO
YES
 The string
{[()]}
meets both criteria for being a balanced string, so we printYES
on a new line.  The string
{[(])}
is not balanced because the brackets enclosed by the matched pair{
and}
are not balanced:[2222(])
.  The string
{{[[(())]]}}
meets both criteria for being a balanced string, so we printYES
on a new line.
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. ChallengeEqual 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 spaceseparated 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 spaceseparated integers describing the cylinder heights in stack 1. The first element is the top of the stack.The third line contains n2 spaceseparated integers describing the cylinder heights in stack 2. The first element is the top of the stack.The fourth line contains n3 spaceseparated 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.ChallengeLargest Rectangle
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
5
1 2 3 4 5
9
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.ChallengeTree: Preorder Traversal
1
\
2
\
5
/ \
3 6
\
4
1 2 5 3 4 6
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.ChallengeTree: Inorder Traversal
1
\
2
\
5
/ \
3 6
\
4
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.ChallengeTree: Postorder Traversal
1
\
2
\
5
/ \
3 6
\
4
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.ChallengeTree: Height of a Binary Tree
 root: a reference to the root of a binary tree.
3
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.ChallengeTree: Level Order Traversal
1
\
2
\
5
/ \
3 6
\
4
For the above tree, the level order traversal is 1 > 2 > 5 > 3 > 6 > 4.void levelOrder(Node * root) {
}
1
\
2
\
5
/ \
3 6
\
4
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. ChallengeTree: Top View
1
\
2
\
5
/ \
3 6
\
4
Top View : 1 > 2 > 5 > 6void topView(node * root) {
}
1
\
2
\
5
/ \
3 6
\
4
1
\
2
\
5
/ \
3 6
\
4
From the top only nodes 1,2,5,6 will be visible.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. ChallengePrint the Elements of a Linked List
2
16
13
16
13
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. ChallengeInsert 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.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 Formatreturn
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.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. ChallengeInsert a Node at the Tail of a Linked List
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.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.5
141
302
164
530
474
141
302
164
530
474
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. ChallengeInsert a node at a specific position in a linked list
sYou’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=4s, 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
3
16
13
7
1
2
16 13 1 7
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
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. ChallengeDelete a Node
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. , where is the element i th of the linked list.
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.8
20
6
2
19
7
4
15
9
3
20 6 2 7 4 15 9
20>6>2>19>7>4>15>9
. We have to delete the node at position 3, which is 19. After deleting that node, the updated linked list is: 20>6>2>7>4>15>9
public class DeleteANode { class Node { int data; Node next; } Node Delete(Node head, int position) { Node current = head; Node prev = current; int counter = 0; if (head == null && position == 0) { return null; } if (position == 0 && head != null) { head = head.next; return head; } else { current = head.next; while (current != null) { if (++counter == position) { prev.next = current.next; break; } prev = current; current = current.next; } } return head; } }
23. ChallengePrint in Reverse
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.
 , where is the i th element in the list.
3
5
16
12
4
2
5
3
7
3
9
5
5
1
18
3
13
5
2
4
12
16
9
3
7
13
3
18
1
5
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
.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. ChallengeReverse a linked list
You’re given the pointer to the head node of a linked list. Change thenext
pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.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.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.Explanation1 5 1 2 3 4 5
Sample Output5 4 3 2 1
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. ChallengeCompare two linked lists
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.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.2
2
1
2
1
1
2
1
2
2
1
2
0
1
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. ChallengeMerge two sorted linked lists
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.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.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.1
3
1
2
3
2
3
4
1 2 3 3 4
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. ChallengeGet 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.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.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.2
1
1
3
3
2
1
2
Sample Output1
3
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. ChallengeDelete duplicatevalue 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.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.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.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; } } return head; } }
Responses