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

public class EquilibriumPoint {

int findEquilibrium(int [] A, int n){
int sum = 0; // initialize sum of whole array
int leftsum = 0; // initialize leftsum

/* Find sum of the whole array */
for (int i = 0; i < n; ++i){
sum += A[i];
}

for (int i = 0; i < n; ++i) {
sum -= A[i]; // sum is now right sum for index i
if (leftsum == sum){
return i;
}
leftsum += A[i];
}

/* If no equilibrium index found, then return 0 */
return -1;
}

public static void main(String[] args) {
EquilibriumPoint ep = new EquilibriumPoint();
int [] ar = {1};
int n = ar.length;
int [] ar2 = {1,3,5,2,2};
int n2 = ar2.length;
int result1 = ep.findEquilibrium(ar, n);
int result2 = ep.findEquilibrium(ar2, n2);
System.out.println(result1);
System.out.println(result2);
}
}
Output :
0
2

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 max_from_right = arr[arr.length - 1];
System.out.print(max_from_right + " ");

for(int i = arr.length-2; i>=0; i--){
if(max_from_right < arr[i]){
max_from_right = arr[i];
System.out.print(max_from_right + " ");
}
}
}

public static void main(String[] args) {
LeadersInArray lead = new LeadersInArray();
int arr1[] = {16, 17, 4, 3, 5, 2};
int arr2[] = {1, 2, 3, 4, 0};
lead.printLeaders(arr1);
lead.printLeaders(arr2);
}
}
Output :
2 5 17
0 4

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

public class ReverseWordsInString {

void reverseWords(String str){
String [] words = str.split(".");
for(int i = words.length-1; i>=0; i--){
System.out.print(words[i]+".");
}
System.out.println();
}

public static void main(String[] args) {
ReverseWordsInString rs = new ReverseWordsInString();
String str = "i.like.this.program.very.much";
String str2 = "pqr.mno";
rs.reverseWords(str);
rs.reverseWords(str2);
}
}​
Output :
much.very.program.this.like.i
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.Arrays;

public class RemoveDuplicatesFromString {
static char[] removeDuplicatesFromString(String string)
{

int[] table = new int[256];
char[] chars = string.toCharArray();

int endIndex = 0;

for(int i = 0; i < chars.length; i++)
{
if(table[chars[i]] == 0)
{
table[chars[i]] = -1;
chars[endIndex++] = chars[i];
}
}

return Arrays.copyOfRange(chars, 0, endIndex);
}

public static void main(String[] args)
{
String str1 = "mathamatic";
String str2 = "skill lync courses";
System.out.println(removeDuplicatesFromString(str1));
System.out.println(removeDuplicatesFromString(str2));
}
}
Output :
mathtic
skil yncoure

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

