CareerCup

Here is a HashMap Based solution

public String findDuplicate(String[] inputStrings){
        Map<String,Integer> inputMap = new HashMap<>();
        int count;
        String uniqueString="";
        for(String input : inputStrings){
            if(inputMap.containsKey(input)){
                count = inputMap.get(input).intValue();
                count++;
                inputMap.put(input, count);
            }else{
                inputMap.put(input, 1);
            }
        }
        for(String input : inputStrings){
            if(inputMap.containsKey(input) && inputMap.get(input).intValue() ==1){
                uniqueString = input;
                break;
            }
        }
        return uniqueString;
    }

public void reverseSentence(String insentence) {
		char[] sentence = insentence.toCharArray();
		int[] blankposlist = new int[100];

		displayArray(sentence);
		int k = 0;
		blankposlist[k++] = -1;

		// storing the position of blank space in the input string.
		for (int i = 0; i < sentence.length; i++) {
			if (sentence[i] == ' ') {
				blankposlist[k++] = i;
			}
		}
		blankposlist[k] = sentence.length;
		// reverse the input string
		reverseString(sentence, 0, sentence.length - 1);

		// Reverse each word
		for (int m = 0; m < sentence.length;) {
			int reverselen = blankposlist[k] - blankposlist[k - 1] - 1;
			reverseString(sentence, m, m + reverselen - 1);
			m = m + reverselen + 1;
			k--;
		}

		displayArray(sentence);
	}

I think the problem can be solved using RabinKarp Algorithm,
Here is the code.
Please tell me if I have done any error.

package com.algorithm.string.pattern.search;

import java.util.Arrays;

public class RabinKarpApplication {

	public int hashValue(String input, int start, int end) {
		int temp = 0;
		char[] inputarr = input.toCharArray();
		for (int i = 0; i < end; i++) {
			temp += inputarr[i];
		}
		return temp;
	}

	boolean checkEquality(char[] source, char[] desti){
		Arrays.sort(source);
		Arrays.sort(desti);
		for(int i=0 ;i< source.length;i++){
			if(source[i] != desti[i]){
				return false;
			}
		}
		return true;
	}

	public boolean matchPattern(String source, String pattern) {
		int patternHashValue = hashValue(pattern, 0, pattern.length());
		int sourceHashValue = hashValue(source, 0, pattern.length());
		if (sourceHashValue == patternHashValue) {
			if(checkEquality(source.substring(0, pattern.length()).toCharArray(), pattern.toCharArray())){
				return true;
			}
		}

		char[] sourcearray = source.toCharArray();
		for (int i = pattern.length() ; i < sourcearray.length; i++) {
			sourceHashValue = sourceHashValue -  sourcearray[i - pattern.length()] + sourcearray[i];
			if(sourceHashValue == patternHashValue){
				if(checkEquality(source.substring(i-pattern.length()+1, i+1).toCharArray(), pattern.toCharArray())){
					return true;
				}
			}
		}

		return false;
	}

	public static void main(String[] args) {
		RabinKarpApplication rkapps = new RabinKarpApplication();
		String source = "bcabbcde";
		String pattern = "abc";
		if(rkapps.matchPattern(source, pattern)){
			System.out.println("Invalid");
		}else{
			System.out.println("Valid");
		}
	}
}

#include<iostream>
#include<cstring>
using namespace std;

int isPalindrome(char *s){
	int len = strlen(s);
	int start = 0, end = len-1;
	bool checkpalindrome = true;
    while(start<end){
		if(*(s+start) == ' '){
			start++;		
		}else if(*(s+end) == ' '){
			end--;
		}else{
			if(*(s+start) != *(s+end)){
				checkpalindrome = false;
				break;		
			}
			start++;
			end--;	
		}
	}
    return checkpalindrome;
}

int main(){
	string str = "ABCB DA";
	cout<<isPalindrome((char*)str.c_str());
}

Please let me know if any mistake I have done

This method may be helpful though signature of the method is little different.

