Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Numbers of the form 2^i 5^j

/**
*
*/
package org.code.dp;

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

/**
*
@author Purna
*
*/
public class Numbers2i5j {


public static void main(String[] args) {
List
<Integer> result = new ArrayList<Integer>();
result.add(Integer.valueOf(
1));

int x2Index = 0;
int x5Index = 0;

int curr = result.get(result.size() - 1);

int x2 = curr * 2;
int x5 = curr * 5;

for (int i = 0; i < 5; i++) {

int minimum = Math.min(x2, x5);
result.add(Integer.valueOf(minimum));
if (x2 == minimum) {
x2Index
++;
x2
= 2 * result.get(x2Index);

}
if (x5 == minimum) {
x5Index
++;
x5
= 5 * result.get(x5Index);
}
}
System.out.println(result);
}
}

Change Maker code in Java

/**
*
*/
package org.code.dp;

public class ChangeMaker {

static int makeChange(int amount, int denomination) {

if (denomination == 1) {
System.out.println(
"notes: " + amount + " denom " + denomination);
System.out.println(
"---------------------------------------");
return 1;
}
int next_denom = getNextDenom(denomination);
int ways = 0;
for (int notes = 0; notes * denomination <= amount; notes++) {
System.out.println(
"notes: " + notes + " denom " + denomination);
ways
+= makeChange(amount - notes * denomination, next_denom);
}
return ways;
}

private static int getNextDenom(int denom) {
switch (denom) {
case 5:
return 2;
case 2:
return 1;
case 1:
return 1;
}
return 0;

}
}

Cards Shuffle Code in Java

package org.code;
import java.util.Arrays;
import java.util.Random;

/**
*
@author Purna
*
* this class just shuffles the given set of cards assuming there are 52
* cards 1-52
*/
public class CardsShuffler {

public static Random randomGenerator = new Random();

public static void main(String args[]) {
int[] cards = new int[5];
for (int index = 0; index < cards.length; index++) {
cards[index]
= index + 1;
}

printCards(cards);
shuffleCards(cards);
}

/**
* shuffles the cards using
*
* Knuth Shuffle
*
*
@param cards
*/
private static void shuffleCards(int[] cards) {

for (int index = 1; index < cards.length; index++) {
int cardToShuffleWith = randomGenerator.nextInt(index);
swapNumbers(cards, index, cardToShuffleWith);
// printing the cards on every shuffle
printCards(cards);
}

}

/**
* Swaps two Cards
*
*
@param cards
*
@param index
*
@param cardToShuffleWith
*/
private static void swapNumbers(int[] cards, int index,
int cardToShuffleWith) {
int temp = cards[index];
cards[index]
= cards[cardToShuffleWith];
cards[cardToShuffleWith]
= temp;
}

/**
* prints the cards
*
*
@param cards
*/
private static void printCards(int[] cards) {
System.out.println(Arrays.toString(cards));
}
}

Shorten a URL

private static int uniqueId = 1925;
private static int radix = 62;
private static Map<String, String> urlsMap = new HashMap<String, String>();
static String[] elements = { "a", "b", "c", "d", "e", "f", "g", "h", "i",
"j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
"w", "x", "y", "z", "1", "2", "3", "4", "5", "6", "7", "8", "9",
"0", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L",
"M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y",
"Z" };
static public Map<String, Integer> map = new HashMap<String, Integer>();

public static void main(String arp[]) {
String shortenedUrl
= shortenURL("http://www.stumbleupon.com/su/28KqXE/www.funnyordie.com/slideshows/ff413570ec/awesomely-inappropriate-test-answers-from-kids/");
System.out.println(
"To redirect to original URL");
System.out.println(urlsMap.get(shortenedUrl));
for (int index = 0; index < elements.length; index++) {
map.put(elements[index],
new Integer(index));
}
decodeURL(shortenedUrl);
}

/**
*
@param string
*/
private static void decodeURL(String string) {
int sum = 0;
for (int i = 0; i < string.length(); i++) {
sum
+= map.get(string.charAt(i) + "") * Math.pow(62, i);
}
System.out.println(sum);
}

