Algorithms

Java Graph Implementation with Search Methods

import java.util.HashMap; import java.util.LinkedList;

public class Chart {

   static class Employee {
       int id;
       String firstName;
       String lastName;
       String jobTitle;
       boolean mapped;

       Employee(int id, String fn, String ln, String jt) {
           this.id = id;
           this.jobTitle = jt;
           this.firstName = fn;
           this.lastName = ln;
       }

       void map() {
           mapped = true;
       }

       void unmap() {
           mapped = false;
       }
   }

   private final HashMap<Employee, LinkedList<Employee>> assignment;

   public Chart(boolean directed) {
       assignment = new HashMap<>();
   }

   public void addEdgeHelper(Employee a, Employee b) {
       LinkedList<Employee> e = assignment.get(a);
       if (e != null) {
           assignment.remove(b);
       } else
           e = new LinkedList<>();
       e.add(b);
       assignment.put(a, e);
   }

   public void addEdge(Employee boss, Employee subordinate) {
       if (!assignment.containsKey(boss))
           assignment.put(boss, null);
       if (!assignment.containsKey(subordinate))
           assignment.put(subordinate, null);
       addEdgeHelper(boss, subordinate);
   }

   public void depthFirstSearch(Employee employee) {
       employee.map();
       System.out.println(employee.firstName + " " + employee.lastName + " is a " + employee.jobTitle);
       LinkedList<Employee> neighbors = assignment.get(employee);
       if (neighbors == null)
           return;
       for (Employee e : neighbors) {
           if (!e.mapped)
               depthFirstSearch(e);
       }
   }

   public void breadthFirstSearch(Employee employee) {
       /*Check if target item is null - if so quit*/
       if (employee == null)
           return;
       /*Declare a queue using LinkedList and add the target item*/
       LinkedList<Employee> queue = new LinkedList<>();
       queue.add(employee);
       /*As long as the queue has data get the first in item .removeFirst*/
       while (!queue.isEmpty()) {
           Employee currentFirst = queue.removeFirst();
           /*If visited move on*/
           if (currentFirst.mapped) {
               continue;
           } else {
               /*else visit it and print it*/
               currentFirst.map();
               System.out.println(currentFirst.id + ": " + currentFirst.firstName + " " + currentFirst.lastName + " - " + currentFirst.jobTitle);
           }
           /*Find neighbors of the current item*/
           LinkedList<Employee> allNeighbors = assignment.get(currentFirst);
           /*If there are none move on*/
           if (allNeighbors == null)
               continue;
           /*else if there are some and not visited, add them to the queue and the process starts over*/
           for (Employee e : allNeighbors) {
               if (!e.mapped)
                   queue.add(e);
           }
       }
   }

   public void resetMapping() {
       for (Employee e : assignment.keySet()) {
           e.unmap();
       }
   }

   public static void main(String args[]) {
       Employee a = new Employee(38, "Jimbo", "Jones", "President");
       Employee b = new Employee(39, "Mike", "McCobb", "VP");
       Employee c = new Employee(43, "Elda", "Two", "VP");
       Employee d = new Employee(48, "Simon", "Sneeth", "VP");
       Employee e = new Employee(56, "Tim", "Scott", "Manager");
       Employee f = new Employee(58, "Bob", "Tilman", "Manager");
       Employee g = new Employee(78, "Andrew", "Cole", "Analyst");
       Employee h = new Employee(83, "Matt", "Lemon", "Analyst");
       Employee i = new Employee(88, "Chris", "Lock", "Analyst");
       Employee j = new Employee(71, "Agnes", "White", "Accountant");
       Employee k = new Employee(61, "George", "Mills", "Manager");
       Employee l = new Employee(59, "Thomas", "Wells", "Manager");
       Employee m = new Employee(63, "Zip", "Two", "Manager");
       Employee n = new Employee(73, "Rasta", "Him", "Technician");
       Employee o = new Employee(89, "Claire", "Collins", "Supervisor");
       Employee p = new Employee(95, "Jim", "Four", "Receptionist");
       Employee q = new Employee(104, "Tom", "Flat", "Receptionist");
       Employee r = new Employee(64, "Grace", "Marks", "Manager");
       Employee s = new Employee(68, "Dan", "Four", "Manager");
       Employee t = new Employee(117, "Shad", "Fifty", "Security");
       Employee u = new Employee(108, "Tall", "Nephew", "Legal");
       Employee v = new Employee(109, "Short", "Nephew", "Legal");

       Chart chart = new Chart(true);
       chart.addEdge(a, b);
       chart.addEdge(a, c);
       chart.addEdge(a, d);
       chart.addEdge(b, e);
       chart.addEdge(b, f);
       chart.addEdge(e, g);
       chart.addEdge(e, h);
       chart.addEdge(e, i);
       chart.addEdge(f, j);
       chart.addEdge(c, k);
       chart.addEdge(c, l);
       chart.addEdge(c, m);
       chart.addEdge(l, n);
       chart.addEdge(k, o);
       chart.addEdge(o, p);
       chart.addEdge(o, q);
       chart.addEdge(d, r);
       chart.addEdge(d, s);
       chart.addEdge(s, t);
       chart.addEdge(r, u);
       chart.addEdge(r, v);
       //System.out.println(a.firstName + " " + a.lastName + " " + a.jobTitle + " " + a.id);
       chart.resetMapping();
       //chart.depthFirstSearch(k);

       chart.resetMapping();
       chart.breadthFirstSearch(a);
   }

}

