Google interview questions #8

ref: http://www.mitbbs.com/article_t/JobHunting/33072599.html

是烙印, 问的是LCA of DAG. 全程不让写代码, 就一直问follow up, 问复杂度, 问怎
么做, 为什么要这么做, 用那个为什么不好, 后来问要是有很多pair of nodes 求LCA
要怎么做preprocessing.

解法：

2个node各做bfs，记录走过的node和距离，如果出现重复就记录2个的距离和，直到找到最小的距离和

follow up：
预先计算出每个node到其他所有node的距离。当给定2个node时，找出所有的共同点，计算距离和

--------------------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33073385.html

x_0 = C (integer)
if x_n is even then x_{n+1} is x_n / 2
if x_n is odd then x_{n+1} to be 3 * x_n + 1

这题的复杂度是O(logC)吗？

https://en.wikipedia.org/wiki/Collatz_conjecture

---------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11377&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

一队人，每一个人有两个值（height，tvalue），其中height代表身高，tvalue代表这个人前面有多少人比他高。现在把这个array of (height, tvalue)打乱，然后要还原这个数列。.

解法：

按height排序，从最低height开始，tvalue就是它在新array里的最终位置。需要注意是，每次都要对之前index前面里已经有多少被放置

最终的index = tvalue + （index之前已经确定的元素个数）

所以复杂度是O(n ^ 2)

nlogn 的解法：根据array的index建立一个bst，附带一个额外的值代表此subtree当前有多少个node被填过

-------------------------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=7849&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

#1 把bst变成双向链表
解法：inorder遍历，保证一个pointer pass by reference

逆序数
解法： divide and conquer(merge sort)

