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

You are given an array of positive numbers from 1 to n, such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted. Look at the below array and give it a try before checking the solution.

The missing number = a sum of the provided array subtracted from a sum of indices + 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 find(int[] arr, int target) {
       int left = 0;
       int right = arr.length - 1;
       while (left <= right) {
           int mid = left + (right - left);
           if (arr[mid] == target)
               return mid;
           if (arr[mid] < target) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       return -1;
   }

   public static void main(String args[]) {
       int[] f = {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(find(f, t));
   }

}

Validate Binary Search Tree

Given a Binary Tree, figure out whether it’s a Binary Search Tree. In a binary search tree, each node’s key value is smaller than the key value of all nodes in the right subtree, and is greater than the key values of all nodes in the left subtree. Below is an example of a binary tree that is a valid BST.

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

}

Determine if two integers add up to given number

Given an array of integers and a value, determine if there are any two integers in the array whose sum is equal to the given value. Return true if the sum exists and return false if it does not. Consider this array and the target sums: 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 sorted lists

Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Consider two sorted linked lists and the merged list below them as an example. 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);
   }

}

Reverse String

Reverse the order of words in a given sentence (an array of characters).

import java.util.Iterator; import java.util.LinkedList;

public class ReverseString {

   public static void lizy(String[] curr) {
       LinkedList<String> y = new LinkedList<>();
       for (int g = 0; g <= curr.length - 1; g++) {
           y.add(curr[g]);
       }
       Iterator i = y.descendingIterator();
       while (i.hasNext()) {
           System.out.print(i.next() + " ");
       }
   }
   public static void main(String args[]) {
       String given = "Hello World";
       String[] given_array = given.split(" ");
       String lineOfCurrencies = "USD JPY AUD SGD HKD CAD CHF GBP EURO INR";
       String multispace = "Kenya    Uganda Tanzania   Burundi     Rwanda";
       String[] currencies = lineOfCurrencies.split(" ");
       String[] ms = multispace.split("\\s+");
       ReverseString.lizy(given_array);
   }

}