Initialization lists and constructors in C++

class Foo
{
    const int someThing;
    const float nothing;
    public:
      Foo()
      {
         someThing = 5;
         nothing = 5.0;
      }


}


The above implementation is wrong as we have to initialize const and refrences in the same line where we declare them.


The above code is same as 
const in x;
x=5; 
which obviously the compiler will not let us do.


the solution for the above problem is we use implicit initialization using the initialization list.



class Foo
{
    const int someThing;
    const float nothing;
    public:
      Foo(): something(5),nothing(5.0)
      {


      }
}


The initialization list is inserted after the constructor parameters, begins with a colon (:), and then lists each variable to initialize along with the value for that variable separated by a comma. Note that we no longer need to do the explicit assignments in the constructor body, since the initializer list replaces that functionality. Also note that the initialization list does not end in a semicolon.

A brief summary of Trees and Binary trees.

A brief summary of everything [Trees].
Trees:
Set of Nodes & Edges that connect them.
Between ANY TWO NODES THERE IS EXACTLY ONE PATH
PATH: connected sequence of EDGES.

Rooted Tree: One distinguished NODE is called a ROOT.
  Every node C, except the ROOT has one parent P, the first node from the node C to the root is its parent P.

C is P's child
Root has No parent.
A node can have n children.
A tree has no loops.

LEAF:  node with no children.
SIBLINGS: node with same parent.
ANCESTORS of node C: nodes in path from C to ROOT including C.
   If node A is the ANCESTOR of node C then node C is a DESCENDANT of node A.

LENGTH of the PATH: Number of edges in the PATH.
DEPTH of node n: Length of path from node n to ROOT.
   Depth of ROOT is 0.
HEIGHT of node n:  Length of path from n to its deepest descendant.
   Height of a leaf is 0.
   Height of Root is HEIGHT OF TREE.

Traversals for a Tree: 
Pre Order : Visit each Node before you visit its children. Eg: list the Directories in Tree form.
Post Order: Visit Node  Children First before visiting the node itself: Eg Summing the size of Sub Folders.
In Order(Binary tree): Visit left child then the Node and then nodes right child.
Level Order(Breadth First): Visit root, then all Depth 1 node(left to right), then Depth 2 nodes, etc..
Depth First:Same as Pre Order.

A BINARY TREE:
A rooted tree where no node has more than 2 children.
Every child is either left child or the right child even if its the only child.


PERFECT BINARY TREE:
A B Tree where all nodes except the LEAF node have exactly two siblings.


A COMPLETE BINARY TREE:
A B Tree Where  all the nodes are filled in the lower levels and the nodes in the Last level are kept to the almost LEFT as possible.


Common Interview Questions(B trees):


Q1)What are the number of NULL nodes a tree on N nodes.
A. The best way is to draw few trees and deduce the relation.
      There are N nodes in the Binary Tree.
      Each node except the ROOT has a parent, i.e N-1 Parents.
      Each node can have 2 Siblings, i.e N nodes can have 2N siblings.
      The total NULL nodes in a B tree of N nodes is 2N-(N-1), i.e N+1 Null nodes..


Q2) what is the minimum height of a B Tree with N nodes.
A. The height of a binary tree is minimum when its a Complete B-Tree.
     At a given level there are 2^level elements
     For a Complete B - Tree with height h the total number of elements is max((2^(N+1))-1).
     (2 to the power of N+1 whole -1).
    from the above two statement we can mathematically concolude the minimum height of a tree
    with n elements is ceil(log2(N))-1 that is Ceiling the value of Log of N to base 2 whole -1.


Q3) What is the maximum height of a B Tree with N nodes.
A. The height is maximum when there is at most 1 node in a level. hence the answer is N-1.


Q4) Min and Max Leaf Nodes in a tree of N nodes.
A. Min leaf node is 1 (When there is at most one element in every level, the last level node is the only leaf)
     Max leaf nodes is (N+1)/2


Q5) Number of leaf nodes in a complete binary tree of N nodes.
A. N is even N/2, and N is odd (N+1)/2, generalizing ceil(N/2).

Date with Design Patterns and Java

This looked promising enough to keep it in my To Do list. have to read it in coming days :)

http://www.devdaily.com/java/java-design-patterns-in-java-examples-tutorials

Solving these programming puzzles surely keeps the brain from rusting..

Can't stop admiring some programming problems and the solution for these are much more adorable than the problems itself.

Given a 2D array, print it in spiral form

/**
*
*/
package com.test.p4;

