Friday, August 30, 2013

Detele characters from input string given in another string

Given two strings, How do we delete all the characters in the first string which are present in the second string?

Find the character set of the string. Create a Boolean array of size equal to the character set size. If the character set is ASCII, the size is 256. This array will be indexed by the character itself.


For example, array['c'] stores whether character 'c' is present in the string are not.

Iterate through each character of the second string, update the corresponding Boolean flag in the array to true.

Now loop through all the characters from the input string and retain the only characters not present in the mask.


Following is the C++ program to do it. This code runs in O(n) time and constant space. I have modified the input string itself without creating an auxiliary array.




#include <iostream>
#include <string>

using namespace std;

void removeChars( char * input, char * mask)
{
 //initialize all the chars to false
 bool charPresent[256] = {false};
 int i;
 //mark all the mask characters to true.
 for( i = 0; mask[i]; ++i)
 {
  charPresent[mask[i]] = true;
 }
 
 int resInd = 0; //to track result string
 int ind = 0; 
 
 while( input[ind] )
 {
  //Add the character only if it is not present in mask
  if( !charPresent[ input[ind] ] )
  {
   input[resInd++] = input[ind];
  }
  ind++;
 }
 input[resInd] = '\0'; //Null terminator to end the string
}
int main()
{
 char inputStr[] = "This is a test";
 char maskStr[] = "aeiou";
 removeChars( inputStr, maskStr);
 cout<<inputStr;
 return 0;
}

Monday, August 26, 2013

Implementing a stack using queue

How do you implement a stack using Queue?

This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack.

This can be done using two queues. One queue acts as the main queue while the other acts as the helper queue.

There are two approaches to solve this problem.

  • Making the pop operation costly and push operation simple
  • Making the push operation costly and pop operation simple
First approach:
 

  • Push operation is simple. It always adds the element to the main queue.
  • To implement pop operation, we remove all but one element from the main queue and add them to the helper queue. We finally remove the remaining one element from main queue and return it. Mark the helper queue as main queue.

Second approach:

  • Pop operation is simple. It simply removes element from the main queue and return it.
  • Push operation first adds the element to the helper queue. Then it removes elements from main queue one by one and add them to the helper queue. The intent behind this is to make the last inserted element to be available for removing. Finally make the helper queue as main queue.

The following table gives snapshots of the algorithm at different stages. Assume the queue is presented from left to right. The left most element is at the front of the queue and right most element is at the rear of the queue.



Operation
First queue
Second queue
Result
Push(1)
1

1 added to the main queue
Push(2)
1 2

2 added to the main queue
Pop()

1
Second queue became the main queue and 2 is removed and returned.
Push(3)

1 3
3 added to the main queue
Push(4)

1 3 4
4 added to the main queue
Pop()
1 3

First queue became the main queue and 4 is removed and returned.

Observe that the elements are popped in the LIFO order.


We will see the implementation of first approach in this post. Implementation of second approach can be taken as an exercise.


/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/26/13
 * Time: 4:47 PM
 */
import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args)
    {
        Stack2Queues stck = new Stack2Queues();
        stck.push(1);
        stck.push(2);
        System.out.println(stck.pop());
        stck.push(3);
        System.out.println(stck.pop());
        System.out.println(stck.pop());
        stck.push(4);
        stck.push(5);
        System.out.println(stck.pop());
        System.out.println(stck.pop());
    }
    static class Stack2Queues
    {
        Queue<Integer> q1;
        Queue<Integer> q2;
        int activeQ;
        public Stack2Queues()
        {
            q1 = new LinkedList<Integer>();
            q2 = new LinkedList<Integer>();
            activeQ = 1;
        }
        public void push(int data)
        {
            Queue<Integer> q;
            if( activeQ == 1)
                q = q1;
            else
                q = q2;
            q.add(data);
        }
        public int pop()
        {
            Queue<Integer> mainQ;
            Queue<Integer> helperQ;
            if( activeQ == 1)
            {
                mainQ = q1;
                helperQ = q2;
                activeQ = 2;
            }
            else
            {
                mainQ = q2;
                helperQ = q1;
                activeQ = 1;
            }
            while( mainQ.size() > 1 )
            {
                helperQ.add(mainQ.remove());
            }
            return mainQ.remove();
        }
    }
}

Sunday, August 25, 2013

Finding the first non repeating character in a string

Given a string as input, how do we find the first non-repeating character?

We have to do this in linear time - O(n) and constant extra space- O(1)

Assuming that the character set is ASCII, the number of characters possible are 256. This will differ if the string contains non-ASCII characters like Unicode.

First we declare a count array of size 256 which will keep track of the count of each character appearing in the given string. We use the character itself as an index into the count array. This will give the O(1) time complexity for accessing the count of that character.

For example we store the count of a character 'a' (ASCII value= 98) in count[98]. 

In the first iteration, we iterate over each character of the string and update it's count in the array.

