January 2010 ~ KodeKnight

Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.

If (rthread == 1), then it means that the right link of the node points to the inorder success.
If its equal to 0, then the right link represents an ordinary link connecting the right subtree.

Similarily left in-threaded tree in which each NULL left pointer is altered to contain a thread to that node's inorder predecessor.

There can be two types of threaded binary tree :-

1) Single Threaded :- i.e nodes are threaded either towards its inorder predecessor or successor.

2) Double threaded:- i.e nodes are threaded towards both the inorder predecessor and successor.

We may also define right and left pre-threaded binary tree, in which NULL right and left pointers of nodes are replaced by their preorder successors and predecessors. A right in and pre threaded tree can be traversed without the use of stack.

We consider the case of right in-threaded binary tree.

 struct node

{

  int value;

  struct node *left;

  struct node *right;

  int rthread;

}

Function to find the inorder successor



node *inorder_successor(node *x)

{

  node *temp;



  temp = x->right;



  if(x->rthread==1)return(temp);



  while(temp->left!=NULL)temp = temp->left;



  return(temp);

}

Function to traverse the threaded tree in inorder



void inorder(node *head)

{

   node *temp;



   if(head->left==head)

   {

      printf("\nTree is empty!\n");

      return;

   }



   temp = head;



   for(;;)

   {

       temp = inorder_successor(temp);

       if(temp==head)return;

       printf("%d ", temp->value);

   }



}

Inserting toward the left of a node in a threaded binary tree.



void insert(int item, node *x)

{

   node *temp;

   temp = getnode();

   temp->value = item;

   x->left = temp;

   temp->left=NULL;

   temp->right=x;

   temp->rthread=1;

}

Function to insert towards the right of a node in a threaded binary tree.



void insert_right(int item, node *x)

{

   node *temp, r;



   temp=getnode();

   temp->info=item;

   r=x->right;

   x->right=temp;

   x->rthread=0;

   temp->left=NULL;

   temp->right=r;

   temp->rthread=1;

}

Function to find the inorder predecessor (for a left threaded binary three)



node *inorder_predecessor(node *x)

{

     node *temp;



     temp = x->left;



     if(x->lthread==1)return(temp);



     while(temp->right!=NULL)

       temp=temp->right;



     return(temp);

}

Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.

January 25, 2010 Binary Search Tree / BST, DS / Data Structures, inorder, kodeknight, postorder, preorder, traversal, tree No comments

For Inorder And Preorder traversals


inorder  = g d h b e i a f j c
preorder = a b d g h e i c f j

Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, "a" is the root of the tree; "gdhbei" are in the left subtree; "fjc" are in the right subtree. "b" is the next root; "gdh" are in the left subtree; "ei" are in the right subtree. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.

For Inorder and Postorder traversals

Scan postorder from right to left using inorder to separate left and right subtrees.


inorder   = g d h b e i a f j c
postorder = g h d i e b j f c a

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.

For Inorder and Levelorder traversals

Scan level order from left to right using inorder to separate left and right subtrees.


inorder     = g d h b e i a f j c
level order = a b c d e f g h i j

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.

Here is some working code which creates a tree out of the Inorder and Postorder traversals. Note that here the tree has been represented as an array. This really simplifies the whole implementation.

Converting a tree to an array is very easy.

Suppose we have a tree like this


      A
  B       C
 D   E   F   G

The array representation would be


a[1] a[2] a[3] a[4] a[5] a[6] a[7]
  A    B    C    D    E    F    G

That is, for every node at position j in the array, its left child will be stored at position (2*j) and right child at (2*j + 1). The root starts at position 1.

// CONSTRUCTING A TREE GIVEN THE INORDER AND PREORDER SEQUENCE

#include <stdio.h>
#include <string.h>
#include <ctype.h>

/*-------------------------------------------------------------
* Algorithm
*
* Inorder And Preorder
* inorder = g d h b e i a f j c
* preorder = a b d g h e i c f j
* Scan the preorder left to right using the inorder to separate left
* and right subtrees. a is the root of the tree; gdhbei are in the
* left subtree; fjc are in the right subtree.
*------------------------------------------------------------*/

static char io[]="gdhbeiafjc";
static char po[]="abdgheicfj";
static char t[100][100]={'\0'};  //This is where the final tree will be stored
static int hpos=0;

void copy_str(char dest[], char src[], int pos, int start, int end);
void print_t();

int main(int argc, char* argv[])
{
  int i,j,k;
  char *pos;
  int posn;

  // Start the tree with the root and its
  // left and right elements to start off

  for(i=0;i<strlen(io);i++)
  {
     if(io[i]==po[0])
     {
        copy_str(t[1],io,1,i,i);             // We have the root here
        copy_str(t[2],io,2,0,i-1);           // Its left subtree
        copy_str(t[3],io,3,i+1,strlen(io));  // Its right subtree
        print_t();
     }
  }

  // Now construct the remaining tree
  for(i=1;i<strlen(po);i++)
  {
     for(j=1;j<=hpos;j++)
     {
        if((pos=strchr((const char *)t[j],po[i]))!=(char *)0 && strlen(t[j])!=1)
        {
            for(k=0;k<strlen(t[j]);k++)
            {
               if(t[j][k]==po[i]){posn=k;break;}
            }
            printf("\nSplitting [%s] for po[%d]=[%c] at %d..\n", t[j],i,po[i],posn);

            copy_str(t[2*j],t[j],2*j,0,posn-1);
            copy_str(t[2*j+1],t[j],2*j+1,posn+1,strlen(t[j]));
            copy_str(t[j],t[j],j,posn,posn);
            print_t();
        }
     }
  }
}

