Reverse a Stack Using Recursion

I am back! I will talk about how to reverse a stack using recursion (note: recursion means we need the function call stack....)
Given a stack S=<0, 1, 2, ..., 8, 9>, where 9 is the topmost element. The reversed stack S' is <9, 8, ..., 2, 1, 0>.  The basic idea is to reverse the smaller stack subS=<0, 1, 2, ..., 8> first to get subS'=<8, ..., 2, 1, 0>, and then put 9 at the bottom of subS' to get S'. So:

void reverse_stack(stack<int> &s){
    if(!s.empty()){
        int ele = s.top();
        s.pop();
        reverse_stack(s);
        put_bottom(s, ele);
    }
}

But how to put an element at the bottom of a stack? we still can use recursion!

void put_bottom(stack<int> &s, int ele){
    if(s.empty()){
        s.push(ele);
        return;
    }
    int topEle=s.top();
    s.pop();
    put_bottom(s, ele);
    s.push(topEle);
}

Divide Two Integers [Leetcode]

Divide two integers without using multiplication, division and mod operator.

Solution: bit manipulation [check here for original solution]

class Solution {
public:
    int divide(int dividend, int divisor) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(divisor==0) return 0; //error
        long long a = abs(double(dividend));
        long long b = abs(double(divisor));
        long long r = 0;
        while(a>=b){
            long long c = b;
            for(int i=0; c<=a; i++, c<<=1){
                a-=c;
                r+=(1<<i);
            }
        }
        return (dividend^divisor)>>31?-r:r;
    }
};

Deepest Left Leaf Node in a Binary Tree [GeeksforGeeks]

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

       1
     /   \
    2     3
  /      /  \  
 4      5    6
        \     \
         7     8
        /       \
       9         10

Check here for more detailed info.

Solution: we recursively traverse the given binary tree. During the traversal, we record the level of the current node and the maxLevel (the level of the deepest left leaf node found so far). If we are encountering a left leaf node and it's level is greater than maxLevel, we know this leaf node is the most recent deepest left leaf node. [Part of code is from GeeksforGeeks]

#include <iostream>
using namespace std;

struct Node{
    int val;
    struct Node *left, *right;
};

Node *newNode(int data){
    Node *temp = new Node;
    temp->val = data;
    temp->left = temp->right =  NULL;
    return temp;
}

void deepestLeftLeaf(Node *root, bool isLeft, int level, int& maxLevel, Node * &ret){
    // Base case
    if (root==NULL)
        return;
    //Update result if 'root' is the deepest left leaf node so far
    if(root->left==NULL && root->right==NULL){
        if(isLeft && level>maxLevel){
            maxLevel = level;
            ret = root;
        }
        return;
    }
    //Recursively find the obj. in its two substrees
    deepestLeftLeaf(root->left, true, level+1, maxLevel, ret);
    deepestLeftLeaf(root->right, false, level+1, maxLevel, ret);
}


// Driver program to test above function
int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    root->right->left->right->left = newNode(9);
    root->right->right->right->right = newNode(10);

    int maxLevel = 0;
    Node *ret = NULL;
    deepestLeftLeaf(root, false, 0, maxLevel, ret);

    if (ret)
        cout << "The deepest left child is " << ret->val << endl;
    else
        cout << "There is no left leaf in the given tree" << endl;

    return 0;
}

Evaluate Reverse Polish Notation [Leetcode]

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Solution: I implemented the algorithm provided in Reverse Polish Notation.

class Solution {
public:
    bool isOperator(string token){
        return token=="+" || token=="-" || token=="*" || token=="/";
    }
    int cal(int lOperand, int rOperand, string op){
        if(op=="+")
            return lOperand+rOperand;
        if(op=="-")
            return lOperand-rOperand;
        if(op=="*")
            return lOperand*rOperand;
        return lOperand/rOperand;
    }
    int evalRPN(vector<string> &tokens) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(tokens.empty())
            return INT_MIN;
        stack<int> s;
        for(size_t i=0; i<tokens.size(); ++i){
            if(isOperator(tokens[i])){
                if(s.size()>=2){
                    int rOperand = s.top();
                    s.pop();
                    int lOperand = s.top();
                    s.pop();
                    s.push(cal(lOperand, rOperand, tokens[i]));
                }
                else
                    return INT_MIN;
            }
            else
                s.push(stoi(tokens[i]));
        }
        if(s.size()==1)
            return s.top();
        return INT_MIN;
    }
}; 

Trie Implementation in C++ [GeeksforGeeks]

Check here for node insertion and searching, and here for node removal. In addition, I used postorder traversal to delete the entire tree.

#include <iostream>
#include <unordered_map>

using namespace std;

struct TrieNode{
    bool leaf;
    unordered_map<char, TrieNode*> children;
    TrieNode():leaf(false), children(){}
};

