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(n²) 
insertion sort,---  O(n²) 
 selection sort---  O(n²) 

Linear search ---  O(n)

Binary search ---  O(log₂N)

Matrix Multiplication -  O(n³)

Find min/max among N numbers-  Q(N)

Quick sort ---  O(Nlog₂N)

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 

http://kpotential.academy

Oral questions for Programming Lab(C Language)

Dear Folkz ! Here is a List of question and answers for your oral exams...
1. What is programming?
Ans: It is writing a set of instructions to computer to perform a particular task automatically which is being done manually.

2. Why C is called powerful language ?
Ans: It provides an interface to interact with hardware of the system, hence it is best suited for system programming. 

3. How C is different from C++.
Ans: It is a procedure oriented programming language, where emphasis is on actions rather than data, where as C++ is object oriented programming language where emphasis is on data .

4. How many keywords are there in C?
Ans: Standard C language has 32 keywords.

5. What are storage classes in C?
Ans: Storage class represent the kind storage being used for storing data. C has four types storage.
i)Automatic(auto) : life and scope are local to the block{} in which it is created
ii)Static(static) : scope is local but life persists between calls
iii)Register(register) : CPU registers are used, purpose to have faster access
iv)External(extern): scope is Global, and life till end of the program.

6. What is the use of keyword volatile?
Ans: If your program is using any shared variable, if there is chance of getting it modified by some other program/routine, we declare it as volatile. i.e it's value can change without our knowledge.

7. Can you apply modulus operator on floating point variables in C ?
Ans: No, C doesn't allow it.It gives an error for it.

8. What is the output this code snippet?
 main(){ int a=0;
  if(a=5)
 printf("Hello");
else
printf("Hi");
}
Ans: Hello. Bcoz, a=5 is not a relational operator, here 5 is assigned to 'a' which is nonzero, hence true.

9. Why we need functions?
Ans: Functions are subprograms written to perform a particular task, They are basis of modular programming. Dividing a big/complex task into small/simple task.
Primarily It avoid repetition of code and saves memory.

10. Is main a built-in function?
Ans: No, It is a user defined function, as the user specifies what to be done in it's body. Of course the name is given by the language system.

11. What is a Pointer?
Ans: It is a variable, which can store address of another variable. These are used to refer variables using their addresses.
Basically, when we make use of local variables in one function and if their values are getting modified in another function, we need to send addresses of these variables. In such scenarios, we need variable which can hold addresses of other variable. Pointers serve this purpose.

12. What is static allocation of memory ?
Ans: It is allocating memory at the time of compile. Hence the size must be known in advance.
Ex: Array uses static allocation.

13. What is dynamic memory allocation?
Ans: It allocates memory at run time, Here we need know the size before run time. The advantage of this type is that, neither we fall short nor waste.
C provide malloac() and calloc()
malloc() can be used allocate single block of memory, where as calloc() can be used allocate contiguous multiple blocks.

14. What is sizeof operator?
Ans: If the no of bytes of a primitive(like int, float..) or user defined data type(stucture) is not known , we can use this to find it.

15. What is the difference between union and structure?
Ans: Structure allocates memory for all of it's elements where as union allocates memory to single variable of its member, which has largest size.

16. What is a function pointer?
Ans: Basically it is a pointer which can store address of some function. We can call the function using it's address.
An example to demonstrate function pointer.

void disp(int);
main()
{
 void (*fp)(int);
 fp=disp;
 fp(5);

}
void disp(int x)
{
 printf("%d",x);
}

17. Why me need explicit typecasting in malloc()?
Ans: By default malloc return address of type void( some compilers return char*), So a void pointer can not be assigned to the other type, so we need to explicitly convert it to the type of left side pointer.

Ex: int *p;
p=(int*) malloc(10);

18. What are the segments of memory?
Ans: Stack: All local variable reside here.
         Heap: memory for run-time allocation comes from here
         Code(Text): program resides here
         Extra: global variable are stored here.
19. What is a dangling pointer?
Ans: If any pointer represent an address which is no more reachable, then it is called dangling pointer.
Ex;
  main()
 {
   int * p;
   p=init();
   printf("%d",*p);
}
 int* init()
{
  int x=5;
  return(&x);
}
Here 'x' is local, when the control exits init, x will be destroyed, but p is still representing an address which is no more valid(unreachable);

20. What is memory leakage ?
Ans: When we allocate memory at run time , it comes from Heap segment, The characteristic of heap memory is that, it must be deallocated by programmer, when it's job is over, If programmer forgets to free it, and comes out of the program, This memory will be held occupied by the system, Though we have finished our task. This creates a hole in memory, leads to memory segmentation issue and thus memory leakage.