// This function is used to split a string into three seperate strings
// This is used to create a root, its left subtree and its right subtree

void copy_str(char dest[], char src[], int pos, int start, int end)
{
  char mysrc[100];
  strcpy(mysrc,src);
  dest[0]='\0';
  strncat(dest,mysrc+start,end-start+1);
  if(pos>hpos)hpos=pos;
}


void print_t()
{
  int i;
  for(i=1;i<=hpos;i++)
  {
    printf("\nt[%d] = [%s]", i, t[i]);
  }
  printf("\n");
}

Given an expression tree, evaluate the expression and obtain a paranthesized form of the expression.

January 25, 2010 Binary Search Tree / BST, DS / Data Structures, expressions, kodeknight, tree No comments

The code below prints the paranthesized form of a tree.



print_infix_exp(node * root)

{

   if(root)

   {

      printf("(");

      infix_exp(root->left);

      printf(root->data);

      infix_exp(root->right);

      printf(")");

   }

}

Creating a binary tree for a postfix expression



node *create_tree(char postfix[])

{

   node *temp, *st[100];

   int i,k;

   char symbol;



   for(i=k=0; (symbol = postfix[i])!='\0'; i++)

   {

        temp = (node *) malloc(sizeof(struct node));//temp = getnode();

        temp->value = symbol;

        temp->left = temp->right = NULL;



        if(isalnum(symbol))

              st[k++] = temp;

        else

        {

              temp->right = st[--k];

              temp->left  = st[--k];

              st[k++]     = temp;

        }

   }

   return(st[--k]);

}

Evaluate a tree



float eval(mynode *root)

{

   float num;



   switch(root->value)

   {

        case '+' : return(eval(root->left) + eval(root->right)); break;

        case '-' : return(eval(root->left) - eval(root->right)); break;

        case '/' : return(eval(root->left) / eval(root->right)); break;

        case '*' : return(eval(root->left) * eval(root->right)); break;

        case '$' : return(eval(root->left) $ eval(root->right)); break;

        default  : if(isalpha(root->value))

                   {

                      printf("%c = ", root->value);

                      scanf("%f", &num);

                      return(num);

                   }

                   else

                   {

                      return(root->value - '0');

                   }



   }

}

First / Lowest common ancestor (LCA) of 2 node in binary tree

January 25, 2010 Binary Search Tree / BST, CrackingTheCodingInterview, DS / Data Structures, kodeknight, LCA/Least Common Ancestor, tree No comments

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

Problem

Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree

Example
So for example look into below figure:

So for node 4 and 14, LCA is 8. So there are lots of solution to find it.

Solutions - Case 1 When it is not a Binary Search Tree

Method 1 - Parent pointer is given
If the graph is threaded i.e. each child has pointer to its immediate parent.

class Node{
    int value;
    Node left;
    Node right;
    Node parent;
}

Find list of all the elements from the nodes to the root in order.
Example for node 4, we get {8, {20,8}}
Find the common element in these two lists which appears first

int getHeight(Node p) {
  int height = 0;
  while (p) {
    height++;
    p = p.parent;
  }
  return height;
}
 
// As root.parent is NULL, we don't need to pass root in.
Node LCA(Node p, Node q) {
  int h1 = getHeight(p);
  int h2 = getHeight(q);
  // swap both nodes in case p is deeper than q.
  if (h1 > h2) {
    swap(h1, h2);
    swap(p, q);
  }
  // invariant: h1 <= h2.
  int dh = h2 - h1;
  for (int h = 0; h < dh; h++)
    q = q.parent;
  while (p && q) {
    if (p == q) return p;
    p = p.parent;
    q = q.parent;
  }
  return NULL;  // p and q are not in the same tree
}

Time Complexity - O(log n)

Method 2 - Bottom up recursion(Single Traversal)

TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                TreeNode l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                TreeNode r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Time Complexity - O(n)

Dry running the code
Consider the 2 nodes - 4 and 14 in the diagram above, for which we have to find the LCA.

so, we call findLCA(root,4, 14)
As, root is not equal to p and q, we proceed further.
left = findLCA(8,4,14)
right = findLCA(22,4,14) - This returns nothing, and recursion of this ends here.

Now, we have
left = findLCA(4,4,14) - This returns 4 as LCA
right = findLCA(12,4,14) - this calls 2 methods - findLCA(10,4,14), findLCA(14,4,14). The latter call returns r.

Now as left and right are null, root = 8 is the LCA.

Method 3 - Storing the root to corresponding node paths
This is taken from here.
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.

// Finds the path from root node to given root of the tree, Stores the
// path in a vector path[], returns true if path exists otherwise false
bool findPath(Node root, ArrayList<Integer> path, int k)
{
    // base case
    if (root == null) return false;
 
    // Store this node in path vector. The node will be removed if
    // not in path from root to k
    path.add(root.data);
 
    // See if the k is same as root's key
    if (root.data == k)
        return true;
 
    // Check if k is found in left or right sub-tree
    if ( (root.left && findPath(root.left, path, k)) ||
         (root.right && findPath(root.right, path, k)) )
        return true;
 
    // If not present in subtree rooted with root, remove root from
    // path[] and return false
    path.remove();
    return false;
}
 
// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int findLCA(Node root, int n1, int n2)
{
    // to store paths to n1 and n2 from the root
    ArrayList<Integer> path1, path2;
 
    // Find paths from root to n1 and root to n1. If either n1 or n2
    // is not present, return -1
    if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
          return -1;
 
    // Compare the paths to get the first different value 
    int i;
    for (i = 0; i < path1.size() && i < path2.size() ; i++)
        if (path1[i] != path2[i])
            break;
    return path1[i-1];
}

Solutions - Case 2 When it is a Binary Search Tree