class Trie{
private:
    TrieNode* root;
public:
    Trie():root(new TrieNode()){}
    ~Trie(){ 
        deleteTrie(root); 
    } 
    //Insert a given word
    void addWord(string s){
        cout << "Insert: " << (s.empty()?"empty string":s) << endl;
        TrieNode* cur = root;
        for(size_t i=0; i<s.size(); ++i){
            if(cur->children.count(s[i])==0)
                cur->children[s[i]] = new TrieNode();
            cur = cur->children[s[i]];
        }
        cur->leaf= true;
    }
    //Search a given word
    bool searchWord(string s){
        cout << "Search: " << (s.empty()?"empty string":s) << endl;
        if(root==NULL)
            return false;
        TrieNode* cur = root;
        for(size_t i=0; i<s.size(); ++i){
            if(cur->children.count(s[i])==0)
                return false;
            cur = cur->children[s[i]];
        }
        return cur->leaf;
    }
    //Delete a given word
    void delWord(string s){
        cout << "Delete: " << (s.empty()?"empty string":s) << endl;
        if(root==NULL)
            return;
        if(s.empty()){
            cout << "Deleting node: empty string"<< endl;
            root->leaf=false;
        }
        delWordHelper(s, root, 0);
    }
    //delword helper
    bool delWordHelper(string s, TrieNode* r, size_t cur){
        cout << "\tGo deep: "<< s[cur] << endl;        
        if(r==NULL)
            return false;
        if(cur==s.size()){ //base case
            r->leaf = false; //unmark the leaf
            if(r->children.size()!=0) //if s is a prefix of other string
                return false;
            return true;
        }
        else{
            if(r->children.count(s[cur])==0) //if can not find s
                return false;
            if(delWordHelper(s, r->children[s[cur]], cur+1)){
                //delete eligible nodes
                cout << "\tDeleting node: "<< s[cur] << endl;
                delete r->children[s[cur]];
                r->children.erase(s[cur]);
                //recursively climb up, and delete eligible nodes
                return r->children.empty() && r->leaf==false;
            }
            return false;
        }
    }
    //Delete the trie following post-order traversal
    void deleteTrie(TrieNode* r){
        if(r==NULL)
            return;
        for(size_t i=0; i<r->children.size(); i++)
            deleteTrie(r->children[i]);
        delete r;
        r = NULL;
    }
    //To avoid shallow copy, you may need to give 
    //copy constructor and overload assignment operator
    Trie(const Trie&);
    Trie& operator=(const Trie&);
};
int main(){
    Trie t = Trie();
    t.addWord("");
    t.addWord("Hello");
    t.addWord("Balloon");

    if (t.searchWord("Hell")) 
        cout << "Found Hell" << endl;
    if (t.searchWord("Hello"))
        cout << "Found Hello" << endl;
    if (t.searchWord("Helloo"))
        cout << "Found Helloo" << endl;
    if (t.searchWord("Ball"))
        cout << "Found Ball" << endl;
    if (t.searchWord("Balloon"))
        cout << "Found Balloon" << endl;
    if (t.searchWord(""))
        cout << "Found empty string" << endl;

    t.delWord("Balloon");
    if (t.searchWord("Balloon"))
        cout << "Found Balloon" << endl;
        
    t.addWord("Balloon");
    t.addWord("Ball");

    t.delWord("Balloon");
    t.delWord("");
    if (t.searchWord(""))
        cout << "Found empty string" << endl;
    return 0;
}

Max Points on a Line [Leetcode]

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution: the key point here is how to check if three points are in the same line, i.e., collinear. Give points i, j, k, we say they are in the same line iff (j.y-i.y)*(k.x-j.x)-(k.y-j.y)*(j.x-i.x)=0. The time complexity is O(n^3). [Note computing the slope of a line is not a good way]

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    //Check if three points, i, j and k, are collinear
    bool sameLine(Point i, Point j, Point k){
        return (j.y-i.y)*(k.x-j.x)-(k.y-j.y)*(j.x-i.x)==0;
    }
    //Check if all points are the same
    bool allSamePoints(vector<Point> &points){
        int i=0;
        while(i<points.size()){
            if(points[i].x!=points[0].x || points[i].y!=points[0].y)
                break;
            ++i;
        }
        return i==points.size();
    }
    int maxPoints(vector<Point> &points) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(points.size()<=1 || allSamePoints(points))
            return points.size();
        int maxPoints = 2;
        for(int i=0; i<points.size(); ++i){
            for(int j=i+1; j<points.size(); ++j){
                if(points[i].x==points[j].x && points[i].y==points[j].y)
                    continue;
                int count = 2;
                for(int k=0; k<points.size(); ++k){
                    if(k!=i && k!=j && sameLine(points[i], points[j], points[k]))
                        count++;
                }
                maxPoints = max(maxPoints, count);
            }
        }
        return maxPoints;
    }
};

17.4 [CTCI]

Write a method which finds the maximum of two integers. You should not use if-else or any other comparison operator.

Solution: Given two numbers a and b: one straightforward idea is to check the sign of a-b; if a-b>0, return a, otherwise b; but it is possible that a-b overflows if a and b have different signs. So we can not do this way. We need to consider two cases:
1. a and b have the same signs: return a if a-b>0, otherwise b;
2. a and b have different signs: return a if a>0, otherwise b;
We define k=1 iff (sign(a)=sign(b) && a-b>0)  OR (sign(a)!=sign(b)&&a>0) and p to be inverse of k, i.e., 1^k. Then, the maximum of a and b is a*k+b*p.

int sign(int a){
    return 1^(a>>31 && 1);
}
int getMax(int a, int b){
    int c = a-b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    
    int diff = sa ^ sb;
    int same = 1^diff;
    int k = sc*same + sa*diff;
    int p = 1^k;
    return a*k+b*p;
}