BFS (Breadth first search ) OR Level Order Traversal on tree

Algorithm

• Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we've visited it, process v, and 
• then visit i.e. mark the vertex as visited and process all of v's neighbors. 
• Now that we've visited and processed all of v's neighbors, 
• we need to visit and process all of v's neighbors neighbors

Example
So consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7
The BFS or level order traversal here is :
1 2 3 4 5 6 7

Solution
The BFS solution is not recursive by nature as it uses Queue rather than stack. We will discuss both recursive and non recursive solution.

Non Recursive solution:
BFS is a first in first out search. So, a non-recursive version of BFS can be done using a queue.

Breadth First Search (BFS) searches the graph one level (one edge away from the starting vertex) at a time. In this respect, it is very similar to the level order traversal that we discussed for trees.
Consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7


                                                       Queue

                           -------------------------------------------
                           |  1
                           --------------------------------------------

Visit each element int the queue, enqueue its left and right nodes and dequeue itself. Once the elements are dequeued, I will put them to the left of the queue.
Visit Node 1, enqueue 2 and 3 and dequeue 1

-------------------------------------------
1                             |  2, 3
                              --------------------------------------------

Visit Node 2, enqueue 4 and 5 and dequeue 2

-------------------------------------------
1, 2                         |  3, 4, 5
                             --------------------------------------------

Visit Node 3, enqueue 6 and 7 and dequeue 3

-------------------------------------------
1, 2, 3                     |  4, 5, 6, 7
                            --------------------------------------------

Visit Node 4, dequeue 4 Nothing to enqueue since 4 has no child nodes

-------------------------------------------
1, 2, 3, 4                 |  5, 6, 7
                            --------------------------------------------

Visit Node 5, dequeue 5, Nothing to enqueue since 5 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5             | 6, 7
                          --------------------------------------------

Visit Node 6, dequeue 6, Nothing to enqueue since 6 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5, 6        |  7
                        --------------------------------------------

Visit Node 7, dequeue 7, Nothing to enqueue since 6 has no child nodes

-------------------------------------------
1, 2, 3, 4, 5, 6, 7     |

To perform a BFS, we use a queue. Every time we visit vertex w's neighbors, we dequeue w and enqueue w's neighbors. In this way, we can keep track of which neighbors belong to which vertex. This is the same technique that we saw for the level-order traversal of a tree. The only new trick is that we need to mark the vertices, so we don't visit them more than once.

public void breadthFirstSearch(vertex v)
{
   Queue q = new Queue();

   v.visited = true;
   q.enQueue(v);

   while( !q.isEmpty() )
   {
       Vertex w = (Vertex)q.deQueue();

       // Print the node.
   
       for(each vertex x adjacent to w)
       { 
           if( !x.visited )
           {
              x.visited = true;
              q.enQueue(x);
           }
        }
    }
}

Layer n+1 gets added to the queue when we process layer n. We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we're at node v and at node w).

Recursive solution
However recursive solution is not very elegant...(it still uses a queue)

void breadthFirstSearch (Node root){
  Queue q;
  q.push(root);
  bfsRecursiveHelper(q)
}
//Helper function
void bfsRecursiveHelper(Queue q){
  if (q.empty()) return;

  Node n = q.pop()
  print "Node: ", n
  if (n.left) q.push(n.left)
  if (n.right) q.push(n.right)
  bfsRecursiveHelper(q)
}

Breadth-first traversal traditionally uses a queue, not a stack. The nature of a queue and a stack are pretty much opposite, so trying to use the call stack (which is a stack, hence the name) as the auxiliary storage (a queue) is pretty much doomed to failure, unless you're doing something stupidly ridiculous with the call stack that you shouldn't be.

On the same token, the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm. This makes it no longer breadth first search on a binary tree, and thus the run-time and whatnot for traditional BFS no longer completely apply. Of course, you can always trivially turn any loop into a recursive call, but that's not any sort of meaningful recursion.


Thanks.

Read More

Check if 2 strings are rotated versions of each other

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-string-problem/.

Problem :

Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?

OR

Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: 'waterbottle' is a rotation of 'erbottlewat'

Example