#2 实现Candy Crush
1.m行n列的矩阵；2.q种花色物品；3.矩阵里每个cell的花色都是random的；4.初始化之后至少一个available的move；5.no 3-run，即初始化的时候不能直接出现三个同种物品连一线的情况。
好像还有其他几个要求，我已经记不清了。
我就开始按照他的要求挨个进行分析。先是random函数，然后就可以用双层for循环来填充每一个cell。我说但是一个available的move这个太难了，因为有太多的情况。就问他要提示，而且我不断做尝试。他说“其实答案比你想想的简单多了。最后直接告诉我：“你可以直接在填充所有的cell之前先创造一个可以move的三个物品先放进去。我恍然大悟，对对对，在双层for循环之前先做这一步操作。
下一个是"no 3-run的条件”。我说就每当在填充一个之前先往上下左右四个方向的两个格子都跟将random生成的物品进行比对。他说：“其实另一种情况。”我说：“就是将要填充的物品正好在两个同色物品之间。”他说对。我说咱们就可以用一个while循环，如果random生成的颜色不符合要求（设置一个boolean函数来判断，这里不要求实现）就继续循环。; u# V. Y: \ p7 B$ {/ a/ [: n
他说：“OK。其实这样会stuck到一种情况，你来想想。”我就想到比如比如当前方格的上、下、左、右各有一种两个同色物品排列，那么这个cell填这四种颜色的任何一种都不对了。”他说对，怎么避免呢？经过他的提示我就写这样的情况下直接清除board中所有已填颜色从头来过。0 L% F- Z) k( F
难点解决了，下一步就是写代码了，然后照相。
感觉这种题目面试官已经在里面设置好了处理的难点来等待你遇到和解决，然后看你尝试解决问题的方法以及交流能力。就像寻宝一样不断地试探、前进、解决问题。
#3 Tries

#4
比如1729 = 1^3 + 12 ^ 3 = 9 ^ 3 + 10 ^ 3。像这种可以由两对或两对以上的立方和组成的数叫做R某某某数（单词记不清了）。让你构造一个函数，输入是N，输出小于N的所有这种数。/ u" f% G( Z( |9 Q0 f- _1 H5 K
其实方法很简单，就是将从1到N的立方根之间的数，从中任取两个来求立方和，然后看结果集当中有没有出现两次或两次以上的数。就是类似于暴力了。

解法: 暴力 + hash，从1开始算到N

----------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11067&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

Google onsite
1. 类似这道题：
给如下的数据格式：<start_time, end_time, value>
For example,
1, 3, 100
2, 4, 200
5, 6, 300
。。。
这些数据时间点可能有重合。在时间段2~3之间，value的和是100+200 = 300. 找出这
组数据中最高的value和
[consider end points]

解法：类似meeting room，把开始、结束时间排序，设2个指针p1, p2。
如果是开始时间，cur + value[p1++], 结束时间cur - value[p2++]

2.find k most frequent words from a file
解法：priority queue + hash map

3.brainstorming: 一个上传文件的service，之前正常运转，突然有一天挂了，这期间
没改代码。问怎么排查问题。

查log，物理硬件

-------------------------------------------------------------------------------
ref： http://www.meetqun.com/forum.php?mod=viewthread&tid=301&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50&page=6

check一个数是否是3的次幂

解法：http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3

遍历

查表，32位内3的幂也就几十位

2分

---------------------------------------------------------------------------------
ref: http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
word wrap

解法：
标准dp

 int cube(int num) {
 return  num * num * num;
}

int minCost(vector<int> &v,vector<int> &dp,int index, int width) {
 if (index == v.size()) return 0;
 if (dp[index] != INT_MAX) return dp[index];
 int len = v[index];
 int minC = INT_MAX;
 for (int i = index; i < v.size(); i++) {
  minC = min(minC, cube(width - len) + minCost(v,dp,i + 1,width));
  len += v[i] + 1;
  if (width < len) break;
 }
 dp[index] = minC;
 return minC;
}

int spawn(vector<int> &v, int width) {
 vector<int> dp(v.size(),INT_MAX);
 return minCost(v,dp,0,width);
}

---------------------------------------
round 1: 给定一个class
class Event {
int id; /nsor id
int timestamp;
boolean status;
}
意思是某个sensor会触发一个事件使其状态status改变，true->false or false->true. 设计数据结构，存储以下信息：每个事件的sensor id, timestamp和status，使其可以响应一种query， query包含id, timestamp,返回这个id在这个时刻的status
follow up: 如果来的event不是按照timestamp递增的，怎么修改数据结构

round 2:
一个二维矩阵，里面是bits (1 or 0)，可以用int 或byte表示，左右翻转这个矩阵，有什么优化

round 3:
一个猜词游戏，给定一个词典，里面的词的长度都一样，有一个secret word在这个词典里，每次从词典里选一个词猜，只会返回和secret word有几个字母是一样的（只知道数量，不知道位置）。问怎样猜能尽量减少猜测次数

Palantir interview question #1

--------------------------------------------------------------------

ref : https://shawnlincoding.wordpress.com/2015/03/16/palantir%E9%9D%A2%E7%BB%8F/
1，
1. 给你一个棋盘 int[][] board, 你可以交换任何一个棋子和它的邻居（横向或者竖向相邻的棋子），如果交换后，在横向或者竖向产生了大于等于三个连续的一样的棋子 e.g. 4 4 4
5
5
5
那么就算交换有效。(就是一个比较常见的游戏，忘记叫啥名字了)
请你写一个函数返回所有可以有效交换的棋子的坐标对。 比如 （（0， 0）， （1， 0）） ， （（3,2），（3,3））.

2，看code，debug， 然后写出正确的code，这个没啥说的

3 Merge interval
Running Median : follow up: O(1) space


--------------------------------------------------------------------------------------

write a fuction to titlecase a string
for example
input: the quick brown fox
output: The Quick Brown Fox
two pointers, remember to update flag


DFS,很像coursera普林算法课讲得CC， 看看所以0是不是在一个CC里面
从0，0开始做一次DFS，如果有0没被marked到那就是invalid的

Day 130, #282 #286 Expression Add Operators, Walls and Gates

Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: 

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

---------------------------------------------------------------------------
COME_BACK
#1 这种for循环内的写法可以简化没有符合时的情况
如1234
1 _ 234
12_34
123_4
1234
-----------
from 1_234:
1_2_34
1_23_4
1_234
........

如果遇到“*”，则返回之前的操作（因为之前的运算符和值都已经存好）
1 + 2 * 3,之前 1 + 2已经算出为3，之前的运算符为+，值为2。然后此时 总值- 2 + 2 * 3
cur为当前的总值，op为之前运算符，val为上一步计算的值

class Solution {
public:
    int target;
    void dfs(vector<string> &rt,string num,int index,string sofar,long cur,string op,long val) {
        if (index == num.length() && target == cur) {
            rt.push_back(sofar);
        }
        
        for (int i = index; i < num.length(); i++) {
            string s = num.substr(index,i + 1 - index);
            if (s != to_string(stol(s))) continue;
            int now = stol(s);
            dfs(rt,num,i + 1,sofar + "+" + s,cur + now,"+",now);
            dfs(rt,num,i + 1,sofar + "-" + s,cur - now,"-",now);
            if (op == "-") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur + val - val * now,op,val * now);
            }else if (op == "+") {
                dfs(rt,num,i + 1,sofar + "*" + s,cur - val + val * now,op,val * now);
            }else {
                dfs(rt,num,i + 1,sofar + "*" + s,val * now,op,val * now);
            }
        }
    }

    vector<string> addOperators(string num, int target) {
        vector<string> rt;
        this->target = target;
        
        for (int i = 1; i <= num.length(); i++) {
            string s = num.substr(0,i);
            if (s != to_string(stol(s))) continue;
            dfs(rt,num,i,s,stol(s),"",stol(s));
        }
        
        return rt;
    }
};

Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

