CareerCup

/*void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);
	
	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);
	
	nTemp--;

	int p, q;

	p = 0;
	q = 0;

	for (int i = 0; i <= nTemp; i++)
	{
		for (int k = 0; k < n; k++)
		{
			if ((i >> k) & 0x1)
			{
				permutationArr[p][q] = 1;
			}
			else
			{
				permutationArr[p][q] = 0;
			}

			if (k != n - 1)
			{
				q++;
			}
		}

		p++;
		q = 0;
	}
}
*/

void calcPermutation(int n, vector<vector<int>> &permutationArr)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n);

	permutationArr.resize(nTemp);
	for (int i = 0; i < nTemp; i++)
		permutationArr[i].resize(n);


	int val = 0;
	int p, q, calc;

	p = 0;
	

	while (val < nTemp)
	{
		q = 0;
		calc = val;
		while (q < n)
		{
			permutationArr[p][q] = calc % 2 ? 0 : 1;
			calc = calc/2;
			q++;
		}
		p++;
		val++;
	}

}


void replaceString(string input)
{
	int i,j;
	int len = strlen(input.c_str());
	int qCount = 0;
	int *qIndexArr = new int[len];

	j = 0;
	for (i = 0; i < len; i++)
	{
		if (input[i] == '?')
		{
			qIndexArr[j] = i;
			j++;
			qCount++;
		}
	}

	if (qCount == 0)
	{
		cout << input << endl;
		return;
	}

	vector<vector<int>> permutationArr;		
	calcPermutation(qCount, permutationArr);
	list<string> l;
	char *temp = new char;

	for (i = 0; i < permutationArr.size(); i++)
	{
		for (j = 0; j < qCount; j++)
		{
			 temp = itoa(permutationArr[i][j],temp, 10);
			input[qIndexArr[j]] = *temp;
		}
		l.push_back(input);
	}

	list<string>::iterator it;

	cout << "Answers is:";
	for (it = l.begin(); it != l.end(); ++it)
	{
		std::cout << ' ' << *it;
		std::cout << '\n';
	}
	
}


int main(int argc, char* argv[])
{
	replaceString("a?b?c?");
	return 0;
}

bool findIfSubSequesnce(string input)
{
map<char, int> m;
map<char, int>::iterator iter;
int i,j;
int len = strlen(input.c_str());
bool isCharRepeated=false;

/*

Step 1: Scan the string to count the number of each letter.
(mean while if the count of any letter
is 4 or more, we already find a repetition of two character, the same character followed by itself and return YES)
If no character is repeated, return NO.
*/

for (i = 0; i < len; i++)
{
iter = m.find(input[i]);
if (iter != m.end())
{
iter->second++;
isCharRepeated = true;
if (iter->second >= 4)
return true;
}
else
{
m.insert(pair<char, int>(input[i], 1));
}

}

if (!isCharRepeated)
return false;

/*
Step 2: Scan second time and append each letter that has been repeated (using the count array from the first step) to a new string (let say a StringBuilder)
*/

string str = "";
for (i = 0; i < len; i++)
{
iter = m.find(input[i]);
if (iter != m.end())
{
if (iter->second > 1)
str += input[i];
}
}


/*
Step 3: If the new string is not palindrom, return YES.
else if newString.length() is odd and the middle is different from one previous return YES.

return NO.
*/
len = strlen(str.c_str());
for (i = 0, j = len - 1; i < j; i++, j--)
{
if (str[i] != str[j])
return true;
}
if (i == j)
{
if (str[i - 1] != str[i])
return true;
else
return false;
}
else
return false;
}


int main(int argc, char* argv[])
{
bool ans = findIfSubSequesnce("abcdacb");
return 0;
}

struct Node {
	int val;
	int index;
	vector<Node*> children;
};

void createTree(Node *head)
{
	Node *node, *qNode;
	char ch;
	queue<Node *> q;

	cout << "Enter value of head node: ";
	cin >> head->val;
	head->index = 0;

	q.push(head);



	while (!q.empty())
	{
		qNode = q.front();
		q.pop();

		cout << "do you want to add child of " << qNode->val << "?" << endl;
		cin >> ch;

		while (ch == 'y' || ch == 'Y')
		{
			node = new Node();
			cout << "Enter value of head node: ";
			cin >> node->val;
			node->index = 0;

			qNode->children.push_back(node);
			q.push(node);
			cout << "do you want to add another child of " << qNode->val << "?" << endl;
			cin >> ch;

		}

	}
}

//Recursive solution
void postorderRec(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	if (head->children.empty())
		cout << head->val << " ";
	else
	{
		for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
		{
			postorderRec(*iter);
		}
		cout << head->val << " ";
	}

}


//Iterative solution
void postorderiTer(Node *node)
{
	if (node == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	stack <Node *>st;
	Node *temp;

	st.push(node);

	while (!st.empty())
	{
		temp = st.top();


		if (temp->index < temp->children.size())
		{
			node = temp->children[temp->index];
			temp->index++;
			st.push(node);
		}
		else
		{
			st.pop();
			cout << temp->val << " ";
		}

	}
	
}

int main()
{
	Node *head =  new Node();
	createTree(head);
	postorderRec(head);
	cout << endl;
	postorderiTer(head);
	return 0;
}

struct Node {
	int val;
	vector<Node*> children;
};

void createTree(Node *head)
{
	Node *node, *qNode;
	char ch;
	queue<Node *> q;

	cout << "Enter value of head node: ";
	cin >> head->val;

	q.push(head);



	while (!q.empty())
	{
		qNode = q.front();
		q.pop();

		cout << "do you want to add child of " << qNode->val << "?" << endl;
		cin >> ch;

		while (ch == 'y' || ch == 'Y')
		{
			node = new Node();
			cout << "Enter value of head node: ";
			cin >> node->val;

			qNode->children.push_back(node);
			q.push(node);
			cout << "do you want to add another child of " << qNode->val << "?" << endl;
			cin >> ch;

		}

	}
}

//Recursive solution
void postorderRec(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	if (head->children.empty())
		cout << head->val << " ";
	else
	{
		for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
		{
			postorderRec(*iter);
		}
		cout << head->val << " ";
	}

}


//Iterative solution
void postorderiTer(Node *node)
{
	if (node == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	stack <Node *>st;
	map<Node *, int> m;
	Node *temp;
	int index;

	st.push(node);
	m.insert(pair<Node *,int>(node, 0));


	while (!st.empty())
	{
		temp = st.top();
		index = m.find(temp)->second;

		if (index < temp->children.size())
		{
			m.find(temp)->second++;
			node = temp->children[index];
			st.push(node);
			m.insert(pair<Node *, int>(node, 0));
		}
		else
		{
			st.pop();
			cout << temp->val << " ";
		}

	}
	
}

int main()
{
	Node *head =  new Node();
	createTree(head);
	postorderRec(head);
	cout << endl;
	postorderiTer(head);
	return 0;
}

I think you want to do right-- in below else condition

else{
			right++;
		}