s1 = "kodeknight" , then s2 can be
odeknightk OR deknightko OR eknightkod and so on.
 i.e. rotating the string 1,2,3 and so on charcters.

Solutions

Method 1 - Club one of the string and rely upon substring method
Here is the solution :

• First make sure s1 and s2 are of the same length.
• Check to see if s2 is a substring of s1 concatenated with s1.

.

boolean checkRotation(string s1, string s2) 
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end

In Java:

boolean isRotation(String s1,String s2) {
    return (s1!=null && s2!=null && 
            s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Method 2 - Use char[] array scan
However if this doesn't clicks to the person's mind, then we can use modulo operator method.

1. Let s1 = char[] a, and s2 = char b[]. 
2. Find index of b[0] in a. You may get single index  called IN or no index or multiple  index. 
3. In case of no index, you can simply return false. 
4. In case of single index, you can check if a[IN+1] = b[1] and so on. If at any point mismatch happens, you can simply return the value. 
5. In case of multiple index, same procedure is repeated as for single index, but for multiple time.

Though method 2 doesn't takes into account the substring method provided to us. So, if substring is provided , method1 is better.

References - stackoverflow , 

Read More

Syntax highlighter for blogs

Read the tutorial here.

Read More

Escape all % characters in a string; % is the escape character

Example :
Input : India has GDP of 10% in 2009
Output : Input has GDP of 10%% in 2009

It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase.

String escapePercent(String input) {
    StringBuilder sb = new StringBuilder();
    char[] str = input.toCharArray();
 
    for (int i = 0; i < input.length(); i++) {
        if (str[i] == ‘%’) sb.append(‘%’);
        sb.append(str[i]);
    }
 
    return new String(sb);
}

Read More

Remove whitespace from a string in-place, in linear time

void removeWhitespace(char* str) {
    int current = 0;
    int ahead = 0;
 
    while (str[ahead] != '\0') {
        while (str[ahead] == ' ') ahead++;
 
        str[current] = str[ahead];
        current++;
        ahead++;
    }
}

Read More

Implementing strcpy

char *strcpy ( char *dest, const char *src );
strcpy is short for string copy, which means it copies the entire contents of src into dest. The contents of dest after strcpy will be exactly the same as src such that strcmp ( dest, src ) will return 0.

size_t strlen ( const char *s );

strlen will return the length of a string, minus the termating character ('\0'). The size_t is nothing to worry about. Just treat it as an integer that cannot be negative, which it is.

Read More

Implementing strcat

char *strcat ( char *dest, const char *src );

strcat is short for string concatenate, which means to add to the end, or append. It adds the second string to the first string. It returns a pointer to the concatenated string. Beware this function, it assumes that dest is large enough to hold the entire contents of src as well as its own contents.

Read More

Implementing strcmp

int strcmp ( const char *s1, const char *s2 );

strcmp will accept two strings. It will return an integer. This integer will either be:

Negative if s1 is less than s2.
Zero if s1 and s2 are equal.
Positive if s1 is greater than s2.

Strcmp is case sensitive. Strcmp also passes the address of the character array to the function to allow it to be accessed.

Read More

Double Linked List Structure

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.

Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked lists to use a list header, or head, that has the same structure as any other list item and is actually part of the list data structure. The picture below shows an empty and nonempty doubly-linked list. By following arrows it is easy to go from the list header to the first and last list element, respectively.

Insertion and removal of an element in a doubly-linked list is in this implementation rather easy. In the picture below we illustrate the pointer changes for a removal of a list item (old pointers have been drawn solid and new pointers are dashed arrows). We first locate the previous list item using the previous field. We make the next field of this list item point to the item following the one in cursor position pos. Then we make the previous field of this following item point to the item preceding the one in the cursor position pos. The list item pointed to by the cursor becomes useless and should be automatically garbage collected.

Implementing the double list items

Double List Node

package com.vaani.ds.doublelist;

final class DoubleListNode {
    Object obj;
    DoubleListNode previous, next;

    public DoubleListNode(Object obj) {
        this(null, obj, null);
    }

    public DoubleListNode(DoubleListNode previous, 

                                   Object obj, DoubleListNode next) {
        this.previous = previous;
        this.obj = obj;
        this.next = next;
    }
}

A class definition with only two constructor methods. The keyword final ensures that this class has no subclasses nor that a user can derive a class from this one.

DoubleLinkedList.java

public class DoubleLinkedList <E>{   
    DoubleListNode<E> head;
    private DoubleListNode<E> tail;
    private int length=0;
    /*
     * creates an empty list
     */
    public DoubleLinkedList() {
        //        head = new DoubleListNode<E>(null);
        //        head.next = head.prev = head;
        head.setPrev(null);
        head.setNext(tail);
        tail.setPrev(head);
        tail.setNext(null);
    }

    public DoubleListNode<E> get(int index) 
                                throws IndexOutOfBoundsException {
        if (index < 0 || index > length) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> cursor = head;
            for (int i = 0; i < index; i++) {
                cursor = cursor.getNext();
            }
            return cursor;
        }
    }

    public E remove(int index) throws IndexOutOfBoundsException {
        if (index == 0) {
            throw new IndexOutOfBoundsException();
        } else {
            DoubleListNode<E> result = get(index);
            result.getNext().setPrev(result.getPrev());
            result.getPrev().setNext(result.getNext());
            length--;
            return result.getValue();
        }
    }
    /*
     * remove all elements in the list
     */
    public final  void clear() {
        head.next = head.prev = head;
    }

    /*
     * returns true if this container is empty.
     */
    public final boolean isEmpty() {
        return head.next == head;
    }

    public int size() {
        return length;
    }


    public String toString() {
        StringBuffer result = new StringBuffer();
        result.append("(head) - ");
        DoubleListNode<E> temp = head;
        while (temp.getNext() != tail) {
            temp = temp.getNext();
            result.append(temp.getValue() + " - ");
        }
        result.append("(tail)");
        return result.toString();
    }

    public void add(int index, E value) 
                                throws IndexOutOfBoundsException {
        DoubleListNode<E> cursor = get(index);
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addHead(E value) {
        DoubleListNode<E> cursor = head;
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }

    public void addTail(E value) {
        DoubleListNode<E> cursor = tail.getPrev();
        DoubleListNode<E> temp = new DoubleListNode<E>(value);
        temp.setPrev(cursor);
        temp.setNext(cursor.getNext());
        cursor.getNext().setPrev(temp);
        cursor.setNext(temp);
        length++;
    }


    /*
     * Return an iterator positioned at the head.
     */
    public final DoubleListIterator head() {
        return new DoubleListIterator(this, head);
    }


}

Read More

First non repeating element in the array

Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’.

Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic.

char returnFirstNonRepeatedChar( char * str )
{
    int i, repeated = 0;
    int len = strlen(str);

    for( i = 0; i < len; i++ )
    {
        repeated = 0;
        for( j = 0; j < len; j++ )
        {
            if( i != j && str[i] == str[j] ) {
                repeated = 1;
                break;
            }
        }         

        if( repeated == 0 ) { 
 // Found the first non-repeated character
            return str[i];
        }
    }

    return '';
}

This approach seems to work perfectly well. But can we do better? Of course we can! With the use of other data structures we can reduce the run time of this algorithm. Any guesses?

Using binary search will not help. Though it looks like easiest way to improve search efficiency on a set of data is to put it in a data structure that allows more efficient searching. What data structures can be searched more efficiently than O(n)? Binary trees can be searched in O(log(n)). But it will not return the "first" non repeating element.

Using hashtable

A hash table could work really handy here. Although, with this approach, we do sacrifice space for runtime improvement. So we can create a hash table by sequentially reading all the characters in the string and keeping count of the number of times each character appears. Once we’ve created the hash table, we can sequentially read the entries to see which one has a count of one. What is the runtime of this algorithm? We have O(n) to create the hash table and another O(n) to read the entries. This results in a runtime of O(n) + O(n) = O(2n) = O(n).

Arrays and hashtables both have constant time element lookup. Begin by trying to take advantage of an array or hashtable because these data structures offer the greatest potential for improvement. You'll want to be able to quickly determine which data structure is better to use.

Hashtables have a higher lookup overhead than arrays. On the other hand, an array would initially contain random values that you would have to take time to set to zero, whereas a hashtable initially has no values. Perhaps the greatest difference is in memory requirements. An array would need an element for every possible value of a character. This would amount to a relatively reasonable 256 elements if you were processing ASCII strings, but if you had to process Unicode strings you would need more than 65,000 elements (Unicode uses 16-bit characters). In contrast, a hashtable would require storage for only the characters that actually exist in the input string. So, arrays are a better choice for long strings with a limited set of possible character values.
hashtables are more efficient for shorter strings or when there are
many possible character values.

Read More

Find anagrams in the array of Strings

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters.

We have already discussed how to check if 2 strings are anagrams here.

Answer: The brute force solution would be to take each string and compare it to every other string in the array one character at a time ( O(n^4) solution, assuming there are n strings with maximum n characters each). This will surely give you the answer but almost certainly not the job unless you improve it.

Let’s use this example to improve on the solution {“abc”, “albert”, “cat”, “gate”, “cab”, “grow”, “act”}

One way we can quicken the string comparison process is by pre-sorting each string alphabetically (any sorting would be fine actually). Pre-sorting helps you avoid comparing each character in a string to each character in another string. You only need to compare every character to the character in the corresponding position of the other string. This reduces the order of the solution ( O(n^2 log n (sorting n strings with n characters each) + n^3 (n^2 comparisons of n characters each)) = O(n^3)) assuming the sorting algorithm is O(n log n)). However, this increases memory usage since you now need to store the original strings so you can print them out later.

After sorting the characters in the string, the array would look like this {“abc”, “abelrt”, “act”, “aegt”, “abc”, “gorw”, “act”}.

Currently, we are comparing each string with every other string. That seems inefficient. How about in addition to sorting the characters in each string, we sort each string in the array alphabetically (again any other sorting will do). Sorting the strings in the array means you do not have to compare each string to every other string, you only have to compare it to the next string in line. If they happen to be the same (i.e. found an anagram), then you can compare with the one after that. Whichever the case is, the order of comparison in this case will be of the order O(n) instead of O(n^2). This sorting will reduce the order to ( O(n^2 log n (sorting characters) + n^2 log n (sorting strings) + n^2 (n comparisons of n characters each)) = O(n^2 log n) assuming the sorting algorithm is O(n log n)). Make sure you also move the strings from the original array in order to maintain the mapping of the sorted array to the original array.

After sorting the strings, the array would look like {“abc”, “abc”, ”abelrt”, “act”, “act”, “aegt”, “gorw”}.

There is an alternate solution using hashing. Put each string in a hash table ( O(n) ). If the spot in the hash table is already taken, then that is an anagram. The order for this solution is ( n^2 (hashing n strings) + n (n insertions into hash table) = O(n^2 ) assuming hashing each string is O(n) ).

Read More

Gold bar with 7 segments

Problem:

You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Solution:

Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact)