------------------------------------------------------------------------
找出所有的gate，然后同时bfs

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size();
        if (m == 0) return;
        int n = rooms[0].size();
        queue<pair<int,int>> que;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    que.push(make_pair(i,j));
                }
            }
        }
        
        int size = que.size();
        int dis = 1;
        while (!que.empty()) {
            int row = que.front().first;
            int col = que.front().second;
            size--;
            que.pop();
           
            if (row + 1 < m && rooms[row + 1][col] > dis) {
                rooms[row + 1][col] = dis;
                que.push(make_pair(row + 1,col));
            }
            if (row - 1 >= 0 && rooms[row - 1][col] > dis) {
                rooms[row - 1][col] = dis;
                que.push(make_pair(row - 1,col));
            }
            if (col + 1 < n && rooms[row][col + 1] > dis) {
                rooms[row][col + 1] = dis;
                que.push(make_pair(row,col + 1));
            }
            if (col - 1 >= 0 && rooms[row][col - 1] > dis) {
                rooms[row][col - 1] = dis;
                que.push(make_pair(row,col - 1));
            }
            
            if (size == 0) {
                size = que.size();
                dis++;
            }
        }
    }
};

Day 129, #277 #278 #281 #283 #284 #285 Find the Celebrity, First Bad Version, Zigzag Iterator, Move Zeroes, Peeking Iterator, Inorder Successor in BST

Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

-------------------------------------------------------------------
COME_BACK
对a做检测，如果a认识b || b不认识a，a就不会是celebrity

// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        for (int a = 0; a < n; a++) {
            int b = 0;
            for (; b < n; b++) {
                if (a == b) continue;
                if (knows(a,b) || !knows(b,a)) {
                    break;
                }
            }
            if (b == n) return a;
        }
        
        return -1;
    }
};

第一个循坏对can进行挑选，如果i不认识can，则说明can一定不是celebrity。如果i认识can，能说明i一定不是celebrity

// Forward declaration of the knows API.
bool knows(int a, int b);

class Solution {
public:
    int findCelebrity(int n) {
        int can = 0;
        for (int i = 1; i < n; i++) {
            if (!knows(i,can)) {
                can = i;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i == can) continue;
            if (!knows(i,can) || knows(can,i)) return -1;
        }
        
        return can;
    }
};

Java, 关键：
1. 所有人都认识celebrity（第二个for循环），如果谁不被人认识，那他就不是celebrity（ 第一个for循环）
2. celebrity谁也不认识（第二个for循环）

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int cand = 0;
        
        for (int i = 1; i < n; i++) {
            if (knows(cand, i)) {
                cand = i;
            }
        }
        
        for (int i = 0; i < n; i++) {
            if ((cand != i && knows(cand, i)) || !knows(i, cand)) return -1;
        }
        
        return cand;
    }
}

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

