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.List; import java.util.Arrays;

public class Missing { public static int findMissing(List<Integer> l) { int tot_prov = 0;

for (int i = 0; i < l.size(); i++) { tot_prov += l.get(i);

} 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);

} int missed = tot_req - tot_prov; return missed; } 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(int value) { root = new Node(value); }

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");

 	}

}