"No one is harder on a talented person than the person themselves" - Linda Wilkinson ; "Trust your guts and don't follow the herd" ; "Validate direction not destination" ;

April 20, 2010

Algorithms - Stack, Queue

Pseudo Code and Approach for Programming Questions
Question #1. Finding all leaders in a array. An element in array is called leader if all following elements are smaller than it.
Example: 10,5,6,4,9,5,4,3,2,1. 9 is a leader as all elements after 9 are less than it.
Approach I: Parse from last element (i=n;i>0;i--) to first element. If a[n] < a[n-1] then a[n] it is a leader. This will complete in O(N) time
Approach II: Follow the same bubble sort approach. O(N2)
Max Value in an Array. O(N) Time
using System;{
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MaxValue
class Program
{
    static void Main(string[] args)
    {
        int[] numbers = new int[10] {100, 10, 5, 4, 20, 40, 90, 88, 99, 1 };
        int currentmax = new int();
        currentmax = numbers[0];
        for(int i = 1; i < 10; i++)
       {
            if(currentmax < numbers[i])
            currentmax = numbers[i];
       }
       Console.WriteLine("Max Value is " + currentmax);
       Console.ReadLine();
    }
}
}
Question #2, You have an Integer Array {1,2,3,4,5,6}. A function which accepts integer array and a number. You need to find atleast 2 possible combinations in the array which produce sum equal to the number
Example: For Array {1,2,3,4,5,6,7} and Number 8. The two possible pairs are {6,2}, {7,1}
Approach 1: Take every element in the array and sum it up with all elements in array and see does it equate to the number.
Example: 1+2, 1+3, 1+4....1+7...If its equal to 8 set it to flag = 1. Same do for next element 2...When flag is 2 (2 elements found) skip the loop. This is again O(N2)

Question#3, How to find whether a string is Palindrome without extra space
Example: LIRIL. This is a palindrome. Start comparision from N to 0 until half of length of message
int palflag = 0
for(i=0;j=strlen(message)-1; i< strlen(message)/2+1;i++,j--)
{
  if(a[i]!= a[j])
   {
      palflag = 1
   }
}
if palflag==0 then Palindrome

Yeah ! Time to relearn and refresh Data structures. Posting below working example and code....

/* C++ Program to Simulate Stack Operations  - Program written using C Free 5.0*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX 5
#define TRUE 1
#define FALSE 0

struct stack
{
      int top;
      int items[MAX];
};

/* Declare Functions */
int overflow(struct stack *);
int empty(struct stack *);

/* Add-push element to stack */
void push(struct stack *, int);

/* Remove-pop element from stack */
int pop(struct stack *);

/* Display elements in stack*/
void display(struct stack *);

int main()
{
      int x, choice;
      struct stack s1, *s;
      s = &s1;
      s->top= -1;
      do
      //loop to provide options on operations on stack
      {
           
            printf("\n 1.PUSH \n 2.POP \n 3.Display \n 4. EXIT \n");
            printf("Enter your choice \n");
            scanf("%d",&choice);
            printf("Choice is %d\n", choice);
            switch(choice)
            {
                  case 1:
                        if(overflow(s))
                        {
                            printf("STACK OVERFLOW \n");                         
                        }
                        else
                        {
                              printf("Enter element to be pushed \n");
                              scanf("%d",&x);
                              printf("%d\n",x);
                              push(s,x);
                        }
                        break;
                  case 2:
                        if(empty(s))     
                              printf("STACK UNDERFLOW \n");
                        else
                              printf("the popped element is %d", pop(s));
                              break;
                  case 3:
                        if(empty(s))
                              printf("STACK EMPTY\n");
                        else
                              display(s);
                              break;
                  case 4:
                        printf("EXITING \n");
                        exit(1);
                  default:printf("Enter 1,2,3 or 4 ONLY \n");
            }
      }while(choice!=4);
      return 0;
}

/* check for overflow */
int overflow(struct stack *s)
{
      printf("value of top variable is %d \n", s->top);
      if(s->top ==(MAX-1))   
            return(TRUE);
      else
            return(FALSE);
}

