Algorithms

Coin Change

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

1) Optimal Substructure
To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.

#include<stdio.h>
// Returns the count of ways we can sum  S[0...m-1] coins to get sum n
int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;
    
    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;
    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;
    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Minimum insertions to form a palindrome

Given a string, find the minimum number of characters to be inserted to convert it to palindrome.

Before we go further, let us understand with few examples:
ab: Number of insertions required is 1. bab
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd
abcda: Number of insertions required is 2. adcbcda which is same as number of insertions in the substring bcd(Why?).
abcde: Number of insertions required is 4. edcbabcde

Let the input string be str[l……h]. The problem can be broken down into three parts:
1. Find the minimum number of insertions in the substring str[l+1,…….h].
2. Find the minimum number of insertions in the substring str[l…….h-1].
3. Find the minimum number of insertions in the substring str[l+1……h-1].

Recursive Solution
The minimum number of insertions in the string str[l…..h] can be given as:
minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise

// A Naive recursive program to find minimum number insertions
// needed to make a string palindrome
#include
#include
#include
// A utility function to find minimum of two numbers
int min(int a, int b)
return a < b ? a : b; }
// Recursive function to find minimum number of insersions
int findMinInsertions(char str[], int l, int h)
{
    // Base Cases
    if (l > h) return INT_MAX;
    if (l == h) return 0;
    if (l == h - 1) return (str[l] == str[h])? 0 : 1;
    // Check if the first and last characters are same. On the basis of the
    // comparison result, decide which subrpoblem(s) to call
    return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1):
                               (min(findMinInsertions(str, l, h - 1),
                                   findMinInsertions(str, l + 1, h)) + 1);
}
// Driver program to test above functions
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertions(str, 0, strlen(str)-1));
    return 0;
}

Output:

3

Dynamic Programming based Solution
If we observe the above approach carefully, we can find that it exhibits overlapping subproblems.
Suppose we want to find the minimum number of insertions in string “abcde”:

                      abcde
	        /       |      \
	       /        |        \
           bcde         abcd       bcd  cd   bcd abc bc
   / | \  / | \ /|\ / | \
de cd d cd bc c………………….

The substrings in bold show that the recursion to be terminated and the recursion tree cannot originate from there. Substring in the same color indicates overlapping subproblems.

How to reuse solutions of subproblems?
We can create a table to store results of subproblems so that they can be used directly if same subproblem is encountered again.

The below table represents the stored values for the string abcde.

a b c d e
----------
0 1 2 3 4
0 0 1 2 3 
0 0 0 1 2 
0 0 0 0 1 
0 0 0 0 0

How to fill the table?
The table should be filled in diagonal fashion. For the string abcde, 0….4, the following should be order in which the table is filled:

Gap = 1:
(0, 1) (1, 2) (2, 3) (3, 4)

Gap = 2:
(0, 2) (1, 3) (2, 4)

Gap = 3:
(0, 3) (1, 4)

Gap = 4:
(0, 4)
// A Dynamic Programming based program to find minimum number
// insertions needed to make a string palindrome
#include
#include
// A utility function to find minimum of two integers
int min(int a, int b)
{   return a < b ? a : b;  }
// A DP function to find minimum number of insersions
int findMinInsertionsDP(char str[], int n)
{
    // Create a table of size n*n. table[i][j] will store
    // minumum number of insertions needed to convert str[i..j]
    // to a palindrome.
    int table[n][n], l, h, gap;
    // Initialize all table entries as 0
    memset(table, 0, sizeof(table));
    // Fill the table
    for (gap = 1; gap < n; ++gap)
        for (l = 0, h = gap; h < n; ++l, ++h)
            table[l][h] = (str[l] == str[h])? table[l+1][h-1] :
                          (min(table[l][h-1], table[l+1][h]) + 1);
    // Return minimum number of insertions for str[0..n-1]
    return table[0][n-1];
}
// Driver program to test above function.
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsDP(str, strlen(str)));
    return 0;
}

Output:

3

Time complexity: O(N^2)
Auxiliary Space: O(N^2)

Another Dynamic Programming Solution (Variation of Longest Common Subsequence Problem)
The problem of finding minimum insertions can also be solved using Longest Common Subsequence (LCS) Problem. If we find out LCS of string and its reverse, we know how many maximum characters can form a palindrome. We need insert remaining characters. Following are the steps.
1) Find the length of LCS of input string and its reverse. Let the length be ‘l’.
2) The minimum number insertions needed is length of input string minus ‘l’.

// An LCS based program to find minimum number insertions needed to
// make a string palindrome
#include
#include
/* Utility function to get max of 2 integers */
int max(int a, int b)
{   return (a > b)? a : b; }
/* Returns length of LCS for X[0..m-1], Y[0..n-1].
   See http://goo.gl/bHQVP for details of this function */
