Find the type of array

Given an array, it can be of 4 types
(a) Ascending
(b) Descending
(c) Ascending Rotated
(d) Descending Rotated
Find out which kind of array it is and return the maximum of that array.

// C++ program to find type of array, ascending
// descending, clockwise rotated or anti-clockwise
// rotated.
#include<bits/stdc++.h>
using namespace std;

// Function to find the type of an array
// and maximum element in it.
void findType( int arr[] , int n)
{

    // boolean variables to check if array is increasing or decreasing
    bool isIncreasing = false , isDecreasing = false;
for( int i = 1 ; i < n ; ++i){
   
   // increasing value found
   if(arr[i-1] < arr[i]){
       isIncreasing = true;
       // if the array was decreasing earlier then its Descending Ascending and maximum is current element
       // example :  2 1 5 4 3 
       if(isDecreasing){
           cout << "Descending rotated Max : " << arr[i] << "\n";
           return;
       }
   }
    // decreasing value found
   else if (arr[i-1] > arr[i]){
       isDecreasing = true;
        // if the array was increasing earlier then its Ascending Descending and maximum is i-1 element
        // eg 4 5 1 2 3
       if(isIncreasing){
           cout << "Ascending rotated Max : " << arr[i-1] << "\n";
           return;
       }
       
   }
   
}

// else array is purely ascending or descending
if(isIncreasing)
    cout << "Ascending  Max : " << arr[n-1] << "\n";
else
   cout <<"Descedning Max : " << arr[0] << "\n";

}

// Driver code
int main()
{
int arr1[] = { 4, 5, 6, 1, 2, 3}; // Ascending rotated
int n = sizeof (arr1) / sizeof (arr1[0]);
findType(arr1, n);

int arr2[] = { 2, 1, 7, 5, 4, 3}; // Descending rotated
n = sizeof(arr2) / sizeof (arr2[0]);
findType(arr2, n);

int arr3[] = { 1, 2, 3, 4, 5, 8}; // Ascending
n = sizeof(arr3) / sizeof (arr3[0]);
findType(arr3, n);

int arr4[] = { 9, 5, 4, 3, 2, 1}; // Descending
n = sizeof(arr4) / sizeof (arr4[0]);
findType(arr4, n);

return 0;
}

Stack | Get Minimum or Maximum Element in O(1) from Stack

The easiest way to achieve this is to create an auxiliary stack and keep pushing minimum ( maximum ) element in it . And to maintain consistency while popping , pop from when auxiliary stack when top elements in both stacks are equal.


Pseudocode :

Stack myStack = new Stack();
Stack maxStack = new Stack ();

void push(int data )
{
    if ( maxStack.isEmpty() || maxStack.peek() < data)
                  maxStack().push(data);

   myStack.push(data);

}

int pop ()
{
          int num = myStack.pop();
        if( ! maxStack.isEmpty() && maxStack.peek() == num )
                      return maxStack.pop();
        return num;
}

What is more important than Performance of code ?

Well you might be amazed , if you are new to industry , that there are actually many factors which have more priority over performance.You should truely consider these aspects before you starts writing yours best efficinent code.

The main domains which have more weight then performance can be as follows in the present context :

Understandability : Writing a very efficient code but its too obfuscated to understand is not a good idea for future reference and documentation.Your next version may be in doom.

Design : Scalability is adhered to proper design , which can be OOPs or Coupling in a MVC frameworks .

Stability : Benchmarking REST APIs and bandwidth can give a detailed idea about performance vs stability .

Security  : As reserachers quotes , this is rising issues since 2000 . User security and privacy is always given top priority against performance .

Features : Living in 2016 , features can save someones life , get you out of emergency or gives you best utility features.

User friendliness : This issue was the most hunting aspect in 90s . Presently you can easily understand the difference between Windows, Macintosh or iOS and Android . This is the most weighted factor when it comes to performance consideration.

Reverse a Linked List Iterative Solution

In Iterative solution for reversing a Linked List  the core idea is as follows :

change link pointers :

next of current to previous
previous to current
current to next of current

Try imagining flow drawing 4 nodes and applying logic from code

Plus in the end  , since ours whole linked list links has been reversed and previous pointer points to last node of actual list given in start,
ours previous pointer holds the new head of reversed list