/*check if stack is empty */
int empty(struct stack *s)
{
      return((s->top==-1)?TRUE:FALSE);
     
}

/* pop element from stack */
int pop(struct stack *s)
{
      return(s->items[(s->top)--]);
}

/* push an element into stack */
void push(struct stack *s, int x)
{
      s->items[++(s->top)]=x;
      printf("value of top variable is %d \n", s->top);
}

/* Display elements from stack */
void display(struct stack *s)
{
      int i;
      printf("The stack is \n");
      for(i=s->top;i>=0;i--)
      {    
            printf("Element is %d\n",s->items[i]);
            printf("value of top variable is %d \n", s->top);
      }
}
Running time of push and pop function is O(1)

#include<stdio.h>
#include<process.h>
#include<stdlib.h>
#include<conio.h>
#define QF 10
/* Program to demonstrate simple circular queue */
/* 0(1) or fixed amount of time for addition  and deletion */
/*in order to insert and delete, rear and front are advanced one position clockwise*/

/* Method to check queue is full */
int qfull(int count)
{
      return(count==QF-1)?1:0;
}

/* Check if queue is empty */
int qempty(int count)
{
      return(count==0)?1:0;
}

/*Insert element at rear(last) position */
void insert_rear(int item, int *count, int *r, int *q)
{
      if(qfull(*count))
      {
            printf("Queue is full \n");
            return;
      }
      //Element assigned at last position
      *r = (*r+1)%QF;
      q[*r]=item;
     (*count)++;
}

/* Delete element in front position of queue */
void delete_front(int *f, int *count, int *q)
{
      if(qempty(*count))     
      {
            printf("QEmpty\n");
            return;
      }
      printf("Element deleted is %d \n",q[(*f)]);
      (*f)=(*f+1)%QF;
      (*count)--;
}

/*Display elements in the queue */
void display(int f, int count, int *q)
{
      int i;
      printf("In display loop f=%d, r=%d",f,count);
      if(qempty(count))
      {
            printf("Q is Empty \n");
            return;
      }
      printf("Contents of Queue are \n");
      for(i=f;i<=count;i++)
      {
            printf("%d\n",q[i]);
      }
}

int main()
{
      int choice, f,r,q[10],item;
      int count=0;
      f=0;r=-1;
      for(;;)
      {
            printf("\n 1.Insert in Front of Queue ");
            printf("\n 2.Delete from Front of Queue ");
            printf("\n 3.Display\n ");
            printf("\n 4.Exit\n ");
            scanf("%d",&choice);
            switch(choice)
            {
                  case 1:
                        printf("\n Enter element to be inserted\n");
                        scanf("%d",&item);
                        insert_rear(item,&count,&r,q);
                        break;
                  case 2:
                        delete_front(&f,&count,q);
                        break;
                  case 3:
                        display(f,count,q);
                        break;
                  case 4:
                        printf("EXITING \n");
                        exit(1);
                  default:printf("Enter 1,2,3,4 ONLY \n");
            }
      }     return 0;
}

Merging two sorted Arrays. Wikipedia & algolist.net I referenced to explain examples for bubble, selection & O(N) optimized solution

