CareerCup

class MyMaxHeap
{
public:

	MyMaxHeap(int n)
	{
		arr.resize(n);
		currentSize = 0;
	}

	int getSize()
	{
		return currentSize;
	}
	int top()
	{
		return currentSize == 0 ? INT_MIN : arr[0];
	}
	void add(int val)
	{
		if (currentSize < arr.size())
		{
			arr[currentSize++] = val;
			heapifyUp(arr, currentSize-1);
		}
		else if(arr[0] > val)
		{
			arr[0] = val;
			heapifyDown(arr);
		}
	}
	void print()
	{
		for (int i = 0; i < currentSize; i++)
			cout << arr[i] << ",";
		cout << endl;
	}

private:
	void heapifyUp(vector<int> &arr, int childIndex)
	{
		if (childIndex == 0)
			return;
		int parentIndex = childIndex / 2;
		while (childIndex > 0 && arr[parentIndex] < arr[childIndex])
		{
			swap(arr[parentIndex], arr[childIndex]);
			childIndex = parentIndex;
			parentIndex /= 2;
		}
	}

	void heapifyDown(vector<int> &arr)
	{
		int parentIndex = 0;
		int childIndex = getMaxChildIndex(arr, parentIndex);

		while (childIndex != -1 && arr[parentIndex] < arr[childIndex])
		{
			swap(arr[parentIndex], arr[childIndex]);
			parentIndex = childIndex;
			childIndex = getMaxChildIndex(arr, parentIndex);
		}
	}
	int getMaxChildIndex(vector<int> &arr, int index)
	{
		int leftChild = 2 * index + 1;
		int rightChild = 2 * index + 2;
		int ans = -1;
		if (rightChild < currentSize)
			ans = arr[rightChild] > arr[leftChild] ? rightChild : leftChild;
		else if (leftChild < currentSize)
			ans = leftChild;
		return ans;
	}
	int currentSize;
	vector<int> arr;
};


int main()
{
	//stream of numbers
	vector<int> input = { 2,3,5,6,7,8,1,8,3,4,67,0 };
	int maxSize = 3;
	MyMaxHeap heap(maxSize);
	for (int i = 0; i < input.size(); i++)
	{
		cout << "Adding " << input[i] << endl;
		heap.add(input[i]);
		heap.print();
	}
	getchar();
}

struct compare
{
	bool operator() (pair<int, int> operand1, pair<int, int> operand2)const
	{
		return operand1.second < operand2.second;
	}
};
int main()
{
	vector<int> input = { 6,7,1,3,2,4,5,2,3,1,2,5 };
	vector<int> keyNums = { 1,2,5 };
	set<int> keySet(keyNums.begin(), keyNums.end());
	map<int, int> keyCounts;
	for (int i = 0; i < keyNums.size(); i++)
		keyCounts[keyNums[i]] = 0;
	// skip non key elements
	int i = 0;
	while (i < input.size())
	{
		if (keySet.find(input[i]) != keySet.end())
			break;
		i++;
	}
	if (i == input.size())
		return 0;
	int ansStartIndex = i, ansMaxLength = INT_MAX, startIndex = i;
	keyCounts[input[i]]++;
	i++;
	while (i < input.size())
	{
		if (keySet.find(input[i]) != keySet.end())
		{
			keyCounts[input[i]]++;
			// check can we move start index towards right
			if (input[startIndex] == input[i])
			{
				keyCounts[input[i]]--;
				startIndex++;
				while ((keySet.find(input[startIndex]) == keySet.end()) || (keyCounts[input[startIndex]] > 1) )
				{
					if(keySet.find(input[startIndex]) != keySet.end())
						keyCounts[input[startIndex]]--;
					startIndex++;
				}
			}
			// Check is there a optimal solution
			if (((*min_element(keyCounts.begin(), keyCounts.end(), compare())).second > 0) && (i - startIndex + 1 < ansMaxLength))
			{
				ansStartIndex = startIndex;
				ansMaxLength = i - startIndex + 1;
			}
		}
		i++;
	}

	cout << "startIndex = " << ansStartIndex << " , length = " << ansMaxLength << endl;
	getchar();
}

struct listNode
{
	int data;
	listNode *next;
	listNode(int val) :data(val), next(NULL){}
};

listNode * createLinkedList(int numberOfNodes)
{
	listNode *head = new listNode(1);
	int i = 2;
	listNode *p = head;
	while (i <= numberOfNodes)
	{
		p->next = new listNode(i);
		p = p->next;
		i++;
	}
	return head;
}


void printLinkedList(listNode *head)
{
	while (head != NULL)
		cout << head->data << ", ", head = head->next;
	cout << endl;
}

