Project 1
LEADERS IN AN ARRAY
Given an array of positive integers. Your task is to find the leaders in the array. An element of array is leader if it is greater than or equal to all the elements to its right side. Also, the rightmost element is always a leader. Complete the function which takes the elements of the array and prints all the leaders.
Constraints:
1 <= N <= 107
0 <=
class LeadersInArray
{
void printLeaders(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
int j;
for (j = i + 1; j < size; j++)
{
if (arr[i] <=arr[j])
break;
}
if (j == size)
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args)
{
LeadersInArray lead = new LeadersInArray();
int arr[] = new int[]{16, 17, 4, 3, 5, 2};
int n = arr.length;
lead.printLeaders(arr, n);
}
}
Output :
17 5 2
REVERSE WORDS IN A GIVEN STRING
Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots. Complete the function which takes a string S containing characters and outputs a single line containing the reversed String.
Constraints:
1 <= T <= 100
1 <= |S| <= 2000
import java.util.*;
class GFG{
static void reverse(char str[],
int start,
int end)
{
char temp;
while (start <= end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
static char[] reverseWords(char []s)
{
int start = 0;
for (int end = 0; end < s.length; end++)
{
if (s[end] == ' ')
{
reverse(s, start, end);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
reverse(s, 0, s.length - 1);
return s;
}
public static void main(String[] args)
{
String s = "i.like.this.program.very.much ";
char []p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
Output :
much.very.program.this.like.i
import java.util.*;
class GFG{
static void reverse(char str[],
int start,
int end)
{
char temp;
while (start <= end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
static char[] reverseWords(char []s)
{
int start = 0;
for (int end = 0; end < s.length; end++)
{
if (s[end] == ' ')
{
reverse(s, start, end);
start = end + 1;
}
}
reverse(s, start, s.length - 1);
reverse(s, 0, s.length - 1);
return s;
}
public static void main(String[] args)
{
String s = "pqr.mno ";
char []p = reverseWords(s.toCharArray());
System.out.print(p);
}
}
Output :
mno.pqr
REMOVE DUPLICATES
Given a string, the task is to remove duplicates from it. Expected time complexity O(n) where n is length of input string and extra space O(1) under the assumption that there are total 256 possible characters in a string. Original order of characters must be kept same. Complete the function that takes a string and prints the modified string without duplicates and same order of characters.
Constraints:
1 <= |string|<= 1000
import java.util.*;
class GFG
{
static String removeDuplicate(char str[], int n)
{
int index = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
public static void main(String[] args)
{
char str[] = "skilllync".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
Output :skilync
2.
import java.util.*;
class GFG
{
static String removeDuplicate(char str[], int n)
{
int index = 0;
for (int i = 0; i < n; i++)
{
int j;
for (j = 0; j < i; j++)
{
if (str[i] == str[j])
{
break;
}
}
if (j == i)
{
str[index++] = str[i];
}
}
return String.valueOf(Arrays.copyOf(str, index));
}
public static void main(String[] args)
{
char str[] = "skill lync courses".toCharArray();
int n = str.length;
System.out.println(removeDuplicate(str, n));
}
}
Output :
skil ync oure
FINDING MIDDLE ELEMENT IN A LINKED LIST
Given a singly linked list of N nodes. The task is to find the middle of the linked list. For example, if given linked list is 1->2->3->4->5 then the output should be 3. If there are even nodes, then there would be two middle nodes, we need to print the
second middle element. For example, if given linked list is 1 ->2->3->4->5->6 then the output should be 4.
The task is to complete the function getMiddle() which takes the list reference and returns data of the middle element of the linked list.
Expected Time Complexity: O(N).
Expected Space Complexity: O(1).
Constraints:
1 <= T <= 500
1 <= N <= 5000
class GFG {
Node head;
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
public void printNode()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.print("Null"+"\n");
}
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print("The middle element is ["
+ temp.data + "]");
System.out.println();
}
}
public static void main(String[] args)
{
GFG list = new GFG();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
list.printNode();
list.printMiddle();
}
}
}
Output :
1->2->3->4->5->NULL The middle element is [3]
2.
class GFG {
Node head;
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public void pushNode(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
public void printNode()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "->");
temp = temp.next;
}
System.out.print("Null"+"\n");
}
public int getLen()
{
int length = 0;
Node temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
public void printMiddle()
{
if (head != null) {
int length = getLen();
Node temp = head;
int middleLength = length / 2;
while (middleLength != 0) {
temp = temp.next;
middleLength--;
}
System.out.print("The middle element is ["
+ temp.data + "]");
System.out.println();
}
}
public static void main(String[] args)
{
GFG list = new GFG();
for (int i = 5; i >= 1; i--) {
list.pushNode(i);
list.printNode();
list.printMiddle();
}
}
}
Output :
2->4->6->7->5->1NULL The middle element is [7]
REVERSE A LINKED LIST
Given a linked list of N nodes. The task is to reverse this list.
Example if linkedlist is Explanation: After reversing the list, elements are.
The task is to complete the function reverseList(givenList) with givenList reference and returns the list after reversing it.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 104
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(85);
list.head.next = new Node(15);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(20);
System.out.println("Given linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
Output :
Given linked list 85 15 4 20 Reversed linked list 20 4 15 85