i.e 7= 1 + 2 + 4 (only two breaks needed)

1- 1st day

2- 2nd day

(1+2) - 3rd day

4 - 4th day

(4+1) - 5th day

(4+2) - 6th day

(4+2+1) - 7th day.

Read More

Implementing a strstr() / indexOf function

strstr() find the substring index into the larger string and returns the index of first occurrence. Below is the code implementation in java. However note that strstr() equivalent in java is indexOf() which do the same thing.

public static int strStr(String large, String possibleSubStr){
    for(int i = 0; i < large.length(); i++ ) {
        for(int j = 0; j < possibleSubStr.length() && i+j < large.length(); j++ ) {
            if(possibleSubStr.charAt(j) != large.charAt(i+j)) {
                break;
            } else if (j == possibleSubStr.length()-1) {
                return i;
            }
        }
    }
    return -1;
}

public static void main (String args[]){
    String large = "abcde";
    String small = "cd";
    System.out.println(strStr(large, small));
}

Read More

Combination of all the possible characters in the string

Question: Write an algorithm to print all possible combinations of characters in a string.
Note : By combination it means number of different strings possible taking 1 or 2 ...or n characters from string, so we dont have to worry about various character permutation. So for beta, when you get eta, you don't have to get its anagrams like ate, tae etc. For a string of length n, there are nCn + nCn-1 + ... + nC1 combinations. For string abc, there are 1 + 3 + 3 = 7 combinations.
nC1 - a, b, c
nC2 - ab, bc, ca
nC3 - abc