listNode * reverseFirstKNodes(listNode *head, int k)
{
	if (head == NULL || head->next == NULL)
		return head;
	listNode *p = head;
	listNode *q = head->next;
	while (k > 1 && q != NULL)
	{
		listNode *r = q->next;
		q->next = p;
		k--;
		p = q;
		q = r;
	}
	head->next = q;
	return p;
}

void reverseKAlternateNodes(listNode *&head, int k)
{
	if (k < 2 || head == NULL || head->next == NULL)
		return;
	listNode *p = head;
	listNode *tail = NULL;
	head = NULL;

	while (p != NULL)
	{
		if (head == NULL)
		{
			head = reverseFirstKNodes(p, k);
			p = head;
		}
		else
		{
			tail->next = reverseFirstKNodes(p, k);
			p = tail->next;
		}

		// skip 2*k -1 nodes

		int  i = 2 * k - 1;
		while (i > 0 && p != NULL)
		{
			p = p->next;
			i--;
		}

		if (p != NULL)
		{
			tail = p;
			p = p->next;
		}
	}
}

int main()
{
	listNode *head = createLinkedList(11);
	reverseKAlternateNodes(head, 3);
	printLinkedList(head);
	// free list head

	getchar();
	return 0;
}

struct treeNode
{
	int key;
	treeNode *left, *right;
	treeNode(int val) :key(val), left(NULL), right(NULL) {}
};

int treeDiameter(treeNode *root, int &maxHeight)
{
	if (root == NULL)
		return -1;
	else if (root->left == NULL && root->right == NULL)
		return 0;
	int leftHeight = 0, rightHeight = 0, leftDiameter = 0, rightDiameter = 0, diameter = 0;

	if (root->left)
	{
		leftDiameter = treeDiameter(root->left, leftHeight);
		diameter += leftHeight + 1;
	}
	if (root->right)
	{
		rightDiameter = treeDiameter(root->right, rightHeight);
		diameter += rightHeight+ 1;
	}

	maxHeight = max(leftHeight, rightHeight) + 1;
	return max(diameter, max(leftDiameter, rightDiameter));
}
int main()
{
	/*
			10
		5		15
	 4	 7	 11	   16
	6	9
	*/

	treeNode *root = new treeNode(10);
	root->left = new treeNode(5);
	root->right = new treeNode(15);
	root->left->left = new treeNode(4);
	root->left->right = new treeNode(7);
	root->left->right->left = new treeNode(6);
	root->left->right->right = new treeNode(9);

	root->right->left = new treeNode(11);
	root->right->right = new treeNode(16);
	int height = 0;
	cout << "diameter = " << treeDiameter(root, height) << endl;
	getchar();
}

according to your code {a:b{}} is valid Json or not ? . FYI {a:b{}} is invalid JSON

unsigned int count2s(int num)
{
	if (num < 3)
		return num == 2 ? 1 : 0;
	string str = to_string(num);
	unsigned int total = 0;
	int len = str.length();
	for (int i = 0; i < len; i++)
	{
		int temp = 0;
		if (i > 0)
			temp += atoi(str.substr(0, i).c_str());

		if (str[i] == '2')
		{
			if (len - i - 1 > 0)
				temp *= (int)pow(10, len - i - 1);
			if(i+1 < len)
				temp += atoi(str.substr(i + 1, len-i-1).c_str()) + 1;
		}
		else
		{
			if (str[i] > '2')
				temp++;
			if (len - i - 1 > 0)
				temp *= (int)pow(10, len - i - 1);
		}
		total += temp;
	}
	return total;
}
int main()
{
	cout << " number of 2s 99 = " << count2s(99) << endl;
	cout << " number of 2s 29 = " << count2s(29) << endl;
	cout << " number of 2s 219 = " << count2s(219) << endl;
	getchar();
}

/*
1->2->3->4->6->7->8->9   ,, K =3

1->2->3  4->5->6  7->8->9
789 456 123
-----

1->2->3->4->5->6->7->8->9   ,, K =2
1->2 3->4 5->6 7->8 9
9 78 56 3->4 1->2 
*/

struct listNode
{
	int data;
	listNode *next;
	listNode(int val) :data(val), next(NULL) {}
};

listNode * createLinkedList(int numberOfNodes)
{
	listNode *head = new listNode(1);
	int i = 2;
	listNode *p = head;
	while (i <= numberOfNodes)
	{
		p->next = new listNode(i);
		p = p->next;
		i++;
	}
	return head;
}

