String Ordered Permutation Algorithm Problem

String Permutation Problem

The algorithm problem goes something like this:

If you are given a character and its possible substitution set, then write a function that would print all the permutation of its characters.

Eg.

Given word “java”

Substitution Set =>
j [“J”, “7”]
a [“@”, “J”, “9”]
v [“V”, “^”]

Based on this, the possible permutations could be: J@V@, 7JV9..

Here is my approach using java


package com.gullele;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author kaleb@gullele.com
 *
 */
public class PassPermutation {
	
	/**
	 * Holds the result of the permutation
	 */
	private List result;
	
	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		PassPermutation word = new PassPermutation();
		word.initializeResult();
		
		List words = word.wordToListMapper("java");
	
		word.permuteIt("", words, 0);
		
		for (String str : word.result) {
			System.out.println(str);;
		}
	}
	
	/**
	 * Recursive function to handle the permutation.
	 * @param words
	 */
	private void permuteIt(String part, List words, int index) {
		int size = words.size();
		if (index == size-1) {
			String word = words.get(words.size()-1);
			for (int i=0 ; i < word.length() ; i++) {
				this.result.add(part + word.charAt(i));
			}
		} else {
			String word = words.get(index);
			index++;
			for (int j=0 ; j < word.length() ; j++) {
				part += word.charAt(j);
				permuteIt(part, words, index);
				part = part.substring(0, part.length()-1);
			}
		}
	}
	
	private void initializeResult() {
		this.result = new ArrayList();
	}
	
	/**
	 * A word to its combination mapping
	 * @param word
	 * @return
	 */
	private List wordToListMapper(String word) {

		Map mapper = this.dictionary();
		List mapped = new ArrayList();
		
		for (Character c:word.toCharArray()) {
			if (mapper.containsKey(c)) {
				mapped.add(mapper.get(c));
			}
		}
		
		return mapped;
	}
	
	/**
	 * A mapping dictionary.
	 * @return
	 */
	private Map dictionary() {
		
		Map mapper = new HashMap();
		mapper.put('j', "J7");
		mapper.put('a', "@J9");
		mapper.put('v', "v^");
		
		return mapper;
	}
}

setting JAVA_HOME on mac osx

How to set JAVA_HOME ON MAC OSX computer

Setting java_home as environment variable might be almost required especially when you use frameworks. Frameworks like axis2 web server and others. Also some code editors require that too.

What is environment variable

Those are variables that would allow you to execute command line actions from any directory, basically from everywhere.

The simplest example is using java -version. In this case, if you don’t have explicit environment variable on where to look for, it requires you to either be in the java folder or to fully list the whole path till bin folder.

Setting JAVA_HOME in mac osx

The first part is to make sure you have java installed in your machine.

java -version

If this is giving you an output with the version, then it means java is installed, otherwise, you should first install it.

The following task will be to find out where the binary files are located.

Click the apple icon on the left top corner of your mac and select system preferences..

system preference

system preference

And from there click Java and you will get the path information from there.

Once you got where the java is located, usually on /Library/Java/JavaVirtualMachines/jdk1.***/Contents/Home

Open the bash properties file


vi ~/.bash_profile

And add the java path here

export JAVA_HOME=export JAVA_HOME=/Library/Java/JavaVirtualMachines/jdk1.8.0_91.jdk/Contents/Home

The above would be what it would look like fro jkd 1.8 on my El Capitan macbook pro.

hello world weblogic – hello world tutorial on weblogic

hello world weblogic app server

There are lots of application servers for java and oracle weblogic is one of them. As of this writing the current and latest weblogic server is 12c

I will show a simple hello world tutorial on weblogic. The tutorial is for beginners of weblogic server.

This hello world weblogic tutorial assumes you have java skill already.

Installing weblogic server

First thing first, lets install and configure weblogic server

Go here and download the one which says Quick Installer for Mac OSX, Windows and Linux (209 MB). It will give you a zip file.

Unzip the file to get fmw_12.2.1.2.0_wls_quick.jar

Run the jar file as
java -Xmx1024m -jar fmw_12.2.1.2.0_wls_quick.jar
And follow the wizard – stay tuned it might take a while

Upon completion, you will get a folder wls12212

Get inside wls12212 folder and issue the following command to configure domain

$ bash oracle_common/common/bin/config.sh

The above command will trigger wizard to follow. Just pick the default values. There is a part where you will be asked for username and password as well.

To start the server run the following
bash user_projects/domains/base_domain/startWebLogic.sh

