Algorithm Archives - Gullele's Corner

find longest word in the sentence

Find the longest word in the sentence

I am using javascript for this question.

It can be done in a lot of ways. The straight forward way could be the fastest probably. You will loop over the array of the words – you can split it with space – ” “.

Then just compare the value of the word length with maximum value and overwrite when it is higher – you know what I mean..

I will show the single liner for this though


var longestWord = "Guess what the longest word in the dictionary is".split(" ").sort(function(a, b){
    return b.length - a.length;
})[0];

Let’s go through what is going on..

The first part "Guess what the longest word in the dictionary is" is the given example sentence we are trying to find the longest word for.

Then we split the string into array of words using the split(" ") function. Now we have array to work with.

Then we sorted the array with sorter function passed to it. Sorter function in this one is anonymous function that we pass to it.

Finally we just took the first element of the sorted array which is sorted by the length of the word.

Also with the same concept, we have have it using reduce function;

"I still am having the wonderfulness of this thing ".split(" ").reduce((word1, word2) => word2.length > word1.length ? word2 : word1 );

That is it!

Get maximum occurring character

Find maximum occurring character from the given string

Max occurring character is the most frequent interview whiteboard question. Ok, there are so many of ways to handle this question and this is just one of them.

I have showed it with 6 characters as starting point and use those as reference. But you can extend that given object to hold as many characters as you want.
Continue reading Get maximum occurring character →

Flatten nested javascript array

How do you flatten array in javascript

If you are given an array that contains literals, arrays and objects and you want to get all the values to one array.

Here is the snippet using recursive function to attain that.


function implode(arr) {
	var res = [];
	for (var i =0; i < arr.length ; i++) {
    	if (Array.isArray(arr[i])) {
        	res = res.concat(implode(arr[i]));
		} else if(typeof arr[i] == 'object' ) {
			var values = Object.values(arr[i]);
        	for (var j = 0 ; j < values.length ; j++) {
            	if (!Array.isArray(values[j]) && typeof values[i] != 'object') {
					res.push(values[j]);
                }else{
                	res = res.concat(implode(values[j]));
				}
			}
		} else {
			res.push(arr[i]);
        }
	}
	return res;
}

javascript queue and stack implementation

Implement Queue Using two Stacks – JavaScript algorithm

Using stack data structure to implement queue in javascript

This is one way of implementing of the stack to be reused as queue using two stacks.

You may complain you are abusing the memory. But we are not copying the data on both stacks we are using the stacks for switching values only


            class Queue {
                constructor() {
                    this.inputStack = [];
                    this.outputStack = [];
                }

                enqueue(item) {
                    this.inputStack.push(item);
                }

                dequeue(item) {
                    this.outputStack = [];
                    if (this.inputStack.length > 0) {
                        while (this.inputStack.length > 0) {
                            this.outputStack.push(this.inputStack.pop());
                        }
                    }
                    if (this.outputStack.length > 0) {
                        console.log(this.outputStack.pop());
                        this.inputStack = [];
                        while (this.outputStack.length > 0) {
                            this.inputStack.push(this.outputStack.pop());
                        }
                    }
                }

                listIn() {
                    let i=0;
                    while(i < this.inputStack.length) {
                        console.log(this.inputStack[i]);
                        i++;
                    }
                }
                listOut() {
                    let i=0;
                    while(i < this.outputStack.length) {
                        console.log(this.outputStack[i]);
                        i++;
                    }
                }
            }

*There is part left out for improvement and refactoring. But, can you see a way to use only one while rather than two whiles and make it a bit efficient?

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
Continue reading String Ordered Permutation Algorithm Problem →

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

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