5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100

#include <iostream>
#include <cassert>

using namespace std;

int main()
{
    int N = 0x400, M = 0x15, i = 30, j = 30;

    assert(j < 32 && i >= 0); //assume 32bit int
    
    int mask = 0x0;
    int leng = j - i + 1;
    while (leng > 0)
    {
        mask = (mask << 1) | 0x1;
        leng--;
    }
    M = M & mask; //M may be truncated
    
    
    while (i > 0)
    {
        M = M << 1;
        --i;
    }
    N = N | M;
    
    cout << hex << N << endl;
    
    return 0;
}

4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i e , if you have a tree with depth D, you’ll have D linked lists)

/*
BFS
v1: stupid extra space comsumption
v2: not tested
*/

#include <iostream>
#include <vector>
#include <deque>
#include <cstdlib>

using namespace std;

class node
{
public:
    int val;
    node *next;
    node (int i):val(i), next(NULL){};
};

class tnode
{
public:
    int val;
    tnode *left;
    tnode *right;
    tnode (int i):val(i),left(NULL),right(NULL){};
};


//not effcient, used extra space
void linkListOfDepth(tnode *n, vector<node *>& res)
{
    if (n == NULL) return;
    
    res.push_back(new node(-1));
    deque<tnode *> queue;
    queue.push_back(n);
    queue.push_back(NULL);
    
    while (! queue.empty())
    {
        tnode *n = queue.front();
        queue.pop_front();
        
        if (n == NULL)
        {   
            if (! queue.empty()) //critical
            {
                res.push_back(new node(-1));
                queue.push_back(NULL);
            }
        }
        else
        {   
            node *tmp = res.back();
            while (tmp->next != NULL) tmp = tmp->next;
            tmp->next = new node(n->val);
            
            if (n->left  != NULL) queue.push_back(n->left);
            if (n->right != NULL) queue.push_back(n->right);
        }
    }
}

//no extra 'new' needed, not tested
void linkListOfDepth_v2(tnode *n, vector<tnode *>& res)
{
    if (n == NULL) return;
    
    deque<tnode *> queue;
    queue.push_back(n);
    queue.push_back(NULL);
    res.push_back(NULL);
    
    while (! queue.empty())
    {
        tnode *n = queue.front();
        queue.pop_front();
        
        if (n == NULL)
        {   
            if (! queue.empty()) //critical
            {
                res.push_back(NULL);
                queue.push_back(NULL);
            }
        }
        else
        {   
            
            if (res.back() == NULL) //NULL mark a begining of linklist
            {
                res.back() = n
            }
            else
            {
                node *tmp = res.back();
                while (tmp->left != NULL) tmp = tmp->left;
                tmp->left = n;
            }
            
            if (n->left  != NULL) queue.push_back(n->left);
            n->left = NULL; //critical
            if (n->right != NULL) queue.push_back(n->right);
        }
    }
}

int main()
{
    vector<node *> res;
    
    vector<tnode *> nvec(6);
    
    //build simulating tree
    for (int i = 0; i < 6; ++i)
    {
        nvec[i] = new tnode(i);
    }
    nvec[0]->left  = nvec[1];
    nvec[0]->right = nvec[2];
    nvec[1]->left  = nvec[3];
    nvec[2]->left  = nvec[4];
    nvec[2]->right = nvec[5];
    
    //method
    linkListOfDepth(nvec[0], res);
    
    //print out
    for (vector<node *>::iterator it = res.begin(); it != res.end(); ++it)
    {
        node *n = *it;
        n = n->next;
        while (n != NULL)
        {
            cout << n->val << ' ';
            n = n->next;
        }
        cout << endl;
    }
    
    //deconstruct
    for (int i = 0; i < 6; ++i)
    {
        delete nvec[i];
    }
    
    for (vector<node *>::iterator it = res.begin(); it != res.end(); ++it)
    {
        node *n = *it;
        while (n != NULL)
        {
            node *prev = n;
            n = n->next;
            delete prev;
        }
    }
    return 0;
}