Answer: Any thoughts? One thing is for sure, we can definitely use some recursive logic here. Let’s approach this problem methodically. Since we need to generate combinations, we can start with a single character and then continue to add a character to combinations we have seen so far. Let’s use "abc" as an example.

static void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
       outstr.append(instr.charAt(i));
       System.out.println(outstr);
       combine(instr, outstr, i + 1);
       outstr.deleteCharAt(outstr.length() - 1);//reduce outstr by 1 char from end
    }
}

Now to call this function:
combine("abc", new StringBuffer(), 0);

Better solution
Though solution is good, it will not work when 1 or more characters are repeated. So here is other solution:

static Set getCombinations(String instr, StringBuffer outstr, int index){
    Set combinations = new HashSet();
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        combinations.add(outstr.toString());
        combinations.addAll(getCombinations(instr, outstr, i + 1));
        outstr.deleteCharAt(outstr.length() - 1);
    }
    return combinations;
}

Calling the function:

Set comb = getCombinations(ms, new StringBuffer(), 0);
System.out.println(comb.toString());

Read More

Concatenate N strings with good optimization

You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?

So here goes the algo:
Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost

OR
you can sort the array on the basis of length...and then just concatenate on the length of the string.

Read More

Check if Tree is a Balanced Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/balanced-binary-tree-problem/.

