Project 1

EQUILIBRIUM POINT

Given an array A of N positive numbers. The task is to find the position where equilibrium first occurs in the array. Equilibrium position in an array is a position such that the sum of elements before it is equal to the sum of elements after it. Complete the function whose argument is the array A and which prints the position at which the elements are at equilibrium if no equilibrium point exists print -1.

Constraints:
1 <= N <= 106
1 <= Ai <= 108

Solution for Equilibrium Point : 

Code :

package Project7;

import java.util.Scanner;

public class EquilibriumPosition {

public static void main(String[] args) {
char choice;
do {
System.out.print("Enter the array length : ");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print("Enter your array : ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int leftSum = 0;
int rightSum = 0;
for (int i = 0; i < n; i++) {
rightSum += arr[i];
}
for (int i = 0; i < n; i++) {
rightSum -= arr[i];
if (leftSum == rightSum) {
System.out.println(i + 1);

}
leftSum += arr[i];
}

{
System.out.println("Do You Want To Continue(Y/N) : ");
}
choice = sc.next().charAt(0);

} while (choice == 'Y' || choice == 'y');
}
}

Output :

Enter the array length : 1
Enter your array : 1
1
Do You Want To Continue(Y/N) :
y
Enter the array length : 5
Enter your array : 1 3 5 2 2
3
Do You Want To Continue(Y/N) :
n

Explain :

• We take the number of elements in the array as input and then the elements of the array.
• Next, we initialize two variables leftSum and rightSum to store the sum of elements to the left and right of the current index, respectively.
• We first calculate the sum of all elements in the array and store it in rightSum.
• Then, we traverse the array and update the leftSum and rightSum variables at each iteration.
• If the leftSum becomes equal to the rightSum, we print the current index + 1 as the first equilibrium position and return. 

----------------------------------------------------------------------------------------------------------------------------------------------

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

Ai <= 107

String

Solution FOR LEADERS IN AN ARRAY :

Code :

package Project7;

import java.util.ArrayList;
import java.util.Scanner;

public class LeadersInArray {
public static void main(String[] args) {
char choice;
do {
System.out.print("Enter the array length : ");
@SuppressWarnings("resource")

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.print("Enter array : ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
ArrayList result = new ArrayList<>();
int max = Integer.MIN_VALUE;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] >= max) {
result.add(arr[i]);
max = arr[i];
}
}
for (int i = result.size() - 1; i >= 0; i--) {
System.out.print(result.get(i) + " ");
}

{
System.out.println("Do You Want To Continue(Y/N) : ");
}
choice = sc.next().charAt(0);

} while (choice == 'Y' || choice == 'y');
}

}

Output :

Enter the array length : 6
Enter array : 16 17 4 3 5 2
17 5 2

Do You Want To Continue(Y/N) :
Y
Enter the array length : 5
Enter array : 1 2 3 4 0
4 0

Do You Want To Continue(Y/N) :
n
 

Explain : 

1. We first take the number of elements in the array as input and then the elements of the array.
2. Next, we initialize an ArrayList result to store the leaders, and a variable max to store the maximum element.
3. We traverse the array in reverse order and check if the current element is greater than or equal to the max variable. If yes, we add it to the result and update the max variable.
4. Finally, we print the elements of result in reverse order, which gives us the leaders in the original array.

----------------------------------------------------------------------------------------------------------------------------------------------

 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

Solution  FOR REVERSE WORDS IN A GIVEN STRING :

Code :

package Project7;

import java.util.Scanner;

public class ReverseWordInAGivenString {
public static void main(String[] args) {
char choice;
do {
System.out.print("Enter your String : ");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] words = s.split("\\.");
StringBuilder result = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
result.append(words[i]);
if (i > 0) {
result.append(".");
}
}
System.out.println("Reverse word for given String are : " + result);

{
System.out.println("do you want to continiue(Y/N) : ");
}
choice = sc.next().charAt(0);
} while (choice == 'Y' || choice == 'y');

}
}