4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

/*
Logic1:
Recursive
Logic2:
Iterative
*/

#include <iostream>
#include <deque>
#include <vector>
#include <utility>

using namespace std;

class node;
typedef deque<node*> nodePtrDeque;
typedef vector<int> intVector;
typedef const vector<int>& constIntVectorRef;
typedef vector<int>::const_iterator constIntVectorItr;
typedef pair<constIntVectorItr, constIntVectorItr> itrPair;
typedef pair<constIntVectorItr, constIntVectorItr>* itrPairPtr;

class node
{
public:
    int val;
    node * right;
    node * left;
    node(int v):val(v), right(NULL), left(NULL){};
};

constIntVectorItr mid(constIntVectorItr s, constIntVectorItr e)
{
    if (s > e)
    {
        return e + 1;
    }
    return ((e - s) % 2) ? (s + (e - s + 1) / 2) : (s + (e - s) / 2); 
};

node * helper(constIntVectorRef vec, constIntVectorItr s, constIntVectorItr e)
{
    if (s > e)
    {
        return NULL;
    }
    else
    {
        constIntVectorItr m = mid(s, e);
        node *n = new node(*m);
        n->left  = helper(vec, s, m - 1);
        n->right = helper(vec, m + 1, e);
        return n;
    }
};

node* Logic1(constIntVectorRef vec)
{
    if (vec.empty()) return NULL;
    /*
    uniformly use iterator of C++ feature. 
    If use pointers, then do keep them consistent.
    */
    return helper(vec, vec.begin(), vec.end() - 1);
};

node* Logic2(constIntVectorRef vec)
{
    if (vec.empty()) return NULL;
    
    node *root = NULL;
    
    constIntVectorItr s = vec.begin();
    constIntVectorItr e = vec.end() - 1;
    
    vector<itrPairPtr> stack; //stack the ranges
    nodePtrDeque nstack; //stack the parent for a range
    
    stack.push_back(new itrPair(s, e));
    nstack.push_back(NULL);
    
    while (! stack.empty())
    {
        itrPairPtr p = stack.back();
        stack.pop_back();
        node* anc = nstack.back();
        nstack.pop_back();
        
        if (p->first <= p->second)
        {
            constIntVectorItr m = mid(p->first, p->second);
            node* n = new node(*m);
            //cout << *m << endl;
            if (p->first == s && p->second == e)
            {
                root = n;
            }
            else
            {
                if (anc->val >= n->val && anc->left == NULL)
                {
                    anc->left = n;
                }
                else if (anc->val <= n->val && anc->right== NULL)
                {
                    anc->right = n;
                }
            }
            
            stack.push_back(new itrPair(p->first, m - 1));
            nstack.push_back(n);
            stack.push_back(new itrPair(m + 1, p->second));
            nstack.push_back(n);
        }
        delete p;
    }
    
    return root;
}

/*
This is better in logic
*/
node * Logic2_v2(const vector<int>& vec)
{
    if (vec.empty()) return NULL;
    
    typedef pair<const vector<int>::const_iterator, const vector<int>::const_iterator> mypair;
    
    const vector<int>::const_iterator s = vec.begin();
    const vector<int>::const_iterator e = vec.end() - 1;
    
    vector<mypair* > stack; //stack the ranges
    vector<node *> nstack; //stack the parent for a range
    
    stack.push_back(new mypair(s, e));
    const vector<int>::const_iterator m = mid(s, e);
    node* root = new node(*m);
    nstack.push_back(root);
    
    while (! stack.empty())
    {
        mypair* p = stack.back();
        stack.pop_back();
        node* anc = nstack.back();
        nstack.pop_back();
        
        if (p->first <= p->second)
        {
            const vector<int>::const_iterator m = mid(p->first, p->second);
            const vector<int>::const_iterator left  = mid(p->first, m - 1);
            const vector<int>::const_iterator right = mid(m + 1, p->second);
            if (left > m - 1)
            {
                anc->left = NULL;
            }
            else
            {
                node *ancleft = new node(*left);
                anc->left = ancleft;
                nstack.push_back(ancleft);
                stack.push_back(new mypair(p->first, m - 1));
            }
            if (right > p->second)
            {
                anc->right = NULL;
            }
            else
            {
                node *ancright = new node(*right);
                anc->right = ancright;
                nstack.push_back(ancright);
                stack.push_back(new mypair(m + 1, p->second));
            }      
        }
        delete p;
    }
    return root;
}

