Project 1
1.
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);
}
}
2
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);
}
}
3
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);
}
}
4
import java.util.Arrays;
public class RemoveDuplicatesFromString {
static char[] removeDuplicatesFromString(String string)
{
//table to keep track of visited characters
int[] table = new int[256];
char[] chars = string.toCharArray();
//to keep track of end index of resultant string
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);
}
// Driver code
public static void main(String[] args)
{
String str1 = "skilllync";
String str2 = "skill lync courses";
System.out.println(removeDuplicatesFromString(str1));
System.out.println(removeDuplicatesFromString(str2));
}
}
5
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);
}
}
6
public class ReverseLinkedList {
static Node head;
// create a new node and add at end
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);
}
}
7
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);
}
}
9
class Node {
int key;
Node left, right;
public Node(int key){
this.key = key;
left = right = null;
}
}
public class BinaryTreeToDLL {
Node root, head;
// Initialize previously visited node as NULL. Since this is static it is the same value that's is accessible in all recursive calls
static Node prev = null;
void BinaryTree2DoubleLinkedList(Node root){
// Base case
if (root == null)
return;
// Recursively convert left subtree
BinaryTree2DoubleLinkedList(root.left);
// Now convert this node
if (prev == null)
head = root;
else
{
root.left = prev;
prev.right = root;
}
prev = root;
// Finally convert right subtree
BinaryTree2DoubleLinkedList(root.right);
}
void printList(Node node)
{
while (node != null)
{
System.out.print(node.key + "==");
node = node.right;
}
}
// Driver program to test above functions
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);
}
}
10
class Graph {
// A class to represent a weighted edge in graph
class Edge {
int src, dest, weight;
Edge()
{
src = dest = weight = 0;
}
};
int V, E;
Edge edge[];
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[e];
for (int i = 0; i < e; ++i){
edge[i] = new Edge();
}
}
// The main function that finds shortest distances from src
// to all other vertices using Bellman-Ford algorithm. The
// function also detects negative weight cycle
void BellmanFord(Graph graph, int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
// Step 1: Initialize distances from src to all other
// vertices as INFINITE
for (int i = 0; i < V; ++i){
dist[i] = Integer.MAX_VALUE;
}
dist[src] = 0;
// Step 2: Relax all edges |V| - 1 times. A simple
// shortest path from src to any other vertex can
// have at-most |V| - 1 edges
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;
}
}
}
// Step 3: check for negative-weight cycles. The above
// step guarantees shortest distances if graph doesn't
// contain negative weight cycle. If we get a shorter
// path, then there is a cycle.
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);
}
// A utility function used to print the solution
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]);
}
// Driver method to test above function
public static void main(String[] args)
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
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;
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);
}
}
11
import java.util.Arrays;
import java.util.HashMap;
public class MinNumberOfSwaps {
public static int minSwaps(int[] nums)
{
int len = nums.length;
HashMap
for(int i=0;i
}
Arrays.sort(nums);
// To keep track of visited elements. Initialize all elements as not visited or false.
boolean[] visited = new boolean[len];
Arrays.fill(visited, false);
// Initialize result
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;
// move to next node
j = hM.get(nums[j]);
cycle_size++;
}
// Update answer by adding current cycle.
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));
}
}