Find missing number

//The missing number = a sum of the provided array subracted from a sum of indeces + 2 //example 1, 2, 4 missing is 3 = (1 +2 +3+4) - (1 +2+4)

import java.util.ArrayList; import java.util.Arrays; import java.util.List;

public class MissingNum {

   public static int findMissing(List<Integer> l) {
       int tot_prov = 0;
       for (Integer integer : l) {
           tot_prov += integer;
       }
       List<Integer> k = new ArrayList<>();
       int tot_req = 0;
       for (int i = 0; i < l.size() + 2; i++) {
           k.add(i);
           tot_req += k.get(i);
       }
       return tot_req - tot_prov;
   }

   public static void main(String[] args) {
       List<Integer> g = Arrays.asList(8, 5, 3, 2, 4, 1, 7);
       System.out.println("The missing number is " + findMissing(g));
   }

}

Mergesort

public class MergeSort {

   private static Comparable[] aux;

   public static void sort(Comparable[] a) {
       aux = new Comparable[a.length];
       sort(a, 0, a.length - 1);
   }

   private static void merge(Comparable[] a, int lo, int mid, int hi) {
       assert isSorted(a, lo, mid);
       assert isSorted(a, mid + 1, hi);
       //copy for [] a to [] aux
       for (int k = lo; k <= hi; k++) {
           aux[k] = a[k];
       }
       // the merging process
       // i is the first index of the first half of the array
       // j is the first index of the second half of the array
       int i = lo, j = mid + 1;

       // for every value of k - the indices of [] a
       for (int k = lo; k <= hi; k++) {
           /*Left half exhausted take from the right*/
           if (i > mid)
               a[k] = aux[j++];
               /*Right half exhausted take from the left*/
           else if (j > hi)
               a[k] = aux[i++];
               /*Current key on the right less than current key on the left take from the right*/
           else if (less(aux[j], aux[i]))
               a[k] = aux[j++];
               /*Current key on the right greater than current key on the left take from the left */
           else
               a[k] = aux[i++];
       }
       assert isSorted(a, lo, hi);
   }

   private static void sort(Comparable[] a, int lo, int hi) {
       if (hi <= lo)
           return;
       int mid = lo + (hi - lo) / 2;
       sort(a, lo, mid);
       sort(a, mid + 1, hi);
       merge(a, lo, mid, hi);
   }

   private static boolean less(Comparable v, Comparable w) {
       return v.compareTo(w) < 0;
   }

   private static boolean isSorted(Comparable[] a, int lo, int hi) {
       for (int i = lo + 1; i <= hi; i++)
           if (less(a[i], a[i - 1])) return false;
       return true;
   }

   public static void show(Comparable[] a) {
       for (int i = 0; i < a.length; i++) {
           //System.out.print(a[i]);
           System.out.println(a[i]);
       }
   }

   public static void main(String args[]) {
       // Comparable[] a = {"E", "E", "G", "M", "R", "A", "C", "E", "R", "T"};

       Comparable[] aa = {"A", "X", "G", "M", "R"};
       Comparable[] bb = {"H", "D", "J", "Y", "Z"};
       /*Merge the two comparable arrays*/
       Comparable[] a = new Comparable[aa.length + bb.length];
       System.arraycopy(aa, 0, a, 0, aa.length);
       System.arraycopy(bb, 0, a, aa.length, bb.length);

       MergeSort.sort(a);
       show(a);
   }

}

Binary Search

public class BinarySearch { public static int binSearch(int[] fg, int t) {

       int left = 0;
       int right = fg.length - 1;