Node* Reverse(Node *head)
{
  if(head == NULL)
      return head;
   
  Node *prev = NULL  , *temp , *curr = head;
   
    while(curr != NULL)
        {
        temp = curr->next;
        curr->next = prev;
        prev  = curr;
        curr = temp;
    }
   
    head = prev;
    return head;
}

Linked List | Swapping Nodes without swapping data

Node* swapNode(Node* head  , int x  , int y )
{

    if(x == y)
        return ;
       
    Node* prevX = NULL  , *currX  = head, *currY = head , *prevY = NULL  ;
   
    //find xth and yth node
    for(int i = 0 ; i < x ; ++i)
    {
        prevX = currX ;
        currX = currX->next;
    }
    for(int i = 0 ; i < y ; ++i)
    {
        prevY = currY ;
        currY = currY->next;
    }
   
   
    if( currX == NULL || currY == NULL )
        reutrn;
       
       
    //doesnt matter x is smaller or bigger then y
   
        //change head ptr
    if(prevX != NULL )
        prevX -> next = currY;
    else
        head = currY;
       
    if(prevY != NULL )   
        prevY ->next = currX;
    else
        head = currX;
       
   
    //swap next pointers
    Node* temp = currX->next;
    currX->next = currY->next;
    currY->next = temp;
   
    return head;
   
}

LinkedList : Messing with head pointer

During my recent course of practice with LinkedList , i experienced many problems are related to keeping track of right Head pointer of the list . Whether its a Swapping Nodes without swapping data or simple insertion and deletion of nodes.

Pointer :  When dealing with Swapping Nodes , Insertion and Deletion at head , if the pointer to previous Node is NULL  , then it means First Node is  under consideration


This is how I approach :

Node* prevNode = NULL ; 
Node* ptr = head;

for(int i = 0 ; i < position ; ++ i
{
      prevNode = ptr;
      ptr = ptr->next;
}


if( prevNode == NULL )
{
     //  manipulate head pointer here
}

Checkout Swapping Nodes without swapping data for a real life problem

Threaded Binary Tree

Threaded binary tree saves stack recursion space used for traversing a tree , by making traversal iterative istead of recursive.
    The right most null node is made to be ponted to its inorder successor while tree formation .
    So space complexity becomes O(1) from O(N)



#include<cstdio.h>
#include<iostream>


//structure of a node in a threded binary tree
struct treeNode{
    int data;
    struct treeNode* right;
    struct treeNode* left;
    bool isRightHanded;
       
};

struct treeNode* leftMost(struct  treeNode* curr)
{
    if (curr == NULL)
        return NULL;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;

}



void traverseThrededTree(struct treeNode* root)
{
    if (root == NULL)
    {
        printf("Empty tree");
        return ;
    }

    struct treeNode* cur = leftMost(root);

    while (cur != NULL)
    {
        printf("%d", cur->data);

        //if node is right handed , go to next node
        if (cur->isRightHanded)
        {
            cur = cur->right;
        }
        else // else go to next leftmost node of the right node , if it exist
        {
            cur = leftMost(cur->right);
        }
    }




}

Find size of a binary tree

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


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int sizeOfTree(struct treeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }

    return sizeOfTree(root->left) + 1 + sizeOfTree(root->right);
}

int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Size of the tree is %d", sizeOfTree(root));
    getchar();
    return 0;
}

Print all paths from root to leaf node in a binary tree

Maintain an array path[] having node's data on each level , and the length of path[] , on every  new level oush the node's data to path[] and increment path len.
If we are at the leaf node ,  print the path[] , or try recursing to left and right child 

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen);

void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}
void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void printPaths(struct node* node)
{
    int path[1000];
    printPathsRecur(node, path, 0);
}

void printPathsRecur(struct treeNode* node, int pat[], int pathlen)
{
    if (node == NULL)
    {
        return;
    }
   
    //add the node to path at this level
    pat[pathlen] = node -> data;
    //increment path len
    ++pathlen;

    //if its a leaf node , print the path
    if (node->right == NULL && node->left == NULL)
    {
        printArray(pat, pathlen);
    }
    else
    {
        //try bith subtree
        printPathsRecur(node->left, pat, pathlen);
        printPathsRecur(node->right, pat, pathlen);
    }
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print all root-to-leaf paths of the input tree */
    printPaths(root);

    getchar();
    return 0;
   
}