Ex;
 main()
{
 int * p;
 p=init();
printf("%d",*p);
}

int* init()
{
 int * q;
q=(int*)malloc(sizeof(int));
return(q);
}

Here the programmer has forgotten to free the memory , once the job is over. i.e he should have given a free() statement in main()
The  correct version of main() would be

main(){
 int * p;
 p=init();
printf("%d",*p);
free(p);
}


Did you find this article useful ? Please comment...
More more such stuff and FREE online courses visit 

www.kpotential.academy

Answers to Java based questions posted...

Q1: Can modulus operation be applied on real numbers in Java?

Ans: Yes, We can use it.  Actually we do not use it for real numbers in  C/C++ languages. But Java allows to use it for real numbers.

Ex: double x=5.123456 , y=2, z;

      z=x%y;

     Here we get z as 1.123456. As it returns remainder, when x is divided by y.

Q2: What error is flagged , when a final variable is tried to modify?

Ans: The error is : " final variable can not be assigned a (new)value", as it is been declared as a constant.        If it were a C/C++ program the error flagged would be " Lvalue required error"(for more info read my post on it), bit difficult to understand the meaning. But Java message for it is simple, we can make out what is going wrong. This is the one reason of Java being SIMPLE.

Q3: Can we use float x=1.234567 ; in Java ?

Ans: No. It flags an error "Loss of precision". Java treats by default real number as of double data type.

We know the size of float is 4 bytes and size of double is 8 bytes. Here float is destination type(left side of assignment) and the real number(literal constant 1.234567)  which is by default of type double, is source.

To take place an implicit conversion the criteria is that, the destination type must be larger or equal to the source type. Here the case is reversed. So the compiler fails to perform implicit conversion and alerts the programmer about losing of data by flagging a message " Loss of precision".

Then how to initialize floating point literals in Java? for this we need to append letter ' f ' to the literal.

float x=1.234567f ; // Now it is correct

Q4: When to declare data/method as static ?

Ans: Since, in Java everything is done inside a class, we must have an object to access the data/methods.

What if we do not have an object in our hand? or else if some data/behavior is not object specific.

For such scenarios  Java provide keyword static. Anything which is not object specific, but common to the entire class  of objects, we can use static. Hence it is accessed with class name not with object/reference.

For example and  detailed discussion on it read my post here..

Q5: Can instance variables be accessed directly from static context without using object/reference?

Ans: No. Since the context is static, we invoke with help of class name. Hence no implicit object is available for this context. So explicit use of object name/reference is must.

For example and detailed discussion read my post here...

Q6: Can constructor be defined with private scope?

Ans: Yes. But usually when we define a class, our requirement would be to create objects of it somewhere outside the class/package. In such scenarios a constructor defined with private scope creates an issue of accessibility. When object is created using keyword new, a constructor gets called. If it is private, then from outside class, you can not invoke it. 

private constructor is useful as long as you restrict object creation inside class.

Q7: Which is the Java equivalent of destructor of C++?

Ans: We know garbage collector is program which performs the job of clean-up of memory. It finds in memory those objects which are no more referred/ or have become unreachable, claims them back. It will not bother, whether the unreachable object has kept opened a file/socket/thread/data base connection etc. This must be addressed by programmer. For this Java provide finalize() method, which the garbage collector calls before taking the unreachable object back to his pocket.

So, For detailed discussion of these topics,subscribe to IT Academy by visiting

www.kpotential.academy 

How did you find the explanation?  please comment ?

Constructors in C++

Constructors in C++ 

Dear Folks.. 

A constructor is a method/member function

which constructs an object. Since an object is user defined variable, there must be some special way to allocate memory for it. This task of allocating, required amount of memory for an object and setting-up it's initial values, is done by this special method/member function.

It is special, as it has method name as class-name for which it is being defined.

The basic characteristics of a constructor are...

• method name same as class-name
• has no return type, not even as void
• called automatically when an object is created
• usually defined with public scope
• can not be defined as virtual for polymorphism

Types of constructors: Broadly we find three types of constructors namely

1. Default Constructor
2. Parameterized Constructor
3. Copy Constructor

Default Constructor: It is responsible for allocating memory for an object which has no parameters. It is characterizied with no arguments in the definition.

If the class has not defined any constructor for it's objects, then the compiler supplies this constructor, hence the name default. Bear in mind, if you define some type of constructor, without defining default constructor, assuming that, the compiler supplies it, this will not work, if you are creating an object without args,some where in the program.In this case, the default constructor must be defined by you.