Problem

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one

Solution

Method 1 - Difference of height at each node should not be greater than 1
Here is the code :

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();

        if(isBalanced(root.left) && isBalanced(root.right) 
                 && Math.abs(lh-rh) < =1)
        {
            return true;
        }else
            return false;
    }
    return true;
}

Time complexity - O(n^2)
For each node, we are calculating hieght again and again, which takes O(n) time. Hence O(n^2)

FOLLOW UP : 
suppose the tree is massively unbalanced. Like, a million nodes deep on one side and three deep on the other. Is there a scenario in which this algorithm blows the stack? Can you fix the implementation so that it never blows the stack, even when given a massively unbalanced tree?

Optimization - We are seeing that we are again and again calculating the hieght of the tree. This can be done in 1 method itself.

public boolean isHeightBalanced(Node root, out int height)
    if (root == null){
        height = 0
        return true
 }
 int heightLeft=0, heightRight=0;
 //height is set by the isHeightBalanced function
    boolean balance = isHeightBalanced(root.left, heightLeft) && isHeightBalanced(root.right, heightRight);
    height = max(heightLeft, heightRight)+1
    return balance and abs(heightLeft - heightRight) <= 1    
}

Though this looks like a small optimization, but this will save lots of time.
Time complexity - O(n)

Another way to write the above code, without using boolean variable, we can get rid of it and instead return the height. We can check the height of each subtree as we recurse down from the root.
If the subtree is balanced, then the function return actual height of the subtree.
If the subtree is not balanced, then the function returns -1.

public int checkHeight(TreeNode root){
    if(root == null)
        return 0;
 
    int leftHeight = checkHeight(root.left);
    if(leftHeight == -1)
        return -1;  //not balanced
 
    int rightHeight = checkHeight(root.right);
    if(rightHeight == -1)
        return -1;
 
    int heightDiff = Math.abs(leftHeight - rightHeight);
    if(heightDiff > 1)
        return -1;
    else
        return Math.max(leftHeight, rightHeight) + 1;
}
 
public boolean isBalanced(TreeNode root){
    if(checkHeight(root) == -1)
        return false;
    else
        return true;
}

Time Complexity: O(N) - (credits)

Method 2 -Difference between minDepth and maxDepth should be less than 1
 A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.

Recursive algorithms always work well on trees, so here’s some code.

int minDepth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + min( minDepth( root->left ),
                    minDepth( root->right ));
}

int maxDepth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + max( maxDepth( root->left ),
                            maxDepth( root->right ));
} 

bool isBalanced( Node * root ) {
    return ( maxDepth( root ) - minDepth( root ) ) <= 1
}