listNode * reverseBatch(listNode *head, int k)
{
	if (head == NULL || head->next == NULL || k < 2) //  below code does not work if k == 1
	{
		return head;
	}

	int i = 0;
	listNode  *prevHeader = NULL;
	listNode  *currentHeader = NULL;
	listNode *p = head;

	while (p != NULL)
	{
		if (i % k == k - 1)
		{
			listNode *temp = p;
			p = p->next;
			temp->next = prevHeader;
		}
		else
		{
			if(i % k == 0)
				prevHeader = currentHeader, currentHeader = p;
			p = p->next;
		}
		i++; 
	}

	head = currentHeader;;
	if (i % k != 0 ) 
	{
		p = head;
		while (p->next != NULL)
			p = p->next;
		p->next = prevHeader;
	}
	
	return head;
}

void printLinkedList(listNode *head)
{
	while (head != NULL)
		cout << head->data <<", ", head = head->next;
	cout << endl;
}

int main()
{
	listNode *head = createLinkedList(9);
	head = reverseBatch(head, 3);
	printLinkedList(head);
	// free list head
	head = createLinkedList(11);
	head = reverseBatch(head, 3);
	printLinkedList(head);
	// free list

	head = createLinkedList(11);
	head = reverseBatch(head, 2);
	printLinkedList(head);
	getchar();
	return 0;
}

Approach: 
We can use recursion to solve this question

bool checkJason(string str, int &index){}
step1: when you hit character '{',  call recursion . And recursion function returns boolean value.
Step2: valid Json string must have equal number of open and closed brackets '{' & '}'
step3: when we hit delimiter characters ',', '{','}'  call checkJasonValuePair(string str, bool allowSuffixColon=false)
step4: CheckJsonValuePair() validate whther the string has ':' character or not.

bool checkJasonValuePair(string str, bool allowSuffixColon=false)
{
	if (str.empty())
		return true;
	int colCount = 0;
	for (int i = 0; i< str.length(); i++)
	{
		if (str[i] == ':')
			colCount++;
	}
	// suffix sould not be :
	if (!allowSuffixColon && str[str.length() - 1] == ':')
		return false;
	return colCount == 1 ? true : false;
}

bool checkJason(string str, int &index)
{
	if (str.empty())
	{
		return  true; 
	}
	stack<char> stk;
	int i = index;
	while (i < str.length())
	{
		if (str[i] == '{')
		{
			stk.push('{');
			string temp;
			i++;
			while (i < str.length() && str[i] != ',' && str[i] != '}' && str[i] != '{')
			{
				temp += str[i];
				i++;
			}
			if (i == str.length() || !checkJasonValuePair(temp, str[i] == '{'))
				return false;

			if (str[i] == '{' && !checkJason(str, i))   // recursive functrion
					return false;
		}
		else if (str[i] == ',')
		{
			i++;
			string temp;
			while (i < str.length() && str[i] != '}' && str[i] != ',' && str[i] != '{')
			{
				temp += str[i];
				i++;
			}

			if (i == str.length() || !checkJasonValuePair(temp, str[i] == '{'))
				return false;  // last charcter should be ‘}’
			else if (str[i] == '{' && !checkJason(str, i))   // recursive functrion
				return false;
		}
		else
		{
			if (str[i] == '}')
			{
				if (stk.empty() || stk.top() != '{')
					return false;
				stk.pop();
			}
			i++;
			return true;
		}
	}

	return stk.empty() ? true: false;
}

int main()
{
	int index = 0;
	cout << " Valid Jason {} = " << checkJason("{}", index) << endl;
	index = 0;
	cout << " Valid Jason {a}= " << checkJason("{a}", index) << endl; // false
	index = 0;
	cout << " Valid Jason {a:b}= " << checkJason("{a:b}", index) << endl;
	index = 0;
	cout << " Valid Jason {a:{b:c}}= " << checkJason("{a:{b:c}}", index) << endl;
	index = 0;
	cout << " Valid Jason {a:b, c:d} = " << checkJason("{a:b, c:d}", index) << endl;
	index = 0;
	cout << " Valid Jason {a:b, c{:d}} = " << checkJason("{a:b, c{:d}}", index) << endl;//false
	index = 0;
	cout << " Valid Jason {a:} = " << checkJason("{a:}", index) << endl;//false
	getchar();
}

