1. Why will the code show error when tried to compiled. Below given is a C program snippet to get height of a binary tree.

int height (struct node * root)
{
	if(root=NULL)
	    return 0;
	else
	{
		return max(height(root->left),height(root->right))+1;
	}
}

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

Solution:

Answer 1:
max function should be defined/declared before usage. If not the function, at least it’s prototype.
int max(int a, int b);

Answer 2:
if(root=NULL)
return 0;

This is an assignment operation. What you really want, is this:
if(root == NULL)
return 0;

 

2. What is the difference Between Call by Value and Call by Reference?

Solution: In call by value a copy of variable is made and all the computation is done on the copied variable not affecting the original value .like if we have int x=9 , int y=8; and we want to pass this to add function int add(int u,int v){} …. then the copies of x and y are made into u and v respectively , without affecting the values of x and y.

In contrast in call by reference the actual object is being copied and the computation being done in the method affects the actual object like we have a order object in the example .

Order or = new Order();
or.setName("Adobe");

now we have method pass this order object to a method public int orderSubmission(Order or){} and set the name of order different as Google , Now the original value that was Adobe  gets changed .

 

3. What is virtual function? Give an example scenario of use.

Solution: A virtual function is a member function of a class that can be overridden at run time in a derived class (dynamic rather than static binding). Calling the function via a base-class pointer will result in a call to the derived class version. The reference is resolved at run time, using the virtual function table (vtable), which is just a table of function addresses. The base class function need not even be defined, it can be “pure virtual”, meant to be defined only in derived classes. This of course makes the base class abstract so it cannot be instantiated, only used as a common ancestor for sub classes.

Scenario:It’s important to make base class destructors virtual, so that the in the event your derived-class object is deleted via a base-class pointer, the derived version of the destructor is called, because your derived class could allocate memory that needs freeing, register for events using a pointer to itself which needs unregistering, etc.

 

4.Write a c program to check number(0123456789) in array of string is valid or not
number is valid only if it is number or number padded with right space
for example char ex[10];
0123456789 valid
012345678a invalid
0123a56789 invalid
01234″ ” valid
012345678″ ” valid
01234567″ ” valid
12345 invalid
1234″ “678 invalid
Solution:

#include<string.h>  
#include<stdio.h>  
bool solve(char* c, int len); 
int main() 
{ 
     char* str = " 12345678"; 
     printf("isnumber:%d\n", solve(str, strlen(str)));	
     return 1; 
} 

bool solve(char* c, int len) 
{ 
    for (int i=0; i<len; i++) 
    { 
          char tmp = c[i]-'0'; 
          if(i!=(len-1)) 
          { 
                 if(tmp10) 
                 { 
                     return false; 
                 } 
          }  
          else if(tmp== ((int)(' ')-'0') || (tmp>=0 && tmp<10)) 
          { 
                return true; 
          } 
    } 
    return false; 
}

 

5. What will be the o/p of the code below if we run it 5 times, will it be same every time or not?

int main()
{ 
    int a ;
    printf("%u\n",&a);
}  

Solution: If you are printing 5 times using a for loop then output will be same. If you are printing 5 times by running program 5 times then o/p will be different as program reserves memory at different location when you run.

 

6.Write a recursive method to get the multiplication of two numbers such that there are minimum number of addition operations.
Solution:

#include <iostream>
using namespace std; 
int Multiply(int a, int b); 
int reccursiveSum(int BigNum, int Smallnum); 

int main() 
{ 
int a = 19, b = 25, c = 0;; 
cout << "enter first number :" << a; 
cin >> a; 
cout << endl << "enter Second number :" << b;  
cin >> b; 
c = Multiply(a,b); 
cout << endl << "Multi value is :" << c;   
cin >> c; 
return 0; 
} 
int Multiply(int a, int b) 
{ 
int result = 0; 
if (a > b) 
   result = reccursiveSum(a, b); 
else 
    result = reccursiveSum(b,a); 
return result; 
} 

int reccursiveSum(int BigNum, int Smallnum) 
{ 
if (Smallnum == 1) 
     return BigNum; 
int result =0,NewNum = 0; 
NewNum = Smallnum/2; 
result = reccursiveSum(BigNum, NewNum); 
result += result; 
if(Smallnum % 2 != 0) 
   result += BigNum; 
return result; 
}

 

7.Write a program to replace each element of an array with a number present on the right side of the element such that the number is least greater than the element. If there is no greater number replace it with -1. Provide an optimized solution.
e.g : 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28
ans : 18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1

Solution:
Method 1:

Here is an O(nlogn) [amortized] approach using  BST where each node points to the next in order successor.

  • read the array from right to left
  • Insert each element into a  BST
  • Output the inorder successor after each insertion

Explanation: The solution O(n^2) does not structure the data in any way. So to optimize it lets try to bring a structure in the data. The operation to optimize is the linear search of the next greater element to the right, currently O(n). If all the elements on the right were in the form of a BST the search would take O(logn) time (. So we start by building the tree from the right of the array (step 1) Each time we insert a new element in the BST we find out its successor which is the output we desire.

Method 2:

#include<iostream>
#include<stack>
using namespace std;
void nextgreaterelement(int a[],int n)
{
    stack s;
    int next,element;
    s.push(a[0]);
    for(int i=1;i<n;i++)
    {
        next=a[i];
        if(!s.empty())
        {
            element=s.top();
            s.pop();
            while(element<next)
            {
                cout<<element<<"->"<<next<<endl;                 
                if(s.empty())                 
                      break;                 
                element=s.top();                 
                s.pop();             
            }             
            if(element>next)
                s.push(element);
        }
        s.push(next);
    }
    while(!s.empty())
    {
        element=s.top();
        s.pop();
        cout<<element<<"->"<<"-1"<<endl;
    }
}

This will give you the immediate value which is greater than the current node not the least one on right side.

 

8.The digits of a number come from a stream digit by digit. At any point tell whether the number formed from the digits so far is a multiple of 3.
Solution:
Steps:

  • Take the sum and check for divisibility by 3.
  • So maintain running sum (mod 3, to cater to overflows) and check if sum is 0 when stream ends.
  • It does not matter whether you get the most significant digit first.

This assumes base 10.