In the next iteration, we go through each character of the array and checking the count of it from the array. The first character that we encounter with the count 1 will be the required answer.

For example if the given input is "this is a test"

the count array will be 
a - 1
e - 1
h - 1
i - 2
s - 3
t - 3

The first character with count=1 is h.

Here is the Java implementation of the above algorithm. 



/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/25/13
 * Time: 4:22 PM
 */
import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
        Scanner reader = new Scanner(System.in);
        String input = reader.nextLine();
        int ind = getFirstNonRepeating(input);
        if( ind != -1)
        {
            System.out.println(input.charAt(ind));
        }
        else
        {
            System.out.println("All characters are repeated");
        }
    }
    public static int getFirstNonRepeating(String input)
    {
        int[] charCount = new int[256];
        int i;
        for( i = 0; i < input.length(); i++)
        { 
             //we use the character itself as an index.
             charCount[ input.charAt(i) ]++;
        }
        for( i = 0; i < input.length(); i++)
        {
            if( charCount[ input.charAt(i) ] == 1)
                return i;
        }
        return -1;
    }
}

Friday, August 23, 2013

Implementing Queue using Stack

How to implement a Queue data structure using Stack?

We have to use only the operations that are supported by Stack ADT*. The methods supported by stack are push(), pop(), and isEmpty(). We have to use only these three operations to implement a Queue. The Queue data structure should primarily support enqueue() and dequeue() operations.

To quickly refresh Stacks, and Queues knowledge;
Stacks are the LIFO (Last-In-First-Out) list in which the last element inserted is the first to be removed.(Example: stack of plates kept in a cafeteria)
Queue is a FIFO ( First-In-First-Out) list in which the first element inserted is the first to be removed (Example: Line of people waiting for a ticket at any counter)

The trick here is to use two stacks, one for adding the data(push-stack), and one for removing the data(pop-stack). So we have to implement enqueue() and dequeue() operations in terms of only stack methods.

enqueue():
First check if the pop-stack is empty. If it is empty, we directly push the element onto the push-stack.
Otherwise We pop all the elements from the pop-stack one-by-one and push them onto the push-stack. Then we push the current element.

dequeue():

First check if the push-stack is empty. If it is empty, we directly pop the element from the pop-stack.
Otherwise we pop all the element from the push-stack one-by-one and push them onto the pop-stack.
Then we pop the element from the pop-stack and return that.

Let us understand this logic with an example. Let us represent the stacks from left to right assuming that the rightmost element is top.

The following table explains a series of enqueue() and dequeue() operations and the status of push and pop-stacks.


Operation
Push-stack
Pop-stack
Comment
Enqueue(1)
1

1 added to push-stack
Enqueue(2)
1, 2

2 added to push-stack
Dequeue()

2
1 removed from queue
Enqueue(3)
2, 3

3 added to push-stack
Enqueue(4)
2, 3, 4

4 added to push-stack
Dequeue()

4, 3
2 removed from queue
Enqueue(5)
3, 4, 5

5 added to push-stack
Dequeue()

5, 4
3 removed from queue

Observe that order of the removed elements. They are in the order of insertion. Performing a series of only enqueue/dequeue operations does not cause any performance problems, as it does not require the elements to be copied between the two stacks.


At any point of time, only one stack is occupied
The worst case occurs when enqueue, and dequeue operations are performed alternatively.


*Abstract Data type: A specification which gives the methods that should be supported by a data structure.

Following is the implementation in Java. I have omitted some exception handling to keep the code simple and clear.



/**
 * Created with IntelliJ IDEA.
 * User: Ravi
 * Date: 8/23/13
 * Time: 1:20 PM
 * To change this template use File | Settings | File Templates.
 */
import java.util.Stack;
public class Main {
    public static void main(String[] args)
    {
        Q2Stacks intQueue = new Q2Stacks();

        intQueue.enqueue(1);
        intQueue.enqueue(2);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(3);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(4);
        intQueue.enqueue(5);
        System.out.println(intQueue.dequeue());
        intQueue.enqueue(6);
        System.out.println(intQueue.dequeue());
        System.out.println(intQueue.dequeue());
        System.out.println(intQueue.dequeue());

    }
    static class Q2Stacks
    {
        private Stack<Integer> pushStack;
        private Stack<Integer> popStack;

        public Q2Stacks()
        {
            pushStack = new Stack<Integer>();
            popStack = new Stack<Integer>();
        }

        public void enqueue(int data)
        {
            if( !popStack.empty() )
            {
                while( !popStack.empty())
                {
                    pushStack.push(popStack.pop());
                }
            }
            pushStack.push(data);
        }

        public int dequeue()
        {
            if( !pushStack.empty() )
            {
                while( !pushStack.empty() )
                {
                    popStack.push( pushStack.pop() );
                }
            }
            return popStack.pop();
        }
    }
}