------------------------------------------------------
Binary search

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            bool bad = isBadVersion(mid);
            if (bad && (mid == 1 || !isBadVersion(mid - 1))) return mid;
            if (bad) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
};

Java, recursion

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        return rec(1, n);
    }
    
    private int rec(int left, int right) {
        if (left > right) return left;
        int mid = left + (right - left) / 2;
        boolean isBad = isBadVersion(mid);
        if (!isBad && isBadVersion(mid + 1)) {
            return mid + 1;
        }
        
        if (isBad) {
            return rec(left, mid - 1);
        }
        
        return rec(mid + 1, right);
    }
}

Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].
-------------------------------------------------------------
适用于k个
http://shibaili.blogspot.com/2015/08/notes-from-others.html

class ZigzagIterator {
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        v.push_back(v1);
        v.push_back(v2);
        zig = 0;
        itrs = vector<int>(v.size(),0);
    }

    int next() {
        hasNext();
        int rt = v[zig][itrs[zig]];
        itrs[zig]++;
        zig = (zig + 1) % v.size();
        return rt;
    }

    bool hasNext() {
        for (int i = 0; i < v.size(); i++) {
            if (itrs[zig] >= v[zig].size()) {
                zig = (zig + 1) % v.size();
            }else {
                return true;
            }
        }
        return false;
    }
private:
    vector<vector<int>> v;
    vector<int> itrs;
    int zig = 0;
};

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i(v1, v2);
 * while (i.hasNext()) cout << i.next();
 */

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

------------------------------------------------------

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                swap(nums[i],nums[zero]);
                zero++;
            }
        }
    }
};

Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

1. Think of "looking ahead". You want to cache the next element.
2. Is one variable sufficient? Why or why not?
3. Test your design with call order of peek() before next() vs next() before peek().
4. For a clean implementation, check out Google's guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

--------------------------------------------------------------------

// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
 Data* data;
public:
 Iterator(const vector<int>& nums);
 Iterator(const Iterator& iter);
 virtual ~Iterator();
 // Returns the next element in the iteration.
 int next();
 // Returns true if the iteration has more elements.
 bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
 PeekingIterator(const vector<int>& nums) : Iterator(nums) {
     // Initialize any member here.
     // **DO NOT** save a copy of nums and manipulate it directly.
     // You should only use the Iterator interface methods.
 }

    // Returns the next element in the iteration without advancing the iterator.
 int peek() {
        if (st.empty()) {
         st.push(Iterator::next());
     }
     return st.top();
 }

 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 int next() {
     if (st.empty()) return Iterator::next();
     int rt = st.top();
     st.pop();
     return rt;
 }

 bool hasNext() const {
     return !st.empty() || Iterator::hasNext();
 }
private:
    stack<int> st;
};

In Java

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {

    private Iterator<Integer> itr;
    private Integer next;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    itr = iterator;
        next = itr.hasNext() ? itr.next() : null;
	}

    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return next;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    
        Integer rt = next;
        next = itr.hasNext() ? itr.next() : null;
        return rt;
	}

	@Override
	public boolean hasNext() {
	    return next != null;
	}
}

Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

------------------------------------------------
遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *mostLeft(TreeNode *root) {
        while (root->left != NULL) {
            root = root->left;
        }
        return root;
    }

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (p->right != NULL) {
            return mostLeft(p->right);
        }
        
        TreeNode *suc = NULL;
        while (root != NULL) {
            if (root->val > p->val) {
                suc = root;
                root = root->left;
            }else {
                root = root->right;
            }
        }
        return suc;
    }
};

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == NULL) {
            return root;
        }
        if (root->val <= p->val) {
            return inorderSuccessor(root->right,p);
        }
        TreeNode *next = inorderSuccessor(root->left,p);
        if (next == NULL) return root;
        return next;
    }
};

Day 128, #256 #265 #267 #273 Paint House, Paint House II, Palindrome Permutation II, Integer to English Words

Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

-----------------------------------------
方程式：
递归：超时，可加memoization