int lcs( char *X, char *Y, int m, int n )
{
   int L[n+1][n+1];
   int i, j;
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
   return L[m][n];
}
// LCS based function to find minimum number of insersions
int findMinInsertionsLCS(char str[], int n)
{
   // Creata another string to store reverse of 'str'
   char rev[n+1];
   strcpy(rev, str);
   strrev(rev);
   // The output is length of string minus length of lcs of
   // str and it reverse
   return (n - lcs(str, rev, n, n));
}
// Driver program to test above functions
int main()
{
    char str[] = "geeks";
    printf("%d", findMinInsertionsLCS(str, strlen(str)));
    return 0;
}

Output:

3

Time complexity of this method is also O(n^2) and this method also requires O(n^2) extra space.

This article is compiled by Aashish Barnwal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Java Program to Implement Trie

This is a Java Program to implement Trie. A trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node, instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

Here is the source code of the Java program to implement Trie. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

class TrieNode 
{
    char content; 
    boolean isEnd; 
    int count;  
    LinkedList<TrieNode> childList; 
 
    /* Constructor */
    public TrieNode(char c)
    {
        childList = new LinkedList<TrieNode>();
        isEnd = false;
        content = c;
        count = 0;
    }  
    public TrieNode subNode(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.content == c)
                    return eachChild;
        return null;
    }
}
 
class Trie
{
    private TrieNode root;
 
