Letter Combinations of a Phone Number

class Solution {
public:
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        string mapping[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        res.clear();
        string s;
        letterCombinationsRe(digits, mapping, s);
        return res;
    }
    void letterCombinationsRe(const string &digits, string mapping[], string &s)
    {
        if (s.size() == digits.size())
        {
            res.push_back(s);
            return;
        }
        string &letters = mapping[digits[s.size()]-'2'];
        for (int i = 0; i < letters.size(); ++i)
        {
            s.push_back(letters[i]);
            letterCombinationsRe(digits, mapping, s);
            s.pop_back();
        }
    }

};

class Solution {
public:
unordered_map<char, string> dig2char;
Solution()
{
    dig2char['2'] = "abc";
    dig2char['3'] = "def";
    dig2char['4'] = "ghi";
    dig2char['5'] = "jkl";
    dig2char['6'] = "mno";
    dig2char['7'] = "pqrs";
    dig2char['8'] = "tuv";
    dig2char['9'] = "wxyz"; 
}  
vector<string> letterCombinations(string digits) {
    vector<string> result;
    result.push_back("");
    if ( digits.size() == 0 )  
    {
        return result;
    }
    int n=digits.length();
    for(int i=0;i<n;i++){
        vector<string> tmp;
        for(int j=0;j<dig2char[digits[i]].length();j++){
            for(int k=0;k<result.size();k++){
                tmp.push_back(result[k]+dig2char[digits[i]][j]);
            }
        }
        result=tmp;
    }
  

    return result;
}

vector<string> letterCombinations2(string digits) {
    vector<string> result;
    if ( digits.size() == 0 )  
    {
        result.push_back("");
        return result;
    }      
    vector<string> temp = letterCombinations(digits.substr(1));
    for(int j = 0; j < dig2char[digits[0]].size(); j ++)
        for(int t = 0; t < temp.size(); t ++ )
            result.push_back(dig2char[digits[0]][j] + temp[t]);    

    return result;
}
};

Longest Common Prefix

    string longestCommonPrefix(vector<string> &strs) {
         string res;
        if (strs.empty()) return res;
        for (int i = 0; i < strs[0].size(); ++i)
        {
            char ch = strs[0][i];
            for (int j = 1; j < strs.size(); ++j)
                if (i == strs[j].size() || strs[j][i] != ch)
                    return res;
            res.push_back(ch);
        }
        return res;
    }

String to Integer (atoi)

 To deal with overflow, inspect the current number before multiplication. If the current number is greater than 214748364, we know it is going to overflow. On the other hand, if the current number is equal to 214748364, we know that it will overflow only when the current digit is greater than 7.(remember INT_MAX  is 2147483647)

    int atoi(const char *str) {
            int num=0; 
            int sign =1; 
            int i =0; 
            while(str[i] == ' ') {i++;} 
           
            if(str[i] == '+'||str[i] == '-'){
                sign=str[i] == '+'?1:-1;
                i++;
            }  
           
            while(str[i]>='0' && str[i] <= '9')
            { 
                 if(str[i] == ' ') break; 
                 if(INT_MAX/10 < num || INT_MAX/10 == num && INT_MAX%10 < (str[i] -'0')) 
                     return sign == -1 ? INT_MIN : INT_MAX; 
                 num = num*10 + str[i++] -'0'; 
            } 
            return num*sign; 
    }

Restore IP Addresses

 dfs
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string ip;
        restoreIpAddressRe(s, res, ip, 0, 0);
        return res;
    }
    void restoreIpAddressRe(string &s, vector<string> &res, string &ip, int deep, int start)
    {
        if (deep == 4 && start == s.size())
            res.push_back(ip);
        if (deep == 4) return;
       
        int num = 0, origSize = ip.size();
        if (origSize != 0) ip.push_back('.');
        for (int i = start; i < s.size(); ++i)
        {
            num = num * 10 + s[i] - '0';
            if (num > 255) break;
            ip.push_back(s[i]);
            restoreIpAddressRe(s, res, ip, deep + 1, i + 1);
            if (num == 0) break;//not allow leading 0
        }
        ip.resize(origSize);
    }
};

//another flavor
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip; // save temporary result in processing
        dfs(s, 0, 0, ip, result);
        return result;       
    }
    void dfs(string s, size_t start, size_t step, string ip, vector<string> &result) {
        if (start == s.size() && step == 4) {  // find a possible result
            ip.resize(ip.size() - 1);
            result.push_back(ip);
            return;
        }

        // since each part of IP address is in 0..255, the length will not more than 3, and not less than 1 as well.
        if (s.size() - start > (4 - step) * 3)
            return;  // optimize, the length of rest part of s string should not more than 3 * remaining part count need to split.
        if (s.size() - start < (4 - step))
            return;  // optimize, the length of rest part of s string should not less than 1 * remaining part count need to split.

        int num = 0;
        for (size_t i = start; i < start + 3; i++) {
            num = num * 10 + (s[i] - '0');

            if (num <= 255) {  // current split is valid, go to next recursion.
                ip += s[i];
                dfs(s, i + 1, step + 1, ip + '.', result);
            }
            if (num == 0) break;  // single 0 is allowed, but '01' is forbidden.
        }
    }
};