Method 3: Take advantage of Key comparison in BST
Looking at the example tree, the lowest common ancestor to 4 and 14, the node with value 8, is different from the other ancestors to 4 and 14 in an important way. All the other ancestors are either greater than both 4 and 14 or less than both 4 and 14. Only 8 is between 4 and 14. You can use this insight to design a better algorithm.

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {

    if (root == null) {
        return null;
    }

    if (root.value == p || root.value == q) {
        return root;
    }

    if (root.value > p && root.value > q ) {
        return findFirstCommonAncestor(root.left, p, q);
    }
    else if (root.value < p && root.value < q ) {
        return findFirstCommonAncestor(root.right, p, q);
    }
    else {
        return root;
    }
}

Time complexity - O(n)

Method 4
1. Find inorder from Root to node n1 and put in an array List L1 (O(N))
2. Find inorder from Root to node n2 and put in an array List L2 (O(N))
3. Pop head elements from each Lists to make sure the nodes themselves are not involved (cuz we only need the ancestor) 0(1)
4. Compare each element of L1 with L2 starting with the greatest index i.e. bottom. The first match is the LCA O(N)

Method 5
1. Find the inorder and the postorder elements of the range [n1,n2]
2. Find the complete postorder of the tree
3. Find out which element from list 1 comes last in list 2. This is the lowest common ancestor

Pre Order traversal - Recursive and Iterative solution

January 24, 2010 Binary Search Tree / BST, DS / Data Structures, kodeknight, preorder, Preorder traversal, traversal, tree No comments

Example
Consider the tree:
div class="separator" style="clear: both; text-align: center;">

To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Recursive solution

