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

Java solution for checking anagram strings – tell if phrases are anagrams

Anagram Algorithm in Java solving if two strings are anagrams or not

This is the java solution for checking if the given two strings are anagrams or not. For the examples of anagrams and the approach I used and analysis of the code, see analysis of anagram algorithm

Find missing numbers from billion number lists with limited memory

Anagram algorithm in Java solution


package algorithm;

import java.util.Arrays;

/**
 * Determine if the given two strings are anagrams or not 
 * A solution in java programming language
 * @author https://gullele.com
 * 
 * Analysis - this would run in o(nlogn) for the sorting part and all other others would be in o(n)
 * Hence it is o(nlogn) + o(n) ==> o(nlogn) assuming worst case sorting.
 */
public class Anagram implements AnagramFinder {

	public static void main(String string[]) {
		String string1 = "Debit Card ";
		String string2 = "bad credit";
		
		AnagramFinder anagramFinder = new Anagram();
		if (anagramFinder.areAnagrams(string1, string2)) {
			System.out.println("Anagrams");
		} else {
			System.out.println("Not Anagrams");
		}
	}
	
	public Anagram() {
		
	}
	
	@Override
	/**
	 * Verify if the given words are anagrams or not
	 */
	public boolean areAnagrams(String s1, String s2) {
		if (s1 == null || s2 == null) { //I don't think we would assume null is anagram at all..
			return false;
		}
		
		//get rid of the spaces 
		s1 = s1.replaceAll("\\s+", "").toLowerCase();
		s2 = s2.replaceAll("\\s+", "").toLowerCase();
		
		//no need to proceed if the length is not the same. assumed the anagrams are the same in length
		if (s1.length() != s2.length()) {
			return false;
		}
		
		//then order the string in characters
		char[] ordereds1 = sortChars(createCharArray(s1)); //o(nlogn)
 	 	char[] ordereds2 = sortChars(createCharArray(s2)); //o(nlogn)
		
 	 	//first thing first, if the size is not the same, then we are done
 	 	int index = 0;
 	 	while (index < ordereds1.length) { //this would run o(n)
 	 		if (ordereds1[index] != ordereds2[index]) {
 	 			return false;
 	 		}
 	 		index++;
 	 	}
 	 	
		return true;
	}
	
	/**
	 * Takes the string and converts it to characters
	 * @param string
	 * @return
	 */
	private char[] createCharArray(String string) {
		return new char[string.length()];
	}
	
	/**
	 * if I have to implement it I can use quick sort and make it at least n(logn)
	 * @param chars
	 * @return array
	 */
	private char[] sortChars(char[] chars) {
		Arrays.sort(chars);
		return chars;
	}
}

The above anagram algorithm solution is in java but it can be performed in any programming language.

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

missing numbers in billion records

Finding missing numbers from billion sequential number list file

You are given a billion numbers but some are missing

This is interesting algorithm question. With my first attempt I have tried it with o(n**2) which needs improvement of course.

Do you know how to find complementary numbers in given array?

The question in detail

You are given a randomly listed billion numbers, from 1 to billion that is. And there are a couple of numbers missing from this list.

The task is to find those missing numbers from a billion list, and you are given a very limited memory resource – you can assume storage is not an issue.

How I proceed with this solution

Continue reading Finding missing numbers from billion sequential number list file

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

testing k complementary pairs algorithm with junit

This is the test class for the java solution of the k-complementary problem listed here


package algorithm;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Before;
import org.junit.Test;

/**
 * Testing KComplementary algorithm
 * 
 * @author Kaleb Woldearegay
 *
 */
public class KComplementaryTest {
	
	private KComplementary kComplementary;
	
	@Before
	public void initiate() {
		this.kComplementary = new KComplementary();
	}
	
	
	@Test
	public void test1() {
		Integer[][] expectedResult = new Integer[][]{{1,9},{5,5},{9,1}};
		int[] test = new int[]{1,5,9};
		
		assertArrayEquals(this.kComplementary.getKComplementaryPairs(10,  test), expectedResult);
	}
	
	@Test
	public void test2() {
		Integer[][] expectedResult = new Integer[][]{{5,7},{7,5}};
		int[] test = new int[]{3,5,7};
		
		assertArrayEquals(this.kComplementary.getKComplementaryPairs(12,  test), expectedResult);
	}
	
	@Test
	public void test3() {
		Integer[][] expectedResult = new Integer[][]{{-1,1},{0,0},{1,-1}};
		int[] test = new int[]{5,-1,0,-2,3, 1};
		
		assertArrayEquals(this.kComplementary.getKComplementaryPairs(0,  test), expectedResult);
	}

}

See more algorithm solutions by clicking Here

Find the pairs that makes K Complementary in the given array java solution

Find K complementary pairs from the given array

So the problem is, given an array of numbers, you are going to find the pairs whose sum is K.

Say, if you are given 7, 1, 5, 6, 9, 3, 11, -1 and K = 10 then the pairs would be

=> 1 and 9
=> 3 and 7
=> 11 and -1

Here is the O(n) solution for the K complementary problem in java

It turns out, this is not a pure O(n) solution. Can you spot why?


package algorithm;

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

/**
 * Algorithm to find the pairs making the K complementary in O(n) complexity
 * 
 * @author http://gullele.com
 * @see KComplementaryTest.java - a JUnit test for this class
 */
public class KComplementary {
	
	private Map pairs;
	
	public static void main(String[] args) {
		KComplementary kcomp = new KComplementary();
		int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
		Integer[][] pairs = kcomp.getKComplementaryPairs(10, numbers);
		
		for (Integer[] thePairs : pairs) {
			System.out.println(" Pairs are "+thePairs[0] + " and " + thePairs[1]);
		}
	}
	
	public KComplementary() {
		this.pairs = new HashMap();
	}
	
	/**
	 * 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). 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 Integer[][] getKComplementaryPairs(int sum, int[] listOfIntegers) {
		
		/*
		 * I could have used the ArrayList assuming the number of pairs we are getting 
		 * is not known, but giving it a little bit of thought, the number of pairs 
		 * is known in advance, at least the maximum we can get is known.
		 * By not using the Array list, the algorithm would run O(n) rather than
		 * O(n**2) since ArrayList.add would would be O(n) by itself 
		 */
		//List complementaryPairs = new ArrayList();
		Integer[][] complementaryPairs = new Integer[listOfIntegers.length][2];
		//First fill up the pairs with the complementary numbers
		for (int number : listOfIntegers) { //O(n) complexity
			this.pairs.put(number, sum-number);
		}
		
		//then filter out the pairs that don't have corresponding complementary number
		int index = 0;
		for (int number : listOfIntegers) { //O(n) complexity 
			int complementary = sum - number;
			//check if this key exists in the pairs
			if ( this.pairs.containsKey(complementary) ) {
				//Had I used array List this would have been used
				//Integer[] comps = {number, complementary};
				//complementaryPairs.add(comps); //this is O(n)
				complementaryPairs[index][0] = number;
				complementaryPairs[index][1] = complementary;
				index ++;
			}
		}
		//System.out.println(index);
		//Now trim the array since we know the exact record
		Integer[][] trimmed = new Integer[index][2];
		
		index = 0;
		for (Integer[] item : complementaryPairs) { //O(n) complexity
			if (item[0] != null) {
				trimmed[index][0] = item[0];
				trimmed[index][1] = item[1];
			}
			index++;
		}
	
		//Total complexity O(n)+O(n)+O(n) ==> O(n)
		
		//had I used arrayList this would have been used
		//return complementaryPairs.toArray(new Integer[0][0]);
		return trimmed;
	}
}


The above solution runs and would do the job without a problem. But it is not linear solution as it claims to be.

I have got another solution that would explain why and comes up with a solution for it. Check it out here

You can see the jUnit for this class also at here

Check if there are three numbers a, b, c giving a total T from array A

I got this question while helping a friend on the course work. It is relatively simple question. But the way how it is approached can make a difference on efficiency.

The question is, given an array of numbers, you are to find if there are three numbers that would total the given number T.

If done in a very naive way, it can soar to o(n^3) like having three loops and checking the sum inside the third loop.. well.. this is a no no..

I have approached it in a log n ( for sorting) and n for (searching) approach..


package algorithm;

import java.util.Arrays;

/**
 * Given an array of integers, find if there are three numbers that would sum up to the 
 * number T
 * 
 * @author http://gullele.com
 *
 */
public class ThreeNumbersSummingT {
	public static void main(String[] args) {
		int[] test = new int[]{1,3,4,5,10,12, 18};
		ThreeNumbersSummingT summt = new ThreeNumbersSummingT();
		
		int[] response = summt.findThreeNumbers(test, 29);
		
		if (response.length > 1) {
			for(int num : response) {
				System.out.println(num);
			}
		} else {
			System.out.println(":( Couldn't find those three gems");
		}
				
	}
	
	public int[] findThreeNumbers(int[] nums, int t) {
		
		int[] indexes = new int[1];
		if (nums.length == 0 || nums.length <= 2) {
			return indexes;
		}
		
		//for primitive this would be quick sort so we have nlogn
		Arrays.sort(nums);
		
		int minIndex =0;
		int maxIndex = nums.length-1;
		int current = 1;
		while (minIndex != maxIndex) {
			if (nums[minIndex] + nums[maxIndex] + nums[current] == t) {
				int[] summingNumbers = new int[3];
				summingNumbers[0] = nums[minIndex];
				summingNumbers[1] = nums[current];
				summingNumbers[2] = nums[maxIndex];
				return summingNumbers;
			}
			
			int lookingFor = t-(nums[minIndex] + nums[maxIndex]);
			//if the number being sought is beyond the max, then jack up the min index
			if (lookingFor >= nums[maxIndex]) {
				minIndex++;
				current = minIndex + 1;
			} else if (nums[minIndex] + nums[maxIndex] + nums[current] < t) {
				current++;
			} else {
				maxIndex--;
				current = minIndex + 1;
			}
			
		}
		
		return indexes;
	}
}


