Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

string stringMultip(string &A, string &B) {

	string res(A.size() + B.size(), '0');
	
	string::reverse_iterator rit1, rit2, rit3, rit4;
	int num_a, num_b, num_c, num_carry, num_res, i;
	
	for(rit1 = A.rbegin(), rit3 = res.rbegin(); rit1 != A.rend(); rit1 ++, rit3 ++) {
		
		num_a = (*rit1) - '0';
		num_carry = 0;
		
		for(rit2 = B.rbegin(), rit4 = rit3; rit2 != B.rend(); rit2 ++, rit4 ++) {
			
			num_b = (*rit2) - '0';
			num_c = (*rit4) - '0';
			
			num_res = num_a * num_b + num_c + num_carry;
			num_carry = num_res / 10;
			(*rit4) = '0' + (num_res % 10);
		}

		// put the carry back to the result
		(*rit4) = '0' + num_carry;
	}

	// remove leading '0's
	for(i = 0; i < res.size(); i ++)
		if(res[i] != '0') 
			break;

	return res.erase(0, i);
}

The following provides a simple test case.

#include <iostream>
#include <string>

using namespace std;

int main ()
{
	string A("123456");
	string B("294987");
	string C("123");
	string D("234");	

	cout << stringMultip(A, B) <<endl;
	cout << stringMultip(C, D) <<endl;
	
	return 0;
}

The problem:
Given a binary tree, return the postorder traversal of its nodes’ values. For example, given binary tree:
a              1
b           /      \
c        4           2
d          \       /
e           10  3
return [10, 4, 3, 2, 1]

#include <iostream>
#include <stack>
#include <string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {};
};

int postorderTraversal(TreeNode *root) {

    const TreeNode *p = root;
    stack<const TreeNode*> s;

    if(p!=nullptr) {
        TreeNode x(p->val);
        s.push(&x);

        if(p->right != nullptr) s.push(p->right);
        if(p->left != nullptr) s.push(p->left);
    }

    while(!s.empty()) {

        p = s.top();
        s.pop();

        if(p->left == nullptr && p->right == nullptr)
            printf("%d\n", p->val);
        else {
            TreeNode x(p->val);
            s.push(&x);

            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
        }
    }

    return 0;
}

int main() {

    TreeNode root(1);
    TreeNode node1(2);
    TreeNode node2(3);
    TreeNode node3(4);
    TreeNode node4(10);

    root.left = &node3;
    root.right = &node1;
    node1.left = &node2;
    node3.right = &node4;

    postorderTraversal(&root);

    return 0;
}

The similar code structure could be used for binary tree inorder traversal. The key idea here is to create a temporary node which holds only the value and push it into the stack. Whenever we meet a node without both childern, we print out its value.

The Problem:

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well formed) parentheses sub-strings.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int longest_valid_parentheses(string const& s) {

    int count = 0, max_count = 0;
    stack<char> stk;

    for(auto c : s) {

        if(c == '(')
            stk.push(c);
        else {
            if( stk.empty() ) //|| stk.top() != '(')
                count = 0;
            else {
                count += 2;
                stk.pop();
            }
        }

        max_count = count > max_count ? count : max_count;
    }

    return max_count;
}

You can test the above code using the following test cases @ http://www.cpp.sh/.

int main()
{
  string test1("(()");
  string test2("(()()(");
  string test3(")()()))(((())))");

  cout << "there are " << longest_valid_parentheses(test1) << " valid parentheses in " << test1 << endl;
  cout << "there are " << longest_valid_parentheses(test2) << " valid parentheses in " << test2 << endl;
  cout << "there are " << longest_valid_parentheses(test3) << " valid parentheses in " << test3 << endl;

  return 0;
}

The output would look like as the follows:

there are 2 valid parentheses in (() 
there are 4 valid parentheses in (()()( 
there are 8 valid parentheses in )()()))(((())))

Given a sorted linked list, remove all the duplicates from the list. For example, given 1->2->3->3->6, return 1->2->6. Another example, given 1->1->1->2->4, return 2->4.

typedef struct node Node;

/* The function removes duplicates from a sorted list */
void removeDuplicates(Node** head)
{ 
  /* do nothing if the list is empty */
  Node* current = *head;  
  if(current == NULL)
     return;

  /* Pointer to traverse the linked list */
  Node* pre_head = (Node*) malloc(sizeof(Node));
  pre_head->next = *head;

  /* Pointer to store the next pointer of a node to be deleted*/
  Node* next_next;
  Node* pre = pre_head;
  bool deleted = false;
 
  /* Traverse the list till last node */
  while(current->next != NULL)
  {
   /* Compare current node with next node */
    if(current->data == current->next->data) {       
		/*The sequence of steps is important*/              
		next_next = current->next->next;
		free(current->next);
		current->next = next_next;
		deleted = true;
    }
    else if (deleted)  {
		pre->next = current->next;
		free(current);
		current = pre->next;
		deleted = false;
    }
	else {
		pre = current;
		current = current->next;
    }
  }

  /* remove the last duplicated node*/
  if (deleted) {
	  pre->next = NULL;
	  free(current);
  }
  
  *head = pre_head->next;
  free(pre_head);
}
 

To test the code, please use the testing program from http://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/.