preorder(N *root)
{
  if(root)
  {
    printf("Value : [%d]", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

Iterative solution

In some ways this is the simplest to understand initially. However, even though each node is processed before the subtrees, it still requires that some information be retained while moving down the tree. In the example
above, the * is processed first, then the left sub-tree followed by the right subtree. Therefore, processing must return to the right sub-tree after finishing the processing of the left subtree.

In the examples given, suppose the the processing involved in the traversal is to print out the information stored in each node.Since movement is down the left side of the tree beginning at the root, information on what is to the right must be kept in order to complete the traversal of the right side of any subtree. The obvious ADT for such information is a stack. Because of its LIFO structure, it will be possible to get the information about the right subtrees back in the reverse order in which it was encountered.

The process of doing a pre-order traversal iteratively then has the following steps (assuming that a stack is available to hold pointers to the appropriate nodes):

1. push NULL onto the stack
2. start at the root and begin execution
3. write the information in the nodeN
4. if the nodeN-> right != NULL , push the pointer onto the stack
We push right one first as we need it last
5. if the nodeN -> left != NULL move the pointer to the node on the left
6. if the nodeN->left == NULL pop the stack
7. repeat steps 3 to 7 until no nodes remain

Using array indirectly as stack

void iterativePreorder(node *root)
{
 node *save[100];
 int top = 0;
 if (root == NULL)
 {
  return;
 }

 save[top++] = root;
 
 while (top != 0)
 {
  root = save[--top];
  printf("[%d] ", root->value);
  if (root->right != NULL)
   save[top++] = root->right;
   if (root->left != NULL)
    save[top++] = root->left;
 }
}

Using proper stack ( for clarity)

void preOrderNonRecursive(node* root) {
    if (!root) {
       return;
    }
    Stack<node*> t = new Stack<node*>();
    t.Push(root);
    while (t.Size() > 0) {
        node* top = t.Pop();
        printf("%d", top->value);
        if (top->right != null) {
            t.Push(top->right);
        }
        if (top->left != null) {
            t.Push(top->left);
        }
    }
}

Running the dry run on the above tree :
push root
stack 6

pop 6, push 8 2
stack 8 2

pop 2, push 5, 1
stack 8 5 1

pop 1,
stack 8 5

pop 5,
stack 8

pop 8, push 7
stack 7

pop 7

So have a look at all pop-order
6 2 1 5 8 7

Find the median in a continous stream of numbers

January 18, 2010 Algorithms, array, Binary Search Tree / BST, CrackingTheCodingInterview, hard, kodeknight, median No comments

Problem

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)

Find the rolling median?

Example

0 1 2 3 4
Right FIND MEDIAN returns 2 as median

Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1

Solution

Method 1 - Using heap
We maintain two heaps: minHeap and maxHeap. If we represent these two heaps in terms of list, minHeap is in descending order whereas maxHeap is in ascending order. If we manage to maintain these two heaps while getting new numbers, the median is either in the first place of minHeap or in the first place of maxHeap (or the average of these two).

Pseudocode

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

if some one calls getMedian...then
   If the heaps contain equal elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Consider the example of sequence of numbers: 1, 2, 3, 4 and 5. The maintainence of minHeap, maxHeap are shown below:

After 1 coming:
minHeap: 1
maxHeap:
median : 1

After 2 coming:
minHeap: 1
maxHeap: 2
median : 1.5

After 3 coming:
minHeap: 1
maxHeap: 2 3
median : 2

After 4 coming:
minHeap: 1 2
maxHeap: 3 4
median : 2.5

After 5 coming:
minHeap: 1 2
maxHeap: 3 4 5
median : 3

Java code

public static class maxComparator implements Comparator<Double> {
    public int compare(Double o1, Double o2) {
        return -o1.compareTo(o2);
    }
}
 
static PriorityQueue<Double> minHeap = new PriorityQueue<Double>(11,
        new maxComparator());
static PriorityQueue<Double> maxHeap = new PriorityQueue<Double>();
 
public static void addToHeap(double number) {
    if (minHeap.size() == maxHeap.size()) {
        if (minHeap.isEmpty())
            minHeap.add(number);
        else if (number > minHeap.peek())
            maxHeap.add(number);
        else { // number < minHeap.peek()
            maxHeap.add(minHeap.poll());
            minHeap.add(number);
        }
    } else if (minHeap.size() > maxHeap.size()) {
        if (number > minHeap.peek())
            maxHeap.add(number);
        else { // number <= minHeap.peek()
            maxHeap.add(minHeap.poll());
            minHeap.add(number);
        }
    } else { // minHeap.size() < maxHeap.size()
        if (number < maxHeap.peek())
            minHeap.add(number);
        else { // number >= maxHeap.peek()
            minHeap.add(maxHeap.poll());
            maxHeap.add(number);
        }
    }
}
 
public static double getMedian() {
    if (minHeap.size() == maxHeap.size())
        return (minHeap.peek() + maxHeap.peek()) / 2;
    else if (minHeap.size() > maxHeap.size())
        return minHeap.peek();
    else
        return maxHeap.peek();
}

Method 2 - Using counting sort for integers
We can use counting sort for integers, which will give us A[n/2] as median. But of course this will not work for

Method 3 - Using Balanced Binary Search Trees

At every node of BST, maintain number of elements in the subtree rooted at that node. We can use a node as root of simple binary tree, whose left child is self balancing BST with elements less than root and right child is self balancing BST with elements greater than root. The root element always holds effective median.
If left and right subtrees contain same number of elements, root node holds average of left and right subtree root data. Otherwise, root contains same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed utmost by 1.
Self balancing BST is costly in managing balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method make use of Heaps to trace median.

Data Structure providing sorted order is a Binary Search Tree. However worst case it can be linear list.
Store the numbers in a BST..if the tree is not fully balanced i.e. it's left or right skewed use tree rotations across the root in O(1) to make the height of left and right subtree same.
Now root node would be at the median. This can be found in O(1) time.

Now the height of left and right subtrees across the root is same and we stop.

Finding height of a binary search tree can be done in O(log h) where h is the height of tree

Method 4 - Using skiplist and queue
See the answer here.

Method 5 - P² algorithm
See the answer here.

Thanks. Please share if you have some other ways.

References

Circular Queue

January 14, 2010 DS / Data Structures, kodeknight, queue No comments

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independent, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.

In queue, we take out the value at front and put the value at rear.

Algorithm for Insertion:-
Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:
Step-4.1: if the "front" points where "rear" is pointing and the queue holds a not NULL value for it, then its a "queue overflow" state, so quit; else go to step-4.2
Step-4.2:insert the new value for the queue position pointed by the "rear"

Algorithm for deletion:-
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one

Circular Queue implementation in c/cpp
#include
using namespace std;
#include

int c=0;

struct node
{
   int info;
   struct node *next;
};
struct node *top;

int empty()
{
   return((top == NULL)? 1:0);
}

void insert(int n)
{
   struct node *p;
   p=new node;
   if(p!=NULL)
   {

   c++;
   p->info=n;
   if(empty())
   top=p;
   else
   p->next=top->next;
   top->next=p;
   top=p;
   }
   else
   cout<<"Not inserted,No memory available";
}

int del()
{

   c--;
   struct node *temp;
   int x;
   temp=top->next;
   x=temp->info;
   if(temp==top)
   top=NULL;
   else
   top->next=temp->next;
   free(temp);
   return(x);
}

void print()
{
   int i =0;
   struct node *temp;
   cout<<"\n\t\t";

if(c==0)
   cout<<"\n\t\tNo elements\n";
   else
   {
   temp = top->next;
   while(i!=c)
{
   cout<info<<" ";
   temp=temp->next;
   i++;
   }
cout<
   }
}

int main()
{
   int s,n;
   cout<<"\n\t\tCIRCULAR QUEUE IMPLEMENTATION\n";
   while(1)
   {
   cout<<"\n\t\t1>Push\n";
   cout<<"\t\t2>Pop\n";
   cout<<"\t\t3>Print\n";
   cout<<"\t\t4>Exit\n";
   cout<<"\t\tEnter your choice:";
   cin>>s;
   switch(s)
   {
   case 1:
   cout<<"\n\t\tEnter the number:";
   cin>>n;
   insert(n);
   break;

   case 2:

   if(empty())
   {
   cout<<"\n\t\tStack underflow\n";

   }
   else
   {
   n=del();
   cout<<"\n\t\tThe pop value is:"<<
   }
   break;

   case 3:
   print();
   break;
   case 4:
   exit(1);
   }
   }
}

Bubble sort

January 14, 2010 array, bubble sort, c, cpp, Data Structure, DS / Data Structures, incomplete, java, kodeknight, programCPP, programming, sorting, Sorting Algorithm, sorting arrays No comments

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

What is Bubble Sort?

The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list.

Example
Consider the array - {28, 18, 7, 4, 10}
So, in first pass is bubbled at the top, it being the smallest.

Finally 4 is on top.

Now, in second pass, 10 bubbles out , it being second smallest element and so on:

Bubble sort implementation in c

void bubbleSort(int arr[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }
      }
}

Bubble sort in cpp:

 #include <iostream>
 
 class BubbleSort
 {
     public:
         BubbleSort(){}
         ~BubbleSort(){}
         void sort(int arr[], int size);
 };
 
 void BubbleSort::sort(int arr[], int size)
 {
     //With every iteration in outer loop, the next maximum element is moved to it's correct position
     for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
     {
         for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
         {
             //Comparing two subsequent elements OR bubble comparison
             //Placing the larger element on the right
             if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
             {
                 int temp = arr[innerLoopIdx];
                 arr[innerLoopIdx] = arr[innerLoopIdx + 1];
                 arr[innerLoopIdx + 1] = temp;
             }
         }
     }
 }
 
 void print(int arr[], int size)
 {
     for(int i = 0; i < size; ++i)
         std::cout << arr[i] << " ";
     std::cout << std::endl;
 }
 
 int main()
 {
     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
     BubbleSort bs;
     bs.sort(arr, 9);
     print(arr, 9);
     return 0;
 }#include <iostream>
 
 class BubbleSort
 {
     public:
         BubbleSort(){}
         ~BubbleSort(){}
         void sort(int arr[], int size);
 };
 
 void BubbleSort::sort(int arr[], int size)
 {
     //With every iteration in outer loop, the next maximum element is moved to it's correct position
     for(int outerLoopIdx = 0; outerLoopIdx < size ; ++outerLoopIdx)
     {
         for(int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx)
         {
             //Comparing two subsequent elements OR bubble comparison
             //Placing the larger element on the right
             if(arr[innerLoopIdx] > arr[innerLoopIdx + 1])
             {
                 int temp = arr[innerLoopIdx];
                 arr[innerLoopIdx] = arr[innerLoopIdx + 1];
                 arr[innerLoopIdx + 1] = temp;
             }
         }
     }
 }
 
 void print(int arr[], int size)
 {
     for(int i = 0; i < size; ++i)
         std::cout << arr[i] << " ";
     std::cout << std::endl;
 }
 
 int main()
 {
     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
     BubbleSort bs;
     bs.sort(arr, 9);
     print(arr, 9);
     return 0;
 }

Bubble sort in java
To come

Bubble sort in java using Generics

import org.junit.Assert;
import org.junit.Test;

class GenericBubbleSorter<T extends Comparable<T>>
{
    public void sort(T[] elems) {
        int size = elems.length;

        for (int outerLoopIdx = 0; outerLoopIdx < size; ++outerLoopIdx) {
            for (int innerLoopIdx = 0; innerLoopIdx < (size - outerLoopIdx - 1); ++innerLoopIdx) {
                if (elems[innerLoopIdx].compareTo(elems[innerLoopIdx + 1]) > 0) {
                    T temp = elems[innerLoopIdx];
                    elems[innerLoopIdx] = elems[innerLoopIdx + 1];
                    elems[innerLoopIdx + 1] = temp;
                }
            }
        }
    }
}

public class BubbleSortTester
{
    private String[] unsortedNames = new String[] {
            "Pankaj",
            "Paresh",
            "Ankit",
            "Sankalp",
            "Aditya",
            "Prem",
            "Rocket",
            "Singh",
            "Alabama",
            "Alaska",
            "Animal" };

    private String[] sortedNames = new String[] {
            "Aditya",
            "Alabama",
            "Alaska",
            "Animal",
            "Ankit",
            "Pankaj",
            "Paresh",
            "Prem",
            "Rocket",
            "Sankalp",
            "Singh" };

    @Test
    public void testStringSort() {
        GenericBubbleSorter<String> bs = new GenericBubbleSorter<String>();
        bs.sort(unsortedNames);
        Assert.assertArrayEquals(unsortedNames, sortedNames);
    }
}

Thanks.

Stack implementation using linked list

January 14, 2010 cpp, cppimpl, Data Structure Templates, DS / Data Structures, java, kodeknight, link list, linked list, stack No comments

We will be understanding the stack implementation using linked list. So, please understand the link list before proceeding.

Lets understand how we can implement the different operation using linked list.

CPP implementation
Here is how we use linked list to implement stack in cpp:

#include <iostream>

using namespace std;

struct node
{
       int info;
       struct node *next;

};

struct node *top;

int empty()
{
    return((top == NULL)? 1:0);
}

void push(int n)
{
     struct node *p;
     p=new node;
     if(p!=NULL)
     {
                p->info=n;
                p->next=top;
                top=p;
     }
     else
         cout<<"Not inserted,No memory available";
}

int pop()
{
    struct node *temp;
    int x;
    x=top->info;
    temp=top;
    top=top->next;
    free(temp);
    return(x);
}

void print()
{

     int i =0;
     struct node * temp;
     temp = top;
     cout<<"\n\t\t";
     if(temp==NULL)
          cout<<"\n\t\tNo elements\n";
     else
     {
         while(temp!=NULL)
         {
              int info = temp->info;
              cout<info<<"  ";
              temp=temp->next;
         }

         cout<<"End of List<<"\n";
      }
}

Implementation in java

Here is the implementation in java

class ListNode<E>
{
    E data;
    ListNode<E> next;
}
public class Stack<E>
{
    private ListNode<E> m_head;
 
    public Stack () {
        m_head = null;
    }
 
    public void push (E n) {
        ListNode<E> tmp = getNewNode();
        tmp.data = n;
 
        ListNode<E> oHead = m_head;
        m_head = tmp;
        m_head.next = oHead;
    }
 
    public void pop () {
        if (isEmpty()) throw new NoSuchElementException("Stack is Empty");
        m_head = m_head.next;
    }
 
    public E top () {
        return m_head.data;
    }
 
    public boolean isEmpty () {
        return m_head == null;
    }
 
    private ListNode<E> getNewNode () {
        return new ListNode<E>();
    }
}

Now testing the class above

import junit.framework.Assert;
 
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
 
public class StackTest
{
    private String[] elems = new String[] { "A", "B", "C" };
    private Stack<String> stack = new Stack<String>();
 
    @Before
    public void setup () {
        for (String str : elems)
        {
            stack.push(str);
        }
    }
 
    @After
    public void destroy () {
        while (stack.isEmpty() == false)
        {
            stack.pop();
        }
    }
 
    @Test
    public void testTop () {
        Assert.assertEquals(stack.top(), "C");
    }
 
    @Test
    public void testPush () {
        Assert.assertEquals(stack.top(), "C");
        stack.pop();
        Assert.assertEquals(stack.top(), "B");
        stack.pop();
        Assert.assertEquals(stack.top(), "A");
    }
}

Please let us know the feedback.

Radix sort

January 14, 2010 DS / Data Structures, kodeknight, programCPP, sorting No comments

What is radix sort?
Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.
2. After each pass, the numbers are collected from the buckets, keeping the numbers in order
3. Now, recursively redistribute the numbers as in the above step '1' but with a following reconsideration: take into account next most significant part of the number, which is then followed by above step '2'.

Radix sort in C:

#include <conio.h>
using namespace std;
#include <iostream>
#include <math>

void radixsort(int num[],int n)
{
     int queue[10][10],inc[10],i,j,k,c,exp;
     for(i=0;i<4;i++)
     {
                exp=pow(10,i);
                for(j=0;j<10;j++)
                                 inc[j]=-1;    
                for(j=0;j<10;j++)
                {                
                                 k=(num[j]/exp)%10;
                                 inc[k]++;
                                 queue[k][inc[k]]=num[j];
                }
                for(k=0,c=0;k<10;k++)
                {
                                 j=0;
                                 if(inc[k]!=-1)
                                                  while(j<=inc[k])
                                                  {
                                                                 num[c++]=queue[k][j];
                                                                 j++;
                                                  }
                }
     }
}

Using the function

int main()
{
    int num[10];
    cout<<"Enter the elements to be sorted :\n";
    for(int i=0;i<10;i++)
            cin>>num[i];
    radixsort(num,10);
    cout<<"The elemments in sorted order are :\n";
    for(int i=0;i<10;i++)
            cout<<<"  ";
    getch();
}

Quick sort

January 14, 2010 Algorithms, Data Structure, divide and conquer, kodeknight, pathological data, programCPP, quicksort, randomized algorithm, sorting, time complexity No comments

Hoore cisca discovered it in 1961.

Why quicksort?

Definitely a greatest hit algorithm
Prevalent in practice
O(n log n) time "on average"
minimal extra memory needed (which gives it leverage over merge sort)

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Quicksort helps us solving this problem.

What is quick sort?

Quick Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.

This algorithm works as follows:

Pick the pivot element of the array , say first element:
Rearrange the array such that:
-- Left of pivot has elements less than pivot
-- Right of pivot has elements greater than pivot

Note that elements left of pivot should not be sorted as whole, but just be less than the pivot.
Now, recursively sort the two half's separately with step 1 and 2.

So the key concept behind Quicksort is the partitioning around a pivot. Choose one of the elements in the array as a pivot. Then rearrange the array so that everything less than the pivot is to its left and everything greater is to its right. Note that this rearrangement does not mean the entire array has to be sorted after this one partition. However, the pivot does end up in the "right" spot. That is, the pivot will not be moved anymore because it is already in the spot where it will be in the sorted array.

2 cool facts about partitioning

Partitioning can be done in linear time without allocating any extra memory
reduces the problem size - i.e. allows us to use divide and conquer approach

Pseudocode of quicksort

 QuickSort(Array a, length n)
    if n = 1 return
    p = ChoosePivot(a, n)
    Parition a around p
    QuickSort(first part)
    QuickSort(second part)

For the time being lets choose pivot as the first element.

Partitioning
Partitioning using linear extra space
The easy to partition the array would be to allocate a temporary array using O(n) space. So, whatever element you find lower than the pivot, place it in start, and whatever you find more that pivot, just place it in end, after the complete scan of array, only 1 hole will remain, just place the pivot there and you are done.

In-place version of partitioning
This will still partition around the pivot in O(n) time. There are various versions of partitioning.

Version 1
Assuming the pivot is the first element in the array, you traverse the array and keep a partitioned part and an unpartitioned part. You use one pointer to traverse the array and another to point to the first element in the partitioned part larger than the pivot. When you find an element smaller than the pivot, you simply swap it with the pointer's element. When you are finished, swap the element one before the pointer with the pivot to finish partitioning.

Partition(a,left,right)
{
   p=a[left];
   i=left+1;
   for(j=l+1;j<right;j++)
   {
      if(a[j]<p)
         swap(a[j],a[i]);
   }
   i++;
   swap(a[left],a[i-1]);
}

Lets dry run this version

So, initially left=0, right =8, as they are the boundaries of the array. Now, i and j initially point to 1 and pivot is 40. Now, i denotes the boundary between the elements less than pivot and more than pivot. j denotes the elements that we have scanned so far.

Now, we see if a[j]<p, so we swap these 2 elements, and increment i, as now it is the boundary between the elements less than pivot.
So, here we compare 10 and 40, and as 10 is less than 40, we swap 20 and 10 i.e. a[i] and a[j] and increment i.

Now, i and j point to 20. We increment j. j = 3.
a[j] > 40, so we continue and increment j again.

j=4, a[j] > 40, so we increment j again.

j=5, a[j] > 40. so we increment j again.

j=6, a[j] = 7. This time, a[j]<40 1.="" 7="" 80="" a="" and="" by="" continued="" element="" i="4" increment="" is="" j="" nbsp="" now.="" once="" p="" pivot="" properly.="" so="" swap="" the="" this="" we="">

Version 2:

Partition(a,left,right)
{
   p=a[left];
   l=left+1;
   while (l < r) {
       while (l < right && a[l] < p) l++; 
       while (r > left && a[r] >= p) r--;
        if (l < r)   swap a[l],a[r]
   }
}

Dry running the version 2

Initial condition: left=0, right = 8, p = a[left] = 40, l = 1, r = 8

Now, executing the while loop - if l is less than r and a[l] is less than pivot, we just increment l.For example, a[1] i.e. 20 is less than 40, so we just increment l further.

Now, we have a[2] i.e. 10, which is still less than 40, so we increment further.

Now, we have 80, which is more than 40, hence we find a[l] > pivot, hence we come out of this loop.

Now, we start with 2nd while loop, checking if a[r] > pivot

as, a[8] or 100 is greater than pivot or 40, we decrement r by 1. Now we come out of this while loop as well as a[7] i.e 30 < 40 the pivot. Now, as l<r, we just swap the a[l] and a[r].

So, we finally have

Now, we again continue with outer while loop as l<r.

Implementation in cpp

Following is the implementation in cpp:
Partition (based on version 2):

int Partition(int *darr, int lb, int ub)
{
    int a;              /* key holder */
    int up, down;
    int temp;
    a = darr[lb];
    up = ub;
    down = lb;

 while (down < up)
 {
  while (darr[down] <= a)   /* scan the keys from left to right */
   down++;
  while (darr[up] > a)      /* scan the keys from right to left */
   up--;
  if (down < up)
  {
   temp = darr[down];          /* interchange records */
   darr[down] = darr[up];
   darr[up] = temp;
  }
 }

 darr[lb] = darr[up];                /* interchange records */
 darr[up] = a;

return up;
}

Quicksort method based on partition:

void quick_sort(int *darr, int lb, int ub)
{
    /* temporary variable, used in swapping */
 int up;
 if (lb >= ub)
  return;

 up = Partition(darr,lb,ub);
 quick_sort(darr, lb, up-1);  /* recursive call - sort first subtable */
 quick_sort(darr, up+1, ub);  /* recursive call - sort second subtable */
}

Analysis of Quicksort

Another cool fact about QuickSort is that every two elements in an array will either get compared once or never. If you think about it, the only comparisons that ever occur are the ones between the pivot and every other element in [start, end]. Once these comparisons are over, there are two recursive calls to QuickSort, both of which do not include the pivot at all. Thus, that pivot can only be compared once at most.

Finding the Optimal Pivot

So far, we have used the first element in the array as the pivot. What if the array were already sorted, or reverse sorted? Then partitioning would leave the pivot either in the same spot or in the back. Then we'd recursively call QuickSort on the (n-1) length subarray. We do this over and over until the array is sorted. This takes O(n²) time. This is worst case scenario of quick sort.

How to choose pivots?
What would be a better way? If we want to balance the two subarrays so that they are about equal in length, then we would want to find the median. Median of the array is element such that half of element are less than other half are more than that element. Thus, if we are lucky enough to be able to get the median as the pivot every time, then the algorithm would be much like MergeSort without the extra memory allocation, running in O(nlogn).

Big idea is to choose the pivots randomly. For every time we pass array of k elements, we will choose the pivot randomly from k elements with equally likely probability. So, every time we call the algorithm we get the different execution, even for same input.

As a side note, this is an instance of adding randomness to our algorithm. Randomness is actually really useful in many applications because it makes things easier, more elegant, and efficient, but more on this later.

What if finding the median is too hard? What other choices do we have. Well, it is established that if we are able to split the subarrays just 25%/75%, then we will still have O(nlogn) running time. If we had 100 elements, we just have to pick an element that is anywhere from 25th smallest to 75th smallest. This is half the total elements, so we have 50% chance of picking this pivot.

In conclusion, we have established that a randomized QuickSort has an average running time of O(nlogn), a blazingly fast algorithm without the extra space allocation.Also, for sorted array, it performs very poorly, with worst case scenario running time as O(n²).

Source

Merge Sort

January 14, 2010 divide and conquer, DS / Data Structures, incomplete, iterative, kodeknight, merge, programCPP, recursion, sorting No comments

Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.

So, we break the array into 2, then sort the 2 arrays, and re-merge them. Breaking the arrays until we reach the base case, so that we can come out or recursion :

Then we merge the 2 arrays, to get the array. Now we have 2 sorted arrays and we combine the arrays, and this is the step is called merge.

Merging the sorted array:

We will see how we can merge the 2 arrays in sorted order.

So, this is merge sort in picture:

Pseudocode for the merge sort algorithm
Here is the pseudocode for mergesort algorithm(recursive OR divide and conquer approach):

mergeSort(arr)
{
  list1 = arr(0-n/2);
  list2 = arr(n/2+1,n);
  list1 = mergeSort(list1);
  list2 = mergeSort(list2);
}

base case
0 or 1 element,

odd number case - In the pseudocode, I have skipped the complexity of array having odd number of elements.

Running time of the algorithm
Merging of 2 sorted array list1 and list2 of size m will be O(m), i.e. traversing 2 arrays of size m.

Also, we have to break the array into 2, until we reach the base case, where there were only 0 or 1 element left.
The height of this binary tree is log n. At each leven j, the size of the array is n/2j, as we have to pass half of the input size .

So, at level j, m = n/2j. So, merging 2 sorted arrays will take O(n/2j) which is O(n). So, total complexity is O(n log n).

Merging is the process of combining two or more sorted arrays into a third sorted array. We can use this technique to sort an array of n elements as follows.
Divide the array into ‘n’ sub arrays of size 1 and merge adjacent pairs of sub arrays. Then we can have approximately n/2 sorted sub arrays of size 2. Repeat this process until there is 1 array containing n elements.
Algorithm1. Establish a sub array ‘a’ with n elements
2. Let size < - 1 3. Repeat steps 4 through 6 until size >= n
4. Subdivide the sub array into sub arrays of size ‘size’
5. Merge adjacent pairs of sub arrays
6. Double the size

Here is the iterative implementation of mergesort in c:

#define MAX 20

void mergesort(int *,int);
void main()
{
 int x[MAX],n,j,i;
 char ans;
 clrscr();
 {
  printf("\nEnter The Length Of The Array\t: ");
  scanf("%d",&n);
  for(i=0;i< n;i++)
  {
   printf("Enter Element %d\t: ",i+1);
   scanf("%d",&x[i]);
  }
  mergesort(x,n);
  printf("\n\t│ Sorted Array :\t\t\t│\n\t│");
  for(i=0;i< n;i++)
   printf("%d\t",x[i]);
 }
 printf("│");
 getch();
}

void mergesort(int x[],int n)
{
 int sub[MAX];
 int i,j,k,list1,list2,u1,u2,size=1;
 while(size< n)
 {
  list1=0;
  k=0;

  while((list1+size)< n)
  {
   list2=list1+size;
   u1=list2-1;
   u2=((list2+size-1)< n)?(list2+size-1):(n-1);

   for(i=list1,j=list2;i< =u1 &&amp;amp; j< =u2;k++)
    if(x[i]< =x[j])
     sub[k]=x[i++];
    else
     sub[k]=x[j++];

   for(;i< =u1;k++)
    sub[k]=x[i++];

   for(;j< =u2;k++)
    sub[k]=x[j++];

   list1=u2+1;
  }
  for(i=list1;k< n;i++)
   sub[k++] = x[i];
  for(i=0;i< n;i++)
   x[i] =sub[i];
  size *= 2;
 }
}

Output:
/********* OUTPUT **********

Enter The Length Of The Array : 5
Enter Element 1 : 12
Enter Element 2 : 69
Enter Element 3 : 78
Enter Element 4 : 2
Enter Element 5 : 5

│ Sorted Array : │
│2 5 12 69 78 │

Fibonacci, triangular, square, cube, pentagon numbers

January 07, 2010 kodeknight, Special Nos. No comments

Fibonacci number is N, iff 5N^2 - 4 OR 5N^2+4 is a perfect square.

Triangular number are of n(n+1) / 2
eg. 1,3,6,10,15....

Square number : N^2

Cube: N^3

Array of 0 and 1, put 0's at even position and 1's at odd position

January 07, 2010 brainteaser, kodeknight, programming, Puzzles No comments

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice verse then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

Thursday, May 15, 2008

This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
while(oddInd
if(oddInd>=strLen) break;
while(evenInd
if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.

jigsaw

Thursday, May 15, 2008

OOPS!!! There was a big mistake in the above code.
This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.

jigsaw

Thursday, May 15, 2008

Perish the thought that anyone should use extra memory!

BTW, the indexes into the array are extra memory.

Too many of these questions are isomorphic with:
"Oh, so you can type in your code? How about if we tie one arm behind your back? YANK! Still typing? How about if we keep hitting you with this baseball bat? Whack, whack, whack! Still at it, huh? Well, at least we got him down to 2 WPM."

Sincerely,

Gene Wirchenko

Gene Wirchenko

Thursday, May 15, 2008

:) That's funny. BTW when he said extra memory, he meant variable amt of memory i guess.

jigsaw

Friday, May 16, 2008

That seems to be what they mean when they say no extra memory. Heck making a function call allocates a frame on the stack so does that mean no function calls either?

I always took it to mean no building a data structure. Which can be a valid restriction if data is going to be changing often(high rebuild costs) or you have a truly large dataset. It can be hard to get a std::vector to hit 100mb if you already have a number of other 100mb chunks floating around.

soup
Friday, May 16, 2008

soup,

The usual complexity-theoretic definition of "no extra memory" is that the program can use a constant number of registers just large enough to index the input.

d
Friday, May 16, 2008

I tried JigSaw's solution in to java(http://pastebin.com/f41fe39d1). I might have mis-understood the code but the resulting array is
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

ved

Monday, May 26, 2008

I think there is a problem in jigsaw's solution.His solution says:
oddInd==0;
evenInd=1;

while(true)
{
while(oddInd if(oddInd>=strLen) break;
while(evenInd if(evenInd>=strLen) break;
swap(str[evenInd], str[oddInd]);
}
First of all.it will produce an an arrangement of 10101010 type of string.But that can be solved by using str[oddInd]==0 and str[evenInd]==1. But more serious problem is if the array is such that it has even no. of elements and each even positions are correctly filled with 0s and there are some extra 0s in odd positions because in that case the first inner while loop executes and then the outer while loop terminates by break statement.

sagsriv

Friday, June 13, 2008

@sagsriv

i guess the depend on understanding of "and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched"

e.g., input array:
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
output array should be:
a)
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
since in the question, it states
"if 0s exceed no. of 1s or vice versa then keep them untouched"

or

b)
{0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 }
to move "0s" to the end.which should can be also done in one pass.

which looks better..lol

ray

Monday, July 07, 2008

Add all the numbers in the array to get the sum. The sum equals to number of ONEs in the array? Then prepare the sequence of 0,1,0,1 ... based on the no. of ONEs using a simple for loop.

Like Us

Followers

Topics

Books for You

Contributors

Search This Blog

Labels

Blog Archive

Blogger news

Blogroll

ADs

Blogger news

Friday, January 29, 2010

Common Operations on BST

Traversal in BST:

Successors and ancestors

Some easy questions on BST

Monday, January 25, 2010

Sunday, January 24, 2010

Monday, January 18, 2010

Example

Solution

Thursday, January 14, 2010

Thursday, January 7, 2010

Labels

Likeus