int customInorderTraversal(TreeNode *rootnode){
	int maxval;

	if(rootnode != NULL){
		maxval = rootnode->val;
		int maxleft = maxval;
		int maxright = maxval;
		if(rootnode->left != NULL)
			maxleft = customInorderTraversal(rootnode->left);
		if(rootnode->right != NULL)
			maxright = customInorderTraversal(rootnode->right);

		if(maxleft == INT_MIN || maxright == INT_MIN){
			return INT_MIN;
		}else{
			if(maxleft <= maxval && maxval <= maxright){
				return maxright;
			}else{
				return INT_MIN;	
			}
    	}
	}else{
		return INT_MAX;
	}
}

int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(4);
    createTree(rootnode);
	int ret = customInorderTraversal(rootnode);
	if(ret == INT_MIN){
		cout<<"\n Input Btree is not BST ";
	}else if(ret == INT_MAX){
		cout<<"\n Empty Tree";
	}else{
		cout<<"\n Input BTree is BST";
	}
}

#include<iostream>
#include<climits>
using namespace std;

class TreeNode{
  public:
	TreeNode* left;
	TreeNode* right;
    int val;
	TreeNode(int);
};

TreeNode::TreeNode( int value ) {
	left = NULL;
	right = NULL;
	val = value;
}

void createTree(TreeNode* node){
	TreeNode* h;
    h = node;
    h->left = new TreeNode(2);
	h->right = new TreeNode(5);
    h->left->left = new TreeNode(1);
	h->left->right = new TreeNode(4);
	h->right->left = new TreeNode(6);
	h->right->right = new TreeNode(7);
}

int customInorderTraversal(TreeNode *rootnode){
	int maxval;

	if(rootnode != NULL){
		maxval = rootnode->val;
		int maxleft = maxval;
		int maxright = maxval;
		if(rootnode->left != NULL)
			maxleft = customInorderTraversal(rootnode->left);
		if(rootnode->right != NULL)
			maxright = customInorderTraversal(rootnode->right);

		if(maxleft == INT_MIN || maxright == INT_MIN){
			return INT_MIN;
		}else{
			if(maxleft <= maxval && maxval <= maxright){
				return maxright;
			}else{
				return INT_MIN;	
			}
    	}
	}else{
		return INT_MAX;
	}
}


int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(3);
    createTree(rootnode);
	int ret = customInorderTraversal(rootnode);
	if(ret == INT_MIN){
		cout<<"\n Input Btree is not BST ";
	}else if(ret == INT_MAX){
		cout<<"\n Empty Tree";
	}else{
		cout<<"\n Input BTree is BST";
	}
}

#include<iostream>
using namespace std;

const int LENGTH = 9;

bool checkRow(int sudo[LENGTH][LENGTH],int rownum){
	int auxarr[LENGTH] = {0};
	for(int i = 0; i<LENGTH; i++){
		if(auxarr[sudo[rownum][i]-1] == 0){
			auxarr[sudo[rownum][i]-1] = 1;
		}else{
			return false;
		}
	}
	return true;
}

bool checkColumn(int sudo[LENGTH][LENGTH],int colnum){
	int auxarr[LENGTH] = {0};
	for(int i = 0; i<LENGTH; i++){
		if(auxarr[sudo[i][colnum]-1] == 0){
			auxarr[sudo[i][colnum]-1] = 1;
		}else{
			return false;
		}
	}
	return true;
}

bool checkSubMatrix(int sudo[LENGTH][LENGTH], int startx, int starty){
	int auxarr[LENGTH] = {0};
	for(int i=startx;i<startx+3;i++){
		for(int j=starty;j<starty+3;j++){
			if(auxarr[sudo[i][j]-1] == 0){
				auxarr[sudo[i][j]-1] = 1;
			}else{
				return false;
			}
		}
	}
	return true;
}