     /* Constructor */
    public Trie()
    {
        root = new TrieNode(' '); 
    }
     /* Function to insert word */
    public void insert(String word)
    {
        if (search(word) == true) 
            return;        
        TrieNode current = root; 
        for (char ch : word.toCharArray() )
        {
            TrieNode child = current.subNode(ch);
            if (child != null)
                current = child;
            else 
            {
                 current.childList.add(new TrieNode(ch));
                 current = current.subNode(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }
    /* Function to search for word */
    public boolean search(String word)
    {
        TrieNode current = root;  
        for (char ch : word.toCharArray() )
        {
            if (current.subNode(ch) == null)
                return false;
            else
                current = current.subNode(ch);
        }      
        if (current.isEnd == true) 
            return true;
        return false;
    }
    /* Function to remove a word */
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not exist in trie\n");
            return;
        }             
        TrieNode current = root;
        for (char ch : word.toCharArray()) 
        { 
            TrieNode child = current.subNode(ch);
            if (child.count == 1) 
            {
                current.childList.remove(child);
                return;
            } 
            else 
            {
                child.count--;
                current = child;
            }
        }
        current.isEnd = false;
    }
}    
 
/* Class Trie Test */
public class TrieTest
{
    public static void main(String[] args)
    {            
        Scanner scan = new Scanner(System.in);
        /* Creating object of AATree */
        Trie t = new Trie(); 
        System.out.println("Trie Test\n");          
        char ch;
        /*  Perform tree operations  */
        do    
        {
            System.out.println("\nTrie Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. delete");
            System.out.println("3. search");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter string element to insert");
                t.insert( scan.next() );                     
                break;                          
            case 2 : 
                System.out.println("Enter string element to delete");
                try
                {
                    t.remove( scan.next() ); 
                }                    
                catch (Exception e)
                {
                    System.out.println(e.getMessage()+" not found ");
                }
                break;                         
            case 3 : 
                System.out.println("Enter string element to search");
                System.out.println("Search result : "+ t.search( scan.next() ));
                break;                                          
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
}

Queue Using Stack

public class QueueUsingStack
{
	Stack input = new Stack();
	Stack output = new Stack();

	public void add(int value)
	{
		input.push(value);
	}

	public int remove(int value)
	{
		if(output.isEmpty())
		{
			while(!input.isEmpty())
			{
				output.push(input.pop());
			}
		}

		return output.pop();
	}
}

Building Password Validator

I am making the our validator configurable so that one can put the limits based on needs. Like if I want to force at least one special character, but not any capital letter, I can pass the required arguments accordingly.

import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class PasswordValidator
{
    private static PasswordValidator INSTANCE = new PasswordValidator();
    private static String pattern = null;
 
    /**
     * No one can make a direct instance
     * */
    private PasswordValidator()
    {
        //do nothing
    }
 
    /**
     * Force the user to build a validator using this way only
     * */
    public static PasswordValidator buildValidator( boolean forceSpecialChar,
                                                    boolean forceCapitalLetter,
                                                    boolean forceNumber,
                                                    int minLength,
                                                    int maxLength)
    {
        StringBuilder patternBuilder = new StringBuilder("((?=.*[a-z])");
 
        if (forceSpecialChar)
        {
            patternBuilder.append("(?=.*[@#$%])");
        }
 
        if (forceCapitalLetter)
        {
            patternBuilder.append("(?=.*[A-Z])");
        }
 
        if (forceNumber)
        {
            patternBuilder.append("(?=.*d)");
        }
 
        patternBuilder.append(".{" + minLength + "," + maxLength + "})");
        pattern = patternBuilder.toString();
 
        return INSTANCE;
    }
 
    /**
     * Here we will validate the password
     * */
    public static boolean validatePassword(final String password)
    {
        Pattern p = Pattern.compile(pattern);
        Matcher m = p.matcher(password);
        return m.matches();
    }
}

Implement LRU Cache – Java Solution

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The key to solve this problem is using a double linked list which enables us to quickly move nodes.

LRU-Cache

import java.util.HashMap;
 
public class LRUCache {
	private HashMap<Integer, DoubleLinkedListNode> map 
		= new HashMap<Integer, DoubleLinkedListNode>();
	private DoubleLinkedListNode head;
	private DoubleLinkedListNode end;
	private int capacity;
	private int len;
 
	public LRUCache(int capacity) {
		this.capacity = capacity;
		len = 0;
	}
 
	public int get(int key) {
		if (map.containsKey(key)) {
			DoubleLinkedListNode latest = map.get(key);
			removeNode(latest);
			setHead(latest);
			return latest.val;
		} else {
			return -1;
		}
	}
 
	public void removeNode(DoubleLinkedListNode node) {
		DoubleLinkedListNode cur = node;
		DoubleLinkedListNode pre = cur.pre;
		DoubleLinkedListNode post = cur.next;
 
		if (pre != null) {
			pre.next = post;
		} else {
			head = post;
		}
 
		if (post != null) {
			post.pre = pre;
		} else {
			end = pre;
		}
	}
 
	public void setHead(DoubleLinkedListNode node) {
		node.next = head;
		node.pre = null;
		if (head != null) {
			head.pre = node;
		}
 
		head = node;
		if (end == null) {
			end = node;
		}
	}
 
	public void set(int key, int value) {
		if (map.containsKey(key)) {
			DoubleLinkedListNode oldNode = map.get(key);
			oldNode.val = value;
			removeNode(oldNode);
			setHead(oldNode);
		} else {
			DoubleLinkedListNode newNode = 
				new DoubleLinkedListNode(key, value);
			if (len < capacity) {
				setHead(newNode);
				map.put(key, newNode);
				len++;
			} else {
				map.remove(end.key);
				end = end.pre;
				if (end != null) {
					end.next = null;
				}
 
				setHead(newNode);
				map.put(key, newNode);
			}
		}
	}
}
 
class DoubleLinkedListNode {
	public int val;
	public int key;
	public DoubleLinkedListNode pre;
	public DoubleLinkedListNode next;
 
	public DoubleLinkedListNode(int key, int value) {
		val = value;
		this.key = key;
	}
}

Implement LRU Cache – C

How to implement LRU caching scheme? What data structures should be used?

We are given total possible page numbers that can be referred. We are also given cache (or memory) size (Number of page frames that cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache. Please see the Galvin book for more details (see the LRU page replacement slide here).

We use two data structures to implement an LRU Cache.

1. A Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
The most recently used pages will be near front end and least recently pages will be near rear end.

2. A Hash with page number as key and address of the corresponding queue node as value.

When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
If the required page is not in the memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of queue, and add the new node to the front of queue.

Note: Initially no page is in the memory.

Below is C implementation:

// A C program to show implementation of LRU cache
#include 
#include 
 
// A Queue Node (Queue is implemented using Doubly Linked List)
typedef struct QNode
{
    struct QNode *prev, *next;
    unsigned pageNumber;  // the page number stored in this QNode
} QNode;
 
// A Queue (A FIFO collection of Queue Nodes)
typedef struct Queue
{
    unsigned count;  // Number of filled frames
    unsigned numberOfFrames; // total number of frames
    QNode *front, *rear;
} Queue;
 
// A hash (Collection of pointers to Queue Nodes)
typedef struct Hash
{
    int capacity; // how many pages can be there
    QNode* *array; // an array of queue nodes
} Hash;
 
// A utility function to create a new Queue Node. The queue Node
// will store the given 'pageNumber'
QNode* newQNode( unsigned pageNumber )
{
    // Allocate memory and assign 'pageNumber'
    QNode* temp = (QNode *)malloc( sizeof( QNode ) );
    temp->pageNumber = pageNumber;
 
    // Initialize prev and next as NULL
    temp->prev = temp->next = NULL;
 
    return temp;
}
 
// A utility function to create an empty Queue.
// The queue can have at most 'numberOfFrames' nodes
Queue* createQueue( int numberOfFrames )
{
    Queue* queue = (Queue *)malloc( sizeof( Queue ) );
 
    // The queue is empty
    queue->count = 0;
    queue->front = queue->rear = NULL;
 
    // Number of frames that can be stored in memory
    queue->numberOfFrames = numberOfFrames;
 
    return queue;
}
 
// A utility function to create an empty Hash of given capacity
Hash* createHash( int capacity )
{
    // Allocate memory for hash
    Hash* hash = (Hash *) malloc( sizeof( Hash ) );
    hash->capacity = capacity;
 
    // Create an array of pointers for refering queue nodes
    hash->array = (QNode **) malloc( hash->capacity * sizeof( QNode* ) );
 
    // Initialize all hash entries as empty
    int i;
    for( i = 0; i < hash->capacity; ++i )
        hash->array[i] = NULL;
 
    return hash;
}
 
// A function to check if there is slot available in memory
int AreAllFramesFull( Queue* queue )
{
    return queue->count == queue->numberOfFrames;
}
 
// A utility function to check if queue is empty
int isQueueEmpty( Queue* queue )
{
    return queue->rear == NULL;
}
 
// A utility function to delete a frame from queue
void deQueue( Queue* queue )
{
    if( isQueueEmpty( queue ) )
        return;
 
    // If this is the only node in list, then change front
    if (queue->front == queue->rear)
        queue->front = NULL;
 
    // Change rear and remove the previous rear
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;
 
    if (queue->rear)
        queue->rear->next = NULL;
 
    free( temp );
 
    // decrement the number of full frames by 1
    queue->count--;
}
 
// A function to add a page with given 'pageNumber' to both queue
// and hash
void Enqueue( Queue* queue, Hash* hash, unsigned pageNumber )
{
    // If all frames are full, remove the page at the rear
    if ( AreAllFramesFull ( queue ) )
    {
        // remove page from hash
        hash->array[ queue->rear->pageNumber ] = NULL;
        deQueue( queue );
    }
 
    // Create a new node with given page number,
    // And add the new node to the front of queue
    QNode* temp = newQNode( pageNumber );
    temp->next = queue->front;
 
    // If queue is empty, change both front and rear pointers
    if ( isQueueEmpty( queue ) )
        queue->rear = queue->front = temp;
    else  // Else change the front
    {
        queue->front->prev = temp;
        queue->front = temp;
    }
 
    // Add page entry to hash also
    hash->array[ pageNumber ] = temp;
 
    // increment number of full frames
    queue->count++;
}
 
// This function is called when a page with given 'pageNumber' is referenced
// from cache (or memory). There are two cases:
// 1. Frame is not there in memory, we bring it in memory and add to the front
//    of queue
// 2. Frame is there in memory, we move the frame to front of queue
void ReferencePage( Queue* queue, Hash* hash, unsigned pageNumber )
{
    QNode* reqPage = hash->array[ pageNumber ];
 
    // the page is not in cache, bring it
    if ( reqPage == NULL )
        Enqueue( queue, hash, pageNumber );
 
    // page is there and not at front, change pointer
    else if (reqPage != queue->front)
    {
        // Unlink rquested page from its current location
        // in queue.
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
           reqPage->next->prev = reqPage->prev;
 
        // If the requested page is rear, then change rear
        // as this node will be moved to front
        if (reqPage == queue->rear)
        {
           queue->rear = reqPage->prev;
           queue->rear->next = NULL;
        }
 
        // Put the requested page before current front
        reqPage->next = queue->front;
        reqPage->prev = NULL;
 
        // Change prev of current front
        reqPage->next->prev = reqPage;
 
        // Change front to the requested page
        queue->front = reqPage;
    }
}
 
// Driver program to test above functions
int main()
{
    // Let cache can hold 4 pages
    Queue* q = createQueue( 4 );
 
    // Let 10 different pages can be requested (pages to be
    // referenced are numbered from 0 to 9
    Hash* hash = createHash( 10 );
 
    // Let us refer pages 1, 2, 3, 1, 4, 5
    ReferencePage( q, hash, 1);
    ReferencePage( q, hash, 2);
    ReferencePage( q, hash, 3);
    ReferencePage( q, hash, 1);
    ReferencePage( q, hash, 4);
    ReferencePage( q, hash, 5);
 
    // Let us print cache frames after the above referenced pages
    printf ("%d ", q->front->pageNumber);
    printf ("%d ", q->front->next->pageNumber);
    printf ("%d ", q->front->next->next->pageNumber);
    printf ("%d ", q->front->next->next->next->pageNumber);
 
    return 0;
}

Output:

5 4 1 3

Simulate a fair coin given only access to a biased coin.

def fairCoin(biasedCoin):
   coin1, coin2 = 0,0
   while coin1 == coin2:
      coin1, coin2 = biasedCoin(), biasedCoin()
   return coin1

Discussion: This is originally von Neumann’s clever idea. If we have a biased coin (i.e. a coin that comes up heads with probability different from 1/2), we can simulate a fair coin by tossing pairs of coins until the two results are different. Given that we have different results, the probability that the first is “heads” and the second is “tails” is the same as the probability of “tails” then “heads”. So if we simply return the value of the first coin, we will get “heads” or “tails” with the same probability, i.e. 1/2.

Note that we did not have to know or assume anything about our biasedCoin function other than it returns 0 or 1 every time, and the results between function calls are independent and identically distributed. In particular, we do not need to know the probability of getting 1. (However, that probability should be strictly between 0 or 1.) Also, we do not use any randomness directly, only through the biasedCoin function.

Here is a simple simulation:

from random import random
def biasedCoin():
   return int(random() < 0.2)

Check if a binary tree is a mirror image or symmetric

bool isMirrorItselfIteratively(BinaryTreeNode *root) 
{
    /// use single queue
    if(!root) return true;
    queue<BinaryTreeNode *> q;
    q.push(root->m_pLeft);
    q.push(root->m_pRight);
    BinaryTreeNode *l, *r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL || l->m_nValue!=r->m_nValue) return false;
        q.push(l->m_pLeft);
        q.push(r->m_pRight);
        q.push(l->m_pRight);
        q.push(r->m_pLeft);
    }

    return true;
}
bool isMirror(BinaryTreeNode *a, BinaryTreeNode *b)
{
    return (a && b) ?  
        (a->m_nValue==b->m_nValue 
        && isMirror(a->m_pLeft,b->m_pRight) 
        && isMirror(a->m_pRight,b->m_pLeft)) :  
    (a == b);
}
bool isMirrorItselfRecursively(BinaryTreeNode *root) 
{
    if (!root)
        return true;

    return isMirror(root->m_pLeft, root->m_pRight);
}

Babylonian method for square root

/*Returns the square root of n. Note that the function
  will not work for numbers which are not perfect squares*/
unsigned int squareRoot(int n)
{
  int x = n;
  int y = 1;
     float e = 0.000001; /* e decides the accuracy level*/
  while(x - y > e)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;
}
 
/* Driver program to test above function*/
int main()
{
  int n = 49;
  printf (" root of %d is %d", n, squareRoot(n));
  getchar();
}
 Convert Phone Number to Word
    public ArrayList<String> letterCombinations(String digits) 
        {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for(int i=0;i<digits.length();i++)
                {
            for(String str: res)
            {
                String letters = map.get(digits.charAt(i));
                for(int j=0;j<letters.length();j++)
                {
                      preres.add(str+letters.charAt(j));
                }
                res.add(preres);
                preres = new ArrayList<String>();
             }
        }      
        return res;
    }