Pascal's Triangle II

    vector<int> getRow(int rowIndex) {
        vector<int> array(rowIndex+1,0);
        for (int i = 0; i <= rowIndex; i++) {
            for (int j = i-1; j > 0; j--){
                array[j] = array[j-1] + array[j];
            }
            array[i]=1;
        }
        return array;
    }

//another
    vector<int> getRow(int rowIndex) {
        vector<int> array(rowIndex+1,1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i-1; j > 0; j--){
                array[j] = array[j-1] + array[j];
            }
        }
        return array;
    }

Pascal's Triangle

easy.  
 vector<vector<int> > generate(int numRows) {
       vector<vector<int> > result;
        if (numRows < 1) return result;
        result.push_back(vector<int>(1,1));//first row (result[0])
        result.resize(numRows);
        for(int ii = 1; ii < numRows; ++ii){
            result[ii].resize(ii+1);
            result[ii][0] = 1;
            result[ii][ii] = 1;
            for(int jj = 1; jj < ii; ++jj){
                result[ii][jj] = result[ii-1][jj-1] + result[ii-1][jj];
            }
        }
        return result;
    }

Triangle

   dp:

 int minimumTotal(vector<vector<int> > &triangle) {
        int row=triangle.size();
        vector<int> dp(row+1,INT_MAX);
          dp[1]=triangle[0][0];
        for(int j=1;j<row;j++){
            for(int i=j+1;i>=1;i--){
                dp[i]=min(dp[i],dp[i-1])+triangle[j][i-1];
            }
        }
        int amin=dp[0];
        for(int i=1;i<=row;i++)
            if(amin>dp[i])
                amin=dp[i];
        return amin;       
    }

换个角度考虑一下，如果这道题不自顶向下进行动态规划，而是放过来自底向上来规划，递归式只是变成下一层对应的相邻两个元素的最小路径和加上自己的值，原理和上面的方法是相同的
    int minimumTotal(vector<vector<int> > &triangle) {
        int N = triangle.size();
        vector<int> dp(N,0);
        for (int i = 0; i < N; ++i)
            dp[i] = triangle[N-1][i];
        for (int i = N - 2; i >= 0; --i)
            for (int j = 0; j <= i; ++j)
                dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);

        return dp[0];
    }

Convert Sorted List to Binary Search Tree

from here
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int n=getLength(head);
        return sortedListToBST(head, 0, n-1);
    }
    TreeNode* sortedListToBST(ListNode *& list, int start, int end) {
         
          if (start > end) return NULL;
          // same as (start+end)/2, avoids overflow
          int mid = start + (end - start) / 2;
          TreeNode *leftChild = sortedListToBST(list, start, mid-1);
          TreeNode *parent = new TreeNode(list->val);
          parent->left = leftChild;
          list = list->next;
          parent->right = sortedListToBST(list, mid+1, end);
          return parent;
    }
    
    int getLength(ListNode *head)
    {
        int length = 0;
        while (head)
        {
            length++;
            head = head->next;
        }
        return length;
    }
};

Flatten Binary Tree to Linked List

