CareerCup

Solution Using Backtracking:

void stringPermute( char *Arr, int idx, int N ) {
   if ( N == idx )
     cout << Arr ;
   else {
        for ( int j = idx; j <= N; j++ ) {
          swap( (Arr+idx), (Arr+j) ) ;
          stringPermute( Arr, idx+1, N ) ;
		  //Now Bactrack
          swap( (Arr+idx), (Arr+j) ) ; 
       }
   }
}

O(N*N!) Runtime

Level Order Traversal.
C++ Version:

int getHeightOfBinaryTree ( NODE* root ) {
	if ( !root )
		return 0 ;
		
	int level = 0 ;
	Queue *Q = CreateQueue() ;
	
	Q->enQueue( root ) ;
	Q->enQueue( NULL ) ; //To Mark End of Level
	
	while ( !Q->isEmpty() ) {
		NODE * node = Q->deQueue() ;
		
		if ( NULL == node ) {
			if ( !Q->isEmpty() )
				Q->enQueue( NULL ) ;
			level++ ;
		}
		else {
			if ( node->left )
				Q->enQueue ( root->left ) ;
			
			if ( node->right )
				Q->enQueue ( root->right ) ;
		}
	}
	return level ;
}

O(N) Time and Space Complexity

Agree

Can be done in 2 ways:
1) Brute Force using 2 loops.
O(N^2) Runtime.
2) Using HashMap to remember the char already present.
O(N) Runtime with Constant Space

char * removeDuplicateChars( char *str ){
 
	char *itr, *src;	 
	itr = str;
	src = str;
	 
	int hashMap[MAX_CHARS];
	for(int i = 0; i < MAX_CHARS; i++) 
		hashMap[i] = 0;
	 
	while( *itr != '\0' ){
		if( hashMap[*itr] == 0 ){
			hashMap[*itr]++;
			*src = *itr;
			src++;
			itr++;
		}	
		else{
			itr++;
		}
	}
	
	if( NULL != src )
		*src = '\0';
		
	return str;
}

A> Reverse the whole string first.
B> Reverse individual words of the output string from step A.