int main()
{
    int arr[10] = {0,1,2,3,4,5,6,7,8,9};
    intVector vec(arr, arr + 10);
    
    //node *root = Logic1(vec);
    //node *root = Logic2(vec);
    node *root = Logic2_v2(vec);
    
    //traverse and deconstruct
    node *n = NULL;
    nodePtrDeque queue;
    queue.push_back(root);
    /*
    set the NULL as level delimiter, made mistake here, be carefull about the logic
    */
    queue.push_back(NULL);
    while (! queue.empty())
    {
        n = queue.front();
        queue.pop_front();
        if (n == NULL)
        {
            cout << endl;
            if (! queue.empty())
                queue.push_back(NULL);
        }
        else
        {
            cout << n->val << ' ';
            if (n->left != NULL)
            {
                queue.push_back(n->left);
            }
            if (n->right != NULL)
            {
                queue.push_back(n->right);
            }
            delete n;
            n = NULL;
        }
    }
    return 0;
};

4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

/*
Logic1:
BFS-iterative
Logic2:
DFS-recursive
Logic3:
DFS-iterative
*/

#include <iostream>
#include <deque>
#include <vector>
#include <cassert>

using namespace std;

/*
Avoid pollution of global namespace
Stupid C++ Tricks #2: Better Enums

*/
namespace STATS
{
    enum Enum
    {
        UNVISIT,
        VISITED,
        FINISHED
    };
}
    
class node
{
public:
    int val;
    STATS::Enum stat;
    deque<node *> adj;
    
    node(int i):val(i),stat(STATS::UNVISIT){};
};

bool logic1(node * src, node * des)
{
    if (src == NULL || des == NULL) return false;
    node *n = NULL;
    deque<node *> queue;
    
    queue.push_back(src);
    src->stat = STATS::VISITED;
    
    while (! queue.empty())
    {
        n = queue.front();
        queue.pop_front();
        if (n == des)
        {
            return true;
        }
        else
        {
            for (deque<node*>::iterator dit = n->adj.begin(); dit != n->adj.end(); ++dit)
            {
                if ((*dit)->stat == STATS::UNVISIT)
                {
                    queue.push_back(*dit);
                    (*dit)->stat = STATS::FINISHED;
                }
            }
        }
    }
    return false;
};

/*
Return value
*/
bool logic2(node * src, node * des)
{
    if (src == NULL || des == NULL) return false;
    bool n = false;
    for (deque<node*>::iterator dit = src->adj.begin(); dit != src->adj.end(); ++dit)
    {
        if ((*dit) == des)
            return true;
        else
        {
            if ((*dit)->stat == STATS::UNVISIT)
            {   
                (*dit)->stat = STATS::VISITED;
                n = n || logic2((*dit), des);
            }
        }
    }
    return n;
};

bool logic3(node * src, node * des)
{
    if (src == NULL || des == NULL) return false;
    node *n = NULL;
    deque<node *> stack;
    
    stack.push_back(src);
    src->stat = STATS::VISITED;
    
    while (! stack.empty())
    {
        node *n = stack.back();
        stack.pop_back();
        
        if (n == des)
        {
            return true;
        }
        else
        {
            for (deque<node*>::iterator dit = n->adj.begin(); dit != n->adj.end(); ++dit)
            {
                if ((*dit)->stat == STATS::UNVISIT)
                {
                    stack.push_back(*dit);
                    (*dit)->stat = STATS::FINISHED;
                }
            }
        }
    }
    return false;
};