Output :

Enter your String : i.like.this.program.very.much
Reverse word for given String are : much.very.program.this.like.i
do you want to continiue(Y/N) :
y
Enter your String : ppr.mno
Reverse word for given String are : mno.ppr
do you want to continiue(Y/N) :
n

Explain :

1. We take the input string as s and split it into words using the split method, with the delimiter as ".". The result is stored in an array of strings words.
2. We create a StringBuilder result to store the reversed string.
3. We traverse the words array in reverse order and append each word to the result. We also append a "." after each word, except for the last word.
4. Finally, we print the result which gives us the reversed string with the words in their original order.

----------------------------------------------------------------------------------------------------------------------------------------------

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

Solution  for Remove Duplicates charecters : 

Code :

package Project7;

import java.util.Scanner;

public class RemoveDuplicates {
public static void main(String[] args) {
char choice;
do {
System.out.print("Enter your String : ");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
boolean[] seen = new boolean[256];
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!seen[c]) {
result.append(c);
seen[c] = true;
}
}
System.out.println("After remove Dublicates char : " + result);

{
System.out.println("Do You Want To Continue(Y/N) : ");
}
choice = sc.next().charAt(0);

} while (choice == 'Y' || choice == 'y');

}
}

Output :

Enter your String : skilllync
After remove Dublicates char : skilync
Do You Want To Continue(Y/N) :
y
Enter your String : skill lync courses
After remove Dublicates char : skil yncoure

Explain : 

1. We take the input string as s
2. We create a boolean array seen of size 256, where each index represents a character in the ASCII set.
3. We create a StringBuilder result to store the modified string.
4. We traverse the input string s and check if the character at the current index has been seen before.
5. If the character has not been seen before, we append it to the result and set its corresponding index in the seen array to true.
6. If the character has been seen before, we do not append it to the result.
7. Finally, we print the result which gives us the modified string without duplicates and in the same order as the original string.

----------------------------------------------------------------------------------------------------------------------------------------------

LinkedList

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

Solution for FINDING MIDDLE ELEMENT IN A LINKED LIST :

Code :

Output :

Explain :

• In the LinkedList class, we have a head node and a count variable to keep track of the number of elements in the linked list.
• The getMiddle() function takes the head of the linked list as input and returns the data of the middle element.
• We use two pointers, slow and fast, to traverse the linked list. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer would have reached the middle of the linked list.
• The add() function adds a new node to the linked list. The new node becomes the head of the linked list and the count is incremented.
• The printList() function prints the linked list.
• In the main() function, we take the input for the number of elements in the linked list and add them to the linked list. Then we call the getMiddle() function to get the middle element of the linked list and print it.

----------------------------------------------------------------------------------------------------------------------------------------------

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

Solution :

Code :

package Project7;

public class ReverseLinkList {

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

@SuppressWarnings("static-access")
public static void main(String[] args) {
ReverseLinkList list = new ReverseLinkList();
list.head = new Node(6);
list.head.next = new Node(5);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(3);
list.head.next.next.next.next = new Node(2);
list.head.next.next.next.next.next = new Node(1);

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);
{
ReverseLinkList list1 = new ReverseLinkList();
list1.head = new Node(20);
list1.head.next = new Node(40);
list1.head.next.next = new Node(60);
list1.head.next.next.next = new Node(70);
list1.head.next.next.next.next = new Node(50);
list1.head.next.next.next.next.next = new Node(10);

System.out.println("Given linked list1");
list1.printList(head);
head = list1.reverse(head);
System.out.println("");
System.out.println("Reversed linked list1 ");
list1.printList(head);
}
}
}

Output :

Given linked list
6 5 4 3 2 1
Reversed linked list
1 2 3 4 5 6 Given linked list1
20 40 60 70 50 10
Reversed linked list1
10 50 70 60 40 20 

----------------------------------------------------------------------------------------------------------------------------------------------