class Solution {
public:
    int helper(vector<vector<int>>& costs, int index,int pre) {
        if (index == costs.size()) return 0;
        int min1 = INT_MAX,min2 = INT_MAX,min3 = INT_MAX;
        if (pre != 0) {
            min1 = costs[index][0] + helper(costs,index + 1,0);
        }
        if (pre != 1) {
            min2 = costs[index][1] + helper(costs,index + 1,1);
        }
        if (pre != 2) {
            min3 = costs[index][2] + helper(costs,index + 1,2);
        }
        
        return min(min(min2,min1),min3);
    }

    int minCost(vector<vector<int>>& costs) {
        return helper(costs,0,-1);
    }
};

DP:
3个array，dp[k][i] = 为在第i个房子涂k的颜色所需要的总花费
dp[0][i] = costs[i][0] + min(dp[1][i - 1],dp[2][i - 1]);
其他2个颜色类同

以下方法已经做过空间优化

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int dp0 = costs[0][0];
        int dp1 = costs[0][1];
        int dp2 = costs[0][2];
        
        for (int i = 1; i < n; i++) {
            int t0 = dp0, t1 = dp1, t2 = dp2;
            dp0 = costs[i][0] + min(t1,t2);
            dp1 = costs[i][1] + min(t2,t0);
            dp2 = costs[i][2] + min(t1,t0);
        }

        return min(min(dp0,dp1),dp2);
    }
};

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

------------------------------------------
2个variable保存上一次涂房子的最小的2个值，first是值，second是颜色

class Solution {
public:
    int minCostII(vector>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int k = costs[0].size();
        vector dp = costs[0];
        int minCost = INT_MAX;
        
        for (int i = 1; i < n; i++) {
            // pair of cost - color
            pair min1 = make_pair(INT_MAX,-1);
            pair min2 = make_pair(INT_MAX,-1);
            // find the smallest two values from previous painting job
            for (int j = 0; j < k; j++) {
                if (dp[j] < min1.first) {
                    min2 = min1;
                    min1.first = dp[j];
                    min1.second = j;
                }else if (dp[j] < min2.first) {
                    min2.first = dp[j];
                    min2.second = j;
                }
            }
            
            for (int j = 0; j < k; j++) {
                if (j == min1.second) {
                    dp[j] = costs[i][j] + min2.first;
                }else {
                    dp[j] = costs[i][j] + min1.first;
                }
            }
        }
    
        for (int i = 0; i < k; i++) {
            minCost = min(minCost,dp[i]);
        }
        
        return minCost;
    }
};

Palindrome Permutation II
 Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

------------------------------
#1 检测所给string是否可生成pal, 跟I一样
#2 典型permutation

class Solution {
public:
    vector<int> collect(string s,string &single) {
        vector<int> count(256,0);
        for (int i = 0; i < s.length(); i++) {
            count[s[i]]++;
        }
        
        for (int i = 0; i < 256; i++) {
            if (count[i] % 2 == 1) {
                if (single == "") {
                    single += i;
                }else {
                    vector<int> t;
                    return t;
                }
            }
        }
        
        return count;
    }

    void rec(vector<string> &rt,vector<int> &count,string s,int total,string single) {
        if (total == 0) {
            string t = s;
            reverse(t.begin(),t.end());
            rt.push_back(s + single + t);
            return;
        }
        
        for (int i = 0; i < 256; i++) {
            if (count[i] < 2) continue;
            string t = s;
            t += i;
            count[i] -= 2;
            rec(rt,count,t,total - 1,single);
            count[i] += 2;
        }
    }

    vector<string> generatePalindromes(string s) {
        vector<string> rt;
        string single = "";
        vector<int> count = collect(s,single);
        if (count.size() == 0) return rt;
        rec(rt,count,"",s.length() / 2,single);
        return rt;
    }
};