Parameterized constructor: It is used to create and initialize objects with arguments. Usually it is used to initialize instance variables.

Copy constructor: It is used to copy states of one object into another object which is being created. It performs deep copy(makes a copy of every state).

// An example to demonstrate all these constructors.

class Account

{

  private:   int acc_no;

             double balance;

  public: /* default constructor*/

          Account(){ acc_no = 100; balance = 500;}

          /* parameterized constructor*/

          Account(int n, double x)

          {

            acc_no = n;

            balance=x;

          }

          /* copy constructor*/

          Account(Account & ax)

          {

            ax.acc_no = acc_no;

            ax.balance =  balance;

          }

          void show()

          {

           cout<<" Account No:"<<acc_no<<endl;

           cout<<" Balance :"<<balance<<endl;

          }

};

void main()

{

  Account a1,a2(121,5000),a3(131,7000);

  Account a4(a2);

  a1.show();

  a2.show();

  a3.show();

  a4.show();

}

output:
Account No:100
Balance :500

Account No:121
Balance :5000

Account No:131
Balance :7000

Account No:121
Balance :5000

If find it useful please share it...

What is garbage collection in Java

Dear Folks !

This post has a very interesting topic for discussion, i.e Garbage collection in Java...

We know memory management is a crucial aspect in programming. In programming languages like C/C++, programmer can allocate and de-allocate memory at run-time of the program. 

Perhaps, you are aware, memory for local variable, is cleared by the system automatically, once the variable goes out of scope.(i.e when control exits the block{} in which it is created).But, when memory  is allocated at run-time from Heap section, it must be de-allocated by the programmer itself.

We programmers are human beings, obviously have the tendency of forgetting things. So what happens if we forget to free/de-allocate the memory which we have allocated at run-time, somewhere in the program. This image makes it clear.

Did you get the point ? 

Yes ! You are right ! When the same program is run multiple times, every time memory is allocated but not made free, so this makes the memory full and make it crash !

How good it is ! if some one manages this de-allocation task from our side...

Be happy ! Garbage Collector is there for you ! Let's see how it does !

Garbage collector is program(thread),running in the background, to find or locate unreachable objects in heap. An object is said be unreachable if it has no reference in stack to refer it. So any object which is no more referenced, is claimed back by the garbage collector. Thus making the memory free for reuse.

Before,claiming the memory back, the garbage collector calls finalize() method to relinquish any resource held by the object(like file,socket etc).

Let me demonstrate it with this example...

class A

{ --------- }

class DemoGC

{

 public static void main(String arg[])

{

 A a1 = new A();

 A a2 = new A();

 A a3 = new A();

-----

----- 

A a4,a5,a6;

a4 = new A();

a5 = new A();

a6 = new A();

-----

-----

a1 = a4; 

/* here the address of a4 overwrites address of a1-- This is how, a1 becomes unreachable */

a2 = a5; 

/* here the address of a5 overwrites address of a2-- This is how, a2 becomes unreachable */

a3 = a6; 

/* here the address of a6 overwrites address of a3-- This is how, a3 becomes unreachable */

----

}

This could be well understood with help of this image...

This is how garbage collector manages the de-allocation of memory. It could be called explicitly by calling  method java.lang.System.gc().

Did you like it ? Please reply/comment/suggest...

Let's share it to grow and to grow to share !

What is this pointer/reference in C++/Java?

Let's explore it !

Let's understand it, through an example, Look at this example. 

Here the method returns the account corresponding to maximum balance. 

                               

So it clear from this example that, the method find() is returning an object corresponding to maximum balance.Two objects are passed to it, one is coming as a parameter and the other is made available to the method implicitly, as find() is invoked with it. Here the explicit object which is coming as parameter is 'a2' , copied in a local object 'ax' and with 'a1' the find method is invoked, hence it is available to the method implicitly.

As 'a1' represents implicit object, it's address is stored in a system pointer called 'this' pointer. To get this object we need to apply ' value at address operator'(*). as show in this slide.

How did you find this post.. Please reply...

What is polymorphism in C++/Java?

Dear Folks !

Polymorphism is an  important feature of object oriented programming paradigm. This makes the language dynamic.(due to this, easy up-gradation/extensibility of  software is possible).

The literal meaning is many forms, i.e one name - many forms. In programming context, it is one method/object with different behaviors under different contexts. In our day-to-day activities we often demonstrate this feature. This image would make us realize it.

Polymorphism can be implemented at compile-time  and run-time of the program. It basically depends on binding(or linking) time of a method call to method definition.

If the information, to bind a call to it's definition is available at compile-time of the program,then we can implement compile-time polymorphism.(static polymorphism).

In C++/Java we implement it, by function/method overloading. For overloading, the condition is that, the methods must have same method name, but vary at least with regard to any one criterion listed below...