int main(){
	int sudoku[LENGTH][LENGTH]={{5,3,4,6,7,8,9,1,2},
								{6,7,2,1,9,5,3,4,8},
								{1,9,8,3,4,2,5,6,7},
								{8,5,9,7,6,1,4,2,3},
								{4,2,6,8,5,3,7,9,1},
								{7,1,3,9,2,4,8,5,6},
								{9,6,1,5,3,7,2,8,4},
								{2,8,7,4,1,9,6,3,5},
								{3,4,5,2,8,6,1,7,9}
								};
							
	int startx = 0;
	int starty = 0;
	bool result = 1;
	for(int i=0;i<LENGTH;i++){
		result = 	result & 
					checkRow(sudoku,i) &
					checkColumn(sudoku,i) &
					checkSubMatrix(sudoku,startx,starty);
		starty += 3;
		if(result){
			if(starty >= LENGTH){
				starty = 0;
				startx += 3;
			}
		}else{
			cout<<"\n Incorrect Solution";
			break;
		}
					
	}
	
	if(result){
		cout<<"\n Correct Solution";
	}
			
}

Time Complexity O(n^3) space complexity O(9)

#include<iostream>
using namespace std;
class Matrix{
	int *mat;
	int row,column;
    public:
	void readMatrix();
	void rotateMatrix90DegClockWise();
	void transposeMatrix();
	void displayMatrix();
	void interchangeColumns();
};

void Matrix::readMatrix(){
    cout<<"Enter the row size : ";
    cin>>row;
    cout<<"Enter the column size : ";
    cin>>column;
    mat = new int[row*column];

    for(int i = 0;i<row ;i++){
	    cout<<"Enter the elements of row "<<i+1<<" :  ";
	    for(int j=0;j<column;j++)
		    cin>>*(mat+i*column+j);
    }
}


void Matrix::displayMatrix(){
    for(int i = 0;i<row ;i++){
		cout<<endl;
		for(int j=0;j<column;j++)
		cout<<*(mat+i*column+j)<<" ";
    }
}

void Matrix::transposeMatrix(){
   
	int *trans = new int(row*column);
	for(int i=0;i<row*column;i++){
		*(trans+i) = 0;
	}
    for (int i = 0; i < row; i++){ 
		for (int j = 0; j < column; j++){
			*(trans +j*row +i) = *(mat + i*column +j);
		}
	}
	row = row + column;
	column = row - column;
	row = row - column;
	for(int i=0;i<row*column;i++){
		*(mat+i) = *(trans+i);
	}
}


void Matrix::interchangeColumns(){
    int temp = 0;
    for(int i=0;i<row;i++){
        for(int j=0;j<column/2;j++){
	 		temp = *(mat+i*column+j);
			*(mat+i*column+j) = *(mat+column*i+(column-1-j));
			*(mat+column*i+(column-1-j)) = temp;
	    }
    }
}

void Matrix::rotateMatrix90DegClockWise(){
	transposeMatrix();
	interchangeColumns();
}

int main(){
    Matrix mat1;
    mat1.readMatrix();
	cout<<"\n Original Matrix ";
	mat1.displayMatrix();
    mat1.rotateMatrix90DegClockWise();
	cout<<"\n Rotated Matrix ";
	mat1.displayMatrix();
}

int main(){
int flag =1;
	while(flag){
		if(flag){
			cout<<"1";
			flag = 0;
		}
		if(!flag){
			cout<<"0";
			flag=1;
		}
	}
}

void TreeOperation::mirrorTree(TreeNode* node){
	if(node != NULL){
		mirrorTree(node->getLeftChild());
		mirrorTree(node->rightChild);
		swapChildren(node);
	}
}

void TreeOperation::swapChildren(TreeNode* parent){
	TreeNode* temp;
	temp=parent->getLeftChild();
	parent->setLeftChild(parent->rightChild);
	parent->rightChild = temp;
}

Please let me know If I am wrong

class TreeNode{
  public:
	TreeNode* left;
	TreeNode* right;
    int val;
	TreeNode(int);
};

TreeNode::TreeNode( int value ) {
	left = NULL;
	right = NULL;
	val = value;
}
int customInorderTraversal(TreeNode *rootnode){
	int maxval;

	if(rootnode != NULL){
		maxval = rootnode->val;
		int maxleft = maxval;
		int maxright = maxval;
		if(rootnode->left != NULL)
			maxleft = customInorderTraversal(rootnode->left);
		if(rootnode->right != NULL)
			maxright = customInorderTraversal(rootnode->right);

		if(maxleft == INT_MIN || maxright == INT_MIN){
			return INT_MIN;
		}else{
			if(maxleft <= maxval && maxval <= maxright){
				return maxright;
			}else{
				return INT_MIN;	
			}
    	}
	}else{
		return INT_MAX;
	}
}