And try to access the server through http://localhost:7001/console

Yaay.. you got your weblogic server up and running.

 

web logic server

Now you can deploy any web applications to the server

On the left pane of the console, you will see deploy link and clicking on that should give you a tool to locate and deploy your war files or folders. If you have simple hello world web app war file upload it there.

You can get sample hello world war file from here

Download the above war file and go to deployments->configuration and click on install.

On the path, locate the downloaded war file and click next next.

Once it is loaded, access the file by going to http://192.168.56.1:7001/simple-servlet/simple

Passing composite object parameter to jersey in Restful Java web

How to pass complex object parameter to jersey

In this tutorial, I will try to show how to pass composite object as a parameter to jersey’s endpoint java application.

It seems like you are working on RESTful API based java application. In that case, chances are high that you are working with jersey.

If you are not familiar with jersey, jersey is an implementation of JAX-RS APIs. Hence, it is a seamless framework by which API based java projects can be implemented.

As of this writing, the current version of jersey is 2.23.
Continue reading Passing composite object parameter to jersey in Restful Java web

J2EE Maven Eclipse Hello World Tutorial Part Two

Hello World Beginner Tutorial using J2EE and Maven

This is part two of J2EE application with maven continued from Part One.

If you haven’t accomplished J2EE with Maven tutorial, please first complete it by going here

Maven relies highly on the pom.xml file that we would put on the project root folder. Lets do that.

In this part of J2EE tutorial and Maven tutorial, we will proceed from creating a pom.xml file which is the heart of maven.

3 Create the pom and compile the project using maven.

3.a put the following pom file in the MavenEclipseJ2EE directory.
Continue reading J2EE Maven Eclipse Hello World Tutorial Part Two

Check if two strings are anagrams or not

Are the two strings or phrases anagrams or not algorithm

First thing first, What is anagram?

Anagrams are phrases/words of which one can be created from the other with rearrangement of characters.

Examples of anagram strings:

Debit card and bad credit
George Bush and He Bugs Gore

Now, given two strings, how would do find if the strings are anagrams or not.

The approach I used is a follows:

1. remove the space out of the strings
2. compare the length of strings, if they don’t match, they ain’t anagrams
3. sort the characters of each string
4. check character by character and see if they match till the end

This is approach I used with o(nlogn) because of the sorting part. All the others can be done in o(n)

A java solution for anagram algorithm

apache error

Java Tomcat error: can not access a member of class with modifiers

Class org.apache.catalina.core.DefaultInstanceManager can not access a member of class with modifiers “” sun.reflect.Reflection.ensureMemberAccess(Reflection.java:102)

If you are on tomcat/or anyother webserver for J2EE and getting this error, then the most probable servlet you have would look like this


package package;

import java.io.IOException;
import java.io.PrintWriter;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

class MyServletClass extends HttpServlet {
...
...
...
}

The fix:

You have missed the class modifier public

public class MyServletClass

Should solve the problem

pass all the jars in classpath when compiling java

How to pass multiple jar files while using javac – compiling java classes

If you have single jar file, you can pass as: lets assume you are compiling file.java

javac path/to/file.java -classpath "path/to/jar/file.jar" -d classpath

But how about if you have multiple jar files to be included in the class path?

If you are on windows you can list the jar files separated by semi colon(;) and in unix you can pass with colon(:)

javac path/to/java/file.java -classpath "file1.jar:file2.jar:dir/*"

The last example is for unix environment but you can apply it to windows with proper path and semicolon

find complementary numbers

Find K Complementary numbers from array Java implementation

Find K complementary numbers from the given array

This is another approach to the problem that I have done it here. On that post, a good deal of visitors pointed out that it is actually o(n*n) not o(n) as I claimed.

Yes, the naive usage of Hashmap for holding the numbers has soared the performance and I have changed the approach as follows.

To remind the k complementary problem and its solution, you are given array of numbers and a number k of which you are going to find numbers that give k complementary. The following is an example of it.

The problem is, given numbers like 7, 1, 5, 6, 9, 3, 11, -1 and given number 10, write a script that would print numbers that would add to 10. In the example, it would be like
7 and 3, 1 and 9, -1 and 11.

Thanks Reda and mtrad for your correction.


package algorithm;

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

/**
 * Algorithm to find the pairs making the K complementary in O(n) complexity
 * 
 * @author http://gullele.com
 */
public class KComplementary2 {
	