Time complexity- O(n)
For each node we calculate maxDepth - takes O(n) time, and minDepth takes O(n) time, and finally the boolean operation takes O(1) time.

Read More

Some Stack Question

 1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used?


Solution:given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below)



2)Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin,which returns the smallest element in the data strucuture all in O(1) worst case time.

Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
    When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.

Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).

You can refer the same implementation solution in java - http://k2code.blogspot.in/2011/12/stack-ds-to-implement-constant-time.html


3)Show how to implement 3 stacks in a single array efficiently?(debated question)

Solution:
Suppose
Stack A contains atmost x elements
Stack B contains atmost Y elements
Stack C contains atmost z elements

take a array of size x+y+z
Now the stack A will grow toward right,
and its operations are
POP_A,PUSH_A

Now stack B will grow towards left
and its operations are
POP_B,PUSH_B

similarly stack C will grow towards left
and its operations are
POP_C,PUSH_C

No OVERFLOW will occur durinng this operation for the stack ..............
The example diagram is

aaaaaaaaaaaa--> <--bbbbbbbbbbbbb <--cccccccccccccccc
grows towards right grows towards left grows towards left
Now stack A if from 0 to x elements ............
Stack B from x+1 to y
C from y+1 to z

More - http://k2code.blogspot.in/2011/12/implement-3-stacks-in-1-array.html


4)Consider a empty stack of integers.Let the numbers 1,2,3,4,5,6 be pushed on to this stack only in the order they appeared from left to right.Let S indicates a push and X indicate a pop operation.Can they be permuted in to the order 325641(output) and order 154623?(if a permutation is possible give the order string of operations.
(Hint: SSSSSSXXXXXX outputs 654321)


Solution: SSSXXSSXSXXX outputs 325641.
154623 cannot be output as 2 is pushed much before 3 so can appear only after 3 is output.


5)Given a string containing N S's and N X's where S indicates a push operation and X indicates a pop operation, and with the stack initially empty,Formulate a rule to check whether a given string S of operations is admissible or not (Hint: A string S of operations should always abide by the properties of the stack which in this case only means you never pop an element from an empty stack)


Solution:Given a string of length 2N, we wish to check whether the given string of operations is permissible or not with respect to its functioning on a stack.
The only restricted operation is pop whose prior requirement is that the stack should not be empty.So while traversing the string from left to right,prior to any pop the stack shouldn't be empty which means the no of S's is always greater than or equal to that of X's.
Hence the condition is at any stage on processing of the string,
no of S's > no of X's




6)Find a simple formula for An, the number of permutations the can be printed on an input of n distinct characters to a stack (similar to question 4)


Solution:The numbers are input in the order 1,2,3,...,N.
So the problem amounts to the number of strings each of N pushes(denoted by S) and N pops(denoted by X).
The only criteria to select a string is at any stage of its processing character by character we should have no of S's > no of X's .

This problem is no different from parentheses problem where N needs to give the no of possible permutations of N parentheses , which if given by Nth catalan number Cn=(2n)!/((n+1)! n!).
For more insite into catalan number refer this link.
http://en.wikipedia.org/wiki/Catalan_number





7)Show that it is possible to obtain the permutation P1P2.........Pn from 1,2,.........n using a stack
if and only if there are no indices i < j < k such that Pj < Pk < Pi.



Solution:The solution can be arrived simply by veirfying that among the 6 possible
orders of Pi,Pj,Pk the rest 5 are possible and the ordering in question i.e is Pi,Pj,Pk is not possible.

We leave it to the reader the verification of possibility of the 5 orderings and deal only with proving that the order Pi,Pj,Pk is not possible.

Suppose say that the order Pi,Pj,Pk is possible.
As Pi is the largest and printed first (i < j < k) followed by Pj and Pk,just before the popping of Pi the ordering of these 3 on the stack shall be Pi,Pk followed by Pj(from top).But as j

Read More

Implement 3 stacks in 1 array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-3-stacks-in-1-array/.

Problem - Implement 3 stacks in 1 array

Solutions
Method 1 - Create 3 stacks with fixed max size
Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: "[" means inclusive, while "(" means exclusive of the end point).

