Sunday, August 9, 2020

Free video tutorial for IT courses is been launched!

 Hello Everyone , a new channel for free video tutorials on IT courses is been launched, To get notified for the same, please subscribe here

https://youtu.be/gqEhUSsvVU4

Wednesday, February 5, 2020

Types of variable in Java

Dear Folks !
In this blog I will be discussing different types of variables in Java. Primarily following three types of variables can be defined in Java,
1. Instance Variables
2. Class Variables
3. Local variables

Let's discuss each one in detail. Instance variables are used to represent specific state of an object and normally they are attributes of a class. For each instance separate memory is allocated for them on heap. They are always accessed with an object/instance. As the state for this variable varies object to object, it's also called non-static variable.

An example to demonstrate the use of instance variables.

class Account
{
   int account_number; // An instance variable
   double balance;  // An instance variable
   -----
   ----- }
class Bank
{
  public static void main(String[] args)
 {
    Account a1 = new Account( );
    a1.account_number = 123;  // like this an object is used to access instance variable
    a1.balance = 5000;
    System.out.println("Account Number :"+a1.account_number);
    System.out.println("Balance:"+a1.balance);
 }
}

Now if you want minimum balance as one of the attribute of an Account, the you can define one more variable as min_bal, but what should be the type of variable. If you declare it as instance variable, the it's state/value is stored with every object(waste of memory), as the value will remain common for all, we can store it in single place and access it for all objects of that class. This is done by define it with a qualifier static. As it's state is for entire class, these are called class variables and hence are accessed with class name.

An example to demonstrate the use of class variables.

class Account
{
   int account_number; // instance variable
   double balance; // instance variable
   static double min_bal; // static variable/class variable
   -----
   ----- }
class Bank
{
  public static void main(String[] args)
 {
    Account a1 = new Account( );
    a1.account_number = 123;
    a1.balance = 5000;
    Account.min_bal=1000;  // like this class name is used to access class variable
    System.out.println("Account Number :"+a1.account_number);
    System.out.println("Balance:"+a1.balance);
    System.out.println("Minimum Balance:"+Account.min_bal);
 }
}

When you declare any variable in a method, it's scope will become local and such variables are called local variable. In the above example ' a1 '  is a local variable.  The memory is from stack, hence they are aslo called stack variables.

The default initial values for these variable are as below

Variable type
Default value for primitive type
Default value for reference  type
Instance
Zero
null
Class variable
Zero
null
Local variable
Not initialized to any default value
null

class DemoLocal
{
  public static void main(String args[])
{
 int i;
 System.out.println(++i);

}
}

If you compile this program. it will flag a compile time error like variable 'i' not initialized.


For any queries please write in comment section.

Thursday, January 3, 2019

Stack implementation using linked list representation in C++


Stack is an important data structure, which works on the principle of Last-In-First-Out(LIFO). It is used in memory modules for storing local variables and implementing recursive calls. It is also used in implementing Lexical analyzers(compilers) to check for syntactical errors. Besides this it can be used for inter-conversion of mathematical expressions(in-fix, post-fix and pre-fix notations).
The image shown here represents a Stack of books.[courtesy internet]
 

Stack uses a pointer called Stack pointer, which always points to the top-most item. It uses operations like PUSH and POP, Push stores an item on top of the stack using stack pointer where as Pop removes a top item. When the stack is Empty, It is called stack under flow condition and If the stack is full it is called stack overflow condition.

Here a Linked List is been used to create stack. The start address of the List(head) represents stack pointer. If the head value is NULL, Stack is Empty, and if the dynamically memory-allocating function(here new operator) return NULL, let's consider it as stack overflow condition.


By implementing algorithms for adding a node at front of the list and deleting a front node, push and pop operations are defined, respectively.  The following code snippet illustrates a generic stack implemented using Linked List

template<class T>
class Stack
{
    struct node
    {
        T data;
        node *link;
    };