char* ReverseAllWords(char* text) {
    int lindex = 0;
    int len = strlen(text) - 1;
    if (len > 1) {
	
        //reverse complete string
        text = ReverseString( text, 0, len );

        //reverse each word
        for (int rindex = 0; rindex <= len; rindex++) {
            if (rindex == len || text[rindex] == ' ') {
                text = ReverseString(text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return text;
}

char* ReverseString(char* str, int begin, int end) {
    while (begin < end) {
        char tempc = str[begin];
        str[begin++] = str[end];
        str[end--] = tempc;
    }
    return str;
}

Can be done by Inorder traversal technique, which will result in O(N) time.

Another Approach:
Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.

Now, suppose we are at node T:

k == num_elements(left subtree of T), then the answer we're looking for is the value in node T
k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

This is O(log N) on average (assuming a balanced tree)

int kSmallestInBST(NODE *root, int k) {
	int count;
	count = sizeOfBST(root->left) + 1;
	if( k == count)
		return (root->data);
	else if( k < count)
		return kSmallestInBST(k,root->left);
	else
		return kSmallestInBST(k-count,root->right);
}

int sizeOfBST(NODE *root) {
	if(NULL == root)
		return 0;
	else
		return (sizeOfBST(root->left) + 1 
		        + sizeOfBST(root->right));
}

An empty tree is a Valid BST. Your first case returns 0 ?

How about this case?

4
/
3
\
8

C++ Version:

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

C++ way for the delete() to remember how much to be destructed is explained below:

Section 16.14 of the C++ FAQ lite answers this:

There are two popular techniques that do this. Both these techniques are in use by commercial-grade compilers, both have tradeoffs, and neither is perfect. These techniques are:

* Over-allocate the array and put n just to the left 
      of the first Fred object.
    * Use an associative array with p as the key and n as the value.

Source: parashift.com/c%2B%2B-faq-lite/num-elems-in-new-array.html

C++: Base Shape class

class shape {
	public:
		shape();
		virtual double area() const;
		virtual double perimeter() const;
	private:
		coordinates position;
		color outline, fill;
};

C Equivalent:

typedef struct shape shape;
typedef struct shape_vtbl shape_vtbl;

struct shape_vtbl {
	double (*area)(shape const *s);
	double (*perimeter)(shape const *s);
};
struct shape {
	shape_vtbl *vptr;
	coordinates position;
	color outline, fill;
};

C++: circle class derived from shape looks like:

class circle: public shape {
	public:
		circle(double r); 
		virtual double area() const;
		virtual double perimeter() const;
	private:
		double radius;
};

#include "shape.h"
typedef struct circle circle;
struct circle {
	shape base; // the base class sub-object
	double radius;
};
void circle_construct(circle *c, double r);

In C++, a call to the virtual area function applied to a shape looks exactly like a non-virtual call, as in:

shape *s;
~~~
s->area();

In C, virtual function calls look unlike any other kind of function call. For example, a call to the virtual area function applied to a shape looks like:

shape *s;
~~~
s->vptr->area(s);

In this case, if s points to a circle (the dynamic type of *s is circle), then the call above calls circle_area. If s points to a rectangle, then the call above calls rectangle_area.

Source: forum.eetindia.co.in/BLOG_ARTICLE_13544.HTM

C++ Code (Queue with DLL and Hash Map)

struct LRUCacheNode {
		int key;
		int value;
		LRUCacheNode* prev;
		LRUCacheNode* next;
		LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;
} ;

class LRUCache{
private:
    hash_map< int, LRUCacheNode* >  Map;
    LRUCacheNode *  Head;
    LRUCacheNode *  Tail;
	int Capacity ;
	int Count ;
    
public:
    LRUCache(int capacity) {
		Capacity = capacity ;
		Count = 0 ;
        Head = new LRUCacheNode;
        Tail = new LRUCacheNode;
        Head->prev = NULL;
        Head->next = Tail;
        Tail->next = NULL;
        Tail->prev = Head;
    }
    
    ~LRUCache ( ) {
        delete Head;
        delete Tail;
    }
    
    int get(int key) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            AttachNodeToFront(node);
            return node->value;
        }
        else
        return -1 ;

    }
    
    void put(int key, int value) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            node->value = value;
            AttachNodeToFront(node);
        }
        else{
			LRUCacheNode* node = new LRUCacheNode ;
            if ( Capacity == Count ) { // If Cache is Full
                RemoveLRUNode ( key ) ;					
            }
            
			node->key = key;
			node->value = value;
			Map[key] = node;
			AttachNodeToFront(node);
			Count++ ;            
        }
    }
private:
	void RemoveLRUNode ( int key ) {
		LRUCacheNode* node = Tail->prev;
        DetachNode(node);
        Map.erase(node->key);
		Count-- ;
	}

    void DetachNode(LRUCacheNode* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
    }
    
    void AttachNodeToFront(LRUCacheNode* node) {
            node->next = Head->next;
            node->prev = Head;
            Head->next = node;
            node->next->prev = node;
    }
};

As pointed out by @Kid of Kop, I doubt a O(n) solution...

Below is a C version of O(n) solution:

void ReplaceChar ( char *str, char Find, char Replace ) {
   while ( *str ) {
        if ( *str == Find )
            *str = Replace ;
        str++ ;
    } 
}

Sample Run:

int main()
{
  cout << "Enter the String ===> " ;
  char * str = new char [ sizeof(char) * MAX_COUNT_LENGTH ] ;
  cin >> str ;
  char *res = convert2Count(str);
  cout << "Output ===> " ;
  cout << res << endl ;
  return 0 ;
}

Enter the String ===> AaaaABBbcccCd
Output ===> A5B3C4D1

Enter the String ===> BBSBSS
Output ===> B2S1B1S2

Enter the String ===> AaV
Output ===> A2V1

C Version:

#define MAX_COUNT_LENGTH 10

char *convert2Count ( char *src ) {
	int repCount = 0, i = 0, j = 0, k = 0;
	char count[MAX_COUNT_LENGTH];
	int length = strlen(src);

	/* The Dest string length is made as Double the length of src in worst case, where
               i/p = abcd and o/p = a1b1c1d1  */
	char *dest = new char [sizeof(char)*(length*2 + 1)];

	for ( i = 0; i < length; i++ ) {
		dest[j++] = toupper( src[i] ) ;

		// Count the number of occurrences of repeated character 
		repCount = 1 ;
		while ( (i + 1) < length && toupper(src[i]) == toupper(src[i+1]) )  {
			repCount++ ;
			i++ ;
		}

		//Copy the Count to Dest String
		sprintf ( count, "%d", repCount ) ;
		for ( k = 0; *(count+k); k++, j++ ) {
			dest[j] = count[k] ;
		}
	}

	dest[j] = '\0';
	return dest;
}

C version:
Returns 0 if strings are same else non-zero value.

int my_strcmp ( char *s, char *t ) {
	while ( *s == *t ) {
		if ( *s == '\0' )
			return 0 ;
			
		s++ ;
		t++ ;
	}
	return ( *s - *t ) ;
}

C++ Version:

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

Case 1: Node is left most node of BST.
Return NULL
Case 2: Node has left sub tree.
In this case it is Maximum Node in the Left Sub-Tree. i.e., the right most node in the left sub-tree
would be the in-order predecessor.
Case 3: Node has no left sub-tree.
In this case in-order predecessor will be the node where we took the latest right turn.
C++ version:

NODE * find_predecessor(NODE * root, NODE * node)
{
    NODE * temp = root, *parent = NULL;
    if (node->left != NULL){  // Max of the Left Sub-Tree
       temp = node->left;
       while (temp->right != NULL) 
			temp = temp->right;
       return temp;
    }
 
    while ( temp != node ){ // Find the Ancestor where we took latest Right Turn
       if (node->data < temp->data){
         temp = temp->left;  
       }
       else {
         parent = temp;
         temp = temp->right;
       }
    }
    return parent;
}

Case 1: Node is left most node of BST.
Return NULL
Case 2: Node has left sub tree.
In this case it is Maximum Node in the Left Sub-Tree. i.e., the right most node in the left sub-tree
would be the in-order predecessor.
Case 3: Node has no left sub-tree.
In this case in-order predecessor will be the node where we took the latest right turn.

C++ version:

NODE * find_predecessor(NODE * root, NODE * node)
{
    NODE * temp = root, *parent = NULL;
    if (node->left != NULL){  // Max of the Left Sub-Tree
       temp = node->left;
       while (temp->right != NULL) 
			temp = temp->right;
       return temp;
    }
 
    while ( temp != node ){ // Find the Ancestor where we took latest Right Turn
       if (node->data < temp->data){
         temp = temp->left;  
       }
       else {
         parent = temp;
         temp = temp->right;
       }
    }
    return parent;
}

C++ version:

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

@ DownVoter, care to explain ?
Let me know if anything wrong in solution...

The problem can be solved by below methods along with their run-times mentioned.
Brute-Force Method --- O (nw)
Using a Heap --- O(n log w)
Using a Deque --- O(n)
The interviewer expected an Optimal Solution in terms of Run-time.

C++ Solution by using a double-ended queue.It supports insertion/deletion from the front and back.

void SlidingWindowMin ( int Arr[], int Num, int WinSize, int SlideMin[]) {
  deque<int> Q;
  
  //Maintain the min element in the window in the front of the queue.
  
  for (int idx = 0; idx < WinSize; idx++) {
    while ( !Q.empty() && 
			Arr[idx] <= Arr[Q.back()] )
      Q.pop_back();
	  
    Q.push_back(idx);
  }
  
  for (int idx = WinSize; idx < Num; idx++) {
    SlideMin[idx-WinSize] = Arr[Q.front()];
  
	while (!Q.empty() && Arr[idx] <= Arr[Q.back()])
      Q.pop_back();
	
	while (!Q.empty() && Q.front() <= idx-WinSize)
      Q.pop_front();
    
	Q.push_back(idx);
  }
  
  SlideMin[Num-WinSize] = Arr[Q.front()];
}

Complexity:
Each element is Inserted and deleted at most once = 2n = O(n)

@zack.kenyon --- I just gave tech description of the question. I didn't think of the Literal meaning of the same :-)

@Westlake --- The i/p and o/p clearly showed what is required. Anyway,I have updated the question for clarity.