Java

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> rt = new ArrayList<>();
        int[] map = new int[128];
        int odd = 0;
        
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)] += 1;
            if (map[s.charAt(i)] % 2 == 1) odd++;
            else odd--;
        }
        
        if (odd > 1) return rt;
        
        String mid = "";
        for (int i = 0; i < 128; i++) {
            if (map[i] % 2 == 1) mid += (char)i;
        }

        perm(rt, "", s.length() / 2, mid, map);
        
        return rt;
    }
    
    private void perm(List<String> rt, String curS, int total, String mid, int[] map) {
        if (total == 0) {
            rt.add(curS + mid + new StringBuilder(curS).reverse().toString());
            return;
        }
        
        for (int i = 0; i < 128; i++) {
            if (map[i] < 2) continue;
            map[i] -= 2;
            perm(rt, curS + (char)i, total - 1, mid, map);
            map[i] += 2;
        }
    }
}

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

----------------------------------------------------------------
注意空格

class Solution {
public:
    string translate(vector<string> &ones,vector<string> &oneTens,vector<string> &tens,vector<string> &ends,int nums,string end) {
        string rt = "";
        if (nums >= 100) {
            rt += ones[nums / 100 - 1] + " Hundred";
            nums %= 100;
        }
        
        if (nums >= 10) {
            if (rt != "") rt += " ";
            if (nums <= 19) {
                rt += oneTens[nums % 10];
                return rt + end;
            }
            rt += tens[nums / 10 - 2];
            nums %= 10;
        }
        
        if (nums >= 1) {
            if (rt != "") rt += " ";
            rt += ones[nums - 1];
        }
        
        return rt + end;
    }


    string numberToWords(int num) {
        if (num == 0) return "Zero";
        vector<string> ones = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
        vector<string> oneTens = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
        vector<string> tens = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
        vector<string> ends = {" Billion"," Million"," Thousand",""};
        
        string rt = "";
        int temp = 0, endI = 0,bill = 1000000000;
        while (num > 0) {
            if (num / bill > 0) {
                if (rt != "") rt += " ";
                rt += translate(ones,oneTens,tens,ends,num / bill,ends[endI]);
            }
            num %= bill;
            bill /= 1000;
            endI++;
        }
        return rt;
    }
};

In Java
注意空格

class Solution {
    private String[] units = {""," Thousand"," Million"," Billion"};
    private String[] singleDigits = {"One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
    private String[] doubleDigitsTenth = {"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    private String[] doubleDigits = {"Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String rt = "";
        for (int i = 0; i < 4; i++) {
            String cur = toWords((num % 1000), units[i]);
            if (!rt.isEmpty() && !cur.isEmpty()) rt = " " + rt;
            rt = cur + rt;
            num /= 1000; 
        }
        
        return rt;
    }
    
    private String toWords(int num, String unit) {
        String s = "";
        if (num == 0) return s;
        
        if (num >= 100) {
            s += singleDigits[num / 100 - 1] + " Hundred";
            num %= 100;
        }
        if (num > 9 && num < 20) {
            if (!s.isEmpty()) s += " ";
            s += doubleDigitsTenth[num % 10];
        } else {
            if (num > 19) {
                if (!s.isEmpty()) s += " ";
                s += doubleDigits[num / 10 - 2];
                num %= 10;
            }
            if (num != 0) {
                if (!s.isEmpty()) s += " ";
                s += singleDigits[num - 1];
            }
        }
        
        return s + unit;
    }
}

Day 127, #248 #249 #250 #252 #253 #254 #255 Strobogrammatic Number III, Group Shifted Strings, Count Univalue Subtrees, Meeting Rooms, Meeting Rooms II, Factor Combinations, Verify Preorder Sequence in Binary Search Tree

Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

-----------------------------------
类似 II。 对最后生成的数字跟low和high做对比，如果在范围内，count就加1
面试时不要用global variable

class Solution {
public:
    string low;
    string high;
    bool compareStrings(string &s1,string &s2) {
        if (s1.length() != s2.length()) return s1.length() < s2.length();
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] != s2[i]) return s1[i] < s2[i]; 
        }
        
        return true;
    }
    
    void helper(vector &rt,string s,int left,int right,int &count) {
        if (left > right) {
            if (s[0] != '0' && compareStrings(low,s) && compareStrings(s,high)) {
                count++;
            }
            return;
        }
        if (left != 0) {
            s[left] = '0',s[right] = '0';
            helper(rt,s,left + 1,right - 1,count);
        }
        s[left] = '1',s[right] = '1';
        helper(rt,s,left + 1,right - 1,count);
        s[left] = '8',s[right] = '8';
        helper(rt,s,left + 1,right - 1,count);
        if (left != right) {
            s[left] = '6',s[right] = '9';
            helper(rt,s,left + 1,right - 1,count);
            s[left] = '9',s[right] = '6';
            helper(rt,s,left + 1,right - 1,count);
        }
    }

    int strobogrammaticInRange(string low, string high) {
        this->low = low;
        this->high = high;
        int count = 0;
        vector rt;
        for (int i = low.length(); i <= high.length(); i++) {
            string s(i,'\0');
            helper(rt,s,0,i - 1,count);
        }
        if (low == "0") return count + 1;
        return count;
    }
};