       while (left <= right) {
           int mid = left + (right - left);
           if (fg[mid] == t)
               return mid;
           if (fg[mid] < t) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       return -1;
   }

   public static void main(String args[]) {
       int[] lsr = {1, 10, 20, 47, 59, 63, 75, 88, 99, 107, 120, 133, 155, 162, 176, 188, 199, 200, 210, 222, 223};
       

       int t = 162;

       System.out.println("The target is at position " + binSearch(lsr, t));
   }

}

Binary Search Tree

public class BinarySearchTree {

   static class Node {
       int value;
       Node left;
       Node right;
       Node(int value) {
           this.value = value;
           this.left = null;
           this.right = null;
       }
   }
   Node root;
   public BinarySearchTree() {
       root = null;
   }
   public boolean isbst(Node root, Node l, Node r) {
       if (root == null)
           return true;
       if (l != null && l.value > root.value)
           return false;
       if (r != null && r.value < root.value)
           return false;
       return isbst(root.left, l, root) && isbst(root.right, root, r);
   }

   public static void main(String args[]) {
       BinarySearchTree bt = new BinarySearchTree();
       bt.root = new Node(10);
       bt.root.left = new Node(5);
       bt.root.right = new Node(15);
       bt.root.left.left = new Node(4);
       bt.root.left.right = new Node(7);
       bt.root.right.left = new Node(13);
       bt.root.right.right = new Node(26);
       if (bt.isbst(bt.root, null, null))
           System.out.println("Is a BST");
       else
           System.out.println("Is not a BST");
   }

}

Sum of two numbers

public class SumOfTwo {

       public static void main(String args[]) {
           Set<Integer> set = new HashSet<>(); /*Populate this Set with target values*/
           /*Array of target values*/
           int[] g = {5, 6, 8, 39, 9, 11, 20, 59, 10, 1};
           /*Insert the arrays values in the set*/
           for (int i = 0; i < g.length; i++) {
               set.add(g[i]);
           }
           /*Set a target number to check for*/
           int y = 20;
           /*If there are a set of numbers that would add up, increment this counter*/
           int counter = 0;
           /*Pick up a number in the set by turns and assign it to x*/
           for (int i = 0; i < g.length; i++) {
               int x = g[i];
               /*Check to see if the set contains target minus found number.*/
               if (set.contains(y - x)) { //if this is true
                   /*If so, increment the counter by 1*/
                   counter += 1;
               }
           }
           if (counter > 0) { /*Some numbers add up*/
               System.out.println("There are sets of numbers that add up to " + y);
           } else { /*No numbers add up*/
               System.out.println("There are no sets of numbers that add up to " + y);
           }

       }

}

Merge two lists

import java.util.Stack; /*This code merges two ordered lists into one keeping their increasing order

* the lists used for testing are in the main function*/

public class MergeLists {

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

   /*This function reads the values of a list and loads them on a Stack, then reads from the stack*/
   public static void loadInStack(Node f) {
       Stack<Integer> pack = new Stack<>();
       if (f == null)
           return;
       pack.push(f.data);
       loadInStack(f.next);
       System.out.println(pack);
   }

   /*This function duplicates the provided list into another one*/
   public static void duplicateList(Node m) {
       Node hold = new Node(-1);
       if (m == null)
           return;
       hold.data = m.data;
       duplicateList(m.next);
       System.out.println(hold.data);
   }

   /*This function reads from two lists picking the lesser of*/
   /*It takes in two lists as variables a and b*/
   public static void pickTwo(Node a, Node b) {
       /*This is a dummy list initialized with -1*/
       Node dummyList = new Node(-1);
       while (a != null && b != null) {
           if (a.data <= b.data) {
               /*populate the dummy list from a, if smaller*/
               dummyList.data = a.data;
               /*Increment a*/
               a = a.next;
           } else {
               /*populate the dummy list from b, if smaller*/
               dummyList.data = b.data;
               /*Increment b*/
               b = b.next;
           }
           /*Print when done*/
           System.out.print(dummyList.data + " -> ");
       }
   }

   public static void main(String args[]) {
       Node f = new Node(2);
       Node g = new Node(7);
       Node h = new Node(8);
       Node i = new Node(11);

       f.next = g;
       g.next = h;
       h.next = i;

       //printNodes(f);

       Node k = new Node(4);
       Node l = new Node(6);
       Node m = new Node(9);
       Node n = new Node(10);
       Node o = new Node(12);

       k.next = l;
       l.next = m;
       m.next = n;
       n.next = o;

       //loadInStack(f);
       //duplicateList(k);
       pickTwo(f, k);
   }

}