/**
* shortens a url
*
* Integer.toString
*
*
@param url
*
*
@return
*/
private static String shortenURL(String url) {
int numberToEnode = uniqueId;
StringBuilder code
= new StringBuilder();
while (numberToEnode > 0) {
code.append(elements[numberToEnode
% radix]);
numberToEnode
= numberToEnode / radix;
}
urlsMap.put(code.toString(), url);
return code.toString();
}

N-Queens Problem in Java

 

/**
*
*/
package org.code;

/**
*
@author Purna
*
*/
public class NQueens {

public int[] queenPlaceInRow;
int size;

/**
*
*/
public NQueens(int size) {
queenPlaceInRow
= new int[size];
this.size = size;
for (int i = 0; i < size; i++) {
queenPlaceInRow[i]
= Integer.MAX_VALUE;
}
}

public static void main(String[] args) {
NQueens nQueens
= new NQueens(8);
nQueens.placeQueen(
0);
}

/**
*
@param row
*/
private void placeQueen(int row) {

if (row == this.size) {
printBoard();
return;
}
for (int i = 0; i < this.size; i++) {
queenPlaceInRow[row]
= i;
if (check(row)) {
placeQueen(row
+ 1);
}
}

}

/**
*
@param row
*
@return
*/
private boolean check(int row) {
for (int i = 0; i < row; i++) {
int diffX = Math.abs(queenPlaceInRow[row] - queenPlaceInRow[i]);
int diffY = row - i;
if (diffX == 0 || diffX == diffY) {
return false;
}
}
return true;
}

/**
*
*/
private void printBoard() {
System.out.println(
"------------------------");
for (int i = 0; i < this.size; i++) {
for (int j = 0; j < this.size; j++) {
if (queenPlaceInRow[i] == j) {
System.out.print(
" Q ");
}
else {
System.out.print(
" . ");
}

}
System.out.println();

}
System.out.println(
"------------------------");

}
}

Kth Element in a list

int findKthElement(Object[] objects, int kth) {
        System.out.println("findKte");
        int i = rd.nextInt(objects.length);
        ArrayList listOne = new ArrayList<>();
        ArrayList listTwo = new ArrayList<>();
        for (int j = 0; j < objects.length; j++) {
            if ((int) objects[j] < (int) objects[i]) {
                listOne.add(objects[j]);
            } else if ((int) objects[j] > (int) objects[i]) {
                listTwo.add(objects[j]);
            }
        }
 
        if (kth <= listOne.size()) {
            return findKthElement(listOne.toArray(), kth);
        } else if (kth > (objects.length - listTwo.size())) {
            return findKthElement(listTwo.toArray(), kth
                    - (objects.length - listTwo.size()));
        } else {
            return (int) objects[i];
        }
    }

Anagram Detector