    static final HashMap<Character,String> map = new HashMap<Character,String>(){{
        put('2',"abc");
        put('3',"def");
        put('4',"ghi");
        put('5',"jkl");
        put('6',"mno");
        put('7',"pqrs");
        put('8',"tuv");
        put('9',"wxyz");
    }} ;

How to convert a number to words (in Java)


// This snippet may be used freely, as long as the authorship note remains in the source code.

private static final String[] lowNames = {
   "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
   "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};

private static final String[] tensNames = {
   "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};

private static final String[] bigNames = {
   "thousand", "million", "billion"};

/**
* Converts an integer number into words (american english).
* @author Christian d'Heureuse, Inventec Informatik AG, Switzerland, www.source-code.biz
**/
public static String convertNumberToWords (int n) {
   if (n < 0) {
      return "minus " + convertNumberToWords(-n); }
   if (n <= 999) {       return convert999(n); }    String s = null;    int t = 0;    while (n > 0) {
      if (n % 1000 != 0) {
         String s2 = convert999(n % 1000);
         if (t > 0) {
            s2 = s2 + " " + bigNames[t-1]; }
         if (s == null) {
            s = s2; }
          else {
            s = s2 + ", " + s; }}
      n /= 1000;
      t++; }
   return s; }

// Range 0 to 999.
private static String convert999 (int n) {
   String s1 = lowNames[n / 100] + " hundred";
   String s2 = convert99(n % 100);
   if (n <= 99) {
      return s2; }
    else if (n % 100 == 0) {
      return s1; }
    else {
      return s1 + " " + s2; }}

// Range 0 to 99.
private static String convert99 (int n) {
   if (n < 20) {
      return lowNames[n]; }
   String s = tensNames[n / 10 - 2];
   if (n % 10 == 0) {
      return s; }
   return s + "-" + lowNames[n % 10]; }

Finding Duplicate Files

public class FindDuplicates {
    private static MessageDigest md;
    static {
        try {
            md = MessageDigest.getInstance("SHA-512");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("cannot initialize SHA-512 hash function", e);
        }
    }

    public static void find(Map<String, List<String>> lists, File directory, boolean leanAlgorithm) throws Exception  {
        String hash;
        for (File child : directory.listFiles()) {
            if (child.isDirectory()) {
                find(lists, child, leanAlgorithm);
            } else {
                try {
                    hash = leanAlgorithm ? makeHashLean(child) : makeHashQuick(child);
                    List<String> list = lists.get(hash);
                    if (list == null) {
                        list = new LinkedList<String>();
                        lists.put(hash, list);
                    }
                    list.add(child.getAbsolutePath());
                } catch (IOException e) {
                    throw new RuntimeException("cannot read file " + child.getAbsolutePath(), e);
                }
            }
        }
    }

    /*
     * quick but memory hungry (might like to run with java -Xmx2G or the like to increase heap space if RAM available)
     */
    public static String makeHashQuick(File infile) throws Exception {
        FileInputStream fin = new FileInputStream(infile);
        byte data[] = new byte[(int) infile.length()];
        fin.read(data);
        fin.close();
        String hash = new BigInteger(1, md.digest(data)).toString(16);
        return hash;
    }

    /*
     * slower but memory efficient  -- you might like to play with the size defined by "buffSize"
     */
    public static String makeHashLean(File infile) throws Exception {
        RandomAccessFile file = new RandomAccessFile(infile, "r");

        int buffSize = 16384;
        byte[] buffer = new byte[buffSize];
        long read = 0;

        // calculate the hash of the whole file for the test
        long offset = file.length();
        int unitsize;
        while (read < offset) {
            unitsize = (int) (((offset - read) >= buffSize) ? buffSize
: (offset - read));
            file.read(buffer, 0, unitsize);
            md.update(buffer, 0, unitsize);
            read += unitsize;
        }

        file.close();
        String hash = new BigInteger(1, md.digest()).toString(16);
        return hash;
    }


    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Please supply a path to directory to find duplicate files in.");
            return;
        }
        File dir = new File(args[0]);
        if (!dir.isDirectory()) {
            System.out.println("Supplied directory does not exist.");
            return;
        }
        Map<String, List<String>> lists = new HashMap<String, List<String>>();
        try {
            FindDuplicates.find(lists, dir, args.length == 1 || !args[1].equals("-quick"));
        } catch (Exception e) {
            e.printStackTrace();
        }
        for (List<String> list : lists.values()) {
            if (list.size() > 1) {
                System.out.println("--");
                for (String file : list) {
                    System.out.println(file);
                }
            }
        }
        System.out.println("--");
    }
}

Serialization/Deserialization of a Binary Tree

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.

Being able to store a binary tree to a file presents lots of benefits. First, we are able to save the binary tree to a file and restore it at a later time. We are also able to transmit the binary tree representation via network and load it into another computer. Without doubt, serialization/deserialization of a binary tree is important and an algorithm to represent a binary tree in a compact way is very desirable.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be “resurrected” later in the same or another computer environment.

Hint:
If you have not read my previous article about Saving a Binary Search Tree to a File, you should read it now. Since we are dealing with a binary tree, not a binary search tree (BST), our previous method will not work. However, this will get you started.

Solution:
Our previous method will not work in the case of Binary Tree, because binary trees are not bound with the same rule as BST. In order for the nodes to be inserted at the correct place, we would need to output the NULL nodes using some kind of sentinel (Here, we use ‘#‘ as the sentinel) as we are doing pre-order traversal.

Assume we have a binary tree below:

    _30_ 
   /    \    
  10    20
 /     /  \ 
50    45  35

Using pre-order traversal, the algorithm should write the following to a file:

30 10 50 # # # 20 45 # # 35 # #

The pre-order traversal code below does all the job to serialize a binary tree, believe it or not!

Deserializing a Binary Tree:

Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

Alternative Solution:
We may also use level-order traversal to write/read binary tree. Level-order traversal works because like pre-order traversal, we see the parent node before its child nodes. The implementation of it using level-order traversal is left as an exercise to the reader. Read my post: Printing a Binary Tree in Level Order on how to traverse a binary tree in level-order.


Enumerates all subsets of N elements using recursion.

public static void comb2(String s) { comb2("", s); }
    private static void comb2(String prefix, String s) {
        System.out.println(prefix);
        for (int i = 0; i < s.length(); i++)
            comb2(prefix + s.charAt(i), s.substring(i + 1));
    }  


Output top N positive integer in string comparison order. For example, let’s say N=1000, then you need to output in string comparison order as below: 1, 10, 100, 1000, 101, 102, … 109, 11, 110, … DFS comes to our rescue.  if you observe a little you can find out that there is a nice pattern Start with a char 1-9 in that order (9 iterations). Add a 0-9 to right of string one at a time and recursively do dfs. if value<=n print it.  recursively keep on adding char to the right.  when value>n. return from dfs call.


Longest Common Substring Given two strings ‘X’ and ‘Y’, find the length of the longest common substring. For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”

int LCSubStr(char *X, char *Y, int m, int n)
 {
     int LCSuff[m+1][n+1];
     int result = 0;  // To store length of the longest common substring

     for (int i=0; i<=m; i++)
     {
         for (int j=0; j<=n; j++)
         {
             if (i == 0 || j == 0)
                 LCSuff[i][j] = 0;
             else if (X[i-1] == Y[j-1])
             {
                 LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
                 result = max(result, LCSuff[i][j]);
             }
             else LCSuff[i][j] = 0;
         }
     }
     return result;
 }

Print Matrix Diagonally

Given a 2D matrix, print all elements of the given matrix in diagonal order. For example, consider the following 5 X 4 input matrix.

    1     2     3     4
    5     6     7     8
    9    10    11    12
   13    14    15    16
   17    18    19    20

Diagonal printing of the above matrix is

    1
    5     2
    9     6     3
   13    10     7     4
   17    14    11     8
   18    15    12
   19    16
   20
public class PrintMatrixDiagonally {

	public static void printDiagnolUpwards(int r, int c, int m[][]) {
		  int i, j, k;

		  for (i = 0; i < r; i++) {
		    for (j = i, k = 0; k < c && j >= 0; j--, k++) {
		      System.out.print(m[j][k] + "\t");
		    }
  		    System.out.println();
		  }

		  for (i = 1; i < c; i++) {
		    for (j = r - 1, k = i; k < c && j >= 0; j--, k++) {
		    	System.out.print(m[j][k] + "\t");
		    }
		    System.out.println();
		  }
		}

	public static void printDiagnolDownwards(int r, int c, int m[][]) {
		  int i, j, k;

		  for (i = 0; i < c; i++) { 		    for (j = 0, k = i; k >= 0 && j < r; j++, k--) {
		    	System.out.print(m[j][k] + "\t");
		    }
			System.out.println();
		  }

		  for (i = 1; i < r; i++) { 		    for (j = i , k = c - 1; k >= 0  && j < r; j++, k--) {
		    	System.out.print(m[j][k] + "\t");
		    }
		    System.out.println();
		  }
		}

public static void main(String[] args) {

		  int m[][] = {
		      { 1,     2,     3,     4},
		      { 5,     6,     7,     8},
		      { 9,     10,    11,    12},
		      { 13,    14,    15,    16},
		      { 17,    18,    19,    20}
		  };

		  printDiagnolUpwards(5, 4, m);
		  System.out.println();
		  printDiagnolDownwards(5, 4, m);
		}
}

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is "applepie" and dictionary contains a standard set of English words, then we would return the string "apple pie" as output. 
String SegmentString(String input, Set dict) {
  if (dict.contains(input)) return input;
  int len = input.length();
  for (int i = 1; i < len; i++) {
    String prefix = input.substring(0, i);
    if (dict.contains(prefix)) {
      String suffix = input.substring(i, len);
      String segSuffix = SegmentString(suffix, dict);
      if (segSuffix != null) {
        return prefix + " " + segSuffix;
      }
    }
  }
  return null;
}

Quick Sort

int partition(int arr[], int left, int right)

{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2]; 

      while (i <= j) {
            while (arr[i] < pivot)                   i++;             while (arr[j] > pivot)
                  j--;

            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      }; 

      return i;
} 

void quickSort(int arr[], int left, int right) {

      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);