/*
step1 : Maintain two counters count1 & count2

count1 contains size of LessThan zigzag order (which starts with <). e,g  a<b>c<d
count2 contains size of GreaterThanzigzag order (which starts with >). e,g  x>y<z>i<j
step2: increase count1 by 1 when you add a new element to LessThan ZigZag order.
increase count2 by 1 when you add a new element to GreaterThan ZigZag order.
Step3: if ith element doesnot meet condition, then  skip it.
*/
int maxZigZagLength(vector<int> &vec)
{
	bool lessThan = true;
	bool greaterThan = true;
	int count1 = 0, count2 = 0;

	for (int i = 1; i < vec.size(); i++)
	{
		if ((lessThan && vec[i - 1] < vec[i]) || (!lessThan && vec[i - 1] > vec[i]))
		{
			lessThan = !lessThan; 
			count1++;
		}

		if ((greaterThan && vec[i - 1] > vec[i]) || (!greaterThan && vec[i - 1] < vec[i]))
		{
			greaterThan = !greaterThan;
			count2++;
		}
	}
	count1++, count2++;
	cout << "Less Than count1 = " << count1 << " , count2 = " << count2 << endl;
	return count1 > count2 ? count1 : count2;
}

int main()
{
	vector<int> vec = { 1,42,59,43,68,44 }; // answer is 1 < 42 > 43< 68 > 44
	cout << "lenght = " << maxZigZagLength(vec) << endl; 

	vector<int> vec1 = { 100,42,54,2,5 }; // answer is  100> 42 <54>2 < 5
	cout << "lenght = " << maxZigZagLength(vec1) << endl;

	vector<int> vec2 = { 1,42,54,20,1 }; // answer is 1<42>20 or 42 < 54 > 20
	cout << "lenght = " << maxZigZagLength(vec2) << endl;
	getchar();
}

Please let me know if you find any bugs in approach

I think it is 3N + 4(N-1) = 7*N-4

check this input ")(("

in wait method, you must do "--innerValue;"

Windows C++ code

#include <stdafx.h>
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
#include <condition_variable>
using namespace std;

#define MAXNUM 90

int num = 1;
condition_variable oneCondition;
condition_variable twoCondition;
condition_variable thirdCondition;
mutex guard;

void thread3()
{
	while (num <= MAXNUM)
	{
		if (num % 3 != 0)
		{
			unique_lock<mutex> lck(guard);
			thirdCondition.wait(lck);
		}
		//cout << "Thread3 : " << num << endl;
		cout << 3;
		++num;
		oneCondition.notify_one();
	}
}

void thread2()
{
	while (num <= MAXNUM-1)
	{
		if (num % 3 != 2)
		{
			unique_lock<mutex> lck(guard);
			twoCondition.wait(lck);
		}
		//cout << "Thread2 : " << num<<endl;
		cout << 2;
		++num;
		thirdCondition.notify_one();
	}
}

void thread1()
{
	while (num <= MAXNUM-2)
	{
		if (num % 3 != 1)
		{
			unique_lock<mutex> lck(guard);
			oneCondition.wait(lck);
		}
		//cout << "Thread1 : " << num << endl;;
		cout << 1;
		++num;
		twoCondition.notify_one();
	}
}

int main()
{
	thread t1(thread1), t2(thread2), t3(thread3);
	t1.join(), t2.join(), t3.join();
	getchar();
}

@Anon, Thanks

@cdhsiung, thanks for pointing bug in my code. now, I have modified code to fix that issue

#include <iostream>
#include <string>
using namespace std;
//Returns INT_MIN if input string s contains non paranthes characters
int MinNumInsersertionsForBalancing(const string& s)
{
	int i=0;
	int leftParanthesisCount = 0;
	int rightParanthesisCount = 0;
	int leftParanthesisToBeInsert = 0;
	while(i < s.length())
	{
		if(s[i] == '(')
		{
			leftParanthesisCount++;
		}
		else if(s[i] == ')')
		{
			// handle ")(" case
			if (leftParanthesisCount <= rightParanthesisCount)
			{
				leftParanthesisToBeInsert++;
			}
			else
			{
				rightParanthesisCount++;
			}
		}
		else
		{
			// error handling
			return INT_MIN;
		}
		i++;
	}
	// (leftParanthesisCount - rightParanthesisCount) give us no. of right paranthesis to be insert
	return leftParanthesisToBeInsert + (leftParanthesisCount - rightParanthesisCount);
}

int main()
{
	cout<<MinNumInsersertionsForBalancing("")<<endl;
	cout<<MinNumInsersertionsForBalancing("(()")<<endl;
	cout<<MinNumInsersertionsForBalancing("))")<<endl;
	cout<<MinNumInsersertionsForBalancing("(())")<<endl;
	// important test case, missed this test case initially
	cout << MinNumInsersertionsForBalancing("))((") << endl;
	cout << MinNumInsersertionsForBalancing(")((") << endl;
	return 0;
}