int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(4);
    	createTree(rootnode); //Create a tree.
	int ret = customInorderTraversal(rootnode);
	if(ret == INT_MIN){
		cout<<"\n Input Btree is not BST ";
	}else if(ret == INT_MAX){
		cout<<"\n Empty Tree";
	}else{
		cout<<"\n Input BTree is BST";
	}
}

Time Complexity : 0(n): Space Complexity 0(3)
If any mistake I have done please let me know.

#include<iostream>
using namespace std;

class TreeNode{
  public:
	TreeNode* left;
	TreeNode* right;
    int val;
	TreeNode(int);
};

TreeNode::TreeNode( int value ) {
	left = NULL;
	right = NULL;
	val = value;
}

void customInorderTraversal(TreeNode *node , TreeNode **prevleaf){

	if(node->left == NULL && node->right == NULL){
		if(*(prevleaf) != NULL){
			(*(prevleaf))->right = node;
		}
		*(prevleaf) = node;
	}else if(node->left == NULL){
		customInorderTraversal(node->right,prevleaf);	
	}else if(node->right == NULL){
		customInorderTraversal(node->left,prevleaf);	
	}else{
		customInorderTraversal(node->left,prevleaf);
		customInorderTraversal(node->right,prevleaf);	
	}
}

void createTree(TreeNode* node){
	TreeNode* h;
    h = node;
    h->left = new TreeNode(2);
	h->right = new TreeNode(3);
    h->left->left = new TreeNode(4);
	h->left->right = new TreeNode(5);
	h->right->left = new TreeNode(6);
	h->right->right = new TreeNode(7);
	h->left->left->left = new TreeNode(8);
	h->left->left->right = new TreeNode(9);
}

void displayLeafs(TreeNode * rootnode){
	TreeNode* root = rootnode;
	while(root->left != NULL){
		cout<<root->val<<" ";
		root = root->left;
	}
	cout<<"\n Leaf Path : ";
	while(root != NULL){
		cout<<root->val<<" ";
		root = root->right;
	}
}

int main(){
	TreeNode* rootnode = (TreeNode*) new TreeNode(1);
    cout<<" Root : "<<rootnode->val;
    createTree(rootnode);
	TreeNode* prev = NULL;
	customInorderTraversal(rootnode,&prev);
	displayLeafs(rootnode);
	
}

Space complexity O(1). TimeComplexity O(n)

void TreeOperation::mirrorTree(TreeNode* node){
	if(node != NULL){
		mirrorTree(node->getLeftChild());
		mirrorTree(node->rightChild);
		swapChildren(node);
	}
}


/**
* Swap the children of a given parent.
* Works only for binary tree.
*/
void TreeOperation::swapChildren(TreeNode* parent){
	TreeNode* temp;
	temp=parent->getLeftChild();
	parent->setLeftChild(parent->rightChild);
	parent->rightChild = temp;
}

How do you get the the integer array ? If the array is found then nothing remains to find the missing number.

We can use a circular queue (size of n) with some modification. Modification is:
When the overflow condition arise we will remove the first element from the queue and put the newly come element in the queue. When the input stream ends the queue will contain just only last n elements. This will give O(n) time complexity.

If the input comes from stream your algorithm will not work.

The problem is similar to pascal triangle. Only a little modification required for boundary conditions.

float distributeWaterUptolevel(int watervol,int row,int column){
	int remainingwater,i,j;
	float glasses[10][10]= {0};
	int uptobeforelebel = ((row-1)*((row-1)+1))/2;
	if(uptobeforelebel > watervol)
		return 0;
	else{
		remainingwater = watervol-uptobeforelebel;
		glasses[0][0]=remainingwater;
		for(i=1;i<row;i++){
			for(j=0;j<=i;j++){
				if(j==0)
					glasses[i][j] = glasses[i-1][j]/2; 
				else if(j==i)
					glasses[i][j] = glasses[i-1][j-1]/2;
				else
					glasses[i][j] = (glasses[i-1][j] + glasses[i-1][j-1])/2;
			}
		}
		return glasses[row-1][column-1];
	}
}

