Untitled
unknown
plain_text
a year ago
19 kB
3
Indexable
CAT -1 1) LOOP DETECTION import java.util.*; class Node{ int data; Node next; Node(int e) { data=e; next=null; } } public class Main{ static Node head=null,temp=null; static int count=1; public static void insert(int e) { temp =new Node(e); if(head==null) head=temp; else{ Node cur=head; while(cur.next!=null) cur=cur.next; cur.next=temp; } } public static void create(int k) { Node t=head; while(count<k) { t=t.next; count++; } temp.next=t; } public static void cycleDetect() { Node fast = head; Node slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow){ System.out.println("Loop found"); return; } } System.out.println("No Loop"); } public static void print() { Node t=head; while(t!=null) { System.out.print(t.data); t=t.next; } } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int e,k; while(true) { e=sc.nextInt(); if(e<0) break; insert(e); } print(); k=sc.nextInt(); create(k); cycleDetect(); } } 2)SEGREGATE EVEN AFTER ODD import java.io.*; import java.util.*; public class Solution { Node head; class Node { int data; Node next; Node(int val) { data = val; next = null; } } public void insert(int val) { Node newnode = new Node(val); Node temp = head; if(head == null) head = newnode; else { while(temp.next!=null) { temp = temp.next; } temp.next = newnode; } } public void segOddEven() { Node evenstart = null; Node evenend = null; Node oddstart = null; Node oddend = null; Node currentnode = head; while(currentnode!=null) { int element = currentnode.data; if(element%2==0) { if(evenstart==null) { evenstart = currentnode; evenend = evenstart; } else { evenend.next = currentnode; evenend = evenend.next; } } else { if(oddstart == null) { oddstart = currentnode; oddend = oddstart; } else { oddend.next = currentnode; oddend = oddend.next; } } currentnode = currentnode.next; } if (oddstart == null) { head = evenstart; } else { head = oddstart; oddend.next = evenstart; } // Set the next of the last node of the even list to null if (evenend != null) { evenend.next = null; } } public void display() { Node temp = head; while(temp!=null) { System.out.print(temp.data+" "); temp = temp.next; } } public static void main(String[] args) { Solution list = new Solution(); Scanner s = new Scanner(System.in); int x = s.nextInt();//1 while(x!=-1) { list.insert(x);//1 x = s.nextInt();//2 } list.segOddEven(); list.display(); } } 3) BITONIC SORT USING DLL import java.util.*; class node { int data; node prev; node next; } class solution { static node head=null,temp=null; public static void insert(int data) { node newnode=new node(); newnode.data=data; newnode.next=null; newnode.prev=null; if (head==null) { head=newnode; temp=newnode; temp.prev=null; } else { temp.next=newnode; newnode.prev=temp; temp=newnode; } } public static void display() { while(head!=null) { System.out.print(head.data+" "); head=head.next; } } public static void bitonic() { node i=head,j=temp,t=null; while(i!=j) { if(i.data>j.data) { j.prev.next=null; t=j.prev; j.prev=null; if(i.prev==null) { head=j; j.next=i; i.prev=j; } else { j.prev=i.prev; i.prev.next=j; j.next=i; i.prev=j; } j=t; } i=i.next; } } public static void main(String []args) { Scanner in=new Scanner(System.in); while(true) { int n=in.nextInt(); if(n<0) { break; } else { insert(n); } } bitonic(); display(); } } 4)MINIMUM STACK import java.util.*; class Mystack { Stack<Integer> s; Stack<Integer> a; Mystack() { s = new Stack<Integer>(); a = new Stack<Integer>(); } void getMin() { if(a.isEmpty()) System.out.println(“Stack is Empty”); else System.out.println(“Minimum element : “ + a.peek()); } void peek(){ if(s.isEmpty()) { System.out.println(“Stack is Empty”); return ; } integer t=s.peek(); System.out.print(“Top most element:” + t); } void pop() { if(s.isEmpty()) { System.out.println(“Stack is Empty”); return ;} else{ int t = s.pop(); System.out.println(“Removed element : “ + t);} if( t == a.peek() ) a.pop(); } void push(int x) { if ( s.isEmpty()) { s.push(x); a.push(x) System.out.println(“ Number Inserted: “+ x); return ; } else { s.push(x); System.out.prinln(“ Number Inserted: “ +x); } if ( x<= a.peek() ) a.push(x); } }; public class Main { public static void main(String args[]) { Mystack s=new Mystack(); Scanner sc = new Scanner(System.in); int n=sc.nextInt(); for( int i=0;i<n;i++) { int m=sc.nextInt(); s.push(m); } s.getMin(); s.pop(); s.getMin(); s.pop(); s.peek(); } } 5)THE CELEBRITY PROBLEM import java.util.*; public class CP { Stack<Integer> s=new Stack<Integer>(); int cpp(int ar[][],int n){ for(int i=0;i<n;i++){ s.push(i); } while(s.size()>1){ int a=s.pop(); int b=s.pop(); if(ar[a][b]==1){ s.push(b); } else{ s.push(a); } } int a=s.pop(); for(int i=0;i<n;i++){ if(a==i){ continue; } else{ if(ar[i][a]==0 || ar[a][i]==1){ return -1; } } } return a; } public static void main(String[] args) { CP s=new CP(); Scanner in=new Scanner(System.in); int n=in.nextInt(); int ar[][]=new int[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ar[i][j]=in.nextInt(); } } System.out.print(s.cpp(ar,n)); } } 6) TOWER OF HANOI import java.util.*; class Main{ static Stack <Integer> sor=new Stack<Integer>(); static Stack <Integer> aux=new Stack<Integer>(); static Stack <Integer> des=new Stack<Integer>(); void change( Stack <Integer> disk1, Stack <Integer> disk2, char p1, char p2) { int v1,v2; if(disk1.isEmpty()) v1=Integer.MIN_VALUE; else v1=disk1.pop(); if(disk2.isEmpty()) v2=Integer.MIN_VALUE; else v2=disk2.pop(); if(v1==Integer.MIN_VALUE) { disk1.push(v2); System.out.println("The value"+v2+" move from "+p2+" to "+p1); } else if(v2==Integer.MIN_VALUE){ disk2.push(v1); System.out.println("The value"+v1+" move from "+p1+" to "+p2); } else if(v1<v2) { disk2.push(v1); disk2.push(v1); System.out.println("The value"+v1+" move from "+p1+" to "+p2); } else { disk1.push(v1); disk1.push(v2); System.out.println("The value"+v2+" move from "+p2+" to "+p1); } } public static void main(String [] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); Main ob=new Main(); char s='S',d='D',a='A'; if(n%2==0) { char temp=a; a=d; d=temp; } int moves=(int)(Math.pow(2,n))-1; for(int i=n;i>0;i--) { ob. sor.push(i); } for(int i=1;i<=moves;i++) { if(i%3==1) ob.change(sor,des,s,d); else if(i%3==2) ob.change(sor, aux,s,a); else if(i%3==0) ob.change(aux,des,a,d); }}} 7) MAXIMUM SLIDING WINDOW import java.util.*; public class Main { public static int[] maxs(int[] arr, int n, int k) { int [] ans=new int[n-k+1]; Deque<Integer> q=new ArrayDeque<>(); for(int i=0;i<k;i++) { while(!q.isEmpty()&& arr[i]>=arr[q.peekLast()]) q.removeLast(); q.addLast(i); } ans[0]=arr[q.peekFirst()]; for(int i=k;i<n;i++) { while(!q.isEmpty()&&q.peekFirst()<=i-k) q.pollFirst(); while(!q.isEmpty() && arr[i]>=arr[q.peekLast()]) q.pollLast(); q.addLast(i); ans[i-k+1]=arr[q.peekFirst()]; } return ans; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } int k=sc.nextInt(); int[]ans=maxs(arr,n,k); for(int i:ans) System.out.print(i+" "); } } 8) STACK PERMUTATIONS import java.util.*; public class Main { public static Boolean checkPermutation(int a[],int b[],int n) { Queue<Integer> input = new LinkedList<>(); for(int i=0;i<n;i++) input.add(a[i]); Queue<Integer> output = new LinkedList<>(); for(int i=0;i<n;i++) output.add(b[i]); Stack<Integer> stack = new Stack<>(); int j=0; for(int i=0;i<n;i++){ stack.push(input.peek()); while(stack.size()>0 && stack.peek()== output.peek()) { stack.pop(); output.poll(); j++; } input.poll(); } if(j==n && stack.size()==0) return true; else return false; } public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int a[] = new int[n]; for(int i =0;i<n;i++) { a[i] = s.nextInt(); } int b[] = new int[n]; for(int i=0;i<n;i++) { b[i] = s.nextInt(); } if(checkPermutation(a,b,n)== true) System.out.print("Yes"); else System.out.println("Not possible"); } } 9) PRIORITY QUEUE USING DLL import java.util.*; class node { int data,prio; node prev,next; } class Main { node front=null,rear=null; void insert(int data,int prio) { node newnode=new node(); newnode.data=data; newnode.prio=prio; newnode.prev=null; newnode.next=null; if(front==null) { front=newnode; rear=newnode; } else { if(prio<=front.prio) { newnode.next=front; front.prev=newnode; front=newnode; } else if(prio>=rear.prio) { rear.next=newnode; newnode.prev=rear; rear=newnode; } else{ while(front!=null&&front.next.prio<=prio) { front=front.next; } newnode.prev=front; newnode.next=front.next; front.next.prev=newnode; front.next=newnode; } } } void print() { while(front!=null) { System.out.print(front.data+" "+front.prio+" "); front=front.next; } } public static void main(String[]args) { Scanner in=new Scanner(System.in); Main obj=new Main(); int n=in.nextInt(); for(int i=0;i<n;i++) { int data=in.nextInt(); int priority=in.nextInt(); obj.insert(data,priority); } obj.print(); } } 10) MEGE SORT USING DLL import java.util.Scanner; class Node { int data; Node next, prev; Node(int val){ data = val; next = null; prev = null; } } class Main { public Node split(Node head) { Node fast = head, slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } Node temp = slow.next; slow.next = null; return temp; } public Node mergeSort(Node node) { if (node == null || node.next == null) return node; Node second = split(node); node = mergeSort(node); second = mergeSort(second); return merge(node, second); } public Node merge(Node first, Node second) { if (first == null) return second; if (second == null) return first; if (first.data < second.data) { first.next = merge(first.next, second); first.next.prev = first; first.prev = null; return first; } else { second.next = merge(first, second.next); second.next.prev = second; second.prev = null; return second; } } } public class Solution { public static void printList_left_right(Node head){ while(head != null){ System.out.print(head.data + " "); head = head.next; } System.out.println(); } public static void printList_right_left(Node head){ Node tail = head; while(tail.next != null) tail = tail.next; while(tail != null){ System.out.print(tail.data + " "); tail = tail.prev; } System.out.println(); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n = sc.nextInt(); int val = sc.nextInt(); Node head = new Node(val); for(int i=0;i<n-1;i++){ val = sc.nextInt(); Node nd = new Node(val); nd.next = head; head = nd; } Main g = new Main(); Node res = g.mergeSort(head); printList_left_right(res); printList_right_left(res); } 11) SORT WITHOUT EXTRA SPACE import java.util.*; class Main { public static int minIndex(Queue<Integer> list, int sortIndex) { int min_index = -1; int min_value = Integer.MAX_VALUE; int s = list.size(); for (int i = 0; i < s; i++) { int current = list.peek(); list.poll(); if (current <= min_value && i <= sortIndex) { min_index = i; min_value = current; } list.add(current); } return min_index; } public static void insertMinToRear(Queue<Integer> list, int min_index) { int min_value = 0; int s = list.size(); for (int i = 0; i < s; i++) { int current = list.peek(); list.poll(); if (i != min_index) list.add(current); else min_value = current; } list.add(min_value); } public static void sortQueue(Queue<Integer> list) { for(int i = 1; i <= list.size(); i++) { int min_index = minIndex(list,list.size() - i); insertMinToRear(list, min_index); } } public static void main (String[] args) { Queue<Integer> list = new LinkedList<Integer>(); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++) { int ele=sc.nextInt(); list.add(ele); } sortQueue(list); while(list.isEmpty()== false) { System.out.print(list.peek() + " "); list.poll(); } } } 12) STOCKSPAN PROBLEM import java.util.*; class Main { Stack<Integer>s=new Stack<Integer>(); public static void main(String[]args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int []stock=new int[n]; for(int i=0;i<n;i++) { stock[i]=in.nextInt(); } int[]span=new int[n]; for(int i=0;i<n;i++) { while(!s.isEmpty()&& stock[i]>=stock[s.peek()]) { s.pop(); } if(s.isEmpty()) { span[i]=1; } else { span[i]=i-s.peek(); } s.push(i); } for(int i=0;i<n;i++) { System.out.print(span[i]+" "); } } }
Editor is loading...
Leave a Comment