    node *head;
    public :
    Stack()             // Constructor
    {
        head=NULL;      // Initializing head to NULL Empty Stack
    }

    void push(T x);
    T  pop();
    int isEmpty();
};

template<class T>
void Stack<T> :: push(T x) // Adding a node at front
{
    node *nn;
    nn = new node;
    nn->data = x;
    nn->link = head;
    head = nn;

}
template<class T>
T Stack<T> :: pop()      // Deleting a front node
{
    T x;
    node *temp = head;
    head = head->link;
    x = temp->data;
    delete temp;
    return x;
}
template<class T>
int Stack<T> :: isEmpty()
{
    if(head == NULL)
        return 1;
    else
        return 0;

}


Stay connected ,In the next post , the application of this Stack will be demonstrated for Evaluation of post-fix expression and conversion of infix expression to post-fix expression.
Your inputs are welcome. 

Monday, August 6, 2018





Merge Sort 



 It is one of the stable sort working on Divide and Conquer Principle. Primarily it keeps  dividing the array  into two parts(approximately) recursively till we find the sub arrays with one element each. Then we start merging the sub-arrays having single elements into an array of two and then these will merged into an array four...like wise we continue merging upwards and finally merge them into single array, and find this arrays as a sorted array. The following image illustrates the concept of partitioning and merging. The worst case complexity of this algorithm is  O(nlog2n)

 

 

C program to perform merge sort:

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

void part(int*,int,int);
void merge(int*,int,int,int);

main()
{
 int a[100],i,n;

 printf("Enter no.of elements\n");
 scanf("%d",&n);

 printf("Enter %d items\n",n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);

 part(a,0,n-1);

 for(i=0;i<n;i++)
  printf("%d\n",a[i]);


}
void part(int *a,int l,int h)
{
 int m;
 if(l<h)
 {
  m=(l+h)/2;
  part(a,l,m);
  part(a,m+1,h);
  merge(a,l,m,h);
 }

}

void merge(int *a,int l,int m,int h)
{
 int i,j,k,temp[100];
 i=l;j=m+1;k=l;

 while(i<=m&&j<=h)
 {
  if(a[i]<a[j])
  {
  temp[k]=a[i];
  i++;
  k++;
  }
  else
  {
  temp[k]=a[j];
  j++;
  k++;
  }


 }
 while(i<=m)
 {
  temp[k]=a[i];
  i++;
  k++;
 }
 while(j<=h)
 {
  temp[k]=a[j];
  j++;
  k++;
  }

 for(i=l;i<=h;i++)
 a[i]=temp[i];

}

/* output


Enter no.of elements
5                                                                              
Enter 5 items                                                                  
0                                                                              
3669                                                                           
4                                                                              
52                                                                             
14                                                                             
0                                                                              
4                                                                              
14                                                                             
52                                                                             
3669
*/

                                                                               
 

Thursday, September 21, 2017

C program for Non recursive(also called Bottom - up ) Merge sort.

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

void merge(int*,int,int,int);
int mini(int x,int y);

main()
{
 int a[100],i,n,j;

 printf("Enter no.of elements\n");
 scanf("%d",&n);

 printf("Enter %d items\n",n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);


/********  Non recursive (also called Bottom up) merge sort **********/
  for(i=1;i<n;i=2*i)
   for(j=0;j<n-i;j=j+2*i)
   merge(a,j,j+i-1,mini(j+2*i-1,n-1));

/**********************/


 for(i=0;i<n;i++)
  printf("%d\n",a[i]);


}


int mini(int x,int y)
{
 if(x<y) 
   return x; 
 else 
   return y;
}



void merge(int *a,int l,int m,int h)
{
 int i,j,k,temp[100];
 i=l;j=m+1;k=l;

 while(i<=m&&j<=h)
 {
  if(a[i]<a[j])
  {
  temp[k]=a[i];
  i++;
  k++;
  }
  else
  {
  temp[k]=a[j];
  j++;
  k++;
  }


 }
 while(i<=m)
 {
  temp[k]=a[i];
  i++;
  k++;
 }
 while(j<=h)
 {
  temp[k]=a[j];
  j++;
  k++;
  }

 for(i=l;i<=h;i++)
 a[i]=temp[i];

}