      if (index < right)
            quickSort(arr, index, right);
}

Merge Sort

In a simple pseudocode form, the algorithm could look something like this:

function merge_sort(m)
    if length(m) ≤ 1
        return m
    var list left, right, result

var integer middle = length(m) / 2

for each x in m up to middle

add x to left

for each x in m after middle

add x to right

left = merge_sort(left)

right = merge_sort(right)

result = merge(left, right)

return result

Following writing merge_sort function, then it is required to merge both the left and right lists created above. There are several variants for the merge() function; one possibility is this:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)             
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

Question: Breadth First Search & Depth First Search

Answer:

public void bfs() {

    	// BFS uses Queue data structure
    	Queue queue = new LinkedList();
    	queue.add(this.rootNode);
    	printNode(this.rootNode);
    	rootNode.visited = true;
    	while (!queue.isEmpty()) {
    		Node node = (Node) queue.remove();
    		Node child = null;
    		while ((child = getUnvisitedChildNode(node)) != null) {
    			child.visited = true;
    			printNode(child);
    			queue.add(child);
    		}
    	}
    	// Clear visited property of nodes
    	clearNodes();
    }

    public void dfs() {
    	// DFS uses Stack data structure
    	Stack stack = new Stack();
    	stack.push(this.rootNode);
    	rootNode.visited = true;
    	printNode(rootNode);
    	while (!stack.isEmpty()) {
    		Node node = (Node) s.peek();
    		Node child = getUnvisitedChildNode(n);
    		if (child != null) {
    			child.visited = true;
    			printNode(child);
    			s.push(child);
    		} else {
    			s.pop();
    		}
    	}
    	// Clear visited property of nodes
    	clearNodes();
    }