int main()
{
        int watervol=7;
	float wateratglass = distributeWaterUptolevel(watervol,4,2);
	if(wateratglass == 0)
	    cout<<"Water are consumed at upper level";
	else
		cout<<"water at specified level is "<<wateratglass<<endl;
   getchar();
   return 0;
}

Solution using DP. This gives 0(n) time complexities. and 0(n) space complexity.

public long memorisedFebonacciSeries(int n) {
		for (int k = 0; k < remfebo.length; k++) {
			remfebo[k] = -1;
		}
		return getFebonacciSeriesRecursion(n);

	}

/**
	 * The method memorized the already calculated febonacci number. If further
	 * calculation required for nth febonacci number it first search in memory
	 * whether nth febonacci number is calculated or not. If it is found in
	 * memory it retrieve the value from memory else it go for calculating the
	 * febonacci number.
	 * 
	 * @param n
	 * @return nth febonacci number.
	 */
	public long getFebonacciSeriesRecursion(int n) {
		if (remfebo[n] > -1) {
			return remfebo[n];
		} else {
			if (n == 0 || n == 1) {
				return n;
			} else {
				remfebo[n] = getFebonacciSeriesRecursion(n - 1)
						+ getFebonacciSeriesRecursion(n - 2);
				return remfebo[n];
			}
		}

}

Greedy algorithm produce optimized solution in each step, but it cannot ensure global optimized solution. Where as Dynamic Programming always produce global optimized solution.

public void getLastNElementFromLinkList(LinkedList<Integer> llist, int n) {
		LinkedList<Integer> templist = new LinkedList<>();
		it = llist.iterator();

		printLastNElement(llist, n);
	}

	void printLastNElement(LinkedList<Integer> llist, int m) {
		totalelement++;
		int elementcountiniteration = totalelement;
		if (it.hasNext()) {
			Integer element = (Integer) it.next();
			printLastNElement(llist, m);
			if ((totalelement - elementcountiniteration) <= 3) {
				System.out.println(element.intValue());
			}
		}
}

public void reverseSentence(String insentence) {
	char[] sentence = insentence.toCharArray();
	int[] blankposlist = new int[100];

	displayArray(sentence);
	int k = 0;
	blankposlist[k++] = -1;

	// storing the position of blank space in the input string.
	for (int i = 0; i < sentence.length; i++) {
	    if (sentence[i] == ' ') {
		blankposlist[k++] = i;
	    }
	}
	blankposlist[k] = sentence.length;
	// reverse the input string
	reverseString(sentence, 0, sentence.length - 1);

	// Reverse each word
	for (int m = 0; m < sentence.length;) {
	    int reverselen = blankposlist[k] - blankposlist[k - 1] - 1;
	    reverseString(sentence, m, m + reverselen - 1);
	    m = m + reverselen + 1;
	    k--;
	}

	displayArray(sentence);
    }

 public void reverseString(char[] inarray, int start, int end) {
	char ch;
	for (int i = 0; i <= (end - start) / 2; i++) {
	    ch = inarray[start + i];
	    inarray[start + i] = inarray[end - i];
	    inarray[end - i] = ch;
	}
    }

void displayArray(char[] inarray) {
		System.out.println("\n---- Displaying array ---");
		for (char element : inarray) {
			System.out.print(element);
		}
	}

Time Complexity O(n) space complexity O(1)

public static void findMissingElementsInSeriese(int[] inputarray) {
	boolean isfound = false;
	for (int i = 0, k = 0; i < inputarray.length; i++) {
	    if (inputarray[i] != i + k + 1) {
		System.out.println((i + k + 1));
		k++;
		isfound = true;
	    }
	}
	if (!isfound) {
	    System.out.println("No missing elements found");
	}
    }