Approach is
1. Create a class "VeryLongINT"
2. it contains two fields 1. vector<int> 2. bool Sign (sign TRUE for +ve num, FALSE for -ve)
3. add operator methods to perform Addition and subtraction
4. whiel performing addition and subtraction operation we need to take care, "VeryLongINT" object sign.
5. E.g (obj1) + (-obj2), here I perform subtraction.
(obj1) + (-obj2) = obj1 - obj2
6. (-obj1) -(obj2) = -(obj+obj2);

// GoogleVeryLongInteger.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

class VeryLongINT
{
public:
	VeryLongINT()
	{
	}

	VeryLongINT(const vector<int> &vect, bool sign1 = true)
	{
		number = vect;
		sign = sign1;
	}

	VeryLongINT(const VeryLongINT &obj)
	{
		number = obj.number;
		sign = obj.sign;
	}
	void printNum()
	{
		cout << endl;
		char ch = sign == true ? '+' : '-';
		cout << ch;
		for (int i = 0; i < number.size(); i++)
			cout << number[i];
	}
	friend VeryLongINT operator+(VeryLongINT obj1, const VeryLongINT obj2);
	friend VeryLongINT operator-(VeryLongINT obj1, const VeryLongINT obj2);
	friend VeryLongINT operator-(VeryLongINT obj);
	friend bool absCompare(const VeryLongINT &obj1, const VeryLongINT &obj2);
private:
	vector<int> number;
	bool sign; // sign flag TRUE if num is +ve otherwise false
};

// Add operator
VeryLongINT operator+(VeryLongINT obj1, VeryLongINT obj2)
{
	if (obj1.sign == obj2.sign)
	{
		VeryLongINT result;
		int i = obj1.number.size() - 1;
		int j = obj2.number.size() - 1;
		int carry = 0;
		while (i >= 0 || j >= 0 || carry == 1)
		{
			int temp = 0;
			if (i >= 0)
			{
				temp += obj1.number[i--];
			}
			if (j >= 0)
			{
				temp += obj2.number[j--];
			}
			temp += carry;
			result.number.push_back(temp % 10);
			carry = temp / 10;
		}
		reverse(result.number.begin(), result.number.end());
		result.sign = obj1.sign;
		return result;
	}
	else
	{
		// if obj1.sign is -ve
		if (obj1.sign == false)
		{
			obj1.sign = true;
			return obj2 - obj1;
		}
		// if obj2.sign is -ve
		else
		{
			obj2.sign = true;
			return obj1 - obj2;
		}
	}
}

//Subtract operator
VeryLongINT operator-(VeryLongINT obj1, VeryLongINT obj2)
{
	if (obj1.sign == obj2.sign)
	{
		if (absCompare(obj1, obj2))
		{
			VeryLongINT result;
			int i = obj1.number.size() - 1;
			int j = obj2.number.size() - 1;
			int carry = 0;
			while (i >= 0 || j >= 0 || carry == 1)
			{
				if (j >= 0)
				{
					int temp = obj1.number[i] - carry - obj2.number[j];
					carry = temp < 0;
					if (carry)
					{
						temp += 10;
					}
					result.number.push_back(temp);
					i--;
					j--;
				}
				else
				{
					if (carry == 1)
					{
						int temp = -carry;
						carry = 0;
						temp += obj1.number[i];
						if (temp > 0 || i > 0)
						{
							result.number.push_back(temp);
						}
						i--;
					}
					while (i >= 0)
					{
						result.number.push_back(obj1.number[i]);
						i--;
					}
				}
			}
			reverse(result.number.begin(), result.number.end());
			result.sign = obj1.sign;
			return result;
		}
		else {
			return -(obj2 - obj1);
		}
	}
	else
	{
		return obj1 + (-obj2);
	}
}

// unary operator
VeryLongINT operator-(VeryLongINT obj)
{
	// just negate sign
	obj.sign = obj.sign ? false : true;
	return obj;
}

bool absCompare(const VeryLongINT &obj1, const VeryLongINT &obj2)
{
	if (obj1.number.size() > obj2.number.size())
	{
		return true;
	}
	else if (obj1.number.size() < obj2.number.size())
	{
		return false;
	}
	else
	{
		for (int i = 0; i < obj1.number.size(); i++)
		{
			if (obj1.number[i] == obj2.number[i])
				continue;
			return obj1.number[i] > obj2.number[i] ? 1 : 0;
		}
		return true;
	}
}