void restore(vector<node *>& nvec)
{
    for (vector<node *>::iterator vit = nvec.begin(); vit != nvec.end(); ++vit)
    {
        (*vit)->stat = STATS::UNVISIT;
    }
};

int main()
{
    //create nodes
    vector<node *> nvec(5);
    for (int i = 0; i < 5; ++i)
    {
        nvec[i] = new node(i);
    }
    
    //build edges
    nvec[0]->adj.push_back(nvec[1]);
    nvec[1]->adj.push_back(nvec[4]);
    nvec[1]->adj.push_back(nvec[2]);
    nvec[2]->adj.push_back(nvec[0]);
    nvec[3]->adj.push_back(nvec[1]);
    nvec[3]->adj.push_back(nvec[2]);
    nvec[4]->adj.push_back(nvec[2]);
    
    cout << logic1(nvec[3], nvec[4]) << endl;
    restore(nvec);
    cout << logic1(nvec[0], nvec[3]) << endl;
    restore(nvec);
    cout << logic2(nvec[3], nvec[4]) << endl;
    restore(nvec);
    cout << logic2(nvec[0], nvec[3]) << endl;
    restore(nvec);
    cout << logic3(nvec[3], nvec[4]) << endl;
    restore(nvec);
    cout << logic3(nvec[0], nvec[3]) << endl;
    
    for (int i = 0; i < 5; ++i)
    {
        delete nvec[0];
        nvec[0] = NULL;
    }
    return 0;
}

4.1 Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

#include <iostream>
#include <climits>

struct Node
{
    Node *right;
    Node *left;
};
    
class Solution
{
    void helper(Node* n, int depth, int& min, int& max)
    {
        if (n->left == NULL && n->right == NULL)
        {
            if (depth < min) min = depth;
            if (depth > max) max = depth;
            return;
        }
        
        if (n->left != NULL)
        {
            helper(n->left, depth + 1, min, max);
        }
        
        if (n->right != NULL)
        {
            helper(n->right, depth + 1, min, max);
        }
    }
    
public:
    
    bool isBalance(Node* root)
    {
        /*min and max are two "GLOBAL" vars, while depth is local*/
        int min = INT_MAX, max = INT_MIN;
        helper(root, 0, min, max);
        return (max - min > 1) ? 0 : 1;
    }
};

int main()
{
    Node nnode[5];
/*
When writing in C-style, nerver forget to
explicitly initialize structs members or array members.
Or use Class or Stl containers instead.
*/
    for(int i = 0; i < 5; ++i)
    {
        nnode[i].left = NULL;
        nnode[i].right = NULL;
    }
    nnode[0].left = &nnode[1];
    nnode[0].right = &nnode[2];
    nnode[1].left = &nnode[3];
    nnode[3].right = &nnode[4];
    Solution S;
    std::cout << S.isBalance(nnode) << std::endl;
    return 0;
}

3.5 Implement a MyQueue class which implements a queue using two stacks.

/*
Logic1: LAZY Dump
*/

#include <stack>
#include <iostream>
#include <cassert>

using namespace std;

template <class T>
class MyQueue
{

private:
    /*
    BIG BUG: typedef stack<T>*, StkPtr;
    COMMA IS NOT NEEDED
    */
    typedef stack<T>* StkPtr;
    StkPtr front, rear;
    
    void _dump(StkPtr des, StkPtr src)
    {
        while (! src->empty())
        {
            des->push(src->top());
            src->pop();
        }
    };
    
public:
    
    MyQueue()
    {
        front = new stack<T>;
        rear = new stack<T>;
    };
    
    ~MyQueue()
    {
        delete rear;
        rear = NULL;
        delete front;
        front = NULL;
    };
    