/** Checks if two words are anagrams or not
*
@param firstWord
*
@param secondWord
*/
public static boolean areAnagram(String firstWord, String secondWord) {

int numberOfUnique = 0;
int processed = 0;
if (firstWord.length() != secondWord.length()) {
return false;
}
int[] chars = new int[256];
for (int i = 0; i < firstWord.length(); i++) {
if (chars[firstWord.charAt(i)] == 0) {
numberOfUnique
++;
}
chars[firstWord.charAt(i)]
++;
}
for (int i = 0; i < secondWord.length(); i++) {
// this char is not there so false
if (chars[secondWord.charAt(i)] == 0)
return false;

chars[secondWord.charAt(i)]
--;

if (chars[secondWord.charAt(i)] == 0) {
processed
++;
if (numberOfUnique == processed) {
System.out.println(processed);
return secondWord.length() == processed + 1;
}
}

}

Remove duplicate Characters without extra memory in java

/**
* Without using extra(large) memory Complexity O(n^2)
*
@param word
*/
private static void removeDuplicates(char[] word) {
int currentIndex = 1;
for (int i = 0; i < word.length; i++) {
int j;
for (j = 0; j < currentIndex; j++) {
if (word[i] == word[j]) {
break;
}
}
if (currentIndex == j) {
word[currentIndex
++] = word[i];
}

}
while (currentIndex < word.length) {
word[currentIndex
++] = ' ';
}
}

Flyweight


Share objects when they are common some common examples are from the JDK
Integer and String objects
The object is restricted to be created through the factory and the object is shared.
/*

 public static Integer valueOf(int i) {
        assert IntegerCache.high >= 127;
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }
*/

Binary Search Tree in Java

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    Node<Key, Value> root;
    public void addNode(Key key, Value val) {
        addNode(this.root, key, val);
    }
    public Node addNode(Node<Key, Value> node, Key key, Value value) {
        if (node == null) {
            Node<Key, Value> nodeTemp = new Node<Key, Value>(key, value);
            if (this.root == null) {
                this.root = nodeTemp;
            }
            return nodeTemp;
        }
        int compareTo = key.compareTo((Key) node.keyT);
        if (compareTo < 0) {
            node.left = addNode(node.left, key, value);
        } else if (compareTo > 0) {
            node.right = addNode(node.right, key, value);
        } else {
            node.keyT = key;
            node.value = value;
        }
        return node;
    }
    Node<Key, Value> getNode(Key key) {
        Node<Key, Value> node = this.root;
        while (node != null) {
            int cmp = key.compareTo((Key) node.keyT);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else if (cmp == 0) {
                return node;
            }
        }
        return null;
    }
    private static void printInOrder(Node<Integer, String> node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<Integer, String>();
        bst.addNode(new Integer(7), "seven");
        bst.addNode(new Integer(8), "eight");
        bst.addNode(new Integer(9), "nine");
        bst.addNode(new Integer(5), "five");
        bst.addNode(new Integer(6), "six");
        bst.addNode(new Integer(4), "four");
        bst.addNode(new Integer(3), "three");
        bst.addNode(new Integer(10), "ten");
        bst.addNode(new Integer(2), "two");
        bst.addNode(new Integer(1), "one");
        printInOrder(bst.root);
    }
}
class Node<T extends Comparable<T>, Value> {
    T keyT;
    Value value;
    Node<T, Value> left;
    Node<T, Value> right;
    Node(T key, Value val) {
        this.keyT = key;
        this.value = val;
    }
}

Quick Sort in Java

 private static void quickSort(Integer[] toSortArray, int low, int high) {
        if (low >= high)
            return;
        int k = partition(toSortArray, low, high);
        quickSort(toSortArray, low, k - 1);
        quickSort(toSortArray, k + 1, high);
    }
    /**
     * given a number index low, it partitions array 
     * such that all numbers less than numbers[]low] are left
     * and greater are right
     * @param numbers
     * @param low
     * @param high
     * @return
     */
    private static int partition(Integer[] numbers, int low, int high) {
        int leftIndex = low;
        int rightIndex = high + 1;
        while (true) {            
            //find left index to swap
            while (numbers[++leftIndex] < numbers[low]) {
                if (leftIndex == high) {
                    break;
                }
            }
            //find right index to swap
            while (numbers[low] < numbers[--rightIndex]) {
                if (rightIndex == low) {
                    break;
                }
            }
            // pointers cross
            if (leftIndex >= rightIndex)
                break;
            //swap
            swap(leftIndex, rightIndex, numbers);
        }
        swap(low, rightIndex, numbers);
        return rightIndex;
    }
    private static void printArray(Integer[] toSortArray) {
        for (int i = 0; i < toSortArray.length; i++) {
            System.out.print(toSortArray[i] + " ");
        }
        System.out.println(" ");
    }
    /**
     * swap 2 numbers at the index
     * 
     * @param minIndex
     * @param index
     * @param numbers
     */
    private static void swap(int minIndex, int index, Integer[] numbers) {
        Integer temp = numbers[minIndex];
        numbers[minIndex] = numbers[index];
        numbers[index] = temp;
    }

Search 24 Bytes

Loading...