Archive for the 'Algorithms' Category

 

How to use PriorityQueue

Apr 03, 2015 in Algorithms, Java

From http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue


// TestPQ.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestPQ {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue =
            new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}


// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Fibonacci algorithm iterative

Jan 28, 2015 in Algorithms

from
http://www.csd.uwo.ca/courses/CS1027b/code/FibonacciDemo.java


    /** Method to calculate the nth Fibonacci number iteratively.
     * @param n
     * @return nth Fibonacci number
     * precondition: n >= 1
     */
    public static long ifib(long n) {
        if (n &lt 2) {
            return 1;
        } else {
            long prev = 1, current = 1, next = 0;
            for (long i = 3; i &lt= n; i++) {
                next = prev + current;
                prev = current;
                current = next;
            }
            return next;
        }
    }

Fibonacci algorithm recursive

Jan 28, 2015 in Algorithms

from http://javadecodedquestions.blogspot.com/2013/01/java-interviews-frequently-asked-puzzles.html


public class FibonacciNumber {
  public static int fibonacci(int n) {
   if (n < 2) {
    return n;
   }
   else {
    return fibonacci(n - 1) + fibonacci(n - 2);
   }
  }
}

from http://stackoverflow.com/questions/8965006/java-recursive-fibonacci-sequence


public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Dakini Princess ..

Nov 29, 2014 in Algorithms

A dakini (Sanskrit: “sky dancer”) is a Tantric priestess of ancient India who “carried the souls of the dead to the sky”. This Buddhist figure is particularly upheld in Tibetan Buddhism. The dakini is a female being of generally volatile temperament, who acts as a muse for spiritual practice.
. . .

dakini

. . .

Merge two sorted arrays in Java

Oct 09, 2013 in Algorithms, Java

. . .

From: based on http://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array


public class m2a {

    public static int[] merge(int[] a, int[] b) {

        int[] ma = new int[a.length + b.length];
        int ax = 0, bx = 0, mx = 0;
        while (ax < a.length && bx < b.length) {
            if (a[ax] < b[bx]) {
                ma[mx++] = a[ax++];
            }
            else {
                ma[mx++] = b[bx++];
            }
        }

        while (ax < a.length) {
            ma[mx++] = a[ax++];
        }

        while (bx < b.length) {
            ma[mx++] = b[bx++];
        }

        return ma;
    }

    public static void main(String[] args) {
        m2a om2a = new m2a();
        int a[] = {1, 3, 5, 7};
        int b[] = {3, 4, 6, 9};
        int ma[] = om2a.merge(a, b);
        for ( int mx = 0 ; mx < ma.length ; mx++ ) {
            System.out.print(ma[mx] + " ");
        }
        System.out.println();
    }

}

More compact, from same post, newer answer ..


public class m2a {

    public static int[] merge(int[] aa, int[] ba) {

        int[] ma = new int[aa.length + ba.length];
        int ax = 0, bx = 0, mx = 0;

        while (ax < aa.length && bx < ba.length) {
            if (aa[ax] < ba[bx])       
                ma[mx++] = aa[ax++];
            else        
                ma[mx++] = ba[bx++];               
        }

        while (ax < aa.length)  
            ma[mx++] = aa[ax++];

        while (bx < ba.length)    
            ma[mx++] = ba[bx++];

        return ma;
    }

    public static void main(String[] args) {
        m2a om2a = new m2a();
        int a[] = {1, 3, 5, 7};
        int b[] = {3, 4, 6, 9};
        int ma[];

        ma = om2a.merge(a, b);
        for ( int mx = 0 ; mx < ma.length ; mx++ ) {
            System.out.print(ma[mx] + " ");
        }
        System.out.println();
    }

}

Entropy ..

Jul 22, 2011 in Algorithms, Linux

From: http://rackerhacker.com/2007/07/01/check-available-entropy-in-linux/

Entropy is the measure of the random numbers available from /dev/urandom, and if you run out, you can’t make SSL connections.

About The Squonk ..

Apr 02, 2010 in Algorithms

The Squonk is of a very retiring disposition and due to its ugliness, weeps constantly. It is easy prey for hunters who simply follow a tear-stained trail. When cornered it will dissolve itself into tears.
True or False?

