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≤A_i≤10^{^4} Where A_i is the i^th Integer in A

Output Format

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

Sample Input 1

Array: arr1432

4
1 4 3 2

Sample Output 1

2 3 4 1

Solution:

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

2.Challenge:2D Array – DS

Given a 6*6  2D Array, arr :

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

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

a b c
  d
e f g

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

For example, given the 2D array:

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

We calculate the following 16 hourglass values:

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

Our highest hourglass value is 28 from the hourglass:

0 4 3
  1
8 6 6

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

Function Description

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

hourglassSum has the following parameter(s):

• arr: an array of integers

Input Format

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

Constraints

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

Task

Given N , Q, and Q queries,execute each query. Note: is the bitwise XOR operation,which corresponds to the ‘operator in most languages. Learn more about it on Wikipedia.

Input Format

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

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

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

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

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

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, a, b, and k.

Input Format

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

Constraints

 

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

5
1 2 3 4 5

9

Explanation

An illustration of the test case follows.

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

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

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

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

Output Format

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

Sample Input

2
16
13

Sample Output

16
13

Explanation

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

Solution:

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

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

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

Input Format

You have to complete the SinglyLinkedListNode Insert(SinglyLinkedListNode head, int data) method which takes two arguments – the head of the linked list and the integer to insert. You should NOT read any input from stdin/console. The input is handled by code in the editor and is as follows: The first line contains an integer n, denoting the number of elements to be inserted at the head of the list. The next n lines contain an integer each, denoting the element to be inserted.Constraints 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) {
 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

 

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

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

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

22. Challenge-Delete a Node

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

Input Format

You have to complete the deleteNode(SinglyLinkedListNode* llist, int position) method which takes two arguments – the head of the linked list and the position of the node to delete. You should NOT read any input from stdin/console. position will always be at least 0 and less than the number of the elements in the list. The first line of input contains an integer n, denoting the number of elements in the linked list. The next n lines contain an integer each in a new line, denoting the elements of the linked list in the order. The last line contains an integer position denoting the position of the node that has to be deleted form the linked list.

Constraints

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

Output Format

Delete the node at the given position and return the head of the updated linked list. Do NOT print anything to stdout/console. The code in the editor will print the updated linked list in a single line separated by spaces.

Sample Input

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

 

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

, 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

, 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

, 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;
			}
		}
		return head;
	}
}