Comparison Merge Sort and Insertion Sort


Sunday, April 17, 2016

Interview/oral questions and answers for Data structures using C++

Q1. What is a data structure?
Ans: It represents a storage in memory. As a subject, it deals with algorithms to store data with required fashion(like Last-In-First-Out or First-In-First-Out) by utilizing optimal(sufficient, neither more nor less, i.e. exact) memory in such a way that it should be retrieved fastly.

Examples:
Simplest: int x; x is an integer data structure
Simple: int a[100]; a is a data structure that stores 100 integers in adjacent memory location.

The examples of important data structures are, stack,queue,linked list, trees , graphs and hash tables.

Q2. What is time complexity and space complexity ?
Ans: Through time complexity one can analyze the running time of an algorithm where as Space complexity indicates the amount memory needed to load the program.

There are three asymptotic notations, used to study an analyze the algorithms.
Big 'O' notation - for specifying upper bound
Theta notation- to specify minimum steps required
 Omega notation - to specify lower bound.

Example:
The complexities of various algorithms..
Bubble sort, ---  O(n2
insertion sort,---  O(n2
 selection sort---  O(n2
Linear search ---  O(n)
Binary search ---  O(log2N)
Matrix Multiplication -  O(n3)
Find min/max among N numbers-  Q(N)
Quick sort ---  O(Nlog2N)
Popping an item from stack-  O(1)
Find maximum/minimum in a BST- O(d)
 where d is depth of tree

Q3. What is Stack and mention some applications of it.
Ans: Stack is a data structure which stores data in Last-In-First-out fashion.
It uses single end called stack pointer for pushing and popping an element from it.
Applications:
i.Used for Lexical analyzer and parser in compiler design
ii.Used to simulate recursive calls
iii.Used to check correctness of expressions(balancing of paranthesis)
iv.Used to convert infix expression to postfix expression.

Q4. What is priority queue? and what are its types?
Ans: It is a queue, where insertion is done in order, but item with certain priority will be removed first.
There are two types,
Ascending Priority queue: In which minimum item is removed first.
Descending Priority queue: In which maximum item is removed first. 

Q5. Which is the data structure used to store hierarchical data/information?
Ans: Trees

Similar way try to Answer following questions:
1. What is height of a tree?
2. What is skewed binary tree?
3. What is minimum spanning tree?
4. What are the graph traversing algorithms?
5. What is the purpose of Dijkstra algo?
6. What are application of queues?
7. Where do you find applications of graphs.
8. What is sequential file ?
9. What is indexed sequential file?
10. What is random access file?
11. Why we need Hash tables? and what are characteristics of a good hasing function?
12.Where do you use Heap data structure?
13. What is the time complexity of Heap sort?
14. What is a threaded binary tree?
15. Where do you find the applications of Expression trees?

OOP and C++ based question:
1. What is the difference between procedure oriented and object oriented programming?
2. What are the features of OOP?
3. What is the purpose of Data abstraction?
4. What we achieve by implementing Data encapsulation?
5. How C++ implements static polymorphism?
6. How C++ implements dynamic polymorphism?
7. What is reference variable in C++?
8. What is the criteria to overload two functions?
9. Why we need  operator overloading in C++?
10. What is the purpose of a namespace?
11. What are templates in C++?
12. What are the different access specifies in C++?
13. Why we need this pointer?
14. What are inline functions?
15. Why we define member functions outside the class using scope resolution operator?
16. What is a constructor? and list it's characteristics.
17. What is a destructor and explain it's purpose
18. What is static and non static data/methods in C++?
19. How C++ allocates memory at run time?
20. What are the different types of inheritances available in C++.

You can find solution for most of the questions in my other posts...

For more such interesting stuff, please subscribe by visiting