int main()
{

	vector<int> a(3, 2);
	vector<int> b(2, 1);
	VeryLongINT *obj1 = new VeryLongINT(a,false);
	VeryLongINT *obj2 = new VeryLongINT(b);
	VeryLongINT result = *obj1 + *obj2;
	obj1->printNum();
	obj2->printNum();
	cout << "\nAddition" << endl;
	result.printNum();
	free(obj1);
	free(obj2);
	cout << "\n*********" << endl;
	vector<int> c(3, 2);
	vector<int> d(4, 1);
	VeryLongINT *obj3 = new VeryLongINT(c);
	VeryLongINT *obj4 = new VeryLongINT(d);
	result = *obj3 - *obj4;
	obj3->printNum();
	obj4->printNum();
	cout << "\nSubtraction" << endl;
	result.printNum();
	free(obj3);
	free(obj4);
	cout << "\n*********" << endl;
	getchar();
	return 0;
}

#include <iostream>
#include <string>
using namespace std;
//Returns INT_MIN if input string s contains non paranthes characters
int MinNumInsersertionsForBalancing(const string& s)
{
	int i=0;
	int leftParanthesisCount = 0;
	int rightParanthesisCount = 0;
	while(i < s.length())
	{
		if(s[i] == '(')
		{
			leftParanthesisCount++;
		}
		else if(s[i] == ')')
		{
			rightParanthesisCount++;
		}
		else
		{
			// error handling
			return INT_MIN;
		}
		i++;
	}
	return abs(leftParanthesisCount-rightParanthesisCount);
}

int main()
{
	cout<<MinNumInsersertionsForBalancing("")<<endl;
	cout<<MinNumInsersertionsForBalancing("(()")<<endl;
	cout<<MinNumInsersertionsForBalancing("))")<<endl;
	cout<<MinNumInsersertionsForBalancing("(())")<<endl;
	return 0;
}

Please let me know if you find any bugin this code

minor correction:

Missed to "printf("%d.", d/ n);"

can you please provide algorithm or approach first before pasting code here

correction

*you no need to write three strings*

1) I think, after appending '0' to smaller string, both string have same size. So you need to three while loops. you can remove last two while loops.

2) you have to handle a case where string does not have '.' . this case num.find() returns -1.

agree, there are still two comparisons.

inside While loop

there should be extra check

if( le < re)
swap( A[le], A[re] );

missed to close file descriptors.

Close(SFD);
Close(DFD);

Nice solution

@Anonymous, nice explanation

Nice answer

there is no recursive macro

below code throws an error"SUM object not found"

#define SUM(x) do{\
				cout<<SUM(x)<<endl;\
				}while(0)

// C++ implementation of a O(n) time method for spiral order traversal
#include <iostream>
#include <stack>
using namespace std;
 
// Binary Tree node
struct node
{
    int data;
    struct node *left, *right;
};

// A utility functiont to create a new node
struct node* newNode(int data)
{
    struct node* node = new struct node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return(node);
}
 
void printSpiral(struct node *root)
{
    if (root == NULL)  return;   // NULL check
	struct node *temp;
    // Create two stacks to store alternate levels
	// Here stack stores tree node pointers
    stack<struct node*> s1;  // For levels to be printed from right to left
    stack<struct node*> s2;  // For levels to be printed from left to right
	stack<struct node*> s3;  // To store the end result, and print it in reverse order 
    // Push first level to first stack 's1'
    s1.push(root);
 
    // Keep ptinting while any of the stacks has some nodes
    while (!s1.empty() || !s2.empty())
    {
        // Print nodes of current level from s1 and push nodes of
        // next level to s2
        while (!s1.empty())
        {
            temp = s1.top(); 
            s1.pop();
            //cout << temp->data << " ";
			s3.push(temp);
            // Note that is right is pushed before left
            if (temp->right)
                s2.push(temp->right);
            if (temp->left)
                s2.push(temp->left);
        }
 
        // Print nodes of current level from s2 and push nodes of
        // next level to s1
        while (!s2.empty())
        {
            temp = s2.top();
            s2.pop();
            //cout << temp->data << " ";
			s3.push(temp);
            // Note that is left is pushed before right
            if (temp->left)
                s1.push(temp->left);
            if (temp->right)
                s1.push(temp->right);
        }
    }
	// Print tree elements in reverse order
	while(!s3.empty())
	{	
		temp = s3.top(); // retrun top element
		s3.pop(); // pop doesn't return anyhting , just removes top element.   
		cout<<temp->data<<" ";
	}
}
 
 
int main()
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(7);
    root->left->right = newNode(6);
    root->right->left  = newNode(5);
    root->right->right = newNode(4);
    cout << "Spiral Order traversal of binary tree is \n";
    printSpiral(root);
 
    return 0;
}

#include <iostream>
using namespace std;

class A{
int i,j;
public:
	A():i(1),j(0)
	{
		i = i/j;  // here it crashes before it reaches to Main() func because of divided-by-zero
		cout<< "A class's constructor \n";
	}
};