public void reverseSentence(String insentence) {
	char[] sentence = insentence.toCharArray();
	int[] blankposlist = new int[100];

	displayArray(sentence);
	int k = 0;
	blankposlist[k++] = -1;

	// storing the position of blank space in the input string.
	for (int i = 0; i < sentence.length; i++) {
	    if (sentence[i] == ' ') {
		blankposlist[k++] = i;
	    }
	}
	blankposlist[k] = sentence.length;
	// reverse the input string
	reverseString(sentence, 0, sentence.length - 1);

	// Reverse each word
	for (int m = 0; m < sentence.length;) {
	    int reverselen = blankposlist[k] - blankposlist[k - 1] - 1;
	    reverseString(sentence, m, m + reverselen - 1);
	    m = m + reverselen + 1;
	    k--;
	}

	displayArray(sentence);
    }

	public void reverseString(char[] inarray, int start, int end) {
	char ch;
	for (int i = 0; i <= (end - start) / 2; i++) {
	    ch = inarray[start + i];
	    inarray[start + i] = inarray[end - i];
	    inarray[end - i] = ch;
	}
    }
	
	 void displayArray(char[] inarray) {
	System.out.println("\n---- Displaying array ---");
	for (char element : inarray) {
	    System.out.print(element);
	}

class MaximumProduct{

public int[] subsequenceOfThreeNumbersHavingMaximumProduct(int[] series) {
		int result[] = { 0, 0, 0 };
		if (series.length < 3) {
			return series;
		}
		result = keepOrdering(result, series[0]);
		result = keepOrdering(result, series[1]);
		result = keepOrdering(result, series[2]);

		for (int i = 3; i < series.length; i++) {
			result = keepOrdering(result, series[i]);
		}

		return result;
	}
	
	public int[] keepOrdering(int[] result, int newelt) {

		if (newelt >= result[2]) {
			result[0] = result[1];
			result[1] = result[2];
			result[2] = newelt;
		} else if (newelt < result[2] && newelt >= result[1]) {
			result[0] = result[1];
			result[1] = newelt;
		} else if (newelt < result[1] && newelt >= result[0]) {
			result[0] = newelt;
		}
		return result;

	}

}

public class AddativeNumberSequence {

	public boolean isAddativeNumber(long number) {

		long[] digitsinnumber = toArray(number);
		long numberofdigits = digitsinnumber.length;
		boolean result = true;
		boolean finalflag = false;
		for (int i = 0; i < numberofdigits / 3; i++) {
			for (int j = 0; j <= numberofdigits - 3 * (i + 1); j = j + i + 1) {
				long part1 = makeNumberFromArray(digitsinnumber, j, j + i,
						i + 1);
				long part2 = makeNumberFromArray(digitsinnumber, j + i + 1, j
						+ 2 * i + 1, i + 1);
				long part3 = makeNumberFromArray(digitsinnumber, j + 2
						* (i + 1), j + 2 * (i + 1) + i, i + 1);
				if (part1 + part2 != part3 && !finalflag) {
					result = false;
					break;
				} else {
					result = true;
				}
			}
			if (result) {
				finalflag = true;
			} else {
				finalflag = false;
			}
		}
		return finalflag;
	}

	public void findAddativeNumberIn(long start, long end) {
		long tempstart = start;
		while (tempstart <= end) {
			if (isAddativeNumber(tempstart)) {
				System.out.print(tempstart + " ,");
			}
			tempstart++;
		}
	}

	public long[] toArray(long inputnumber) {
		long[] numberarray;
		int numlengthcount = 0;
		long tempnumber = inputnumber;
		while (tempnumber > 0) {
			numlengthcount++;
			tempnumber = tempnumber / 10;
		}
		numberarray = new long[numlengthcount];
		tempnumber = inputnumber;
		int i = 0;
		while (i < numlengthcount) {
			numberarray[numlengthcount - 1 - i] = tempnumber % 10;
			tempnumber = tempnumber / 10;
			i++;
		}
		return numberarray;
	}

	public long makeNumberFromArray(long[] numarray, int start, int end,
			int digitcount) {
		long sum = numarray[end];
		int prod = 1;
		int i = 1;
		while (i < digitcount) {
			prod *= 10;
			sum += numarray[end - i] * prod;
			i++;
		}
		return sum;
	}

}