public class FindMiddleOFLL {
static Node head;
int count = 0;

public Node createNode(int data, Node head){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return head;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

void findMiddle(Node head){
Node slow_ptr = head;
Node fast_ptr = head;
if(head!=null){
while(fast_ptr!=null && fast_ptr.next!=null){
slow_ptr = slow_ptr.next;
fast_ptr = fast_ptr.next.next;
}
System.out.println(slow_ptr.data);
}
}

public static void main(String[] args) {
FindMiddleOFLL ll = new FindMiddleOFLL();
head = ll.createNode(1, head);
head = ll.createNode(2, head);
head = ll.createNode(3, head);
head = ll.createNode(4, head);
head = ll.createNode(5, head);
head = ll.createNode(6, head);

ll.findMiddle(head);
}
}
Output :
4

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

public class ReverseLinkedList {
static Node head;

public Node createNode(int data, Node head){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return head;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

Node reverseLL(Node head){
Node prev = null;
Node current = head;
Node next;

while(current!=null){
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}

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

public static void main(String[] args) {
ReverseLinkedList rll = new ReverseLinkedList();
head = rll.createNode(1, head);
head = rll.createNode(2, head);
head = rll.createNode(3, head);
head = rll.createNode(4, head);
rll.printList(head);
head = rll.reverseLL(head);
System.out.println();
rll.printList(head);
}
}
Output :
1 --> 2 --> 3 --> 4 --> NULL
4 --> 3 --> 2 --> 1 --> NULL

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

public class PairwiseSwapLL {
static Node head;

Node pairwiseSwap(Node head){
Node temp = head;

while(temp !=null && temp.next != null){
swap(temp, temp.next);
temp = temp.next.next;
}
return head;
}

void swap(Node n1, Node n2){
int temp = n1.data;
n1.data = n2.data;
n2.data = temp;
}

public Node createNode(int data, Node head){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return head;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

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

public static void main(String[] args) {
PairwiseSwapLL ps = new PairwiseSwapLL();
head = ps.createNode(1, head);
head = ps.createNode(2, head);
head = ps.createNode(3, head);
head = ps.createNode(4, head);

ps.printList(head);
ps.pairwiseSwap(head);
ps.printList(head);
}

}
Output :
1-->2-->3-->4-->NULL
2-->1-->4-->3-->NULL

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

class Node{
int data;
Node next;

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

public class addTwoNosRepresentedByLL {
static Node head1, head2, head3, head4;

public Node createNode(int data, Node head){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return head;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

static Node reverseLL(Node head){
Node prev = null;
Node current = head;
Node next;

while(current!=null){
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}

Node addTwoLists(Node first, Node second)
{

Node res = null;
Node prev = null;
Node temp = null;
int carry = 0, sum;

while (first != null || second != null) {

sum = carry + (first != null ? first.data : 0) + (second != null ? second.data : 0);

carry = (sum >= 10) ? 1 : 0;

sum = sum % 10;

temp = new Node(sum);

if (res == null) {
res = temp;
}

else {
prev.next = temp;
}

prev = temp;

if (first != null) {
first = first.next;
}
if (second != null) {
second = second.next;
}
}

if (carry > 0) {
temp.next = new Node(carry);
}

return res;
}

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

public static void main(String[] args)
{
addTwoNosRepresentedByLL list = new addTwoNosRepresentedByLL();

head1 = list.createNode(4, head1);
head1 = list.createNode(5, head1);
System.out.print("First List is ");
list.printList(head1);

head2 = list.createNode(3, head2);
head2 = list.createNode(4, head2);
head2 = list.createNode(5, head2);
System.out.print("Second List is ");
list.printList(head2);

Node Rhead1 = reverseLL(head1);
Node Rhead2 = reverseLL(head2);

Node rs = list.addTwoLists(Rhead1, Rhead2);
Node result = reverseLL(rs);
System.out.print("Resultant List is ");
list.printList(result);

System.out.println();

addTwoNosRepresentedByLL list2 = new addTwoNosRepresentedByLL();

head3 = list2.createNode(6, head3);
head3 = list2.createNode(3, head3);
System.out.print("First List is ");
list.printList(head3);

head4 = list2.createNode(7, head4);
System.out.print("Second List is ");
list.printList(head4);

Node Rhead3 = reverseLL(head3);
Node Rhead4 = reverseLL(head4);

Node rs2 = list.addTwoLists(Rhead3, Rhead4);
Node result2 = reverseLL(rs2);
System.out.print("Resultant List is ");
list.printList(result2);
}
}

Output :
First List is 4 5
Second List is 3 4 5
Resultant List is 3 9 0

First List is 6 3
Second List is 7
Resultant List is 7 0

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

class Node {
int key;
Node left, right;

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

public class BinaryTreeToDLL {
Node root, 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.key + "==");
node = node.right;
}
}

public static void main(String[] args)
{
BinaryTreeToDLL tree = new BinaryTreeToDLL();
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);

tree.BinaryTree2DoubleLinkedList(tree.root);

tree.printList(tree.head);

}
}
Output :
25==12==30==10==36==15

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)

class Graph {

class Edge {
int src, dest, weight;
Edge()
{
src = dest = weight = 0;
}
};

int V, E;
Edge edge[];

Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i){
edge[i] = new Edge();
}
}

void BellmanFord(Graph graph, int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];

for (int i = 0; i < V; ++i){
dist[i] = Integer.MAX_VALUE;
}
dist[src] = 0;

for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]){
dist[v] = dist[u] + weight;
}
}
}

for (int j = 0; j < E; ++j) {
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println(-1);
return;
}
}
printArr(dist, V);
}

void printArr(int dist[], int V)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "tt" + dist[i]);
}

public static void main(String[] args)
{
int V = 5;
int E = 8;

Graph graph = new Graph(V, E);

graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;

graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;

graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;

graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;

graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;

graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;

graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;

graph.edge[7].src = 4;
graph.edge[7].dest = 3;
graph.edge[7].weight = -3;

graph.BellmanFord(graph, 0);
}
}
Output :
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1

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

import java.util.Arrays;
import java.util.HashMap;

public class MinNumberOfSwaps {
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap hM = new HashMap<>();
for(int i=0;i hM.put(nums[i], i);
}

Arrays.sort(nums);

boolean[] visited = new boolean[len];
Arrays.fill(visited, false);

int ans = 0;
for(int i=0;i

if(visited[i] || hM.get(nums[i]) == i){
continue;
}

int j = i, cycle_size = 0;
while(!visited[j]) {
visited[j] = true;

j = hM.get(nums[j]);
cycle_size++;
}

if(cycle_size > 0) {
ans += (cycle_size - 1);
}
}
return ans;
}
public static void main(String[] args){
int []a = {1, 5, 4, 3, 2};
System.out.println(minSwaps(a));
int []b = {8, 9, 16, 15};
System.out.println(minSwaps(b));
}
}
Output :
2
1

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

import java.util.Stack;

public class getMinElement {
Stack s;
Integer minEle;

getMinElement() {
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(); // Top element.

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 static void main(String[] args)
{
getMinElement s = new getMinElement();
s.push(2);
s.push(3);
s.pop();
s.getMin();
s.push(1);
s.getMin();
}
}
Output :
Number Inserted: 2
Number Inserted: 3
Top Most Element Removed: 3
Minimum Element in the stack is: 2
Number Inserted: 1
Minimum Element in the stack is: 1