#include<stdio.h>
int main()
{

      int a[5]={90,100,190,300,1000};
      int b[5]={10,80,380,390,1100};
      int i=5;
      int c[10];
      int d[10];
      int e[10];
      int min, temp=0;
      int k=0,l=0;
      int iPos,iMin,j;
      for(i=0;i<5;i++)
      {
            c[k]=a[i];
            d[k]=a[i];
            k++;
            c[k]=b[i];
            d[k]=b[i];
            k++;
      }
      printf("Merged Array is \n");
      for(i=0;i<10;i++)
      {
            printf("%d\n",c[i]);
      }

      /* Bubble Sort  O(N2)*/
      for (iPos = 0; iPos < 10; iPos++)
      {
        for (i = iPos+1; i < 10; i++)
          {
            if (c[iPos] > c[i])
              {
                      temp = c[iPos];
                  c[iPos]=c[i];
                  c[i]=temp;
              }
          }
      }
      printf("Sorted Array -Bubble Sort is \n");
      for(i=0;i<10;i++)
      {
            printf("%d\n",c[i]);
      }
     
      /* Selection Sort O(N2)*/
      /*http://en.wikipedia.org/wiki/Selection_sort */
      for (iPos = 0; iPos < 10; iPos++)
      {
        iMin = iPos;
        for (i = iPos+1; i < 10; i++)
          {
            if (d[i] < d[iMin])
              {
                iMin = i;
              }
          }
      temp = d[iPos];
      d[iPos]=d[iMin];
      d[iMin]=temp;
      }
      printf("Sorted Array -Selection Sort is \n");
      for(i=0;i<10;i++)
      {
            printf("%d\n",d[i]);
      }

      /* O(N) Logic - http://www.algolist.net/Algorithms/Merge/Sorted_arrays */
      /*    int a[5]={90,100,190,300,1000};
            int b[5]={10,80,380,390,1100};
      */
      i = 0;
      j = 0;
      k = 0;
      int m=5,n=5;
      while (i < m && j < n)
            {
            if (a[i] <= b[j])
                        {
                  e[k] = a[i];
                  i++;
            }
                   else
                  {
                  e[k] = b[j];
                  j++;
            }
            k++;
      }
      if (i < m)
            {
            for (int p = i; p < m; p++)
                        {
                  e[k] = a[p];
                  k++;
            }
      } else
            {
            for (int p = j; p < n; p++)
                        {
                  e[k] = b[p];
                  k++;
            }
      }
      printf("Sorted Array - O(N) is \n");
      for(i=0;i<10;i++)
      {
            printf("%d\n",e[i]);
      }
}

/* Program to swap Pair of words */
#include<stdio.h>
#include<string.h>
int main()
{
      char a[100]="abcdefgh";
      int len = strlen(a);
      printf("length of A is %d\n",len);
      int i,j;
      char c;
      /* Input abcdefgh, output cdabghef */
      for(i=0;i<len;i+=4)
      {
            c = a[i+2];
            printf("%c\n",c);
            a[i+2] = a[i]; //Assign 2 with 0
            a[i] = c; //Assign 0 with 2
            c = a[i+3];
            printf("%c\n",c);
            a[i+3] = a[i+1];//Assign 3 with 1
            a[i+1]=c;//Assign 1 with 3
      }
      printf("Modified string is %s\n",a);
}

/* C Program - Longest Palindrome in given string O(N2) Solution*/
#include<stdio.h>
#include<string.h>
char s[100]="MaxLengthStringAAAAA";
int length;
int checkpalindrome(int, int);
int main()
{
      length = strlen(s);
      int i,j;
      int count,currentcount;
      int startpos, endpos;
      count=0, currentcount=0;
      printf("length is %d\n",length);
      for(i=0;i<length;i++)
      {
            for(j=i+1;j<length;j++)
            {
                  printf("i value is %d, j value is %d\n",i,j);
                  if(checkpalindrome(i,j))
                  {
                        currentcount = j-i;
                        if(currentcount > count)
                        {
                              count=currentcount;
                              startpos =i;
                              endpos = j;
                        }
                  }
            }
      }
      printf("\nResult is Start %d, End is %d\n",startpos,endpos);
      printf("Longest palindrome in a string Result \n");
      for(i=startpos;i<=endpos;i++)
      {
            printf("%c",s[i]);
      }
      return 0;  
}
int checkpalindrome(int start, int end)
{
      int a,b;
      int flag=1;
      for(a=start,b=end;a<b;a++,b--)     
      {
            printf("character at postion a is %c, b is %c\n",s[a],s[b]);
            if(s[a]!=s[b])
            {
                  flag=0;
                  break;     
            }
      }
      printf("Flag value is %d\n",flag);
      return flag;
}
C Program convert Numbers into words
Program to calculate size of tree
Program to determine if two trees are identical
There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full round of the circle. Mileage of car is fixed

1: Choose any node to start;
2: Get fuel;
3: Go clockwise;
4: If fuel is over, go to 5, else go to 6:
5: Move your car clockwise to the next node;
6: Check if it is the start node;
7: If it isn’t, go to 2, else STOP;

Happy Reading!!

No comments: