CareerCup

Good one!!

Please suggest me solution better then this.

public class BST {

	int data;
	private BST lc;
	private BST rc;
	int sumSoFar;
	BST replaceRootWithSumofGreaterNode(BST root){
		
		if(root != null){
			root.rc = replaceRootWithSumofGreaterNode(root.rc);
			sumSoFar+= root.data;
			root.data = sumSoFar;
			root.lc = replaceRootWithSumofGreaterNode(root.lc);
		}	
		return root;
	}
	BST addNode(BST root, int data){
		
		if(root == null){
			root = new BST();
			root.data = data;
			root.lc = root.rc = null;
			return root;
		}else{
			if(data<root.data){
				root.lc = addNode(root.lc,data);
				return root;
			}
			else{
				root.rc = addNode(root.rc,data);
				return root;
			}
		}
	}
	 void inorder(BST root){
		 if(root!=null){
			 inorder(root.lc);
			 System.out.print(root.data+"->");
			 inorder(root.rc);
		 }
	 }
	public static void main(String[] args) {
		BST b = new BST();
		BST root = null;
		int arr[] = {5,3,8,6,10,1,4,7,9,2};
		for(int data: arr){
			root = b.addNode(root, data);
		}
		b.inorder(root);
		System.out.print("\n\n");
		b.sumSoFar = 0;
		root= b.replaceRootWithSumofGreaterNode(root);
		b.inorder(root);
	}

}

Hello Bhupal,
My mistake..correct output should be Q = {4,6,-3,1,5,9}.

Reverse complete string and then reverse each words from starting.
Eg: I am Don

Step 1: noD ma I
Step 2: Don am I

Please suggest me better solution if exist.

@Mike: don't use extra field in node..only you need modify given BST node.
struct node
{
int data;
struct node *left;
struct node *right;
};

@Shiva..Good solution..Thanks :)

It can be done in single go. Simply do level order traversal, whenever level change, add 1st node of that level, when level end, add last visited element and also keep checking element which has no child (leaf node) and add all of them. This will return required result.

Looks sth wrong in question. Serilization and Deserializtion is done in the context of object of any class. We can create Class which implement Binary Tree and do serilization to further execute BinaryTree object in different JVM.

@Anonymous: tree is not BST, so inorder will not work.
Try level order traversal and assign temp variable with small value and keep searching bigger element.

Do inorder traversal, keep checking previously visited node is less then current node or not.
Please note, inorder traversal of binary tree prints data in sorted order.
Time Complexity: O(N), Space Complexity: O(N) for creating stack in recursive call.

#include <stdio.h>
#include <stdlib.h>
 
void printRepeating(int arr[], int size)
{
  int i;
  printf("The repeating elements are: \n");
  for (i = 0; i < size; i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}
 
int main()
{
  int arr[] = {1, 2, 3, 1, 3, 6, 6};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Replace A[N-1...N-1-i] by B[N-1...N-1-i] . My mistake..

What if no bounded range given and there could be some -ve value. Please note, these precondition was not there in question.

//Least common ancestor of given two node wold be required result.

int LCA(BinarySearchTree root, int node1, int node2){
		if(root == null){
			return -1;
		}else{
			if((root.data > node1 && root.data <node2) || (root.data< node1 && root.data > node2)){
				return root.data;
			}else{
				if(node1 < node2){
					if(node1 < root.data){
						return LCA(root.left, node1, node2);
					}else{
						return LCA(root.right, node1, node2);
					}
				}else{
					if(node2 < root.data){
						return LCA(root.left, node1, node2);
					}else{
						return LCA(root.right, node1, node2);
					}
				}
			}
		}
	}

#include <stdio.h>
#include <conio.h>
#include <string.h>

int doAction(char, char *, int *, int *);
void main(){
	int X=0,Y=0;
	char command[20];

	printf("Enter command: ");
	gets(command);
	int i=0, isActionPerformed = 1;
	char currDrn = 'E';
	while(command[i]){
		isActionPerformed = doAction(command[i], &currDrn, &X,&Y);
		if(!isActionPerformed){
			printf("\nYou have entered wronge command.."); break;
		}
		i++;
	}
	if(isActionPerformed)
		printf("\nFinal position of Robot is: (%d, %d).", X, Y);
	getch();
}

int doAction(char ch, char *currDrn, int *X, int *Y){
	
	switch(ch){
		case 'E':  *currDrn = ch; printf("\nTurned to East.."); break;
		case 'W':  *currDrn = ch; printf("\nTurned to West.."); break;
		case 'N':  *currDrn = ch; printf("\nTurned to North.."); break;
		case 'S':  *currDrn = ch; printf("\nTurned to South.."); break;
		case 'M':  if(*currDrn == 'N'){
			         if((*Y)-1 >= 0){
						  (*Y)--; printf("\n Moved one step towards North.");
					 }else{
						 printf("\n You have crossed top boundry limit..");
						 return 0;
					 }
				   }
				   else if(*currDrn == 'S'){
					   if((*Y)+1 < 10){
						  (*Y)++; printf("\n Moved one step towards South.");
					 }else{
						 printf("\n You have crossed bottom boundry limit..");
						 return 0;
					 }
				   }
				   else if(*currDrn == 'E'){
					   if((*X)+1 < 10){
						  (*X)++; printf("\n Moved one step towards East.");
					 }else{
						 printf("\n You have crossed left boundry limit..");
						 return 0;
					 }
				   }
				   else if(*currDrn == 'W'){
					   if((*X)-1 >= 0){
						  (*X)--; printf("\n Moved one step towards West.");
					 }else{
						 printf("\n You have crossed right boundry limit..");
						 return 0;
					 }
				   }
				   break;
		default: return 0;
	}
	return 1;

# include <stdio.h>
# include <conio.h>
#include  <string.h>

void main(){
	int arr[26];
	char str[16];
	char mat[4][4] = {{'d','a','c','b'},
	                  {'o','g','t','l'},
	                  {'l','p','l','e'},
	                  {'m','x','t','m'}};

	for(int i=0; i<26; i++){
		arr[i] = 0;
	}
	for(int i=0;i<4; i++){
		for(int j= 0; j<4; j++){
			arr[mat[i][j]-97]++;
		}
	}
	printf("Enter any String: ");
	gets(str);
	int k, found = 1;
	for(k=0; k< strlen(str); k++){
		if(arr[*(str +k) -97]){
			arr[*(str +k) -97]--;
		}else{
			found = 0; break;
		}
	}
	if(found)
		printf("\nString found");
	else
		printf("\nString not found");
	getch();
}

void getKthLargestElement(Node *root, int k){
	int num = 0;
	count(root, &num);
	getKthSmallestElement(root,num-k+1,num);
}
//To find kth smallest element in in BST
void getKthSmallestElement(Node *root, int k, int num){
   static int count, found;
   if(root && !found ){	
         getKthSmallestElement(root->left, k, num);
         count++;
         if(count == k){
	        printf("%d",root->data); found =1; return; 
         }
         else if(count == num && !found){
	        printf("\nData not found"); return;
         }
         getKthSmallestElement(root->right, k, num);
   }
}
void count(Node *root, int *p){	
	if(root){
		count(root->left, &(*p));
		(*p)++;
		count(root->right, &(*p));
	}
}

public class RotateMatrix {
    final int ROW = 5;
    final int COL = 5;
	public static void main(String[] args) {
		int mat[][] = {{2,1,5,3,4},{5,8,6,4,4},{9,12,6,9,4},{8,7,6,5,2},{1,2,3,4,5}};
		RotateMatrix rm = new RotateMatrix();
		System.out.println("Original Matrix:");
		rm.displayMat(mat);
		//Get transpose of matrix
        int temp;
		for(int i=0, j=0; i<rm.ROW; i++){
			j=i;
			for(; j<rm.COL; j++){
				if(i!=j){
					temp = mat[i][j];
					mat[i][j] = mat[j][i];
					mat[j][i] = temp;					
				}				
			}
		}
		System.out.println("Matrix after transpose:");
		rm.displayMat(mat);
		int c = 0;
		while(c<rm.COL/2){
			for(int i=0; i<rm.ROW; i++){
				temp = mat[i][c];
				mat[i][c] = mat[i][rm.COL-c-1];
				mat[i][rm.COL-c-1] = temp;
			}
			c++;
		}
		System.out.println("Matrix after rotation:");
		rm.displayMat(mat);
	}
	void displayMat(int mat[][]){

		for(int i=0; i<ROW; i++){
			for(int j=0; j<COL; j++){
				System.out.print(mat[i][j]+" ");
			}
			System.out.print("\n");
		}
		System.out.print("\n");
	}
}