Mirror a Binary tree

Mirror a binary tree works by recursing in post order , and then swapping left and right pointers of the node

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void mirror(struct treeNode* node)
{
    if (node == NULL)
        return;
    //go to left node
    mirror(node->left);
    mirror(node->right);

    //swap left and right node child pointers
    struct treeNode* temp = node->left;
    node->left = node->right;
    node -> right = temp;


}

void inOrder(struct treeNode* node)
{
    if (node == NULL)
        return;

    inOrder(node->left);
    printf("%d ", node->data);

    inOrder(node->right);
}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    /* Print inorder traversal of the input tree */
    printf("\n Inorder traversal of the constructed tree is \n");
    inOrder(root);

    /* Convert tree to its mirror */
    mirror(root);

    /* Print inorder traversal of the mirror tree */
    printf("\n Inorder traversal of the mirror tree is \n");
    inOrder(root);

    getchar();
    return 0;
   
}

Find Height of a Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int maxDepth(struct treeNode* root)
{
    if (root == NULL)
        return 0;
    else
           
    {   

        return ( max(maxDepth( root->left) , maxDepth(root->right) ) + 1 );
    }
}

int main()
{
    struct treeNode *root = newNode(1);

    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Hight of tree is %d", maxDepth(root));

    getchar();
    return 0;
   
}

Diameter of Binary Tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}


void printArray(int ints[], int len)
{
    int i;
    for (i = 0; i<len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}

int maximum(int a, int b)
{
    return a>=b?a : b;
}

int height(struct treeNode* root)
{
    if (root == 0)
    {
        return 0;
    }

    int h = 1 + maximum(height(root->left) , height(root->right));
    return h;
}

/*
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1
*/

int diameter(struct treeNode* root)
{
    if (root == 0)
        return 0;
    int rHeight = height(root->right);
    int lHeight = height(root->left);

    int lDiameter = diameter(root->left);
    int rDiameter = diameter(root->right);

    return maximum(1 + rHeight + lHeight, maximum(lDiameter, rDiameter));

}




int main()
{
    /* Constructed binary tree is
    1
    /   \
    2      3
    /  \
    4     5
    */
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Diameter of the given binary tree is %d\n", diameter(root));

    getchar();
    return 0;
}

Delete a Binary Tree

Using postorder traversal , delete tree , as we should delete child nodes first instead of parent node for straight tree deletion
#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};   


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

void deleteTree(struct treeNode* node)
{
    if (node == NULL)
    {
        return;
    }

    deleteTree(node->left);
    deleteTree(node->right);
    free(node);

}
int main()
{
    struct treeNode *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    deleteTree(root);
    root = NULL;

    printf("\n Tree deleted ");

    getchar();
    return 0;
   
}

Check If Both Binary Trees Are Identical

Complexity O(m) where m is size of tree with nodes m <=n , where n is size of other tree

#include<stdio.h>


#include<stdlib.h>


struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;

};


struct treeNode* newNode(int n)
{
    struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
    node->data = n;
    node->left = NULL;
    node->right = NULL;
    return  node;

}

int isIdentical(struct treeNode* A, struct treeNode* B)
{
    //if both are empty , return 1
    if (A == NULL  && B == NULL)
    {
        return 1;
           
    }

    if(A != NULL && B != NULL)
    {
        //check if the data at root or root of subtree (while recursion) , and left and right subtree are equal
        //by recursing to left and right subtree
        return A->data == B->data && isIdentical(A->left, B->left) && isIdentical(A->right, B->right);
    }
    //else both trees are not identical ,one empty and other is not ,  return 0
    else return 0;
}

int main()
{
    struct treeNode *root1 = newNode(1);
    struct treeNode *root2 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);

    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);

    if (isIdentical(root1, root2))
        printf("Both tree are identical.");
    else
        printf("Trees are not identical.");

    getchar();
    return 0;
}

Swap nibbles of a given number

#define swapNibble(num)   (( num & 0xF ) << 4 )  |  ( ( num 7 0xF0 ) >> 4 )

( num & 0xF ) << 4 ) : This grabs first nibble of nummber  and left shifts the nibble  to 4 places

