Stack using arrays

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<limits.h>

struct Stack {
    int top;
    unsigned int capacity;
    int* array;

};

//function to create a stack  , initialising with capacity as zero

struct Stack* createStack(unsigned int cap)
{
    struct Stack* newStack = (struct Stack*) malloc(sizeof(struct Stack));

    newStack->top = -1;
    newStack->capacity = cap;
    newStack->array = (int*)malloc(sizeof(int)* newStack->capacity);
    return  newStack;
}


int isFullStack(struct Stack* stack)
{
    return stack->top == stack->capacity - 1;
}

int isEmptyStack(struct Stack* stack)
{
    return stack->top ==  - 1;
}

void push(struct Stack* stack , int item )
{
    if (isFullStack(stack) == 1)
    {
        printf("Stackoverflow");
        return;
    }

    stack->array[++stack->top] = item;
    printf("Pushed on stack %d \n ", item);

}

int pop(struct Stack* stack)
{
    if (isEmptyStack(stack) == 1)
    {
        printf("Stack Underflow");
        return INT_MIN;
    }

    printf("Popped %d\n", stack->array[stack->top]);
    return stack->array[stack->top--] ;

}

void peek(struct Stack* stack)
{
    if (isEmptyStack(stack))
    {
        printf("Empty stack \n");
        return;
    }
    printf("%d\n" , stack->array[stack->top]);
    ;
}

int main()
{
    struct Stack* stack = createStack(100);
    push(stack , 1 );
    push(stack, 2);
    push(stack, 3);

    pop(stack);
    peek(stack);

    pop(stack);
    pop(stack);
    peek(stack);
    push(stack, 1);
    peek(stack);

    getchar();
    return 0;

       




}

Finding comman characters between two strings aka String intersection

<?php

    /**
    * function to find comman alphabets in two string
    * @params $strOne and $strTwo , two strings to compare
    *
    * @return $comman string consisting a string of comman  characetrs
    */
    function commanAlphabets($strOne , $strTwo)
    {
   
        echo  " String to comapre  :  $strOne with $strTwo " ;
       
        //convert to arrays
        $charArrayOne = str_split($strOne);
        $charArrayTwo = str_split($strTwo);
       
        //implode to find intersections
        $comman =  array_unique (array_intersect($charArrayOne , $charArrayTwo));
       
        return $comman;
    }
   
   
    $result = commanAlphabets("AMITABH BACHCHAN" , "RAJNIKANT");
   
   
        echo "<br> Comman characters are as follows : <br> ";
        //print string of comman characters
        echo implode($result);
   
?>

Finding comman characters in a given string

<?php
    //given string
    $str  = "JIMMY AND JOLLY";
    echo  "Given String :  $str <br>" ;
   
    //convert to character array
    $charArray = str_split($str);
   
    //$result["charBooleans"] = array_fill(0, 25, 0);
    $result["charBooleans"] = new SplFixedArray(26);
   
   
    for( $i = 0 , $len =  count($charArray)    ; $i < $len ; ++$i  )
    {
       
        if($charArray[$i] == ' ')
            continue;
       
        for( $j = $i + 1   ; $j < $len  ; ++$j  )
        {
           
            //check if characters are same
                if( $charArray[$i] == $charArray[$j] &&  $charArray[$i] != ' ' && $result["charBooleans"][$i] != 1 )
            {
                //ord() converts char to ASCII value
                $num =   ord($charArray[$i]) - 65;
                 //echo "num :  $num and char  $charArray[$i]: <br>";
                $result["charBooleans"][$num] = 1;
                //the character exist in string hence break from inner loop
                break;
            }
           
        }
    }
   
    for( $i = 0 , $len = count($result["charBooleans"])   ; $i < $len ; ++$i  )
    {
        if($result["charBooleans"][$i] == 1)
        {
            echo chr(65 + $i) ;
            echo "<br>";
        }
    }   
?>

Check if a string is a rotation of other given String

In a rotation we cut a string at a rotation point such that on rotation eg -
jimmy <=> myjim
So ,
s1 = "jimmy" = x + y where y = "my" and x = "jim" 
s2 = "myjim" = y + x
So if a rotated string  "myjim" has to be a rotation of "jimmy" then it should be a substring of  - xyxy = "jimmyjimmy" = s1s1

So checking if a string "myjim" is a substring of a String xyxy = "jimmyjimmy" will prove that it is an rotation of String xy = "jimmy"
 



public  isRot(String s1 , String s2)
{
    int len =  s1.length();
    // if both  strings are of same length and not empty
    if(len == s2.length() && len >= 0  )
    {
        // concatanate string s1 within new buffer
        String s1s1 = s1+s1;
        return isSubString(s1s1 , s2);
    }
    return false;
   
}