PAIRWISE SWAP ELEMENTS OF A LINKED LIST

Given a singly linked list of size N. The task is to swap elements in the linked list pairwise. For example, if the input list is 1 2 3 4, the resulting list after swaps will be 2 1 4 3.

Complete the function pairWiseSwap() which takes the the linked list and retu rns the modified linked list after swapping pairwise nodes.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 103

Solution for PAIRWISE SWAP ELEMENTS OF A LINKED LIST

Code :

package Project7;

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

public class PairwiseSwap {
static Node head;

@SuppressWarnings("static-access")
public static void main(String[] args) {
PairwiseSwap list = new PairwiseSwap();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(2);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(7);
list.head.next.next.next.next.next.next.next = new Node(8);
System.out.println("Original linked list:");
list.printList();
list.head = list.pairWiseSwap(head);
System.out.println("\nModified linked list:");
list.printList();
}

Node pairWiseSwap(Node head) {
Node current = head;
while (current != null && current.next != null) {
int temp = current.data;
current.data = current.next.data;
current.next.data = temp;
current = current.next.next;
}
return head;
}

void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
}

Output :

Original linked list:
1 2 2 4 5 6 7 8
Modified linked list:
2 1 4 2 6 5 8 7 

Explain : 

1. The Node class represents a node in the linked list, which contains an integer data and a reference to the next node next.
2. The LinkedList class represents a linked list, which contains a reference to the head node head.
3. The pairWiseSwap method swaps the elements in the linked list pairwise by using a temp pointer that starts from the head of the linked list.
4. The while loop continues until the temp pointer is null or the temp.next pointer is null.
5. Inside the while loop, we swap the elements of the current pair by using a temporary variable k.
6. We then advance the temp pointer by 2 to reach the next pair.
7. The printList method prints the elements of the linked list by using a temp pointer that starts from the head of the linked list.
8. The main method creates a linked list, prints the linked list before and after the pairwise swap, and calls the pairWiseSwap method.

----------------------------------------------------------------------------------------------------------------------------------------------

ADD TWO NUMBERS REPRESENTED BY LINKED LISTS

Given two numbers represented by two linked lists of size N and M. The task is to return a sum list. The sum list is a linked list representation of the addition of two input numbers.

Complete the function addTwoLists() which takes both the linked lists and returns the new list.

Expected Time Complexity: O(N) + O(M)
Expected Auxiliary Space: O(N) + O(M)

Constraints:
1 <= N, M <= 5000

Solution :

Code :

package Project7;

public class LinkedList {

static Node head1, head2;

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;

addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
printList(result.next);
}

private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}

private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}

void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}

@SuppressWarnings("static-access")
public static void main(String[] args) {
LinkedList list = new LinkedList();

// creating first list
list.head1 = new Node(4);
list.head1.next = new Node(5);
System.out.print("First one list is ");
list.printList(head1);

// creating second list
list.head2 = new Node(3);
list.head2.next = new Node(4);
list.head2.next.next = new Node(5);
System.out.print("Second one list is ");
list.printList(head2);

System.out.print("Resultant list is ");

list.addTwoLists(head1, head2);
System.out.println("-------------------------------------------");
{
LinkedList list1 = new LinkedList();

// creating first list
list1.head1 = new Node(6);
list1.head1.next = new Node(3);
System.out.print("First next list is ");
list1.printList(head1);

// creating second list
list1.head2 = new Node(7);
System.out.print("Second next list is ");
list1.printList(head2);

System.out.print("Resultant list is ");

list1.addTwoLists(head1, head2);
}
}

}

Output :

First one list is 4 5
Second one list is 3 4 5
Resultant list is 3 9 0
-------------------------------------------
First next list is 6 3
Second next list is 7
Resultant list is 7 0

----------------------------------------------------------------------------------------------------------------------------------------------

Trees

BINARY TREE TO DLL

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In -Place. The left and right references in nodes are to be used as previous and next references respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.

Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL .

Expected Time Complexity: O(N).
Expected Space Complexity : O(H). H is the height of the tree and this space is used implicitly for recursion stack.

Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000

Solution :

Code :

package Project7;

class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
left = right = null;
}
}

public class BinaryTreeDdl {
Node root;

Node head;

static Node prev = null;

void BinaryTree2DoubleLinkedList(Node root) {

if (root == null)
return;

BinaryTree2DoubleLinkedList(root.left);

if (prev == null)
head = root;
else {
root.left = prev;
prev.right = root;
}
prev = root;

BinaryTree2DoubleLinkedList(root.right);
}

void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.right;
}
}

// Driver program to test above functions
public static void main(String[] args) {
// Let us create the tree as shown in above diagram
BinaryTreeDdl tree = new BinaryTreeDdl();
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);

// convert to DLL
tree.BinaryTree2DoubleLinkedList(tree.root);

// Print the converted List
tree.printList(tree.head);

}
}

Output :

25 12 30 10 36 15 

----------------------------------------------------------------------------------------------------------------------------------------------

Graph

BELLMAN FORD ALGORITHM

Implement the Bellman Ford Algorithm to find Shortest paths to all vertices from a single source.

Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.

If there is a negative weight cycle then print -1

Expected Time Complexity- O(VE)

MINIMUM SWAPS TO SORT

Given an array of integers. Find the minimum number of swaps required to sort the array in non-decreasing order.

complete the function minSwaps() which takes the array arr[] and prints the minimum number of swaps required to sort the array. If the array is already sorted, return 0.

Constraints:
1 <= size of A <= 105
1 <= A[] <= 106

Expected Time Complexity: O(NlogN).
Expected Space Complexity : O(N).

Solution :

Code :

Output :

Explain :

----------------------------------------------------------------------------------------------------------------------------------------------

Stacks Queues

GET MINIMUM ELEMENT FROM STACK

You are given N elements and your task is to Implement a Stack in which you can get minimum element in O(1) time.

Complete the three methods push() which take one argument an integer 'x' to be pushed into the stack, pop() which returns a integer popped out from the stack and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)

Expected Time Complexity : O(1) for all the 3 methods.
Expected Space Complexity : O(1) for all the 3 methods.

Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

Solution FOR GET MINIMUM ELEMENT FROM STACK :

Code :

package Project7;

import java.util.Stack;

class MyStack {
Stack s;
Integer minEle;

MyStack() {
s = new Stack();
}

void getMin() {

if (s.isEmpty())
System.out.println("Stack is empty");

else
System.out.println("Minimum Element in the " + " stack is: " + minEle);
}

void peek() {
if (s.isEmpty()) {
System.out.println("Stack is empty ");
return;
}

Integer t = s.peek();

System.out.print("Top Most Element is: ");

if (t < minEle)
System.out.println(minEle);
else
System.out.println(t);
}

void pop() {
if (s.isEmpty()) {
System.out.println("Stack is empty");
return;
}

System.out.print("Top Most Element Removed: ");
Integer t = s.pop();

if (t < minEle) {
System.out.println(minEle);
minEle = 2 * minEle - t;
}

else
System.out.println(t);
}

void push(Integer x) {
if (s.isEmpty()) {
minEle = x;
s.push(x);
System.out.println("Number Inserted: " + x);
return;
}

if (x < minEle) {
s.push(2 * x - minEle);
minEle = x;
}

else
s.push(x);

System.out.println("Number Inserted: " + x);
}
};

public class MinimumElementFromStack {
public static void main(String[] args) {
MyStack s = new MyStack();

s.push(2);
s.push(3);
s.getMin();
s.push(1);
s.getMin();

}
}

Output :

 Number Inserted: 2
Number Inserted: 3
Minimum Element in the stack is: 2
Number Inserted: 1
Minimum Element in the stack is: 1

----------------------------------------------------------------------------------------------------------------------------------------------