@zack.kenyon --- The i/p and o/p clearly showed what is required. Anyway,I have updated the question for clarity.

@CT - Can you please elaborate your answer.

It is Next Larger Element not the Largest...
O/p: {12,12,10,10,10,2,10,10,3,2}

C++ Version:

O(n2) version:

void ReplaceNextLargest ( int * Arr, int N ) {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = i + 1; j < N; j++ ) {
            if ( Arr[j] > Arr[i] ) {
                Arr[i] = Arr[j] ;
                break;
            }
        }
    }
}

O(n) Version:

> Take stack and Initially push the Index 0 on to the stack.
> Traverse All Elements of the Array from left to right.
>> If the stack is Empty push the element in the stack.
>> If the stack is Non-Empty AND Current-Element > Stack-Top-Index-Element, then replace the Stack-Top-Index element in Array with Current-Element and Pop the Stack. Else Push the Index on to the Stack.

void ReplaceNextLargest ( int * Arr, int N ) {
    stack<int> stk;
    stk.push(0);

    for( int idx = 1; idx < N; idx++ ) {
        while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) ) {
            Arr[stk.top()] = Arr[idx];
            stk.pop();
        }
        stk.push(idx);
    }
}

Using Doubly Linked List:

typedef struct DoublyLinkedListNode {
    int Data;
    DoublyLinkedListNode *Next;
    DoublyLinkedListNode *Prev;
    DoublyLinkedListNode(int n) {
        Data = n;
        Next = NULL;
        Prev = NULL;
    }
} DLstack;
 
class Stack {
public:
	Stack ( ) ;
	~Stack ( ) ;
	int Pop ( ) ;
	void Push ( int num ) ;
	int Mid ( ) ;
	void PopMid ( ) ;
	void Display ( ) ;
	bool isEmpty ( ) ;
private:
    int top;
    DLstack *stack;
    DLstack *midNode; //Keeps track of middle element
    DLstack *lastNode;
    bool midFlag; //To check the behaviour of Mid Element
};
Stack::Stack() {
	stack = NULL;
	top = 0;
	midNode = NULL;
	lastNode = NULL;
	midFlag = false;
}
Stack::~Stack() {
	while( stack ) {
		DLstack* temp = stack;
		stack = stack->Next;
		delete temp;
	}
}
void Stack::Push(int n) {
	DLstack *newNode = new DLstack(n);
	if( !stack ) { // Stack is Empty
		stack = newNode;
		midNode = newNode;
		lastNode = newNode;
		midFlag = true;
	}
	else {
		lastNode->Next = newNode;
		newNode->Prev = lastNode;
		lastNode = newNode;
		//Update the Mid Element Node
		midFlag = !midFlag;
		if(midFlag)
			midNode = midNode->Next;
	} 
	top++;
}
int Stack::Pop() {
	int nRet=0;
	DLstack *temp = lastNode;
	lastNode = lastNode->Prev;
	if(lastNode)
		lastNode->Next = NULL;
	nRet = temp->Data;
	delete temp;

	top--;
	//Update the Mid Element Node
	midFlag = !midFlag;
	if(midFlag)
		midNode = midNode->Prev;
   
	return nRet;
}
int Stack::Mid() {
	return midNode->Data;
}
void Stack::PopMid() {
	if( midNode ) {
		DLstack *temp = midNode;
		if( midNode->Prev ) 
			midNode = midNode->Prev;
		
		midNode->Next = temp->Next;
		temp->Next->Prev = midNode;
		delete temp;
		
		midFlag = !midFlag;
		if(midFlag)
			midNode = midNode->Next;
			
		top--;
	}
}
void Stack::Display() {
	DLstack* temp = stack;
	while( temp ) {
		cout<<temp->Data;
		temp = temp->Next;
		(temp!=NULL)?cout<<"<=>":cout<<"\n";
	}
}
bool Stack::isEmpty() {
if( NULL == stack )
		return true;
	return false;
}

C++ Code (Queue with DLL and Hash Map)

struct LRUCacheNode {
		int key;
		int value;
		LRUCacheNode* prev;
		LRUCacheNode* next;
		LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;
} ;