public static boolean isSubString(String big , String small)
{
    if(big.indexOf(small) >= 0)
        return ture ;
    else
        return false;
}

Check if two strings are permuatations of eachother

public static boolean permutation (String s, String t)
{
    //  check if they are of same lenght
    if( s.lenght() != t.length() )
    {
        return false;
    }
   
    int letters [] = new int[128] ; // for ASCII strings
   
    char[] s_array = s.toCharArray();
   
    for( char c : s_array)// count number of each character in s
    letters[c]++;
   
    for( int i = 0 ; i < t.length() ; ++i)
    {
        int c = (int) t.charAt(i);
        if(--letters[c] < 0 )
        return false
    }
    return true;
}

Reverse a String

void reverse(char* str)
{
    char* end = str;
   
    char tmp;
   
    if(str)
    {
        //find the end of the string
        while(end) ++end;
   
        --end; // since the last character is the null character
   
        //swap the elements starting from start and end till pointers meet in middle at same address
        while(str < end )
        {
            tmp = *str;
            *str++ = *end ;
            *end-- = tmp;
   
        }
    }
}

Check if a String is made up of unique characters

//only for lower case letters between a-z , bit vector method
    public static boolean isUniqueChars(String str)
   
    {
        int length =  str.length();
       
        //for ASCII string
        if(length > 128)
        {
            return false;
        }
       
        int checker = 0 ; // bit vector
       
        for(int i = 0 ; i < length ; ++i)
        {
            int val = str.charAt(i) - 'a';
            if( ( checker & ( 1 << val ) ) > 0 ) return false ; // check if the character's bit position in bit vector is already 'on'
            checker |= ( 1 << val ); // turn the bit on for character's position
        }
       
        return  true ;
       
    }
   

Arrays and String - Comman Techniques

HashTables -
    Data Structures mapping keys to the values for highly efficient lookup.
   
    2 parts - An underlying array
              A hash()
    A hash() maps keys to an integer , which indicates index in the array . The object is stored at that index.
   
    Trivial Style  -
        Create an array equal to the size of all possible key such that object allocation takes on index generated by hash(key)

    Pitfalls -
        Requires unique hash values for all keys to prevent overwrite
        To prevent "collisions" arrays need to be extremely large
   
    Optimal Solutions -
        Linked List -
                 Store objects in a linked list at index generated by  (  hash(key) % array_length  ) .
                 To get object at a particular key , we must search linked list at that index for this key
        BST -
                 Guarrantees O( log n ) lookup time , since we can keep a tree balanced .
                 Additionally we may use less space , since a large array no needs to be allocated in the very beginning.
                 Creating a BST at each bucket of ours HashMap ,instead of linked lists for degenerate hash(key) % array_length values , can bring
                 down total complexity  -
                Using LinkedList -  O(1) + O(n) - to search in the linked list
                Using BST -  O(1) + O(log n)
       
example  -
            public HashMap< Integer , Student > buildMap( Student[] students )
            {
                HashMap<Integer , Student> map =  new HashMap<Integer , Student>();
                for(Student s : students) map.append(s.getId() , s );
                return map;
            }
               

ArrayList -
            A dynamically resizing array , resizing when needed and still providing O(1) access .
            The array doubles in size , when it is full  taking O(n) time which is so rare such that amortized time is still O(1)
           
        eg. -
        public ArrayList<String> merge ( String[] words , String[] more )
        {
            ArrayList<String> sentence = new ArrayList<String>();
            for(String s : words) sentence.add(s);
            for(String s : words) sentence.add(s);
            return sentence;
        }
   
   
StringBuffer -

    A trivial style of concatanating the string is as follows , what would be its running time
    assuming all strings in array are of length x and there are n strings  -
    public String joinWords(String words[])
    {
        String sentence = "";
        for(String w : words)
        {
            sentence = sentence + words ;
        }
        return sentence;
    }
   
    On each concatanation a new copy of the string is created and two strings are copied character by character.
    First iteration -  x characters copied
    Second iteration - 2x characters copied
    .....
    ........
    ..........
    Total copying instances (assighnments) = x ( 1 + 2 + 3.. n ) = x * ( n*(n+1)/2 ) = O(x * n^2)
   
While StringBuffer can avaoid this problem as it simply creates an array of all the strings , copying them back to a string only when necessary

        public String joinWords(String words[])
    {
        StringBuffer sentence = "";
        for(String w : words)
        {
            sentence.append(w);
        }
        return sentence.toString();
    }