binary tree problems with solution

today is saturday and was catching upon some blogs. Then come across some binary tree algorithms and it reminded me the famous stanford binary tree questions.. decided to work on those and got to the mid of it..
Actually the questions get harder as you go further.. the first 7 are relatively easy..
I will continue to work on them and post my solution here.
the solutions are given on the this page but, it is advisable to work them out without looking a the solution..

here it is!


#include
#include
/*
 * @author http://gullele.com
 * binary tree problems and solutions.
 */
struct Node
{
	int number;
	struct Node *left;
	struct Node *right;
};

int minValue(struct Node *head);
int maxDepth(struct Node *head);
int countNode(struct Node *head);
void printTree(struct Node *head);
void postOrderTraversal(struct Node *head);
struct Node *createNode(int value);
int hasPathSum(struct Node *head, int sum);
struct Node *head = NULL;
struct Node *head2=NULL;
int main()
{
	struct Node *head=createNode(10);
	struct Node *left=createNode(8);
	struct Node *right=createNode(15);
	struct Node *right1=createNode(5);
	struct Node *right2=createNode(1);
	head->left=left;
	head->right=right;
	left->left=right1;
	right1->left=right2;

	struct Node *head2=createNode(5);
	struct Node *two=createNode(2);
	struct Node *seven=createNode(7);
	struct Node *eleven=createNode(11);
	struct Node *lfour=createNode(4);
	struct Node *thirteen=createNode(13);
	struct Node *eight=createNode(8);
	struct Node *rfour=createNode(4);
	struct Node *one=createNode(1);
	
	head2->left=lfour;
	head2->right=eight;
	lfour->left=eleven;
	eleven->left=seven;
	eleven->right=two;
	eight->left=thirteen;
	eight->right=rfour;
	rfour->right=one;

	printf("Size of the tree is %d n", countNode(head));
	printf("Max depth is %d n", maxDepth(head)-1);
	printf("Minimum Value is %d n", minValue(head));
	printTree(head2);
	printf("n");
	postOrderTraversal(head);
	int hasSum = hasPathSum(head2,17);
	if(hasSum)
		printf("it has sum");
	else
		printf("it does not has sum");
	return 0;
}

/**
 * Takes the head of the binary tree and counts how many children are there in the tree
 * it will recursively count the left and right nodes to come to the conclusion
 */
int countNode(struct Node *head)
{
	if (head==NULL)
	{
		return 0;
	}
	return countNode(head->left)+1+countNode(head->right);
}

/**
 * Finds the maximum depth of the tree
 *
 */
int maxDepth(struct Node *head)
{
	int maxLength = 0;
	if (head==NULL)
	{
		return 0;
	}
	else
	{
		int leftMax = 1 + maxDepth(head->left);
		int rightMax = 1 + maxDepth(head->right);
		if (leftMax > rightMax)
		{
			return leftMax;
		}
		return rightMax;
	}
}

/**
 * Works on the Binary Search Tree - since on the BST, for sure the left child is always lesser in value.
 */
int minValue(struct Node *head)
{
	if(head==NULL)
		return 0; //might not be valid answer here
	struct Node *current=head;
	while(current->left!=NULL)
	{
		current=current->left;
	}
	return current->number;
}

/**
 * Prints the value of the BST
 * this is inorder traversal
 */
void printTree(struct Node *head)
{
	if (head==NULL)
	{
		return;
	}
	else
	{
		printTree(head->left);
		printf("%d, ", head->number);
		printTree(head->right);
	}
}	

int hasPathSum(struct Node *head, int sum)
{
	int localsum = 0;
	if (head == NULL)
	{
		return 0;
	}
	else if(head->left==NULL && head->right==NULL)
	{
		return (sum-head->number == 0);
	}
	else
	{
		int temp=sum-head->number;
		return hasPathSum(head->left, temp) || hasPathSum(head->right, temp);
	}
}
/**
 * Post order traversal version of the tree traversal
 */
void postOrderTraversal(struct Node *head)
{
	if (head==NULL)
	{
		return;
	}
	else
	{
		printTree(head->left);
		printTree(head->right);
		printf("%d, ", head->number);
	}
}

/**
 * Create new node
 */
struct Node *createNode(int value)
{
	struct Node *newNode=malloc(sizeof(struct Node));
	newNode->number=value;
	newNode->left=NULL;
	newNode->right=NULL;
	return newNode;
}