• for stack 1, we will use [0, n/3)
• for stack 2, we will use [n/3, 2n/3)
• for stack 3, we will use [2n/3, n)

Here is the code :

int stackSize = 300;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0, 0, 0}; // stack pointers to track top element

void push(int stackNum, int value) {
 /* Find the index of the top element in the array + 1, and
 increment the stack pointer */
 int index = stackNum * stackSize + stackPointer[stackNum] + 1;
 stackPointer[stackNum]++;
 buffer[index] = value;
}


int pop(int stackNum) {
 int index = stackNum * stackSize + stackPointer[stackNum];
 stackPointer[stackNum]--;
 int value = buffer[index];
 buffer[index]=0;
 return value;
}

int peek(int stackNum) {
 int index = stackNum * stackSize + stackPointer[stackNum];
 return buffer[index];
}


boolean isEmpty(int stackNum) {
 return stackPointer[stackNum] == stackNum*stackSize;
}

Method 2 - Getting space efficient solution
Here is the procedure to do so:

1. Define two stacks beginning at the array endpoints and growing in opposite directions.
2. Define the third stack as starting in the middle and growing in any direction you want.
3. Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

So this is what happens: 

• First stack grows from left to right.
• Second stack grows from right to left.
• Third stack starts from the middle. Suppose odd sized array for simplicity. Then third stack grows like this:

  
  * * * * * * * * * * *
        5 3 1 2 4

First and second stacks are allowed to grow maximum at the half size of array. The third stack can grow to fill in the whole array at a maximum.
Worst case scenario is when one of the first two arrays(arrays at both ends) grows at 50% of the array. Then there is a 50% waste of the array. To optimize the efficiency the third array (i.e. the array in the middle) must be selected to be the one that grows quicker than the other two.

The code can be like this:

public class StackNode {
    int value;
    int prev;

    StackNode(int value, int prev) {
        this.value = value;
        this.prev = prev;
    }
}


public class StackMFromArray {
    private StackNode[] stackNodes = null;
    private static int CAPACITY = 10;
    private int freeListTop = 0;
    private int size = 0;
    private int[] stackPointers = { -1, -1, -1 };

    StackMFromArray() {
        stackNodes = new StackNode[CAPACITY];
        initFreeList();
    }

    private void initFreeList() {
        for (int i = 0; i < CAPACITY; i++) {
            stackNodes[i] = new StackNode(0, i + 1);
        }
    }

    public void push(int stackNum, int value) throws Exception {
        int freeIndex;
        int currentStackTop = stackPointers[stackNum - 1];
        freeIndex = getFreeNodeIndex();
        StackNode n = stackNodes[freeIndex];
        n.prev = currentStackTop;
        n.value = value;
        stackPointers[stackNum - 1] = freeIndex;
    }

    public StackNode pop(int stackNum) throws Exception {
        int currentStackTop = stackPointers[stackNum - 1];
        if (currentStackTop == -1) {
            throw new Exception("UNDERFLOW");
        }

        StackNode temp = stackNodes[currentStackTop];
        stackPointers[stackNum - 1] = temp.prev;
        freeStackNode(currentStackTop);
        return temp;
    }

    private int getFreeNodeIndex() throws Exception {
        int temp = freeListTop;

        if (size >= CAPACITY)
            throw new Exception("OVERFLOW");

        freeListTop = stackNodes[temp].prev;
        size++;
        return temp;
    }

    private void freeStackNode(int index) {
        stackNodes[index].prev = freeListTop;
        freeListTop = index;
        size--;
    }

