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 →

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?

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

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

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

Kadane’s algorithm in C – Dynamic Programming

How do we find a keys that hold maximum consecutive values in sum from the given array?
The usual approach could be O(n^2).

But Kadanes algorithm can perform this same problem in a linear time.
here is the implementation using C

#include <stdio.h>

/*
 * @author http://gullele.com
 * 
 */
void main()
{
        printf("Kadane's Algorithmn");
        int nums[] = {-1,2,3,-9,8,7,2};
        int start_index;
        int end_index;
        int sum = maximum_consequential_sum(nums, &start_index, &end_index);
        printf("maximum sum is %d n",sum );
        printf("maximum index starts at %d n", start_index);
        printf("maximum index ends at %d n", end_index);
}
/*
 * Get the maximum subsequent sum from the given array
 * function performing kadane's Algorithm 
 */
int maximum_consequential_sum(int* nums, int*start_index, int*end_index)
{
        int max_start_index = 0, max_end_index = 0;
        int max_sum = 0;
        int cur_index, cur_max_sum = 0;
        for(cur_index = 0; cur_index <= max_sum ; cur_index++)
        {
                cur_max_sum += nums[cur_index];
                if (cur_max_sum > max_sum)
                {
                        max_sum = cur_max_sum;
                        max_end_index = cur_index;
                }
                if (cur_max_sum < 0)
                {
                        cur_max_sum = 0 ;
                        max_start_index = cur_index + 1;
                }
        }
        *start_index = max_start_index;
        *end_index = max_end_index;
        return max_sum;
}

The above code is, of course, just for illustration purpose. Make sure to check
for empty array and possible division by zero stuff..

To run this on Linux

1. Save the above file as kadanes.c
2. go to terminal and locate to the file
3. gcc kadanes.c -o kadane
4 run as ./kadane

** you can use this code as you like. As the same time, I am not responsible for anything, in case if you use it.
Thanks

Click here to see more algorithm solutions