Question: Sudoku Checker

Answer:

public class SudokuChecker

{
	public SudokuChecker( int[][] input )
	{
	  puzzle = input;
	}

	public boolean completed()
	{
		for(int i = 0; i < 9;i++)
		{
			for(int j = 0;j < 9;j++) 			{ 				if(puzzle[i][j] > 9 || puzzle[i][j] < 1)
				{
					return false;
				}
			}
		}
		return true;
	}

	public boolean checkPuzzle()
	{
	    for(int i = 0; i < 9;i++) // use checkRow to check each row
			if(!checkRow(i))
				return false;

	    for(int i = 0; i < 9;i++) // use checkColumn to check each column
			if(!checkColumn(i))
				return false;

	    for(int i = 0; i < 9;i += 3) // use checkSquare to check each of the 9 blocks
		 	for(int j = 0; j < 9;j += 3)
				if(!checkSquare(i, j))
					return false;

		return true;
	}

	public boolean checkRow( int r )
	{
	   resetCheck();
	   for( int c=0; c<9; c++ )
	    	if( !digitCheck( puzzle[r][c] ) )
	    		return false;

		return true;
	}

	public boolean checkColumn( int c )
	{
		resetCheck();
		for( int r=0; r<9; r++ )
			if( !digitCheck( puzzle[r][c] ) )
				return false;

		return true;
	}