    T pop_front()
    {
        assert((!front->empty()) || (!rear->empty()));
        if (rear->empty())
        {
            _dump(rear, front);
        }
        T rval = rear->top();
        rear->pop();
        return rval;
    };
    
    void push_back(T ele)
    {
        if (front->empty())
        {
            _dump(front, rear);
        }
        front->push(ele);
    };
    
};

int main()
{
    MyQueue<int> mq;
    mq.push_back(1);
    mq.push_back(3);
    cout << mq.pop_front() << endl;
    cout << mq.pop_front() << endl;
    mq.push_back(4);
    cout << mq.pop_front() << endl;
    mq.push_back(5);
    cout << mq.pop_front() << endl;
    return 0;
}

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

#include <iostream>
#include <stack>
#include <climits>
#include <cassert>

using namespace std;

class MinStack
{
private:

    stack<int> *s;
    stack<int> *m;

public:
    
    MinStack()
    {
        s = new stack<int>();
        m = new stack<int>();
        m->push(INT_MAX);
    };
    
    virtual ~MinStack()
    {
        delete m;
        m = NULL;
        delete s;
        s = NULL;
    };
    
    void push(int ele)
    {
        s->push(ele);
        if (ele < m->top())
        {
            m->push(ele);
        }
    };
    
    int pop()
    {
        /*
        CAUTION: Check Overflow and Underflow
        */
        assert(! s->empty());
        int rval = s->top();
        s->pop();
        if (rval == m->top())
        {
            m->pop();
        }
        return rval;
    };
    
    int min()
    {
        assert(m->top() != INT_MAX);
        return m->top();  
    };
};


int main()
{
    MinStack s;
    s.push(10);
    s.push(5);
    cout << s.min() << endl;
    s.push(8);
    s.push(2);
    cout << s.min() << endl;
    s.pop();
    cout << s.min() << endl;
    return 0;
}

3.1 Describe how you could use a single array to implement three stacks.

/*
Logics:
1. {->|      |<-|      <-]
stacks 1&2 share a segment of array and stack 3 has a fixed length.
Samewise, we can also use %3 to idx the elements of stacks.

2. See approach two in the Solution, its space complexity is high.
I don't like this idea.
*/
#include <iostream>
#include <cassert>

using namespace std;

class Stack{
    static const int SIZE = 3;
    static const int STACKNUM = 3;
    int* array;
    int* last;
    int num;
public:
    Stack(int i = 3):num(i){
        assert(i > 0 && i <= STACKNUM);
        array = new int[num * SIZE];
        for (int i = 0; i < num * SIZE; ++i){
            array[i] = 0;
        }
        last = new int[num];
        for (int i = 0; i < num; ++i){
            last[i] = i;
        }
    }
    virtual ~Stack(){
        delete []array;
        delete last;
        array = last = NULL;
    }
    void push(int stackNum, int val){
        assert (stackNum >0 && stackNum <= num);
        assert (last[stackNum - 1] < num * SIZE);
        array[last[stackNum - 1]] = val;
        last[stackNum - 1] += num;
    }
    void pop(int stackNum){
        assert (stackNum >0 && stackNum <= num);
        assert (last[stackNum - 1] >= 0);
        last[stackNum - 1] -= num;
    }
    int top(int stackNum){
        assert (stackNum >0 && stackNum <= num);
        assert (last[stackNum - 1] - num >= 0);
        return array[last[stackNum - 1] - num];
    }
};

int main(){
    Stack* stack = new Stack(3);
    stack->push(1, 1);
    stack->push(1, 2);
    stack->push(1, 3);
    //stack->push(1, 3);
    stack->pop(1);
    stack->pop(1);
    //stack->pop(1);
    cout << stack->top(1) << endl;
    stack->push(2, 3);
    cout << stack->top(2) << endl;
    //stack->push(100, 3);
    //cout << stack->top(100) << endl;
    return 0;
}

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node EXAMPLE Input: the node ‘c’ from the linked list a->b->c->d->e Result: nothing is returned, but the new linked list looks like a->b->d->e