( num 7 0xF0 ) >> 4 ) : And this grabs the next nibble of the number and right shifts the nibble  to 4 places

Finally we use bitwise OR  swap is completed

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;

       




}

Stack with Linked List

//STACK WITH linked list

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

struct StackNode {
    int data;
    struct StackNode* next;
};

struct StackNode* newNode(int data)
{
    struct StackNode* node = (struct StackNode*) malloc(sizeof(struct StackNode));
    node->data = data;
    return node;

}

int isEmpty(struct StackNode* root)
{
    return !root;
}

void push(struct StackNode** root, int item)
{
    struct StackNode* node = newNode(item);
    node->next = *root;

    *root = node;
    printf("pushed %d \n", item);

}

void pop(struct StackNode** root)
{
    if (isEmpty(*root))
    {
        printf("Underflow \n");
        return;
    }
    int poped = (*root)->data;
    struct StackNode* temp = *root;
    *root = (*root)->next;
    free(temp);

    printf("popped %d\n", poped);

}

void peek(struct StackNode* root)
{
    if (isEmpty(root))
    {
        printf("empty stack \n");
        return;
    }
    printf("peeked %d \n" , root->data);

}


int main()
{
    struct StackNode* stackRoot = NULL;
    push(&stackRoot, 4);
    push(&stackRoot, 6);

    pop(&stackRoot);

    peek(stackRoot);

    pop(&stackRoot);
    peek(stackRoot);
    push(&stackRoot, 6);
    peek(stackRoot);

    getchar();
    return 0;


}

Tid Bits - Stack :

Stack can be FILO - First in last out or LIFO - First in last out .
Underflow condition - When a pop operation  is performed on an empty stack
Peek Operation   : get the topmost item
Stack can be implemented using an array or a Linked List
Basic ADT : Using arrays :
            struct Stack {
                int top  ;
                unsigned int capacity ;
                int* array ;
              }
             
              Disadvantages using array :
             
              No dynamic size
              Doesnt grow or shrink using depending on needs at runtime
             
              Using Linked List :
              struct StackNode {
                int data ;
                struct StackNode* next ;
              }
             
 Balancing of symbols:
Infix to Postfix/Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals.
Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver.



We need postfix notations because compiler scans the expressions from left to right or from right to left
Consider the below expression: a op1 b op2 c op3 d
If op1 = +, op2 = *, op3 = +

The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.


The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are not required in postfix.

Efficiency of Short Hand Notation

Why x += 1 ; is more efficient than x = x+1 ?

It is related to how assembler references the memory location accesss .
The ALU uses registers for referencing values and accumulator for storing partial results .
 So , for case 1 : 
  x =  x + 1 ;
 
  MOV A , (x) ;  // Move the value at memory location x in accumultor A  . The value of x is stored in register
  ADD A , 1  ; // ADD 1 IN ACCUMULATor
  MOV (X) ,  A ; // Move the value in accumulator at memory location referenced by x
 
  for case 2 :
  x += 1
  ADD (x) , 1 ; // Add 1 at memory location referenced by x
 
  So , so coz of efficient dereferncing and no partial result generation  , short hand artihmatic noations are efficient even though at an abstract view all operations produce same results

Java tid bits :

1 : A class that implpementing an interface becomes an abstract class if it dont implements all the functions declared inside Interface and hence cant be used for instantiating objects

2 : Interfaces having only variables can be used for making set of Global Constants which can be used by other classes , just like constants declared in C header files


3 : Packages help in resuing classes across programmes
4 : Only at runtime, interpreter loads the class used from other package , during compilation , compiler only  checks whther the .class file is present in package imported

5: A java source file can only have one class declared as public because filename should be same as the public class with .java extension . But many non public classes can be defined

6:
Exception class is a subclass of Throwable , hence so do all user defined exceptions

7 : in switch case statements only constant values or literals are allowed
 final String a = "" , b = "fa";
     switch("dgh")
     {
     case "sdg":
         break;
     case a+b :
         break;
     }
    
8:  Runtime : polymorphism (overriding) and Compiletime - Inheritance of methods and attributes by subclasses

9 :  Java's interpreter do thread switching for multi threading
10 : States of a Thread :
New Born State : When an object of a class extending java.lang.Thread is made
Runnable state : on calling start()
Running state : Java runtime schedules thread calling run()