http://www.sing365.com/music/lyric.nsf/Squonk-lyrics-Genesis/6EF5A0D7E2CAE720482569600014CC3F

Reversing a singly-linked list in Java .. iterative and recursive methods ..

Dec 27, 2009 in Algorithms, Java

From http://www.java2blog.com/2014/07/how-to-reverse-linked-list-in-java.html


public void reverse(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;
    ListNode next = null;

    while (curr != null) {
        next = curr.next;
        curr.next = prev; // reverse link to previous
        prev = curr;
        curr = next;
    }

    return prev;
}

Recursive method:

public ListNode reverseList(ListNode head) {
    // from: http://www.java2blog.com/2014/07/how-to-reverse-linked-list-in-java.html
    if ( head == null || head.next == null )
        return head;

    ListNode rlist = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return rlist;
}

. . .

Breadth first search traversal algorithm..

Dec 02, 2009 in Algorithms, Java

http://en.allexperts.com/q/Computer-Science-3197/Bread-First-Search-Algorithm.htm


BFS(G, s)
 for each vertex u in V - { s } do
   u.color = white
   u.dist = infinity  // ''dist'' is distance from s
   u.pred = nil       // ''pred'' is predecessor
 s.color = gray
 s.dist = 0
 s.pred = nil
 Q = { s }            // ''Q'' is a FIFO queue
 while Q not empty do
   u = Q.head         // get element on top of queue
   for each v in neighbors(u) do  // visit every node u has an edge to
     if v.color == white then
       v.color = gray
       v.dist = u.dist + 1
       v.pred = u
       Q.enqueue(v)   // add v to back of queue
   Q.dequeue          // pop u off top of queue
   u.color = black

And a bit more Java-ish..


BFS(root) {
  cn = root;

  s.push(cn.getValue()); // Save node value on stack
  cn.setValue(-1); // mark node visited
  q.enqueue(cn);

  while(! q.isEmpty() ) {
    cn = q.dequeue();
    foreach v in cn.getChildren() {
      if (v.getValue() != -1) {
        // This node not visited yet
        s.push(v.getValue()); // save node value on stack
        v.setValue(-1); // mark node visited
        q.enqueue(v);
      }
    }
  }

}

And even simpler..


BFS(root) {
  cn = root;

  cn.visit(); // mark node visited
  q.enqueue(cn);

  while(! q.isEmpty() ) {
    cn = q.dequeue();

    foreach v in cn.getChildren() {
      if ( ! v.visited() ) {
        // This node not visited yet
        v.visit(); // mark node visited
        q.enqueue(v);
      }
    }
  }

}

Java example of basic cache (LRU) using LinkedHashMap ..

Aug 24, 2009 in Algorithms, Java, JavaUsage

From http://stackoverflow.com/questions/1229780/question-about-lru-cache-implementation-in-java

import java.util.Map;
import java.util.LinkedHashMap;

public class t1 {

    final int MAX_ENTRIES = 2;

    Map cache = new LinkedHashMap(MAX_ENTRIES+1, .75F, true) {
        // This method is called just after a new entry has been added
        public boolean removeEldestEntry(Map.Entry eldest) {
            System.out.println("eldest: " + eldest.getKey() + "=" + eldest.getValue());
            return size() > MAX_ENTRIES;
        }
    };

    public void cacheAdd(String pkey, String pstr) {
        // Add to cache
        cache.put(pkey, pstr);
    }

    public static void main(String[] args) {
        t1 ot1 = new t1();
        ot1.cacheAdd("k1", "str1");
        ot1.cacheAdd("k2", "str2");
        ot1.cacheAdd("k3", "str3");
        ot1.cacheAdd("k4", "str4");
    }

    /* --
// Get object
Object o = cache.get(key);
if (o == null && !cache.containsKey(key)) {
    // Object not in cache. If null is not a possible value in the cache,
    // the call to cache.contains(key) is not needed
}

// If the cache is to be used by multiple threads,
// the cache must be wrapped with code to synchronize the methods
cache = (Map)Collections.synchronizedMap(cache);
-- */

}

Also, see http://codeidol.com/java/javagenerics/Maps/Implementing-Map/
. . .