/**
* @author Thejas
*
*Print a given matrix in spiral form
Given a 2D array, print it in spiral form. See the following examples.

Input:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Input:
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
Output:
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
*/
public class print2DSpiral {

/**
* @param args
*/
int row=3,column=6;
int rowThreshold = row;//number of rows to traverse to print a fixed column
int columnThreshold = column; //number of columns to traverse to print elements of a fixed row
//int array[][]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
int array[][]={{1,2,3,4,5,6},{7,8,9,10,11,12},{13,14,15,16,17,18}};
/*
* once right reduce rowthreshold by 1
* once down reduce columnthreshold by 1
* once left reduce rowthreshold by 1
* once up reduce columnthreshold by 1
*/
public void printLeft(int i,int j,int value)
{
for(int k=0;k<columnThreshold;k++)
{
if(value > 0)
{
System.out.print(array[i][j]+" ");
value--;j--;
}
}
rowThreshold--;
if(value>0)
{
printUp(i-1, ++j, value);
}
return;
}
public void printRight(int i,int j,int value)
{
for(int k=0;k<columnThreshold;k++)
{
if(value > 0)
{
System.out.print(array[i][j]+" ");
value--;j++;
}
}
rowThreshold--;
if(value>0)
{
printDown(i+1, --j, value);
}
return;
}
public void printUp(int i,int j,int value)
{
for(int k=0;k<rowThreshold;k++)
{
if(value > 0)
{
System.out.print(array[i][j]+" ");
value--;i--;
}
}
columnThreshold--;
if(value>0)
{
printRight(++i, j+1, value);
}
return;
}
public void printDown(int i,int j,int value)
{
for(int k=0;k<rowThreshold;k++)
{
if(value > 0)
{
System.out.print(array[i][j]+" ");
value--;i++;
}
}
columnThreshold--;
if(value>0)
{
printLeft(--i, j-1, value);
}
return;
}
public static void main(String[] args) {
// TODO Auto-generated method stub

print2DSpiral printIt = new print2DSpiral();
printIt.printRight(0,0,printIt.row*printIt.column);
return;
}

}

String Puzzle

package com.test.p3;

/**
* @author light
*
* Suppose we are given a string 000011112222.
* Make it 012012012012 in O(n) time and O(1) space.
*/
public class FindPattern {

public static void main(String args[])
{
String str="000011112222";
for(int i=0;i<str.length();i++)
{
System.out.print(i%(3));
}
}
}

Find the repeating and the missing in 1..n array of size n

/**
*
*/
package com.test.p2;

/**
* @author Thejas
*Find the repeating and the missing
*Given an unsorted array of size n. Array elements are in range from 1 to n.
*One number from set {1, 2, …n} is missing and one number occurs twice in array.
*Find these two numbers.
*
* Examples:
*arr[] = {3, 1, 3}
*Output: 2, 3 // 2 is missing and 3 occurs twice
*arr[] = {4, 3, 6, 2, 1, 1}
*Output: 1, 5 // 5 is missing and 1 occurs twice
*
******************************************************************************************
*Solution:
*Traverse array from 0th index, take the value at the current index in the array as the index and
*negate the value at this new index.While Traversing check if the value of the value of current index is -ve,
*if yes we have got the Repeated element at array of current index.
*
*Now traverse the same array and break when you find a positive value in the array for current index.
*current index+1 is ur missing element
******************************************************************************************/
public class FindRepeatingMissing {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int array[]={5,3,7,2,4,1,5};
int n=array.length;
int i=0,missing=0,repeat=0;
for(;i<n;i++)
{
if(array[(Math.abs(array[i]))-1] > 0)
{
array[(Math.abs(array[i]))-1] = array[(Math.abs(array[i]))-1]*(-1);
}else{
repeat=Math.abs(array[i]);
}
}
i=0;
for(;i<n;i++)
{
if(array[i]> 0)
{
missing=i+1;
}
}

System.out.println("The Missing ="+missing+" and Repeated ="+repeat+" !!");
return;
}

}

Programming Puzzles -Arrays

package com.test.progs;

/**
* @author Thejas
*
*
* Given an unsorted array arr[] and two numbers x and y,
* find the minimum distance between x and y in arr[].
* The array might also contain duplicates.
* You may assume that both x and y are different and present in arr[].

Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 and 5 is 2.

Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.

Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.

*/
public class MinDist2num {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//test Data
int array[] = {1,4,22,55,2,3,6,7,0,22,3,55,22,0,2,4,5,10,55,2,6,7};
int x=6,y=7;
int i=0,prev=-1,dist=10000;//set a high value for initial distance Dist

for(i=0;i<array.length;i++)
{
if(array[i]==x){
prev=i;
}else if(array[i]==y && prev!=-1){
dist=(i-prev)<dist?(i-prev):dist;
int temp=x;
x=y;
y=temp;
prev=i;
}else if(prev==-1 && array[i]==y)
{
int temp=x;
x=y;
y=temp;
prev=i;
}
}
System.out.println("the minimum distance between "+x+" "+y+" = "+dist);
return;
}

}
/****************************************************************************************
Solution:
Travrse array from 0th index note down the first occurance of either of the elements X or Y in a variable say PREV.
when first occurance of either is found swap X and Y such that found element is X and the other Y.
traverse array further if element at index is X update PREV with index else
if it is Y update variable DIST with distance of PREV and index if lesser than current value of DIST
and swap X and Y set PREV value to that of the index
******************************************************************************************/