Group Shifted Strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order.

-----------------------------------
注意：是string里的每一个字母都往后挪一次

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string,vector<string>> dic;
        for (int i = 0; i < strings.size(); i++) {
            string key = "";
            
            for (int j = 1; j < strings[i].length(); j++) {
                int diff = strings[i][j] - strings[i][j - 1];
                if (diff >= 0) {
                    key += to_string(diff) + ",";
                }else {
                    key += to_string(diff + 26) + ",";
                }
            }
            dic[key].push_back(strings[i]);
        }
        
        vector<vector<string>> rt;
        for (auto kv : dic) {
            vector<string> t = kv.second;
            sort(t.begin(),t.end());
            rt.push_back(t);
        }
        
        return rt;
    }
};

Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.
--------------------------------------
uni-value subtree的定义是tree里所有的node都含有相同的值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string helper(TreeNode *root, int &count) {
        if (root == NULL) {
            return "";
        }
        
        string left = helper(root->left,count);
        string right = helper(root->right,count);
        string val = to_string(root->val);
        if ((left == "" || val == left) && (val == right || right == "")) {
            count++;
            return val;
        }
        return "#";
    }

    int countUnivalSubtrees(TreeNode* root) {
        if (root == NULL) return 0;
        int count = 0;
        helper(root,count);
        return count;
    }
};

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

------------------------------------------

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    class Cmp {
    public:
        bool operator() (Interval &i1, Interval &i2) {
            if (i1.start == i2.start) {
                return i1.end < i2.end;
            }
            return i1.start < i2.start;
        }  
    };

    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(),intervals.end(),Cmp());
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};

Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

-------------------------------------
sort所有时间点，从头开始扫，如果是开始时间，count + 1。结束时间，count - 1

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool cmp(int i1, int i2) {
        if (abs(i1) == abs(i2)) return i1 < i2;
        return abs(i1) < abs(i2);
    }

    int minMeetingRooms(vector<Interval>& intervals) {
        vector<int> times;
        for (int i = 0; i < intervals.size(); i++) {
            times.push_back(intervals[i].start);
            times.push_back(-intervals[i].end);
        }
        
        sort(times.begin(),times.end(),cmp);
        int minNumber = 0;
        int cur = 0;
        for (int i = 0; i < times.size(); i++) {
            if (times[i] >= 0) {
                cur++;
                minNumber = max(minNumber,cur);
            }else {
                cur--;
            }
        }
        
        return minNumber;
    }
};

Java, with PriorityQueue

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals.length <= 1) return intervals.length;
        
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(intervals[0].end);
        int size = 1;
        
        for (int i = 1; i < intervals.length; i++) {
            if (q.peek() <= intervals[i].start) {
                q.poll();
            }
            q.add(intervals[i].end);
            size = Math.max(size, q.size());
        }
        
        return size;
    }
}

Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

--------------------------------------------------------
典型的combination，注意边界条件

class Solution {
public:
    void combination(vector> &rt, int n,vector v,int start,int orig) {
        if (n == 0 || start == orig) return;
        if (n == 1) {
            vector t = v;
            rt.push_back(t);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            if (n % i != 0) continue;
            v.push_back(i);
            combination(rt,n / i,v,i,orig);
            v.pop_back();
        }
    }