	public boolean checkSquare( int row, int column )
	{
		resetCheck();
		for(int r = 0; r < 3;r++)
			for(int c = 0; c < 3;c++)
				if( !digitCheck( puzzle[r + row][c + column] ) )
					return false;

		return true;
	}

	public boolean digitCheck( int n )
	{
		if( n != 0 && digits[n] )
			return false;
		else
		{
			digits[n] = true;
			return true;
		} 
	}

	public void resetCheck()
	{
		digits = new boolean[10];
	}

	int[][] puzzle;
	boolean[] digits;

	public static void main(String[] args)
	{
		int[][] puzzleLegacy = { { 7,8,1,6,0,2,9,0,5 },
	                       { 9,0,2,7,1,0,0,0,0 },
	                       { 0,0,6,8,0,0,0,1,2 },
	                       { 2,0,0,3,0,0,8,5,1 },
	                       { 0,7,3,5,0,0,0,0,4 },
	                       { 0,0,8,0,0,9,3,6,0 },
	                       { 1,9,0,0,0,7,0,8,0 },
	                       { 8,6,7,0,0,3,4,0,9 },
	                       { 0,0,5,0,0,0,1,0,0 } };

		int[][] puzzle = { { 7,8,1,6,3,2,9,4,5 },
	                       { 9,5,2,7,1,4,6,3,8 },
	                       { 4,3,6,8,9,5,7,1,2 },
	                       { 2,4,9,3,7,6,8,5,1 },
	                       { 6,7,3,5,8,1,2,9,4 },
	                       { 5,1,8,4,2,9,3,6,7 },
	                       { 1,9,4,2,6,7,5,8,3 },
	                       { 8,6,7,1,5,3,4,2,9 },
	                       { 3,2,5,9,4,8,1,7,8 } };

		SudokuChecker sudoku = new SudokuChecker( puzzle );                       
		if( sudoku.checkPuzzle() )
			System.out.println("There are no rule violations");
		if( sudoku.completed() )
			System.out.println("Puzzle is done");
		else
	      System.out.println("Puzzle is NOT done"); 
	}
}

