1. Find a cycle in the given array and return the length of a cycle
for example, a[0] = 2, a[1] = 0, a[2] = 3, a[3] = 1, a[4] = 2, a[5] =4;
a[0]=2 -> a[2]=3 -> a[3]=1 -> a[1] =0 -> a[0]=2 ….
2->3-1>0->2->3->1->0->…
so return value should be 3.
Solution:

int cycle(int a[], int num)
 {
	int count = 0;
	//find a cycle
	int *fast = a, *slow = a, *start = a;
	do{
		fast = &a[*fast];
		fast = &a[*fast];
		slow = &a[*slow];
	}while(fast != slow);
	//fix slow pointer, and move another pointer to run a cycle
	start = slow;
	do 
	{
		start = &a[*start];
		//slow = &a[*slow];
		count++;
	}while(start != slow);
	printf("address is same %d\n", *slow);
}

 

2. Check if tree is BST.
Solution:

int testBst(struct tree * root) 
{ 
   if (NULL == root) 
      return 0; 
   else 
   { 
      if (!( (!root->left || root->left->key < root->key) && (!root->right || root->right->key > root->key ) )) 
         return 0; 
      testBst(root->left); 
      testBst(root->right); 
   } 
   return 1; 
}

 

3. You are given N unique numbers a1<a2<a3<…an. Find out the count of all possible binary search tress that can be constructed using these numbers.
for example with 3 elements 1,2,3 there are 5 possible BST and for 1,2,3,4 there are 14 BST.
Solution:
let count(n)= number of BST possible using n distinct keys
Then
count(n) = sum[ k=1 to n ] ( count(k-1) * count(n-k) )

 

4.What will be output ?

class z
{
};
class x
{
   int a;
};
int main()
{
   std::cout << sizeof(X) << '\n';
   std::cout << sizeof(z) << '\n';
}

Solution: Output – 4,1
Reason: Class without any data members and member function such type of class is known as empty class. Size of object of empty class is always 1 byte. When we create object of any class at that time object always gets 3 characteristics i.e.

  • State
  • Behaviour
  • Identity

When we create object of empty class at that time State of that object is nothing. Behaviour of that object is also nothing, but compiler assigns a unique address to that object. Memory in Computer is always organized in the form of bytes and minimum memory available at object address location is 1 byte. That’s why size of object of empty class is 1 byte.

 

5. You have the string = {aabb, aafd,acff,aacg,…..}. If i am writing a as first char or first two char or first three char and so on, it should show the all unique combination of words started with the that characters for eg. say if I am writing aa then it show that aabb or aafd………I have tried using hash map is it increase my complexity or should i have to use list.
Solution:

/*This code Needs some modification anybody who got the logic can try it.. and it does work for "a" and "aa", but doesn't work for input "ac" */

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class StringChallenge 
{
    public static void main(String[] args)
       {
	// TODO Auto-generated method stub
	String[] input = { "aabb", "aafd", "acff", "aacg", "acfg" };
	List lst = new ArrayList();
	for (String str : input) 
           {
	    lst.add(str);
	   }
        System.out.println("enter your option: ");
	Scanner in = new Scanner(System.in);
	String expt = in.nextLine();
	char[] inp = expt.toCharArray();
	for (int i = 0; i < inp.length; i++) 
        {
	    while (lst.get(i).contains(expt)) 
                {
		  System.out.println(lst.get(i) + " ");
		  lst.remove(i);
		  continue;
	            }
         }
     }
}