class LRUCache{
private:
    hash_map< int, LRUCacheNode* >  Map;
    LRUCacheNode *  Head;
    LRUCacheNode *  Tail;
	int Capacity ;
	int Count ;
    
public:
    LRUCache(int capacity) {
		Capacity = capacity ;
		Count = 0 ;
        Head = new LRUCacheNode;
        Tail = new LRUCacheNode;
        Head->prev = NULL;
        Head->next = Tail;
        Tail->next = NULL;
        Tail->prev = Head;
    }
    
    ~LRUCache ( ) {
        delete Head;
        delete Tail;
    }
    
    int get(int key) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            AttachNodeToFront(node);
            return node->value;
        }
        else
        return -1 ;

    }
    
    void set(int key, int value) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            node->value = value;
            AttachNodeToFront(node);
        }
        else{
			LRUCacheNode* node = new LRUCacheNode ;
            if ( Capacity == Count ) { // If Cache is Full
                RemoveLRUNode ( key ) ;					
            }
            
			node->key = key;
			node->value = value;
			Map[key] = node;
			AttachNodeToFront(node);
			Count++ ;            
        }
    }
private:
	void RemoveLRUNode ( int key ) {
		LRUCacheNode* node = Tail->prev;
        DetachNode(node);
        Map.erase(node->key);
		Count-- ;
	}

    void DetachNode(LRUCacheNode* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
    }
    
    void AttachNodeToFront(LRUCacheNode* node) {
            node->next = Head->next;
            node->prev = Head;
            Head->next = node;
            node->next->prev = node;
    }
};

@ashot madatyan --- Thanks for pointing it. Edited...

The Animal Family can be broadly classified as below sub categories:
> Bird Family
> Mammal Family
> Insect Family
> Fish Family

Animals can be also classified based on many of their characteristics, such as:
> Carnivores vs Herbivores
> Scavengers
> Land vs. Water Animals
> Noctural or Night Animals
> Cold Blooded vs Warm Blooded Animals
> Vertebrates vs. Invertebrates
> Fly / Swim / Run
> Number Of Legs

class Animal {
   String Name ;
   List <Characteristic> Characteristics ;
   .....
};

class Characteristic {
   String Name;
   ...
};

class Carnivores : public Characteristic {
  bool isCarnivores ();
  ...
};

class Legs : public Characteristic {
  int NumberOfLegs ();
  ...
};

@ishan.4525 --- logging.apache.org/log4j/1.2/download.html ,i got from here.

C++ Code (Queue with DLL and Hash Map)

struct LRUCacheNode {
		int key;
		int value;
		LRUCacheNode* prev;
		LRUCacheNode* next;
		LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ;
} ;

class LRUCache{
private:
    hash_map< int, LRUCacheNode* >  Map;
    LRUCacheNode *  Head;
    LRUCacheNode *  Tail;
	int Capacity ;
	int Count ;
    
public:
    LRUCache(int capacity) {
		Capacity = capacity ;
		Count = 0 ;
        Head = new LRUCacheNode;
        Tail = new LRUCacheNode;
        Head->prev = NULL;
        Head->next = Tail;
        Tail->next = NULL;
        Tail->prev = Head;
    }
    
    ~LRUCache ( ) {
        delete Head;
        delete Tail;
    }
    
    int get(int key) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            AttachNodeToFront(node);
            return node->value;
        }
        else
        return -1 ;

    }
    
    void set(int key, int value) {
        LRUCacheNode* node = Map[key];
        if(node)
        {
            DetachNode(node);
            node->value = value;
            AttachNodeToFront(node);
        }
        else{
			LRUCacheNode* node = new LRUCacheNode ;
            if ( Capacity == Count ) { // If Cache is Full
                RemoveLRUNode ( key ) ;					
            }
            
			node->key = key;
			node->value = value;
			Map[key] = node;
			AttachNodeToFront(node);
			Count++ ;            
        }
    }
private:
	void RemoveLRUNode ( int key ) {
		LRUCacheNode* node = Tail->prev;
        DetachNode(node);
        Map.erase(node->key);
		Count-- ;
	}

    void DetachNode(LRUCacheNode* node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
    }
    
    void AttachNodeToFront(LRUCacheNode* node) {
            node->next = Head->next;
            node->prev = Head;
            Head->next = node;
            node->next->prev = node;
    }
};