	public static void main(String[] args) {
		KComplementary2 kcomp = new KComplementary2();
		int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
		
		for (Integer number : kcomp.getKComplementaryPairs(10, numbers)) {
			System.out.println(" Pairs are "+ number + " and " + (10-number));
		}
	}
	
	public KComplementary2() {}
	
	/**
	 * An algorithm to find the pair from the given array that would sum up the given K
	 * 
	 * @note - the algorithm would be done in o(n)+o(nlogn). First it will run through the whole 
	 * numbers and creates a temporary list of pairs in HashMap with 
	 * (value, sum-value). 
	 * @param sum
	 * @param listOfIntegers
	 * @return
	 */
	public List getKComplementaryPairs(int sum, int[] listOfIntegers) {
		
		/*
		 * The algorithm works using front and last pointers on ascendingly sorted array. The front would be 
		 * instantiated with 0 and last with length-1; if the arr[front]+arr[last] == sum, then pick
		 * the numbers and add them to the pair array.
		 * if their sum is greater than sum, it means time to check the  second higher number that is lower
		 * than the current highest number. And the reverse would hold true if the sum is less than the sum
		 * time to move to the next higher number from the lower side.
		 */
		if (listOfIntegers == null || listOfIntegers.length == 0) {
			return null;
		}
		
		//quick sort the array 
		quickSort(0, listOfIntegers.length-1, listOfIntegers);
		
		int[] sortedArray = listOfIntegers;
		
		//holder for the complementary pairs
		List pairs = new ArrayList();
		int frontPointer = 0;
		int lastPointer = sortedArray.length-1;
		
		while (frontPointer < lastPointer) {
			int currentSum = sortedArray[frontPointer] + sortedArray[lastPointer];
			if (currentSum == sum) {
				/*
				 * Since sum is found, increment front and decrement last pointer
				 * Only one number is required to be hold, the other can be found 
				 * from sum-number since complementary 
				 */
				pairs.add(sortedArray[frontPointer]);//adding is o(1)
				frontPointer++;
				lastPointer--;
			} else if (currentSum > sum) {
				lastPointer--;
			} else {
				frontPointer++;
			}
		}
		
		return pairs;
	}
	
	/**
	 * sort the numbers. I have used quick sort here. QuickSort is nlogn in average case 
	 * well, in worst case it still would be n**2 though :(
	 * @param numbers
	 * @return sorted array numbers.
	 */
	public void quickSort(int lowerIndex, int higherIndex, int[] numbers) {
		/*
		 * Recursively inarray sort. Start from arbitrary value to compare from and recursively sort its 
		 * left and right.
		 */
		int pivot = lowerIndex+(higherIndex-lowerIndex)/2;
		int lower = lowerIndex;
		int higher = higherIndex;
		
		while (lower < higher) {
			while (numbers[lower] < numbers[pivot]) {
				lower++;
			}
			while (numbers[higher] > numbers[pivot]) {
				higher--;
			}
			
			//swap those needed to be on the left on those on the right.
			if (lower <= higher) {
				int temp = numbers[lower];
				numbers[lower] = numbers[higher];
				numbers[higher] = temp;
				lower++;
				higher--;
			}
		}
		if (lowerIndex < higher) {
			quickSort(lowerIndex, higher, numbers);
		}
		
		if (lower < higherIndex) {
			quickSort(lower, higherIndex, numbers);
		}
	}
}

Love algorithms? See how you would solve the following

Can you find the three numbers that would sum to T from given array?

From a file of billion numbers, find missing numbers with limited memory

Find longest palindrom from sequence of characters

Given the string, find the longest palindrom you can form from it


/**
 * @author gullele.com
 */
public class LongestPalindrom {
	public static void main(String[] args) {
		LongestPalindrom longest = new LongestPalindrom();
		System.out.println(longest.longest("zzbmbmbdmm"));
	}
	
	public String longest(String string) {
		if (string.length() == 0 || string == null) {
			return "";
		}
		

		StringBuffer palindrom = new StringBuffer();
		Map charBag = new HashMap();
		for (Character c : string.toCharArray()) {
			int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
			if ((totalChar + 1) % 2 == 0) {
				palindrom.append(c);
				palindrom = palindrom.insert(0, c);
				charBag.remove(c);
				continue;
			}
			charBag.put(c, ++totalChar);
		}
		
		if (charBag.size() > 0) {
			Iterator it = charBag.entrySet().iterator();
			Map.Entry pair = (Map.Entry)it.next();
			String c = pair.getKey().toString();
			palindrom.insert(palindrom.length()/2, c);
		}
		return palindrom.toString();
	}
}