    vector> getFactors(int n) {
        vector> rt;
        if (n == 1) return rt;
        vector v;
        combination(rt,n,v,2,n);
        return rt;
    }
};

Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

------------------------------------------------------
用stack，有额外空间
#1 因为是preorder，一开始队列成递减（如果root没有左子树，则为只有一个元素的递减数列），压入所有遇到的node
#2 遇到拐点时说明此node为之前某一个node的右子树，则开始pop stack，直到找到之前的那个node，然后将minVal设好，pop掉的部分都为已经验证过的，符合bst条件的
#3 如果在遍历的过程中发现一个node的值小于minVal，则返回false

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        if (preorder.size() == 0) return true;
        stack<int> st;
        int minVal = INT_MIN;
        st.push(preorder[0]);
        
        for (int i = 1; i < preorder.size(); i++) {
            if (preorder[i] < minVal) return false;
            if (preorder[i] > preorder[i - 1]) {
                while (!st.empty() && preorder[i] > st.top()) {
                    minVal = st.top();
                    st.pop();
                }
            }
            
            st.push(preorder[i]);
        }
        
        return true;
    }
};

COME_BACK
O(1) 空间，run time complexity未知，最坏可能为O(n^2)

bool verifyPreorder(vector<int>& preorder) {
        if (preorder.size() == 0) return true;
        int minIndex = -1;
        int top = 0, end = 0;
        
        for (int i = 1; i < preorder.size(); i++) {
            if (minIndex != -1 && preorder[i] < preorder[minIndex]) return false;
            if (preorder[i] > preorder[i - 1]) {
                while (top >= end && preorder[i] > preorder[top]) {
                    minIndex = top;
                    top--;
                }
            }
            if (top < end) end = i;
            top = i;
        }
        
        return true;
    }

Day 126, #243 #244 #245 Shortest Word Distance, Shortest Word Distance II, Shortest Word Distance III

Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

----------------------------------------------------------------------------

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int shortest = words.size();
        int pos1 = -words.size(), pos2 = -words.size();
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word1) {
                pos1 = i;
                shortest = min(shortest,pos1 - pos2);
            }
            if (words[i] == word2) {
                pos2 = i;
                shortest = min(shortest,pos2 - pos1);
            }
        }
        return shortest;
    }
};

Shortest Word Distance II

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

-----------------------------------------------------------------------

class WordDistance {
public:
    WordDistance(vector<string>& words) {
        for (int i = 0; i < words.size(); i++) {
            if (dic.find(words[i]) == dic.end()) {
                vector<int> t = {i};
                dic[words[i]] = t;
            }else {
                dic[words[i]].push_back(i);
            }
        }
    }

    int shortest(string word1, string word2) {
        int i = 0, j = 0;
        int distance = INT_MAX;
        
        while (i < dic[word1].size() && j < dic[word2].size()) {
            distance = min(distance,abs(dic[word1][i] - dic[word2][j]));
            if (dic[word1][i] < dic[word2][j]) {
                i++;
            }else {
                j++;
            }
        }
        
        return distance;
    }
private:
    unordered_map<string,vector<int>> dic;
};


// Your WordDistance object will be instantiated and called as such:
// WordDistance wordDistance(words);
// wordDistance.shortest("word1", "word2");
// wordDistance.shortest("anotherWord1", "anotherWord2");

Shortest Word Distance III

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

---------------------------------------------------------------------

class Solution {
public:
    int sameWords(vector<string>& words, string word) {
        int distance = words.size();
        int pre = -words.size();
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word) {
                distance = min(distance,i - pre);
                pre = i;
            }
        }
        return distance;
    }

    int shortestWordDistance(vector<string>& words, string word1, string word2) {
        if (word1 == word2) return sameWords(words,word1);
        int pos1 = -words.size(), pos2 = -words.size();
        int shortest = words.size();
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word1) {
                shortest = min(shortest,i - pos2);
                pos1 = i;
            }else if (words[i] == word2) {
                shortest = min(shortest,i - pos1);
                pos2 = i;
            }
        }
        
        return shortest;
    }
};