@The Artist --- Anyway thanks for the input, i am going through the log4j implementation,to understand how it is designed.

The Interviewer wanted me to Design the Logging mechanism as if it was design to be part of OS. Not using any existing facilities.

Write To File --- i answered the same with Serialize with a lock and after the interviewer told about Performance, i told about the Protecting of just the Write Offset. And told about the Live and Frozen buffer.

The per CPU log idea is a good one... Need to think about it...

When a hint was given about the Not all logs are written in File --- After some research i found the below (Chain Of Responsibility Pattern)

class Logger {
    static int ERR = 1;
    static int INFO = 2;
    static int DEBUG = 3;
    virtual void message(String msg, int priority) {
            writeMessage(msg);
            next.message(msg, priority);
    }
} ;
 
class StdoutLogger : Logger {
	void writeMessage(String msg) {
		...
    }
};
  
class EmailLogger : Logger {
  void writeMessage(String msg) {
		...
    }
} ;
 
class StderrLogger : Logger {
    void writeMessage(String msg) {
		...
    }
} ;

void RecursiveReverse(struct node** root ) {
	if (*root == NULL) 
			return;
	
	struct node* cur;
	struct node* rest;
	
	cur = *root;
	
	rest = cur->next;
	
	if (rest == NULL) 
			return;
	
	RecursiveReverse(&rest);
		
	// put the cur elem on the end of the list	
	cur->next->next = cur; 
	cur->next = NULL;
		
	// fix the root poniter
	*root = rest; 
}


void Reverse(struct node** root) {
	struct node* result = NULL;
	struct node* cur = *root;
	
	while (cur != NULL) {
		struct node* next = cur->next;		
		
		cur->next = result;
		result = cur;
		
		cur = next;
	}
	*root = result;
}

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

struct TrieTrieNode {
  TrieNode() : isWord(false) {
	for(int i = 0;i < 26;++i)
	  children[i] = 0;
  }

  ~TrieNode() {
	for(int i = 0;i < 26;++i)
	  if(children[i]) 
		delete children[i];
  }

  TrieNode*& child(char c) {
	//For Simplicity, converts all characters to lowercase
	return children[tolower(c)-'a'];
  }

  TrieNode* children[26];
  bool isWord ;
};

class Trie {
  public:
    Trie() {
      root = new TrieNode;
    }

    ~Trie() {
      delete root;
    }

    void addWord(string word) {
      TrieNode* curr = root;
      for(int i = 0;i < word.length();++i){
        char& c = word[i];
        if(!isalpha(c)) 
			continue;
        if(!curr->child(c))
          curr->child(c) = new TrieNode;
        curr = curr->child(c);
      }
      curr->isWord = true;
    }

    bool searchWord(string word) {
      TrieNode* curr = root;
      for(int i = 0;i < word.size();++i) {
        char& c = word[i];
        if(!isalpha(c)) 
			continue;
        if(!curr->child(c)) 
			return false;
        curr = curr->child(c);
      }
      return curr->isWord;
    }
  private:
    TrieNode* root;
};

To Build the Dictionary of words from a txt file:

Trie trie;
string temp;
ifstream fdDict("/path/to/dictionary/words/file");
while(!fdDict.eof()) {
	fdDict >> temp;
	trie.addWord(temp);
}

int removeDuplicates ( int Arr[], int Len ) {
  if ( Len <= 1 )
		return Len ;
		
	int Index = 0, Itr = 1 ;
	
	while ( Itr < Len ) {
		if ( Arr[Itr] != Arr[Index] )
			Arr[++Index] = Arr[Itr] ;
		
		Itr++ ;
	}
	
	return ( Index + 1 );
}

Method returns the Index to the End of Distinct Elements in the Array.

The keyword "mutable" is used to allow a particular data member of const object to be modified. It simply allows you to modify a variable in a 'const' method.
Most popularly used for Marking a boost::mutex member as mutable allowing const functions to lock it for thread-safety reasons

'num' cannot be modified because it is being accessed through a const object

A Planet Class can have properties of Name,Radius, Distance from the SUN in AU. The behaviour can be getters.
The Sun class be defined as a Singleton.
The SolarSystem has composition of Planets and the Sun.