/*
Logics
1. keep the structure, while shift the value O(n)
2. a->b->c->e delete c instead of b, and set the value of b to c O(1)

I didn't realize "This problem can not be solved if the node to be deleted is the last node 
in the linked list"

practise coding in C.
*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

struct node{
    char val;
    node* next;
};

void append(node* head, char c){
    assert(head != NULL);
    node *nc = (node*)malloc(sizeof(node));
    nc->val = c;
    nc->next = NULL;
    while (head->next != NULL){
        head = head->next;
    }
    head->next = nc;
}

node* find(node* head, char c){
    assert(head != NULL);
    while (head != NULL){
        if (head->val == c){
            return head;
        }
        head = head->next;
    }
    return NULL;
}

void deleteN(node* n){
    assert(n != NULL);
    assert(n->next != NULL);
    node *tmp = n->next;
    n->val = n->next->val;
    n->next = n->next->next;
    free(tmp);
}

void freeN(node* head){
    if (head == NULL) return;
    while(head->next != NULL){
        node* tmp = head->next;
        free(head);
        head = tmp;
    }
}

void print(node *head){
    if (head == NULL) return;
    while(head->next != NULL){
        printf("%c ", head->val);
        head = head->next;
    }
    printf("%c ", head->val);
}

int main(){
    node* head = (node*)malloc(sizeof(node));
    head->val = 'a';
    head->next = NULL;
    append(head, 'b');
    append(head, 'c');
    append(head, 'd');
    append(head, 'e');
    deleteN(find(head, 'c'));
    print(head);
    freeN(head);
    return 0; 
}

2.2 Implement an algorithm to find the nth to last element of a singly linked list

/*
Logics
1. two pointers solution O(n) one screen
2. find length and length - n; two screens
3. bruteforce, O(n^2)

Seek for bug free code.
*/
#include <list>
#include <cassert>
#include <iostream>

using namespace std;

typedef list<int>::const_iterator lit;

int findNthToLast(list<int> const & l, int n){
    lit p1 = l.begin(), p2 = l.begin();
    while (n > 0){
        ++p2; --n;
        assert(p2 != l.end());
    }
    while (p2 != l.end()){
        ++p1; ++p2;
    }
    return *(--p1);
}

/*
BUG
void helper(lit p, lit e, int s, int n, int& ans){
*/
void helper(lit p, lit e, int s, int& n, int& ans){
    /*
    BUG
    if (n == 0) ans = *p;
    */
    
    /*
    list iterator doesn't support +(int) only ++ and --
    note that I am mistakenly try to random access an element
    if (p + 1 != e){
    */
    
    /*
    Classic Paradigm of Backtracking!!!
    */
    if (p != e){
        ++p; ++s;
        helper(p, e, s, n, ans);  
        --p; --s;
        assert(n <= s);
        if (n == 0) ans = *p;
        --n;
    }
}

int recursivefindNthToLast(list<int> const & l, int n){
    int ans = 0;
    helper(l.begin(), l.end(), 0, n, ans);
    return ans;
}

int main(){
    int a[4] = {1, 2, 3, 4};
    list<int> l(a, a+4);
    cout << findNthToLast(l, 0) << endl;
    cout << findNthToLast(l, 1) << endl;
    cout << findNthToLast(l, 2) << endl;
    cout << findNthToLast(l, 3) << endl;
    //cout << findNthToLast(l, 5) << endl;
    cout << recursivefindNthToLast(l, 0) << endl;
    cout << recursivefindNthToLast(l, 1) << endl;
    cout << recursivefindNthToLast(l, 2) << endl;
    cout << recursivefindNthToLast(l, 3) << endl;
    cout << recursivefindNthToLast(l, 5) << endl;    
}

/*
I didn't realize its recursion nature.
in recursion, you always reach the last element first, and then backtrack.
Think about DFS
*/