 (i) Number of arguments

 (ii) Type of arguments

If we can create a mismatch among the methods being overloaded,  using these two parameters, then, the compiler can uses this, to discriminate the calls and accordingly bind the call to definitions at compile-time. 

Note: The return-type information is useless in overloading, hence bears no significance w.r.t compile-time polymorphism.

/* Let's demonstrate it in C++ */

float compuTax(float gross_sal)

{

 return 20*gross_sal/100;

}

float compuTax(float gross_sal, float bonus)

{

 return (20*gross_sal/100) + (30*bonus/100) ;

}

void main()

{

 -----

 -----

tax1=compuTax(650000);

tax2=compuTax(700000,299999);

-----

}

Notice here, the return type for both methods is same, still overloading  is possible. The mismatch is been created using argument numbers.
Let's check , how it works...

In C++, operator overloading uses compile-time polymorphism.

Now, Let's explore run-time polymorphism...

We know, if the mismatch is not created either in terms of number of arguments or type of arguments, then method overloading is not possible, as the compiler fall short of information to link the calls, to their respective definitions.In such scenarios since the compiler has no information, it postpones the job of binding till run-time of the program. At run-time, the system will link the method calls to the respective definitions, based on the information made available to  it during run-time.Hence it is called dynamic ploymorphism.
In C++ it is implemented using virtual functions, and in Java, it is implemented using dynamic dispatch of methods.
Let's see how it's implemeted in Java...

class Employee // super class
{
 protected double sal;
 void init(double x) { sal=x;}
 double compuTax(){ return 0.2*sal; }
}

class Manager extends Employee
{
 protected double bonus;
 void setBonus(double x){ bonus=x;}
 double compuTax(){return 0.2*sal + 0.3* bonus ;}
}
class DemoPoly
{
 public static void main(String args[])
 {
   Employee empref;
   Employee tom = new Employee();
   tom.init(50000);

   Manager jerry=new Manager();
   jerry.init(70000);
   jerry.setBonus(10000); 
   double tom_tax, jerry_tax;
  
   empref=tom;
   tom_tax= empref.compuTax();
   empref=jerry;
   jerry_tax=empref.compuTax();
   
   System.out.println("Tom has to pay a tax of "+tom_tax);
 System.out.println("Jerry has to pay a tax of "+jerry_tax);
 } // end of main method
}

Output
Tom has to pay a tax of 10000
Jerry has to pay a tax of 17000
You can notice here that the calls(in red) have same signature, i.e same argument type and number, as compiler is not able to bind, it postpones till run-time. The run-time system, checks what is being represented at this instant,by superclass (empref) reference, and then accordingly links and calls the method of that class/object.
If the superclass reference is representing employee, compuTax() of Employee is called, if it is representing manager, compuTax() of manager is called and so on...
You would appreciate this feature, after going through the following scenario.

Say, you want to add one more new class to your existing system, let's say class Supervisor, you will do it like this...

class Supervisor extends Employee
{
 protected double overtime_package;
 void setpackage(double x){ overtime_package=x;}
 double compuTax(){ return 0.2*sal + 0.15* overtime_package ;}
}

class DemoPoly
{
 public static void main(String args[])
 {
   Employee empref;
   Employee tom = new Employee();
   tom.init(50000);

   Manager jerry=new Manager();
   jerry.init(70000);
   jerry.setBonus(10000); 
   double tom_tax, jerry_tax,peter_tax;
  
   empref=tom;
   tom_tax= empref.compuTax();
   empref=jerry;
   jerry_tax=empref.compuTax();
   
   Supervisor peter=new Supervisor()
   empref=peter;
   peter_tax= empref.compuTax();
   System.out.println("Tom has to pay a tax of "+tom_tax);
   System.out.println("Jerry has to pay a tax of "+jerry_tax);
   System.out.println("Peter has to pay a tax of "+peter_tax);

 } // end of main method
}

This is how due to dynamic polymorphism, easy up-gradation or extensibility of software is possible. This is how we make the old code use new code, with little changes or no changes in existing code ...

How do you justify that, birds in this image are demonstrating polymorphic behavior !!!

Did you find this article worth reading  ?  please comment...
Let's share to grow and grow to share...