A a;// Global object , it invokes A's constructor

int main()
{
	cout<< "hello after main"<<endl;
	return 0;
}

using one array is sufficient

it seems, I wringly used front & rear indexes

test cases:

1. verify SMS receiver phone no.
2. whether sender opted for SMS plan or not (if he not opted for SMS plan, then his telecom operator does not allow him to send SMS )
3. huge SMS message
4. empty SMS message
5. sending message to multiple phone no.s (or group)

Youtube uses adobe flash player,

1. adobe flash player crashed
2. adobe flash player incompatible with browser through which you are playing youtube video
3. there is some problem with video file

debugging :

attach debugger and see adobe flash player is loaded are not.
once you attach debugger, you get all exceptions of the problem,and anlayze them.

#include <malloc.h>

#define QUEUE_SIZE 100

struct tree
{
	int data;
	struct tree *left, *right;
};

struct queue 
{
	struct tree *nodes[QUEUE_SIZE];
	int front,rear;
};

void printLevelOrder(struct tree *root)
{
	struct queue *Q = (struct queue *) malloc(sizeof(struct queue));
	struct tree *P;
	queueInit(Q);
	queueAdd(Q, root);
	queueAdd(Q, NULL);
	
	while(!queueEmpty(Q))
	{
		P = queueDel(Q);
		if(P == NULL)
		{
			if(queueEmpty(Q))
				return;
			printf("\n");
			queueAdd(Q, NULL);
		}
		else
		{
			printf("%d,",P->data);
			if(P->left != NULL)
				queueAdd(Q, P->left);
			if(P->right != NULL)
				queueAdd(Q, P->right);
		}
	}
}

/* Queue functions */
void queueInit(struct queue *Q)
{
	Q->front = Q->rear = -1;
}

void queueAdd(struct queue *Q, struct tree *node)
{
	if((Q->front+1)%QUEUE_SIZE == Q->rear)
	{
		printf("\n Queue is full");
	}
	else
	{
		Q->front = (Q->front + 1)% QUEUE_SIZE;
		Q->nodes[Q->front] = node;
		if(Q->rear == -1 )
		{
			Q->rear = 0;
		}
	}
}

struct tree * queueDel(struct queue *Q)
{
	if( Q->rear == -1)
	{
		printf("\n queue is empty ");
		return NULL;
	}
	else
	{
		struct tree *temp = Q->nodes[Q->rear];
		Q->rear = (Q->rear + 1) % QUEUE_SIZE;
		/* Queue is empty */
		if(Q->rear > Q->front)
		{
			Q->front = Q->rear = -1;
		}
		return temp;
	}
}

int queueEmpty(struct queue *Q)
{
	return Q->rear == -1 ? 1 : 0 ;
}

Nice solution

Nice solution

Let us say X = XOR sum of all elements from 0 to N
Y = XOR sum of given elements ( 0 to N , one number missed )

X xor Y vallue is the missed number.

@sachin, nice code

nice code, you handled all the cases

Nice solution!

int numOfPaths(int A[4][4], int n)
{
	int B[4][4];
	// if starting point blocked then no path is there to reach right down
	if( A[0][0] == 0)
	{
		return 0;
	}
	else
	{
		int i,j;
		for(i=0; i<n; i++)
		{
			if( A[0][i] == 0 )
				break; // exit from the for loop, and set remaining elements the first row set to ZERO
			B[0][i] = A[0][i];
		}
		
		while(i<n)
			B[0][i++] = 0; 

		for(i=1; i<n; i++)
		{
			if( A[i][0] == 0 )
				break;// exit from the for loop, and set remaining elements in the first column set to ZERO
			B[i][0] = A[i][0];
		}
		while(i<n)
			B[i++][0] = 0;

		for(i=1; i<n; i++)
			for(j=1; j<n; j++)
				if( A[i][j] == 0)
					B[i][j] = 0;
				else
					B[i][j] = B[i-1][j] + B[i][j-1];
		return B[n-1][n-1];
	}	
}

int main()
{
	int A[4][4] = {{1,1,1,1},
	{0,1,0,1},
	{0,1,1,0},
	{1,1,1,1}};
	
	int paths = numOfPaths(A, 4);
	printf("\n numofpaths = %d\n", paths);
	return 0;
}

We can solve this problem in O(n) time complexity.

Step1:

Array[] = {2,3,1,5} Permute[] ={5,2,1,3}

Step2:
2315 -->exchange 2 & 3
3215 -->exchange 3 & 5
5213

total 2 swap operations

Step3:

int i = 0, swapCount = 0, j;
while(i < n)
{
  if( Array[i] == Permute[i] )
  {
     i++;
  }
  else
  {
   j = findElementIndex( Permute, A[i] );
   Swap(A,i,j); // Swap i & j indexes elements
   swapCount++;
  }
}

correction

int main()
{

char input[] = {'a','b','c'};
char permute[3] = {};

permutations(input, permute, 3, 0);

return 0;
}

The Boyer-Moore Majority Vote Algorithm fails to find correct majority in the below input arrays

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

int numbers[SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

#include <iostream>
using namespace std;

class base{
};

class der : public base {
public:
	der() : base()
	{
		//base();
		cout<<"hello "<<endl;
	}
};

int main()
{
	der d;
	return 0;
}

int main()
{

	int a[] = { 1,4,6,2,3,0,5};
	int lcs[100], p[100];
	int i=0,j=0, maxIndex=0;
	//initialize
	int size = sizeof(a)/sizeof(a[0]);
	for(i=0; i < size; ++i)
	{
		lcs[i]=1;  p[i] = -1;
	}
	
	for(i=1; i< size; i++ )
	{
		for(j = i-1; j>=0; j-- )
		{
			if( (a[j] < a[i] ) && (lcs[i] < (lcs[j] + 1)))
			{
				lcs[i] = lcs[j]+1;
				p[i]  = j;
				if( lcs[maxIndex] < lcs[i] )
					maxIndex = i;
			}
		}
	}
	i = maxIndex;
	do
	{
		cout<<a[i]<<",";
		i = p[i];		
	}while(i!=-1);

	return 0;
}

Time complexity O(n2)

int LCS[1024][1024];

int LongestCommonSubsequence( char pattern1[], int m, char pattern2[], int n)
{
	if ( m >= 1024 || n >= 1024)
	{
		printf("\n too long pattern \n");
		return -1; // return error -1
	}
	else
	{
		int i=0,j=0;

		while(i<m)
		{
			LCS[i++][n] = 0;
		}
		while(j<n)
		{
			LCS[m][j++] = 0;
		}

		for( i = m-1; i>= 0 ; i-- )
		{
			for( j= n-1; j>=0 ;j--)
			{
				LCS[i][j] = LCS[i+1][j+1];

				if(Pattern1[i] == pattern2[j] )
					LCS[i][j]++;

				if( LCS[i+1][j] > LCS[i][j] )
					LCS[i][j] = LCS[i+1][j];
				if(LCS[i][j+1] > LCS[i][j])
					LCS[i][j] = LCS[i][j+1];
			}
		}
		return LCS[0][0];
	}
}

Time complexity O(mn)

NOTE: I am learning efficient programming(i.e.. time & space optimized code,easily understandable code).If you find any error in my below code, could you please let me know errors/suggestions in the code.

struct list
{
	int data;
	struct list *next;
};


int isPalindromeRecursive(struct list *header, struct list **traverseNode)
{
	if( (*traverseNode)->next == NULL )
	{		
		*traverseNode = header->next;		
		return 1;
	}
	else if((*traverseNode)->next->next == NULL)
	{		
		*traverseNode = header->next->next;
		return header->data == header->next->data; // when list contains even no. of nodes
	}
	else
	{
		*traverseNode = (*traverseNode)->next->next;
		if(!isPalindromeRecursive(header->next, traverseNode))
			return 0;
		if(header->data != (*traverseNode)->data)
		{			
			return 0;
		}
		else
		{
			*traverseNode = (*traverseNode)->next;
			return 1;
		}
	}
}

int isPalindrome(struct list *header)
{
	if( header == NULL )
	{
		printf("\n Invalid list \n");
		return -1; 
	}
	else if(header->next == NULL)
	{
		return 1;
	}
	else if( header->next->next == NULL )
	{
		return header->data == header->next->data;
	}
	else
	{
		struct list *traverseNode = header;
		if(isPalindromeRecursive(header, &traverseNode))
		{
			printf("\n list is Palindrome \n");
return 1;
		}
		else
		{
			printf("\n list is not Palindrome \n");
return 0;
		}
	}
}

NOTE: I am learning efficient programming(i.e.. time & space optimized code,easily understandable code).If you find any error in my below code, could you please let me know errors/suggestions in the code.

void mergingSortedArrays(int *A, int m, int *B, int n)
{
	int i = m-1, j = n-1, k = m+n-1;

	while( i >= 0 && j >= 0 )
	{
		if(B[j] >= A[i] )
		{
			B[k--] = B[j--] ;
		}
		else
		{
			B[k--] = A[i--] ;
		}
	}
	while( i >= 0 )
	{
		B[k--] = A[i--];
	}
}

Time complexity: O(n)
Space Complexity : O(1)