    public static void main(String args[]) {
                    // Test Driver
        StackMFromArray mulStack = new StackMFromArray();
        try {
            mulStack.push(1, 11);
            mulStack.push(1, 12);
            mulStack.push(2, 21);
            mulStack.push(3, 31);
            mulStack.push(3, 32);
            mulStack.push(2, 22);
            mulStack.push(1, 13);
            StackNode node = mulStack.pop(1);
            node = mulStack.pop(1);
            System.out.println(node.value);
            mulStack.push(1, 13);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

References :
http://stackoverflow.com/questions/4770627/how-to-implement-3-stacks-with-one-array
http://stackoverflow.com/questions/3060104/how-to-implement-three-stacks-using-a-single-array

Read More

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)].
See here for the full implementation.

Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.
To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values. (Of course, there's some extra logic here is case one of the stacks is empty, but that's not too hard to work around).
It will have O(1) get_min() and push() and amortized O(1) pop().

Read More

Find the minimum element in the rotated sorted sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

// always restrict the search to the unsorted 
// sub-array. The min is always there.
public static int findMin(int[] a, int start, int end){
  int mid = (start + end)/2;
  if(start == mid){//only 1 element
    return a[mid+1];
  }else if(a[start] > a[mid]){
    return findMin(a, start, mid);
  }else if(a[mid+1] > a[start]){
    return findMin(a, mid+1, end);
  }
  //else{
  //  return a[mid+1];
  //}
}

To begin with we call findMin(array, 0, array.length-1).
Doing it iteratively:

// index of first element
l = 0

// index of last element.
h = arr.length - 1

// always restrict the search to the unsorted 
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
        // find mid.
        mid = (l + h)/2
        // decide which sub-array to continue with.
        if (arr[mid] > arr[h]) {
                l = mid + 1
        } else {
                h = mid
        }
}
// answer
return arr[l]

Read More

Search an element in the sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

So for example we have sorted array as  -

2,3,6,12, 15, 18.

Now suppose the array is rotated k times ( we don't know k), such that array becomes

15, 18,2,3,6,12

Answer: We can do a binary search with some modified checks.

So lets take arr as array, start be start of the array, end be arr.length-1 and x be the number to find.

Pseudocode: 

1. Find the middle of array
2. Select the sorted array part
   If a [middle]  >  a[start] - That means this part of array is sorted and is without rotation. So, we choose array to search as [start] to a[middle] otherwise we choose a[middle] to a[end].
3. Now, depending on the array we searched in step 2, we will get the sorted array now. Now if key x lies in range of the array, we will search for the element in that range, otherwise other range. 

So, second step helps us get the sorted array on which we can apply binary search. 

Program in java

public int rotatedSearch(int[] arr, int start, int end,
                          int x){
    if(arr[start] == x){
        return start;
    } else if(arr[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }

    int middle = (start + end) / 2;

//we have no rotation between start and middle, i.e. normal sorted array
//if left sub array is sorted
   if(arr[start] <= arr[middle]){
//if x is less than middle - then x may lie in this part of array
        if(x <= arr[middle] && x >= arr[start]){
            return rotatedSearch(arr, start, middle-1, x);
        } else {
            return rotatedSearch(arr, middle+1, end, x);
        }
    }
//if right sub array is sorted
    else if(arr[middle] <= arr[end]){
        if(x >= arr[middle] && x <= arr[end] ){
            return rotatedSearch(arr, middle+1, end, x);
        } else {
            return rotatedSearch(arr, start, middle-1, x);
        }
    } else {
        return -1;
    }
}

Time Complexity - O(log n)
Thanks.

Read More

Reverse a String using bits

Question: Reverse a string in C using as little additional memory as possible.

Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.

Method 1 - Normal Reversal of String

void reverseString(char* str)
{
    int i, j;
    char temp;
    i=j=temp=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
}

Method 2 - Using xor to swap 2 characters
The second solution is slightly better than the first as it does not need the char space. It uses bitmanipulation (XOR in this case) to swap the chars in place.

void reverseStringBetter(char* str)
{
    int i, j;
    i=j=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        str[i] ^= str[j] ;
        str[j] ^= str[i] ;
        str[i] ^= str[j] ;
    }
}

Basically it is using swapping the 2 variables without using temporary variable.
Even though the second solution uses less space, the first one is probably a better solution in terms of readability and maintainability. The compilers are very advanced now and are able to reduce the swap instructions in the first solution into a single execution step. However, the same might not happen for the second solution so in real life situations, it is better to use the first solution although the second solution seems smarter and better theoretically.

Read More

Pick a Random Byte

Problem:

 You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.

Solution: 

Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?

Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.

When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.

Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.

Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.

If you have suggestions or comments, they are always welcome.

Read More