Project 1
1)
public static int equilibriumPoint(int[] arr, int n) {
int sum = 0; // to store the total sum of the array
int leftSum = 0; // to store the sum of elements to the left of the current element
// Calculate the total sum of the array
for(int i = 0; i < n; i++) {
sum += arr[i];
}
// Check if there is an equilibrium point in the array
for(int i = 0; i < n; i++) {
sum -= arr[i]; // subtract the current element from the total sum
if(leftSum == sum) { // check if the left sum is equal to the remaining sum
return i; // return the equilibrium point
}
leftSum += arr[i]; // add the current element to the left sum
}
return -1; // no equilibrium point found
}
------------------
2)
public static void findLeaders(int[] arr) {
int n = arr.length;
int max = arr[n-1]; // initialize the maximum element to be the rightmost element
System.out.print(max + " "); // print the rightmost element as it is always a leader
for (int i = n-2; i >= 0; i--) {
if (arr[i] >= max) {
max = arr[i];
System.out.print(max + " "); // print the current leader
}
}
}
You call this function as integer
int[] arr = {16, 17, 4, 3, 5, 2};
findLeaders(arr);
O/P- 2 5 17
-------------------------------
3)
public static String reverseStringWithoutWords(String s) {
// Split the string by dots to get the individual words
String[] words = s.split("\.");
// Reverse the whole string by iterating over the characters in reverse order
StringBuilder sb = new StringBuilder();
for (int i = s.length()-1; i >= 0; i--) {
sb.append(s.charAt(i));
}
// Replace the dots in the reversed string with the individual words
int j = 0;
for (int i = 0; i < sb.length(); i++) {
if (sb.charAt(i) == '.') {
sb.replace(j, i, words[words.length-1]);
j = i+1;
words = Arrays.copyOfRange(words, 0, words.length-1);
}
}
sb.replace(j, sb.length(), words[0]); // Replace the last word
return sb.toString();
}
String s = "i.like.this.program.very.much";
String reversed = reverseStringWithoutWords(s);
System.out.println(reversed);
o/p-hcuM.yrev.margorP.siht.ekil.i
--------------------------
4)
public static String removeDuplicates(String s) {
boolean[] seen = new boolean[256]; // assume 256 possible characters in the string
LinkedList list = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!seen[c]) {
seen[c] = true;
list.add(c);
}
}
StringBuilder sb = new StringBuilder(list.size());
for (Character c : list) {
sb.append(c);
}
return sb.toString();
}
-------------------
5)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static int getMiddle(Node head) {
if (head == null) {
return -1; // return -1 if the list is empty
}
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
}
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
int middle = getMiddle(head);
System.out.println(middle);
o/p-3
---------------
6)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static Node reverseList(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
--------------------
7)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static 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;
}
--------------
8)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public static Node addTwoLists(Node first, Node second) {
Node dummy = new Node(0);
Node current = dummy;
int carry = 0;
while (first != null || second != null) {
int sum = carry;
if (first != null) {
sum += first.data;
first = first.next;
}
if (second != null) {
sum += second.data;
second = second.next;
}
current.next = new Node(sum % 10);
carry = sum / 10;
current = current.next;
}
if (carry > 0) {
current.next = new Node(carry);
}
return dummy.next;
}
------------
9)
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
class BinaryTreeToDLL {
Node prev = null, head = null;
public Node bToDLL(Node root) {
if (root == null) {
return null;
}
bToDLL(root.left);
if (prev == null) {
head = root;
} else {
prev.right = root;
root.left = prev;
}
prev = root;
bToDLL(root.right);
return head;
}
}
----------
10)
import java.util.*;
class Edge {
int src, dest, weight;
Edge() {
src = dest = weight = 0;
}
}
class Graph {
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(int src) {
int dist[] = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 1; i < V; ++i) {
for (int j = 0; j < E; ++j) {
int u = edge[j].src;
int v = edge[j].dest;
int weight = edge[j].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; ++i) {
int u = edge[i].src;
int v = edge[i].dest;
int weight = edge[i].weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("-1");
return;
}
}
for (int i = 0; i < V; ++i)
System.out.print(dist[i] + " ");
}
}
public class Main {
public static void main(String[] args) {
int V = 5, E = 8;
Graph graph = new Graph(V, E);
// add edge 0-1 (or A-B in above figure)
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = -1;
// add edge 0-2 (or A-C in above figure)
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 4;
// add edge 1-2 (or B-C in above figure)
graph.edge[2].src = 1;
graph.edge[2].dest = 2;
graph.edge[2].weight = 3;
// add edge 1-3 (or B-D in above figure)
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 2;
// add edge 1-4 (or A-E in above figure)
graph.edge[4].src = 1;
graph.edge[4].dest = 4;
graph.edge[4].weight = 2;
// add edge 3-2 (or D-C in above figure)
graph.edge[5].src = 3;
graph.edge[5].dest = 2;
graph.edge[5].weight = 5;
// add edge 3-1 (or D-B in above figure)
graph.edge[6].src = 3;
graph.edge[6].dest = 1;
graph.edge[6].weight = 1;
--------------------
11)
import java.util.*;
public class Solution {
public int minSwaps(int[] arr) {
int n = arr.length;
int[] temp = Arrays.copyOfRange(arr, 0, n);
Arrays.sort(temp);
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < n; i++) {
m.put(arr[i], i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != temp[i]) {
ans++;
int init = arr[i];
arr[i] = temp[i];
m.put(init, m.get(temp[i]));
arr[m.get(temp[i])] = init;
}
}
return ans;
}
}
------------
12)
import java.util.Stack;
class SpecialStack {
Stack stack = new Stack<>();
int min = Integer.MAX_VALUE;
void push(int x) {
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
int pop() {
if (stack.isEmpty()) {
return -1;
}
int x = stack.pop();
if (x == min) {
min = stack.pop();
}
return x;
}
int getMin() {
if (stack.isEmpty()) {
return -1;
}
return min;
}
}