TheAlgorithms · AzadN · Oct 31, 2020 · Oct 31, 2020 · Nov 4, 2020
@@ -0,0 +1,121 @@
+package DataStructures.Graphs;
+
+import java.util.*;
+// A graph with nodes as jobs and edges as dependencies
+class jobGraph2
+{
+    ArrayList<jobNode2> nodes;
+    //ArrayList<Integer> jobs;
+    HashMap<Integer,jobNode2> graph=new HashMap<>();
+
+    jobGraph2(ArrayList<Integer> jobs)
+    {
+        //this.jobs=jobs;
+        this.nodes=new ArrayList<>();
+        for(int job:jobs)
+            this.addNode(job);
+    }
+
+    void addDep(int job, int dep)
+    {
+        jobNode2 j=this.getNode(job);
+        jobNode2 depNode=this.getNode(dep);
+        j.deps.add(depNode);
+        depNode.prereqCount++;
+    }
+
+    void addNode(int job)
+    {
+        this.graph.put(job,new jobNode2(job));
+        nodes.add(graph.get(job));
+    }
+
+    jobNode2 getNode(int job)
+    {
+        if(!graph.containsKey(job))
+            addNode(job);
+        return graph.get(job);
+    }
+}
+// Nodes of a job-graph consisting of the job and its number of pre-requisites
+class jobNode2
+{
+    int job, prereqCount;
+    ArrayList<jobNode2> deps;
+    jobNode2(int job)
+    {
+        this.job = job;
+        this.deps = new ArrayList<jobNode2>();
+        this.prereqCount=0;
+    }
+}
+public class TopoSortKahn
+{
+    // Gives the topological ordering given a set of jobs and their prerequisites
+    public static ArrayList<Integer> topoSort(ArrayList<Integer> jobs, ArrayList<Integer[]> deps)
+    {
+        jobGraph2 graph=createJobGraph(jobs, deps);
+        return getOrderedJobs(graph);
+    }
+
+    public static jobGraph2 createJobGraph(ArrayList<Integer> jobs, ArrayList<Integer[]> deps)
+    {
+        jobGraph2 j= new jobGraph2(jobs);
+        for(Integer[] t : deps)
+            j.addDep(t[0], t[1]);
+        return j;
+    }
+
+    public static ArrayList<Integer> getOrderedJobs(jobGraph2 graph)
+    {
+        ArrayList<Integer> orderedJobs=new ArrayList<>();
+        ArrayList<jobNode2> nodesWithNoPrereqs=new ArrayList<>();
+        for(jobNode2 x:graph.nodes)
+        {
+            if(x.prereqCount==0)
+                nodesWithNoPrereqs.add(x);
+        }
+        while(nodesWithNoPrereqs.size()!=0)
+        {
+            jobNode2 temp = nodesWithNoPrereqs.remove(nodesWithNoPrereqs.size() - 1);
+            orderedJobs.add(temp.job);
+            removeDeps(temp,nodesWithNoPrereqs);
+        }
+        boolean graphHasEdges=false;
+        for(jobNode2 t:graph.nodes)
+        {
+            if (t.prereqCount != 0) {
+                graphHasEdges = true;
+                break;
+            }
+        }
+        return graphHasEdges ?new ArrayList<>():orderedJobs;
+    }
+
+    public static void removeDeps(jobNode2 node, ArrayList<jobNode2> nodesWithNoprereqs)
+    {
+        while(node.deps.size()!=0)
+        {
+            jobNode2 dep=node.deps.remove(node.deps.size()-1);
+            dep.prereqCount--;
+            if(dep.prereqCount==0)
+                nodesWithNoprereqs.add(dep);
+        }
+    }
+
+    public static void main(String[] args)
+    {
+        // Sample Testcase
+        Scanner s=new Scanner(System.in);
+        ArrayList<Integer> jobs=new ArrayList<>(Arrays.asList(1,2,3,4,5,6,7));
+        ArrayList<Integer[]> deps=new ArrayList<>();
+        deps.add(new Integer[]{2,3}); // (2, 3) indicates that job 2 has to be completed before starting job 3
+        deps.add(new Integer[]{2,5});
+        deps.add(new Integer[]{1,3});
+        deps.add(new Integer[]{3,4});
+        deps.add(new Integer[]{4,6});
+        deps.add(new Integer[]{5,6});
+        deps.add(new Integer[]{6,7});
+        System.out.println(topoSort(jobs,deps));
+    }
+}
@@ -0,0 +1,35 @@
+package Maths;
+
+public class HappyNumber {
+
+    // Check if a number is happy or not. Refer : https://mathworld.wolfram.com/HappyNumber.html
+    public static boolean isHappy(int num)
+    {
+        int slow=num, fast=num;
+        do
+        {
+            slow = digitSquareSum(slow); // Move one step
+            fast = digitSquareSum(digitSquareSum(fast)); // Move 2 steps
+        } while(slow != fast);
+        return slow == 1; // See if the cycle is stuck on number 1
+    }
+
+    public static int digitSquareSum(int num)
+    {
+        int sum = 0, digit;
+        while(num > 0)
+        {
+            digit = num % 10;
+            sum += digit * digit;
+            num /= 10;
+        }
+        return sum;
+    }
+
+    public static void main(String[] args)
+    {
+        // Testcases
+        System.out.println(isHappy(23));
+        System.out.println(isHappy(11));
+    }
+}
@@ -0,0 +1,49 @@
+package Misc;
+
+import java.util.*;
+class ParenthesisString{
+    String str;
+    int openCount, closedCount; // Open & Closed Parenthesis count respectively
+
+    public ParenthesisString(String str, int openCount, int closedCount)
+    {
+        this.str  =str;
+        this.openCount = openCount;
+        this.closedCount = closedCount;
+    }
+}
+
+public class generateBalancedParenthesis {
+    // Follows a BFS-based approach to generate all combinations of balanced paranthesis with 'A' number of pairs
+    // Time complexity : O(4^n/sqrt(n)) Refer this : https://en.wikipedia.org/wiki/Central_binomial_coefficient
+    // Space complexity : O(n*2^n)
+    public static List<String> generateParenthesis(int A)
+    {
+        List<String> res=new ArrayList<>();
+        Queue<ParenthesisString> queue=new ArrayDeque<>();
+        queue.add(new ParenthesisString("", 0, 0));
+        while(!queue.isEmpty())
+        {
+            ParenthesisString ps = queue.poll();
+            // Add to the result if the max open & closed parenthesis count is reached
+            if(ps.openCount == A && ps.closedCount == A)
+                res.add(ps.str);
+            else
+            {
+                if(ps.openCount < A) // Add if we can add an open parenthesis
+                    queue.add(new ParenthesisString(ps.str + "(", ps.openCount+1, ps.closedCount));
+
+                if(ps.openCount > ps.closedCount) // Add if we can add a closed parenthesis
+                    queue.add(new ParenthesisString(ps.str + ")", ps.openCount, ps.closedCount+1));
+            }
+        }
+        return res;
+    }
+
+    public static void main(String[] args)
+    {
+        // Testcases
+        System.out.println(generateParenthesis(4));
+        System.out.println(generateParenthesis(8));
+    }
+}
@@ -0,0 +1,45 @@
+package Misc;
+
+import java.util.*;
+public class largestRange
+{
+    // Finds the length of longest occurring consecutive numbers range in an array
+    public static int longestRange(int[] nums)
+    {
+        int longestRange = 0;
+        HashMap<Integer,Boolean> num = new HashMap<>();
+        for(int x : nums)
+            num.put(x,true);
+        for(int x : nums)
+        {
+            if(!num.get(x))
+                continue;
+            num.replace(x, false);
+            int currentRange=1;
+            int left = x-1;
+            int right = x+1;
+            while(num.containsKey(left))
+            {
+                num.replace(left, false);
+                currentRange+=1;
+                left--;
+            }
+            while(num.containsKey(right))
+            {
+                num.replace(right, false);
+                currentRange+=1;
+                right++;
+            }
+            if(currentRange > longestRange)
+                longestRange = currentRange;
+        }
+        return longestRange;
+    }
+
+    public static void main(String[] args) {
+        // Testcases
+        System.out.println(longestRange(new int[]{1, 2, 3, 4, -1, 11, 10}));
+        System.out.println(longestRange(new int[]{-1, 1, 3, 5, 7}));
+        System.out.println(longestRange(new int[]{0, 1, 2, 3, 4, 7, 6, 5}));
+    }
+}
@@ -0,0 +1,103 @@
+package Misc;
+
+import java.util.*;
+public class rangeInSortedArray
+{
+    public static void main(String[] args)
+    {
+        // Testcases
+        System.out.println(Arrays.toString(sortedRange(new int[]{1 ,2 ,3, 3, 3, 4, 5}, 3)));
+        System.out.println(Arrays.toString(sortedRange(new int[]{1 ,2 ,3, 3, 3, 4, 5}, 4)));
+        System.out.println(Arrays.toString(sortedRange(new int[]{0, 1, 2}, 3)));
+    }
+
+    // Get the 1st and last occurrence index of a number 'key' in a non-decreasing array 'nums'
+    // Gives [-1, -1] in case element doesn't exist in array
+    public static int[] sortedRange(int[] nums, int key)
+    {
+        int[] range=new int[]{-1,-1};
+        alteredBinSearchIter(nums,key,0,nums.length-1,range,true);
+        alteredBinSearchIter(nums,key,0,nums.length-1,range,false);
+        return range;
+    }
+
+    // Recursive altered binary search which searches for leftmost as well as rightmost occurrence of 'key'
+    public static void alteredBinSearch(int[] nums, int key, int left, int right, int[] range, boolean goLeft)
+    {
+        if(left>right)
+            return;
+        int mid=(left+right)/2;
+        if(nums[mid]>key)
+            alteredBinSearch(nums,key,left,mid-1,range,goLeft);
+        else if(nums[mid]<key)
+            alteredBinSearch(nums,key,mid+1,right,range,goLeft);
+        else
+        {
+            if(goLeft)
+            {
+                if(mid==0 || nums[mid-1]!=key)
+                    range[0]=mid;
+                else
+                    alteredBinSearch(nums,key,left,mid-1,range,goLeft);
+            }
+            else
+            {
+                if(mid==nums.length-1 || nums[mid+1]!=key)
+                    range[1]=mid;
+                else
+                    alteredBinSearch(nums,key,mid+1,right,range,goLeft);
+            }
+        }
+    }
+
+    // Iterative altered binary search which searches for leftmost as well as rightmost occurrence of 'key'
+    public static void alteredBinSearchIter(int[] nums, int key, int left, int right, int[] range, boolean goLeft)
+    {
+        while(left<=right) {
+            int mid = (left + right) / 2;
+            if (nums[mid] > key)
+                right = mid - 1;
+            else if (nums[mid] < key)
+                left = mid + 1;
+            else {
+                if (goLeft) {
+                    if (mid == 0 || nums[mid - 1] != key) {
+                        range[0] = mid;
+                        return;
+                    }
+                    else
+                        right = mid - 1;
+                } else {
+                    if (mid == nums.length - 1 || nums[mid + 1] != key) {
+                        range[1] = mid;
+                        return;
+                    }
+                    else
+                        left = mid + 1;
+                }
+            }
+        }
+    }
+
+    public static int getCountLessThan(int[] nums, int key)
+    {
+        return getLessThan(nums,key,0,nums.length-1);
+    }
+
+    public static int getLessThan(int[] nums, int key, int left, int right)
+    {
+        int count = 0;
+        while (left <=right)
+        {
+            int mid = (left + right) / 2;
+            if (nums[mid] > key)
+                right=mid - 1;
+            else if (nums[mid] <= key)
+            {
+                count = mid + 1;//Atleast mid+1 elements exist which are <= key
+                left=mid+1;
+            }
+        }
+        return count;
+    }
+}