//iterative
void flatten(TreeNode *root) {
    while ( root ) {
        if ( root->left ) {
            TreeNode *ptr = root->left;
            while ( ptr->right ) ptr = ptr->right;
            ptr->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
        root = root->right;
    }
}

//recursive
void flatten(TreeNode *root) {
    if (!root) return;

    TreeNode* left = root->left;
    TreeNode* right = root->right;

    if (left) {
        root->right = left;
        root->left = NULL;

        TreeNode* rightmost = left;
        while(rightmost->right) {rightmost = rightmost->right;}
        rightmost->right = right; //the right most points  to the original right child
    }

    flatten(root->right); //tail recursion        
}

Linked List Cycle II

 //Let x be: Length of head to cycle started node
//Let y be: Length of the cycle

//Let hare run two steps while tortoise runs one step
//while both of them entered the cycle, the hare is definitely to overlap the tortoise at some node, we define it as m:
//The hare totally runs: x + ky + m The tortoise totally runs: x + ty + m Thus, (x + ky + m)/(x + ty + m) =2, then ky = 2ty + x + m. we have (x + m) mod y = 0 We can conclude //that if the hare run more x steps, it will reach the cycle's starting node.


ListNode *detectCycle(ListNode *head) {
    if (head == NULL) return NULL;
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    if (fast == NULL || fast->next == NULL) return NULL;
    fast = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

Remove Nth Node From End of List

ListNode *removeNthFromEnd(ListNode *head, int n) {
    ListNode dummy(0), *back = &dummy, *front = &dummy;
    dummy.next = head;
    while (n--) front = front->next;
    while (front->next) {
        front = front->next;
        back = back->next;
    }
    ListNode *del = back->next;
    back->next = del->next;
    delete del;
    return dummy.next;
}

Copy List with Random Pointer

 /**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

//from anniekim
class Solution {
public:
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        return copyRandomList_1(head);
    }
   
    RandomListNode *copyRandomList_1(RandomListNode *head) {
        for (RandomListNode *cur = head; cur; cur = cur->next->next) {
            RandomListNode *newNode = new RandomListNode(cur->label);
            newNode->next = cur->next;
            cur->next = newNode;
        }
       
        for (RandomListNode *cur = head; cur; cur = cur->next->next)
            if (cur->random)
                cur->next->random = cur->random->next;
       
        RandomListNode dummy(0), *curNew = &dummy;
        for (RandomListNode *cur = head; cur; cur = cur->next) {
            curNew->next = cur->next;
            curNew = curNew->next;
            cur->next = cur->next->next;
        }
        return dummy.next;
    }
   
    RandomListNode *copyRandomList_2(RandomListNode *head) {
        if (!head) return NULL;
        unordered_map<RandomListNode *, RandomListNode *> map;
        RandomListNode dummy(0), *curNew = &dummy, *cur = head;
        while (cur)
        {
            if (map.find(cur) == map.end())
                map[cur] = new RandomListNode(cur->label);
            if (cur->random && map.find(cur->random) == map.end())
                map[cur->random] = new RandomListNode(cur->random->label);
            curNew->next = map[cur];
            curNew = curNew->next;
            curNew->random = map[cur->random];
            cur = cur->next;
        }
        return dummy.next;
    }
};

Remove Duplicates from Sorted List II -interesting

 //from anniekim, iterative
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode dummy(0);dummy.next=head;
        ListNode *prev=&dummy;
        while(prev->next){
            int val=prev->next->val;
            ListNode *node=prev->next;
            if(!node->next||node->next->val!=val){
                prev=prev->next;
                continue;
            }
            while(node&&node->val==val){
                ListNode*del=node;
                node=node->next;
                delete del;
            }
            prev->next=node;
        }
        return dummy.next;

    }

//recursive
ListNode *deleteDuplicates(ListNode *head) {
    if (!head) return NULL;
    if (!head->next || head->val != head->next->val) {
        head->next = deleteDuplicates(head->next);
        return head;
    }
    int val = head->val;
    while(head && head->val == val) {
        ListNode *del = head;
        head = head->next;
        delete del;
    }
    return deleteDuplicates(head);
}

Remove Duplicates from Sorted List

ListNode *deleteDuplicates(ListNode *head) {
    if (!head) return head;
    ListNode *cur = head;
    while (cur->next)
    {
        if (cur->val == cur->next->val)
        {
            ListNode *del = cur->next;
            cur->next = del->next;
            delete del;
        }
        else
        {
            cur = cur->next;
        }
    }
    return head;
}

Rotate List

ListNode *rotateRight(ListNode *head, int k) {
    if (!head) return NULL;
    ListNode* tail = head;
    int count = 1;
    while (tail->next)
    {
        tail = tail->next;
        count++;
    }
    k = k % count; // in case the list rotates more than one round.
    if (k == 0) return head;
    ListNode* cur = head;
    for (int i = 0; i < count - k - 1; i++)
        cur = cur->next;
    ListNode* newHead = cur->next;
    cur->next = NULL;
    tail->next = head;
    return newHead;
}

Reverse Linked List II

 ListNode *reverseBetween(ListNode *head, int m, int n) {
    ListNode dummy(0), *ins = &dummy;
    dummy.next = head;
    for (int i = 0; i < m-1; ++i)
        ins = ins->next;
    ListNode *cur = ins->next;
    for (int i = 0; i < n-m; ++i) {
        ListNode *move = cur->next;
        cur->next = move->next;
        move->next = ins->next;
        ins->next = move;
    }
    return dummy.next;
}

//another flavor
ListNode *reverseBetween(ListNode *head, int m, int n) {
   
    int c=n-m;
    if(c==0) return head;
    ListNode*dhead,*dtail;
    dhead=dtail=head;
    ListNode dummy(0);dummy.next=head;
    ListNode*prev=&dummy;
    while(c>0){
        dtail=dtail->next;c--;
    }
   
    while(--m>0)
    {
        prev=dhead;
        dhead=dhead->next;
        dtail=dtail->next;
       
    }
    ListNode*end=dtail->next;
    ListNode*curr=dhead;
    while(curr->next!=end)
    {
        ListNode*ne=curr->next->next;
        curr->next->next=prev->next;
        prev->next=curr->next;
        curr->next=ne;
    }

    return dummy.next;
 
}

Reorder List

    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL) return;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* reverseHead = slow->next;           // find the second half of list
        slow->next = NULL;                           // make first half end point to null
        reverseHead = reverse(reverseHead);         // reverse second half    
        ListNode* cur = head;       
        while(reverseHead != NULL) {                // link together
            ListNode* tmp = reverseHead->next;
            reverseHead->next = cur->next;
            cur->next = reverseHead;
            cur = cur->next->next;
            reverseHead = tmp;
        }
    }
   
    ListNode* reverse(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode dummy(0);
        dummy.next = head;
        head = &dummy;
        ListNode* cur = head->next;
        while(cur->next != NULL) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = head->next;
            head->next = tmp;
        }
        return head->next;
    }

Insertion Sort List

    ListNode *insertionSortList(ListNode *head) {
        if(!head) return NULL;
        ListNode*dummy=new ListNode(0);
        dummy->next=head;
        while(head->next){
            ListNode*tmp=head->next;
            if(tmp->val<head->val){
                head->next=tmp->next;
                ListNode*pre=dummy;
                while(pre->next->val<=tmp->val)
                    pre=pre->next;
                tmp->next=pre->next;
                pre->next=tmp;
            }
            else
                head=head->next;
        }
        return dummy->next;
    }

Sort List

    ListNode *sortList(ListNode *head) {
        if(!head||!head->next) return head;
        ListNode*fast,*slow;
        fast=slow=head;
        while(fast->next&&fast->next->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*head2=slow->next;
        slow->next=NULL;
        head=sortList(head);
        head2=sortList(head2);
        return merge(head,head2);
    }
//insert the nodes of l2 into l1
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*prev=&dummy;
        dummy.next=l1;
        while(l2&&prev->next){
            if(l2->val<prev->next->val){
                ListNode*ne=l2->next;
                l2->next=prev->next;
                prev->next=l2;
                l2=ne;
            }
            prev=prev->next;
        }
        if(prev->next==NULL)
            prev->next=l2;
        return dummy.next;
    }

//another flavor of merge function, from annikim
    ListNode*merge(ListNode*l1,ListNode*l2){
        ListNode dummy(0),*last=&dummy;
        while(l1&&l2){
            ListNode**min=l1->val<l2->val?&l1:&l2;
            last->next=*min;
            last=last->next;
            *min=(*min)->next;
        }
        if(l1)
            last->next=l1;
        if(l2)
            last->next=l2;
        return dummy.next;   
    }

google面试

1. 有这么个游戏，举个例子：给你5个空_ _ _ _ _, 每次猜一个字母，这里出题人想让你猜出来clock，假如你猜a，告诉你这里面没有。你又猜c，他把c全写出来，所以你有c _ _ c _。 让你最多猜10次。写一个程序去猜。输入是几个空，要考虑每次猜的反馈，尽量把词猜出来。
2. 坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的id，区域的id自己定。用二叉树。
题意补充解释。比如我说插入x=1, y = 1, 第一象限就被分成了4个部分。各个部分的id自己随便定，数据结构和查找方式也随便选，只要能让插入和查找这两个操作时间短就行了，关于id如果相同方格 每次查询结果都一样当然最好，我当时是没关注这点，问他忽略行吗，他说行。

3. 大整数加法，我去，还结结实实问了45分钟...
4. 1. 两个数组，问是不是permutation。 然后如果只能用constant space怎么做：quicksort。然后如果再让这两个数组是imutable，而且只能是n的复杂度，那不可能有办法给出正确答案，给出的答案可以 是错的，可以怎么做：找他们的几个次序统计量比一比，一样就说是，不一样就说不是。如果得到不是，那一定不是，如果得到是，那可能不是。
   2. 二叉树直径，用dp达到n的复杂度。


review:
1.第一题其实就是经典的游戏 hangman......wiki之..
2. 如作者所说，使用二叉树。每一个结点有一个val和range(left,right)，那么左孩子的range是(left,val)，右孩子的range是(val,right), 以此类推。
4.1. immutable O(n) memory O(n) time hashmap 搞一下
mutable O(1) memory O(nlogn) time quicksort 搞一下
immutable O(1) memory O(n) time 正确性不保证的话，用几个统计量大概看看就好，比如最大值，最小值，均值，方差，中位数之类的...
 4.2 应该说的是找两个Node之间最大距离吧，二叉树标准题，类似leetcode 中的Binary Tree Maximum Path Sum

int maxDistance(Node* root) {
        int depth = 0;
        return maxDistanceHelper(root, depth);
}

int maxDistanceHelper(Node* root, int &depth) {
        if (root == NULL) {
                depth = 0;
                return 0;
        }
        int leftDepth = 0, rightDepth = 0;
        int maxDistanceFromLeft = maxDistanceHelper(root->left, leftDepth);
        int maxDistanceFromRight = maxDistanceHelper(root->right, rightDepth);
        depth = max(leftDepth, rightDepth) + 1;
        return max(leftDepth + rightDepth + 1, max(maxDistanceFromLeft, maxDistanceFromRight));
}

google/fb面经

1. 给个数组seq， 和一个total，找 if there is a contiguous sequence in seq
which sums to total.

注意，这里的contiguous意思是位置上的邻接，而不是consecutive

2. use trie to implment word search suggestion.
3. given a prefix expression, convert it to postfix expression(+12 -> 12+)
4. given a array of integers, find the minimum in a sliding window of size 4. eg. Input: [2,1,3,4,6,3,8,9,10,12,56]  Output: [1,1,3,3,3,3,8,9]
5. given an integer target, calculate the minimum number of integer square summation equal to that target



Answer:

1.
O(n) solution for unsorted array.

An example
arr=[-1 4 1 0 -2 -3 7],
sum = 2

step 1: accumulate the sums
arr -> acc = [0 -1 3 4 4 2 -1 6]. Insert 0 at the front

step 2: traverse the acc with hash table.
 the hash table uses the sum up to each index i + the target sum as the key,
and index i as the mapping value,
the "acc" array contain the sum up to each index j
if acc[j] is already the key in the hash table with mapping value i, you know the
subarray [i+1,j] is summed up to the target sum

2.

void convertPreFixToPostFix(char[] expr)
{
   if(expr.length>=3)
   {
         boolean operandNotFound=true;
   Stack stack=new Stack();
   int i=0;
   while(i<expr.length)
   {
   if(expr[i] is operator)
   {
      stack.push(expr[i]);
   }
   else
   {
       Print expr[i];
    if(operandNotFound)
    {
     operandNotFound=false;
     print expr[++i];
    }
    Print stack.pop();
   }
   i++;
   }
   
   }

}

5. here 

detect Linked List Cycle

基本思想就是使用两个指针~~~~一个在前步进为2,一个在后步前为1,如果前面的指针可以追到后面的指针表明有环

bool hasLoop(Node *head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast)
      return true;
  }
  return false;
}

Longest Substring with At Most Two Unique Characters

1

given a string ,return the longest substring that contains at most two unique
characters.

public int maxLength(String s){
        if (s.isEmpty()) return 0;
      //diffCharIndex 是从右往左起第一个不同字符的位置。
      //currentLength是以当前扫描位置字符为最后一个字符的符合条件的字符长度
        int diffCharIndex = -1, currentLength = 1, maxLength = 1;
        for (int i = 1; i < s.length(); i++)
        {
            if (s.charAt(i) != s.charAt(i-1))
            {
                 if (diffCharIndex == -1 || s.charAt(i) == s.charAt(diffCharIndex)) {
                    currentLength++;  }
                else { currentLength = i - diffCharIndex; }
                diffCharIndex = i-1;
            }
            else currentLength++;
            if (currentLength > maxLength) maxLength = currentLength;
        }
        return maxLength;
    }

下面的修改为返回字符串

  string maxLength(string s){
      if (s.empty()) return 0;
      int diffCharIndex = -1, currentLength = 1, maxLength = 1;
      int maxStart=0;
      for (int i = 1; i < s.length(); i++)
      {
          if (s[i] != s[i-1])
          {
              if (diffCharIndex == -1 || s[i] == s[diffCharIndex]) {
                  currentLength++;  }
              else { currentLength = i - diffCharIndex;  }
              diffCharIndex = i-1;
          }
          else currentLength++;
          if (currentLength > maxLength) {maxLength = currentLength; maxStart=i-currentLength+1;}
      }
      return s.substr(maxStart,maxLength);
  }

2
Longest Substring Of Two Unique Characters
Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string abcabcabcbcbc, the longest run of two characters is the 6-character run of bcbcbc that ends the string.


Here is a O(N) solution written in C#:
public static string GetLongestSubset(string str) {
            if (str == null)
                throw new ArgumentNullException ("str");

            if (str.Length == 0)
                return String.Empty;
        
            int s1 = 0, s2 = 0;

            // Get next unique char
            for(int i = 1; i < str.Length; i++) {
                if (str [i] != str[s1]) {
                    s2 = i;
                    break;
                }
            }

            if (s2 == 0)
                return str; // all chars are the same

            int sequenceStart = 0;
            int maxStart = 0, maxEnd = 0;
            int maxDiff = 0;

            // Scan for longest sequences
            for (int i = s2 + 1; i < str.Length; i++) {
                // Can this new char belong to the current substring we are building up?
                if (str [i] != str [s1] && str [i] != str [s2]) {
                    int diff = i - sequenceStart;
                    if (diff >= maxDiff) {
                        maxDiff = diff;
                        maxStart = sequenceStart;
                        maxEnd = i - 1;
                    }
                    if (s1 > s2) {
                        sequenceStart = s1;
                        s2 = i;
                    } else {
                        sequenceStart = s2;
                        s1 = i;
                    }
                } else if (str [i] != str [i - 1]) {
                    // Track start of each char sequence containing the same char
                    if (str [i] == str [s1]) {
                        s1 = i;
                    } else {
                        s2 = i;
                    }
                }
            }

            int lastDiff = str.Length - sequenceStart;
            if (lastDiff >= maxDiff) {
                maxDiff = lastDiff;
                maxStart = sequenceStart;
                maxEnd = str.Length - 1;
            }

            return str.Substring (maxStart, (maxEnd - maxStart) + 1);
        }

reverse a list

reverse a list:

//iterative
ListNode* reverse(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    ListNode dummy(0);
    dummy.next = head;
    head = &dummy;
    ListNode* cur = head->next;
    while(cur->next != NULL) {
        ListNode* tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = head->next;
        head->next = tmp;
    }
    return head->next;
}

//recursive
ListNode* reverse(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    ListNode* next=head->next;
    ListNode* newhead=    reverse(next);
    next->next=head;
    head->next=NULL;
    return newhead;   

}
   

Decode Ways

//dp, from anniekim
int numDecodings(string s) {
    if (s.empty() || s[0] == '0')
        return 0;
    int N = s.size();
    int dp[N+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 1; i < N; ++i)
    {
        if (s[i] == '0')
        {
            if (s[i-1] != '1' && s[i-1] != '2')
                return 0;
            dp[i+1] = dp[i-1];
        }
        else
        {
            int num = s[i] - '0' + (s[i-1] - '0') * 10;
            if (num >= 11 && num <= 26)
                dp[i+1] = dp[i] + dp[i-1];
            else
                dp[i+1] = dp[i];
        }
    }
    return dp[N];
}

//same idea, but less space
int numDecodings(string s) {
    if (s.empty() || s[0] == '0')
        return 0;
    int N = s.size();
    int cur=0,prev1=1,prev2=1;
    for (int i = 1; i < N; ++i)
    {
        if (s[i] == '0')
        {
            if (s[i-1] != '1' && s[i-1] != '2')
                return 0;
            cur = prev2;
        }
        else
        {
            int num = s[i] - '0' + (s[i-1] - '0') * 10;
            if (num >= 11 && num <= 26)
                cur = prev1 + prev2;
            else
                cur = prev1;
        }
        prev2=prev1;
        prev1=cur;
    }
    return prev1;
}

//another flavor
    int numDecodings(string s) {
        if(!s.size()||s[0]=='0')return 0;
        if(s.length()==1) return 1;
        int cur=0,prev1=1,prev2=1;
        for(int i=1;i<s.length();i++)
        {
            if(s[i]!='0')
                cur+=prev1;
            if((s[i-1]=='1'||s[i-1]=='2'&&s[i]<'7'))
                cur+=prev2;
            prev2=prev1;
            prev1=cur;
            cur=0;
        }
        return prev1;
    }

Gray Code

two methods are provided.

first one is from codeganker
这道题要求求出n位的格雷码对应的二进制数，主要在于找到一种格雷码的递增方法（gray code并不是唯一的，可以有多种）。
我们来看看有了n-1位的格雷码如何得到n位的格雷码呢？其实方法比较简单，首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码，它们一定是合法的因为除了第一位（都是0）其余位都跟n-1的格雷码一致，所以两两之间只相差一位，满足要求。接下来看看如何接上剩下的2^(n-1)个，我们把n-1位的格雷码倒序排列，然后在每个前面添加1，然后接到上述的前2^(n-1)个就可以了。首先因为是倒序过来，所以中间两个元素除去第一位其他都是一样的（因为原来最后一个，现在倒序过来就是第一个），而他们第一位分别是0和1，满足格雷码的要求。而剩下的元素因为我们是n-1位的格雷码倒序排列，所以两两都是满足要求的，加上前面都一样的位1，仍然满足条件。最后看看这些数字是不是都不一样，前半部分和后半部分肯定不会一样，而因为前半部分都是0开头，后半部分都是1打头，所以互相之间也不会有重复，可以看出覆盖了所有数字，而且依次下来均满足条件。
如此我们提出了格雷码的递推方法，我们只需要做一次位数的循环，每次根据上面结果构造当前位数的结果即可。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。代码如下：

    vector<int> grayCode(int n) {
        vector<int> ret;
        if(n==0){
            ret.push_back(0);
            return ret;
        }
        ret.push_back(0);
        ret.push_back(1);
        for(int i=2;i<=n;i++){
            int tmp=1<<i-1;
            int vsize=ret.size();
            for(int j=vsize-1;j>=0;j--){
                ret.push_back(ret[j]+tmp);
            }
        }
        return ret;
    }

//second one. regard every gray code as a vertex of a graph, two vertex has an edge iff their gray code differ by one bit. Then do DFS from  the vertex of gray code 0

    vector<int> grayCode(int n) {
        int num=1<<n;
        int mark[num];
        for(int i=0;i<num;i++)
            mark[i]=0;
        vector<int> ret;
        dfs(n,0,mark,ret);
        return ret;
    }
    void dfs(int n, int v,int mark[],vector<int>& aqueue)
    {
         mark[v]=1;int tmp;
         aqueue.push_back(v);
         for(int i=0;i<n;i++)
         {
             tmp=v^(1<<i);
             if(mark[tmp]==0)
             {
                dfs(n,tmp,mark,aqueue);
                break;
             }
                
         }
    }

Container With Most Water

int maxArea(vector<int> &height) {
    int res = 0;
    int l = 0, r = height.size()-1;
    while (l < r)
    {
        if (height[l] <= height[r])
        {
            res = max(res, (r-l) * height[l]);
            l++;
        }
        else
        {
            res = max(res, (r-l) * height[r]);
            r--;
        }
    }
    return res;
}

Here is the proof. Proved by contradiction:

Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with aol and aor (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. Sow when we have visited the one that shows up firstly, the program will laterly move from this one so that the program can never consider the pair(aol, aor).  WLOG, let's say we visited aol firstly but not aor. When a pointer stops at a_ol, it won't move until the right pointer arrives at a value, say arr, that is greater than aol before it reaches aor. In this case, we does move aol. But notice that the volume of aol and arr is already greater than aol and aor (as it is wider and same height), which means that aol and aor is not the optimal solution -- Contradiction!


Here is a simple proof for the solution. Use v[low, high] indicates the volume of container with low and high. suppose height[low] < height[high], then we move low to low+1, that means we ingored v[low, high-1],v[low, high-2],etc, if this is safe, then the algorithm is right, and it's obvious that v[low, high-1],high[low, high-2]...... can't be larger than v[low, high] since its width can't be larger than high-low, and its height is limited by height[low].

Simplify Path

[解题思路]
利用栈的特性，如果substring element
1. 等于“/”，跳过，直接开始寻找下一个element
2. 等于“.”，什么都不需要干，直接开始寻找下一个element
3. 等于“..”，弹出栈顶元素，寻找下一个element
4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element

最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。

string simplifyPath(string path) {  
    vector<string> stack;  
    assert(path[0]=='/');  
    int i=0;  
    while(i< path.size())  
    {  
        while(path[i] =='/' && i< path.size()) i++; //skip the begining '////' 
        if(i == path.size())  
            break;  
        int start = i;  
        while(path[i]!='/' && i< path.size()) i++; //decide the end boundary 
        int end = i-1;  
        string element = path.substr(start, end-start+1);  
        if(element == "..")  
        {  
            if(stack.size() >0)  
                stack.pop_back();  
        }  
        else if(element!=".")  
            stack.push_back(element);     
    }  
    if(stack.size() ==0) return "/";  
    string simpPath;  
    for(int i =0; i<stack.size(); i++)  
        simpPath += "/" + stack[i];  
    return simpPath;  
}  

//another one

1. traverse the string to record each folder name.
2. two special cases:

a.double dot:pop one.
b.single dot: do nothing (don't push it).

string simplifyPath(string path) {
    vector<string>   nameVect;
    string name;

    path.push_back('/');
    for(int i=0;i<path.size();i++){
        if(path[i]=='/'){
            if(name.size()==0)continue;
            if(name==".."){     //special case 1：double dot，pop dir
                 if(nameVect.size()>0)nameVect.pop_back();
            }else if(name=="."){//special case 2:singel dot，don`t push
            }else{         
                nameVect.push_back(name);
            }
            name.clear();
        }else{
            name.push_back(path[i]);//record the name
        }
    }

    string result;
    if(nameVect.empty())return "/";
    for(int i=0;i<nameVect.size();i++){
        result.append("/"+nameVect[i]);
    }
    return result;
}

Unique Paths II

 [解题思路]
和Unique Path一样的转移方程：
Step[i][j] = Step[i-1][j] + Step[i][j-1] if Array[i][j] ==0
or            = 0 if Array[i][j] =1


       int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
            int m = obstacleGrid.size();  
            if(m ==0) return 0;  
            int n = obstacleGrid[0].size();  
            if(obstacleGrid[0][0] ==1) return 0;  
            vector<int> maxV(n,0);  
            maxV[0] =1;  
            for(int i =0; i<m; i++)  
            {  
                 for(int j =0; j<n; j++)  
                 {  
                      if(obstacleGrid[i][j] ==1)  
                           maxV[j]=0;  
                      else if(j >0)  
                           maxV[j] = maxV[j-1]+maxV[j];  
                 }  
            }  
            return maxV[n-1];  
       }  

Partition List

    ListNode *partition(ListNode *head, int x) {
        ListNode dummy(x-1);dummy.next=head;
        ListNode *cur=&dummy,*prev=&dummy;
        while(cur->next){
            if(cur->next->val>=x){
                cur=cur->next;
            }
            else{
                if(prev==cur){
                    prev=prev->next;
                    cur=cur->next;
                }else{
                    ListNode*tnode=cur->next;
                    cur->next=tnode->next;
                    tnode->next=prev->next;
                    prev->next=tnode;
                    prev=tnode;
                }
            }
        }
        return dummy.next;
    }

//second flavor, from anniekim
ListNode *partition(ListNode *head, int x) {
    ListNode leftdummy(-1);
    ListNode rightdummy(-1);
    ListNode * lhead = &leftdummy;
    ListNode * rhead = &rightdummy;
    for(ListNode*cur = head; cur; cur=cur->next){
        if(cur->val<x){
            lhead->next = cur;
            lhead = lhead->next;
        }else{
            rhead->next = cur;
            rhead = rhead->next;
        }
    }
    lhead->next = rightdummy.next;
    rhead->next = nullptr;
    return leftdummy.next;
}

Search in Rotated Sorted Array II

如果有重复数字，那么，如果A[m]>=A[l],那么[l,m]为递增序列的假设就不能成立了，比如如下数据
[1,3,1,1,1]

解决办法：
如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件
1. A[m]>A[l]  递增
2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

 bool search(int A[], int n, int target) {  
            int start = 0;  
            int end = n-1;  
            while(start <= end)  
            {  
                 int mid = (start+end)/2;  
                 if(A[mid] == target) return true;  
                 if(A[start] < A[mid])  
                 {  
                      if(target>=A[start] && target<A[mid])  
                           end = mid-1;  
                     else   
                          start = mid+1;  
                 }  
                 else if(A[start] > A[mid])  
                 {  
                      if(target>A[mid] && target<=A[end])  
                           start = mid+1;  
                      else  
                           end = mid-1;  
                 }  
                else //skip duplicate one, A[start] == A[mid]  
                      start++;  
            }  
            return false;  
       }  

Search in Rotated Sorted Array

[解题思想]
同样是二分，难度主要在于左右边界的确定。需要结合两个不等式：
1. A[middle] ? A[left]
2. A[middle] ? target

   int search(int A[], int n, int target) {
        int i = 0, j = n - 1;
        while (i <= j)
        {
            int mid = (i + j) / 2;
            if (A[mid] == target)
                return mid;
            if (A[i] <= A[mid])
            {
                if (A[i] <= target && target < A[mid])
                    j = mid - 1;
                else
                    i = mid + 1;
            }
            else
            {
                if (A[mid] < target && target <= A[j])
                    i = mid + 1;
                else
                    j = mid - 1;
            }
        }
        return -1;
    }

Reverse Nodes in k-Group

    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode dummy(0);dummy.next=head;
        ListNode*cur=head,*prev=&dummy;
        ListNode*nextsec=head;//start of next group
        while(cur){
            int tmp=k;
            while(nextsec&&tmp-->0)
                nextsec=nextsec->next;
            if(tmp>0)
                return dummy.next;
            while(cur->next!=nextsec){
                ListNode*tnode=cur->next;
                cur->next=tnode->next;
                tnode->next=prev->next;
                prev->next=tnode;
            }
            prev=cur;
            cur=nextsec;
        }
        return dummy.next;
    }


//another flavor, from anniekim

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (k <= 1) return head;
        int reverseTimes = GetLength(head) / k;
        ListNode dummy(0); dummy.next = head;
        ListNode *ins = &dummy, *cur = ins->next;
        while (reverseTimes--)
        {
            for (int i = 0; i < k - 1; ++i) {
                ListNode *move = cur->next;
                cur->next = move->next;
                move->next = ins->next;
                ins->next = move;
            }
            ins = cur;
            cur = ins->next;
        }
        return dummy.next;
    }

    int GetLength(ListNode *head) {
        int length = 0;
        while (head) {
            head = head->next;
            length++;
        }
        return length;
    }
};

Count and Say

 easy

生成规律就是代码思路～用prev记录第i个字符串，cur为第i+1个字符串。

逐个访问prev的元素并进行统计。c为当前字符，count为c连续出现的个数。

当前访问的元素prev[i]与c不同时，将count, c转化成字符串格式，插入cur中；更新c和count. 

string countAndSay(int n) {
    string prev="1";
    string cur="";
    for(int i=2;i<=n;i++){
        int len=prev.length();
        char c=prev[0];
        int count=1;
        int j=1;
        while(j<len){
            if(c==prev[j]){
                j++;count++;
            }else{
                cur+='0'+count;
                cur+=c;
                count=1;
                c=prev[j++];
            }
        }
        cur+='0'+count;
        cur+=c;
        prev=cur;
        cur="";
    }
    return prev;
}

find kth largest/smallest element in a binary search tree

do inorder traversal

//kth smallest

void findK(Node* p, int& k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

//kth largest 

void findK(Node* p, int& k) {
  if(!p || k < 0) return;
  findK(p->right, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->left, k); 
} 

Find common elements in two BST -interesting

InOrder traversing both the trees iteratively and checking for any common elements...
Time O(n) ... Space O(n)

a good answer:
void dups(node* a, node* b)
{
    if(!a || !b)
        return;
    stack<node*> p,q;
    node* n1 = a, *n2 = b;
    while(true)
    {
        if(n1)
        {
            p.push(n1);
            n1 = n1->left;
        }
        else if(n2)
        {
            q.push(n2);
            n2 = n2->left;
        }
        else if (!p.empty() && !q.empty())
        {
            n1 = p.top();
            n2 = q.top();           
            if(n1->data < n2->data)
            {
                p.pop();
                n1 = n1->right;
                n2 = NULL;
            }
            else if(n2->data < n1->data)
            {
                q.pop();
                n2 = n2->right;
                n1 = NULL;
            }
            else
            {
                cout<<n1->data<<" ";
                p.pop();
                q.pop();
                n1 = n1->right;
                n2 = n2->right;
            }
        }
        else
            break;
    }
}


//a recursive one

void intersect(node* a, node* b) {
    if (!a || !b) return;
    if (a->value < b->value) {
        intersect(a, b->left);
        intersect(a->right, b);
    }
    else if (a->value > b->value) {
        intersect(a->left, b);
        intersect(a, b->right);
    }
    if (a->value == b->value) {
        printf("%d ", a->value);
        intersect(a->left, b->left);
        intersect(a->right, b->right);
    }
}

My Learnings: Find common elements in given two Binary Search Tr...

My Learnings: Find common elements in given two Binary Search Tr...: /* * Two BST are given find common elements in both * Algo works like this: * Iteratively traverse both the tree in inorder f...

distributed algorithm to find median

What is the distributed algorithm to determine the median of arrays of integers located on different computers?
In a situation like there are a number of servers, each  server is holding a billion integers and medium of  integers in all servers combined must be found.

 by Michael Harris


Suppose you have a master node (or are able to use a consensus protocol to elect a master from among your servers).  The master first queries the servers for the size of their sets of data, call this n, so that it knows to look for the k = n/2 largest element.

The master then selects a random server and queries it for a random element from the elements on that server.  The master broadcasts this element to each server, and each server partitions its elements into those larger than or equal to the broadcasted element and those smaller than the broadcasted element.

Each server returns to the master the size of the larger-than partition, call this m.  If the sum of these sizes is greater than k, the master indicates to each server to disregard the less-than set for the remainder of the algorithm.  If it is less than k, then the master indicates to disregard the larger-than sets and updates k = k - m.  If it is exactly k, the algorithm terminates and the value returned is the pivot selected at the beginning of the iteration.

If the algorithm does not terminate, recurse beginning with selecting a new random pivot from the remaining elements.

Analysis:

Let n be the total number of elements and s be the number of servers.  Assume that the elements are roughly randomly and evenly distributed among servers (each server has O(n/s) elements).  In iteration i, we expect to do about O(n/(s*2^i)) work on each server, as the size of each servers element sets will be approximately cut in half (remember, we assumed roughly random distribution of elements) and O(s) work on the master (for broadcasting/receiving messages and adding the sizes together).  We expect O(log(n/s)) iterations.  Adding these up over all iterations gives an expected runtime of O(n/s + slog(n/s)), and assuming s << sqrt(n) which is normally the case, this becomes simply (O(n/s)), which is the best you could possibly hope for.

Note also that this works not just for finding the median but also for finding the kth largest value for any value of k.