Question: Subset Sum Problem

Answer 1: Recursive

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || 
                           isSubsetSum(arr, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0 

Following is naive recursive implementation that simply follows the recursive structure mentioned above.

// A recursive solution for subset sum problem
#include
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
   // Base Cases
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;
   // If last element is greater than sum, then ignore it
   if (set[n-1] > sum)
     return isSubsetSum(set, n-1, sum);
   /* else, check if sum can be obtained by any of the following
      (a) including the last element
      (b) excluding the last element   */
   return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
}
// Driver program to test above function
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
  else
     printf("No subset with given sum");
  return 0;
}

Output:

 Found a subset with given sum

The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).

Answer 2: using Dynamic programming

We can solve the problem in Pseudo-polynomial time using Dynamic programming. We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]

// A Dynamic Programming solution for subset sum problem
#include
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
    //  with sum equal to i
    bool subset[sum+1][n+1];
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
      subset[0][i] = true;
    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= sum; i++)
      subset[i][0] = false;
     // Fill the subset table in botton up manner
     for (int i = 1; i <= sum; i++)
     {
       for (int j = 1; j <= n; j++)
       {
         subset[i][j] = subset[i][j-1];
         if (i >= set[j-1])
           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
       }
     }
    /* // uncomment this code to print table
     for (int i = 0; i <= sum; i++)
     {
       for (int j = 0; j <= n; j++)
          printf ("%4d", subset[i][j]);
       printf("\n");
     } */
     return subset[sum][n];
}
// Driver program to test above function
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  if (isSubsetSum(set, n, sum) == true)
     printf("Found a subset with given sum");
  else
     printf("No subset with given sum");
  return 0;
}

Output:

Found a subset with given sum

Time complexity of the above solution is O(sum*n).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Reference: http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/


Question: Number-theoretic computations

Answer: http://cr.yp.to/ntheory.html


Question: If you have one billion numbers and one hundred computers, what is the best way to locate the median of the numbers?

Answer:

I don’t believe sorting is required, and I think any algorithm involving sorting a billion/100 numbers is going to be slow. Let’s consider an algorithm on one computer.

1) Select 1000 values at random from the billion, and use them to get an idea of the distribution of the numbers, especially a range.

2) Instead of sorting the values, allocate them to buckets based on the distribution you just calculated. The number of buckets is chosen so that the computer can handle them efficiently, but should otherwise be as large as convenient. The bucket ranges should be so that approximately equal numbers of values go in each bucket (this isn’t critical to the algorithm, but it helps efficiency. 100,000 buckets might be appropriate). Note the number of values in each bucket. This is an O(n) process.

3) Find out which bucket range the median lies. This can be done by simply examining the total numbers in each bucket.

4) Find the actual median by examining the values in that bucket. You can use a sort here if you like, since you are only sorting maybe 10,000 numbers. If the number of values in that bucket is large then you can use this algorithm again until you have a small enough number to sort.

This approach parallelizes trivially by dividing the values between the computers. Each computer reports the totals in each bucket to a ‘control’ computer which does step 3. For step 4 each computer sends the (sorted) values in the relevant bucket to the control computer (you can do both of those algorithms in parallel too, but it probably isn’t worth it).

The total process is O(n), since both steps 3 and 4 are trivial, provided the number of buckets is large enough.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: