Algorithms

Below is a collection of algorithms. The title of the algorithm describes (as much as possible) what the algorithm does.

Java Graph Implementation with Search Methods

The algorithm below implements the organization chart below:

Jimbo Jones is employee id 38 and is the President.

Mike McCobb, id 39, is a VP and reports to Jimbo Jones.

Elda Two, id 43, is a VP and reports to Jimbo Jones.

Simon Sneath, id 48, is a VP and reports to Jimbo Jones.

Tim Scott, id 56, is a Manager and reports to Mike McCobb.

Bob Tilman, id 58, is a Manager and reports to Mike McCobb.

Andrew Cole, id 78, is an Analyst and reports to Tim Scott.

Matt Lemon, id 83, is an Analyst and reports to Tim Scott.

Chris Lock, id 88, is an Analyst and reports to Tim Scott.

Agnes White, id 71, is an Accountant and reports to Bob Tilman.

George Mills, id 61, is a Manager and reports to Elda Two.

Thomas Wells, id 59, is a Manager and reports to Elda Two.

Zip Two, id 63, is Manager and also reports to Elda Two.

Rasta Him, id 73, is a Technician and reports to Thomas Wells.

Claire Collins, id 89, is a Supervisor and reports to George Mills.

Jim Four, id 95, is a Receptionist and reports to Claire Collins.

Tom Flat, id 104, is a Receptionist who reports to Claire Collins.

Grace Marks, id 64, is a Manager and reports to Simon Sneath.

Dan Four, id 68, is a Manager and reports to Simon Sneath.

Shad Fifty, id 117, is in Security and reports to Dan Four.

Tall Nephew, id 108, is in Legal and reports to Grace Marks.

Short Nephew, id 109, is in Legal and reports to Grace Marks.

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

}

Level Order Traversal of Binary Tree

Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.

import java.util.LinkedList;

public class Lot {

   static class Node {
       int value;
       Node left;
       Node right;
       Node(int v) {
           this.value = v;
           this.left = this.right = null;
       }
   }
   Node root;
   public Lot() {
       root = null;
   }
   void lot() {
       LinkedList<Node> queue = new LinkedList<>();
       //Queue<Node> queue = new LinkedList<Node>();
       queue.add(root);
       while (!queue.isEmpty()) {
           Node tempNode = queue.removeFirst();
           //Node tempNode = queue.poll();
           System.out.print(tempNode.value + " ");
           if (tempNode.left != null)
               queue.add(tempNode.left);
           if (tempNode.right != null)
               queue.add(tempNode.right);
       }
   }
   public static void main(String args[]) {
       Lot l = new Lot();
       l.root = new Node(100);
       l.root.left = new Node(50);
       l.root.right = new Node(200);
       l.root.left.left = new Node(25);
       l.root.left.right = new Node(75);
       l.root.right.right = new Node(350);
       System.out.println("Level order traversal is as follows: ");
       l.lot();
   }

}

String Segmentation

You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further. import java.util.HashSet; import java.util.Set;

public class Dictionary {

   boolean pair(Set<String> dictionary, String a) {
       for (int i = 0; i < a.length(); i++) {
           String first_word = a.substring(0, i);
           if (dictionary.contains(first_word)) {
               String second_word = a.substring(i);
               if (dictionary.contains(second_word) || pair(dictionary, second_word)) {
                   return true;
               }
           }
       }
       return false;
   }

   public static void main(String[] args) {
       Dictionary dictionary = new Dictionary();
       Set<String> dict = new HashSet<>();
       dict.add("geo");
       dict.add("science");
       dict.add("politics");
       dict.add("thermal");
       dict.add("physical");
       dict.add("mis");
       dict.add("under");
       dict.add("stand");
       dict.add("understand");
       String word = "misunderstand";
       if (dictionary.pair(dict, word)) {
           System.out.println("The test word " + word + " fits in two words in the dictionary");
       } else {
           System.out.println("The test word " + word + " does not make dictionary words");
       }
   }

}

Computing number combinations

Suppose we have coin denominations of [1, 2, 5] and the total amount is 7. We can make changes in the following 6 ways:

public class Combinations {

   static int changeOptions(int[] denominations, int amount) {
       int[] solution = new int[amount + 1];
       solution[0] = 1;
       for (int x : denominations) {
           for (int i = x; i < (amount + 1); ++i) {
               solution[i] += solution[i - x];
           }
       }
       return solution[solution.length - 1];
   }

   public static void main(String[] args) {
       int[] denominations = new int[]{1, 2, 5, 10};
       int amount = 5;
       int result = changeOptions(denominations, amount);
       System.out.println("There are " + result + " combinations in forming " + amount + " given the factors below: ");
       for (int denomination : denominations) {
           System.out.println(denomination);
       }
   }

}

Sum of two numbers

Are there two numbers in the provided set that add up to the given number?

Brute force method

We start with a brute force method that checks every number. Big 0(n).

import java.util.HashSet; import java.util.Set;

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

   }

}

Two pointer method

This method uses a function to find the two numbers then makes a determination import java.util.Arrays;

public class Addends {

   static void doTwoNumbersAdd(int[] a, int b) {
       int[] z = findAddingNumbers(a, b);
       if (z.length > 0) {
           System.out.println("There are two numbers that add up to " + b);
       } else {
           System.out.println("There are no numbers that add up to " + b);
       }
   }

   static int[] findAddingNumbers(int[] arr, int t) {
       Arrays.sort(arr);
       int lo = 0;
       int hi = (arr.length - 1);
       while (lo < hi) {
           if (arr[lo] + arr[hi] == t) {
               return new int[]{arr[lo], arr[hi]};
           } else if (arr[lo] + arr[hi] < t) {
               lo++;
           } else {
               hi--;
           }
       }
       return new int[]{};
   }

   public static void main(String[] args) {
       int[] provided = {8, 5, 7, 3, 2, 9, 6, 4};
       int target = 12;
       System.out.println("These two numbers that add up to " + target + " are " + Arrays.toString(Addends.findAddingNumbers(provided, target)));
       Addends.doTwoNumbersAdd(provided, target);
   }

}

Find two numbers that add up

You have a set of numbers and another number (target) that is comprised of two numbers in the set added up. How do you find if there are two numbers in the set that add up? import java.util.Arrays;

public class TwoThatAdd {

   static int[] showAdded(int[] set, int target) {
       Arrays.sort(set);
       int left = 0;
       int right = (set.length - 1);
       while (left < right) {
           if (set[left] + set[right] == target) {
               return new int[]{set[left], set[right]};
           } else if (set[left] + set[right] < target) {
               left++;
           } else {
               right--;
           }
       }
       return new int[]{};
   }

   public static void main(String[] args) {
       int[] options = {2, 4, 6, 7, 11, 13, 16};
       int target = 18;
       System.out.println(Arrays.toString(TwoThatAdd.showAdded(options, target)));
   }

}

Find distinct letters in a word

import java.util.HashSet; import java.util.Set;

public class Distinct {

   void print_distinct(String given) {
       /*Take the given word and split it with commas to create an array*/
       String[] arrayed = given.split("");
       /*Add the values of the arrays to a set*/
       Set<String> set = new HashSet<>(Arrays.asList(arrayed));
       /*A set contains distinct values. Print them*/
       System.out.println("Print distinct contents" + Arrays.toString(set.toArray()));
   }

   public static void main(String[] args) {
       Distinct d = new Distinct();
       String given = "mississippi";
       d.print_distinct(given);
   }

}