Monday, February 24, 2014

http://www.impactinterview.com/2009/10/140-google-interview-questions/

140 Google Interview Questions

October 24th, 2009 by lewis

Friday, February 14, 2014

C++ 计算时判断溢出

方法一
===========================================================
short, int, long 类型
a). 相加的时候，例如 a + b，判断 INT_MAX - a 和 b的大小
b). 相减的时候，例如 a - b，可以转换为a + (-b), 然后类似上一条来判断。

要注意的是，b变为-b的时候，有可能发生溢出，需要单独判断。
如果b不是INT_MIN，可以转换后是直接按a) 来做
如果b是INT_MIN，要把 -b分拆为 -(b+1) 和1，因为是特例，我们可以直接改写为 a + -(b+1) + 1, 因为后面两个直接溢出，可以调整顺序，变为a + 1 + -(b+1)

以上这个办法，有缺点
第一、处理起来啰嗦
第二，INT_MAX-a本身就有可能溢出

方法二
===========================================================

转换为上下限更高的数据类型，然后来判断

比如 int 类型的 a+b，我们可以转换为 (long)a + (long)b, 然后和INT_MAX 或者 INT_MIN比较

如果是long，可以转化为long long

如果是long long，可以转化为double

double以后，就有内置函数类比较了

http://www.cplusplus.com/reference/cmath/isfinite/

http://www.cplusplus.com/reference/cmath/isinf/

方法二
===========================================================
对于 short, int, long, long long 类型的数据a 和 b 的加减法，判断溢出通用的做法可以是
先判断是否同号，
如果相加异号或者相减同号，无溢出
如果相加同号或者相减异号，换为无符号数，unsigned的，先运算c = a + b
然后通过比较a, b 和c的符号来判断是否溢出。

而对于float， double， long double 这些，会有内置的函数isfinite，isinf来比较，参见

http://www.cplusplus.com/reference/cmath/isfinite/

http://www.cplusplus.com/reference/cmath/isinf/

/* isinf example */
#include <stdio.h> /* printf */
#include <math.h> /* isinf, sqrt */

int main()
{
printf ("isinf(0.0) : %d\n",isinf(0.0));
printf ("isinf(1.0/0.0) : %d\n",isinf(1.0/0.0));
printf ("isinf(-1.0/0.0) : %d\n",isinf(-1.0/0.0));
printf ("isinf(sqrt(-1.0)): %d\n",isinf(sqrt(-1.0)));
return 0;
}

Thursday, February 13, 2014

k sum problem （k 个数的求和问题）

问题陈述：

在一个数组，从中找出k个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的index不同）

解法：

2 sum 用hash table做，可以时间O(n)，空间O（n），
2 sum 如果用sort以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用hash table做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2）的时候，nlogn就不是主要的时间消耗成分，也就更适合2sum的sort后双指针扫描查找的办法。

那么，对于k sum， k>2的，如果用sort的话，可以对 n-2的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法，时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k>2) 问题（一个size为n的array, 查找k个数的一个tuple，满足总和sum为0），有没有时间复杂度在O(n^(k-2))的办法？

之前常规的一层一层剥离，n的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个n的因子，但是这样时间开销还是太多

我们可以通过对问题分解来解决
举个例子
...-5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5.... 要找 4 sum = 0
那么先分解
4 分成 2 sum + 2 sum 来解决，但是这里的子问题2 sum没有sum=0的要求，是保留任何中间值。只有当子问题的2 sum解决以后，回归原问题的时候，我们才又回归原始的2 sum问题，这时候sum=0
子问题，空间和时间消耗，都是O(n^2)
回归大问题，时间消耗，是O(n^2)

假设k sum中 k = 2^m, 那么一共有m层，会有m次分解
分解到最底层，时间空间消耗从原始O(n)变为新的O(n^2)
分解到次底层，时间空间消耗从 O(n^2)变为新的O((n^2)^2)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))

和之前的方法O(n^(k-1))相比，O(n^(2logk))的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。

通过问题的分解 + hashtable的运用，能明显减少时间消耗，但是空间消耗变大是个问题。比如说，如果有10^6的int类型数组，我如果用这个hashtable的办法，就要有10^12的pair，这就有10T以上的空间消耗。

问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。

另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k这种非确定性的要求。

Friday, February 7, 2014

How to write resume

Link: http://www.mitbbs.com/article/JobHunting/32620869_0.html
Author: skydoor

发信人: skydoor (海阔天空), 信区: JobHunting
标题: Amazon内推不少简历后的分享
发信站: BBS 未名空间站 (Thu Feb 6 18:49:32 2014, 美东)

最近收到不少朋友的简历，我都一一帮忙内推Amazon了，看了不少简历之后，写点东西
分享一下，不少朋友我在submit之前，都给了修改意见，我不负责招人，我说的不一定
对，大家可以探讨。

我的帖子不代表Amazon观点和要求，只是我个人看法。

基本思想是，你的简历反映了你是否用心，人家很容易看清楚你是否用心，如何从一大
堆简历里面脱颖而出，第一，不能有硬伤；第二，要言之有物；第三，不要confuse别人

首先，你的简历的名字不要太general。不少朋友命名，resume.pdf，resume.doc，我
觉得，你可以在简历的名字上传递更多地信息，比如，resume_John_Smith.pdf，
resume_John_Smith_Amazon.pdf, 是不是更好一些？这样人家一看就觉得是有备而来
的，也方便人家在一大堆简历里面迅速找到你，不然人家还要点开看是谁？

第二，表述要一致。特别是时间，有的朋友简历里面, Sep 2013, Fall 2013,
January 2013, 08/2013 或者直接2012-2013没有月份。我的point是不管哪个方式，你
一定要一致。要么全部简写，要么全部整个单词，要么都是数字，总之要统一。

第三，不是好东西不要写。比如GPA，如果你GPA 3.5以下，其实就不用写了，可以写
类似5/100之类的；比如skills，你如果不太懂，千万不要写什么 basic knowldge of
XXXX。总之就是，没人指望你很牛，但是，你不牛的部分，就不需要强调了。

第四，如果你申请马工，一定要强调skill的关键词。个人建议，你描述的project的
时候，尽量多写类似，“...in Java” “...in Java” “...in Python” “...in C
++” 之类。

第五，如果你很多paper的，申请马工，没有必要让publication占据很多位置，你可以
不把作者写全，可以不写具体杂志哪些页，也可以只写“selected publictions”。总
之就是不要喧宾夺主。

第六，不要confuse别人，你最好把你的简历拿去一个非同学非同一个系的朋友看看，
看是否有哪些地方对方咋一看很不知所以的地方。

第七，没必要限定在一页里面，一页半也是OK的

细节决定成败，你从一大堆人里面脱颖而出，绝对是大量的正确的细节决定的结果。

Monday, February 3, 2014

Reservoir Sampling Proof

http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

一开始有k个
每个数字被选进来的概率都是1

第k+1个，要放进去，那么前面每个被换出去的概率是 1/(k+1), 没被换出去的概率是k/(k+1)
有k-1个数字，是留下来了，留下来的概率是k/(k+1)
有1个数字，换出去了，新进来的，被选进来的概率是 k/(k+1)
所有数字留下来的概率都是k/(k+1)

然后，处理第k+2个
第k+2个，要放进去，那么前面每个被换出去的概率是 1/(k+2), 没被换出去的概率是(k+1)/(k+2),
有k-1个数字, 是留下来了, (k+1)/(k+2), 再加上上一次的概率，留下来的总概率是k/(k+1) * (k+1)/(k+2) = k/(k+2)
有1个数字，换出去了，那么新进来的数字被选进来的概率是 k/(k+2)
所有数字留下来的概率都是k/(k+2)

假设当前处理了n个样本，选出了k个数，并且满足条件
k个选出的样本，每个样本在n个样本中被抽出的概率都是k/n
那么处理第n+1个样本的时候
1). 第n+1个样本被选进k的概率是 k/(n+1)，即，被换进的样本的概率是 k/(n+1)
2). 对于前k个样本，留下的概率是 n/(n+1)，与之前的概率 k/n，做条件概率相乘，截止到目前该样本仍然留在k个样本中的总概率是 n/(n+1) * k/n = k/(n+1)
综合1) 2), k个样本每个留下的概率都是 k/(n+1)

以此类推，对于每个状态，即处理过的样本总量为n的时候，所有留下来的样本的全局总概率都是k/n

Farthest Ascending Pair

Problem :
Given a sequence of integers A[n], find a pair of integers A[x]<A[y], such that y-x >= j-i and A[i]<A[j]

Solution:
In courtesy of JConstantine

 
class Solution
{
    public:
    std::vector<int> findLongestAscendingPair(const std::vector<int> &v) {
        std::vector<int> ret(2,0);
        int n = v.size();
        if(n == 0) return ret;
        std::vector<int> left(n,0);
        std::vector<int> right(n,0);
        left[0] = v[0];
        right[n-1] = v[n-1];
        for(int i=1; i<n; i++){
            left[i] = std::min(v[i], left[i-1]);
        }
        
        for(int i=n-2; i>=0; i--){
            right[i] = std::max(v[i], right[i+1]);
        }
        
        int i = 0, j = 0, distance = 0;
        while(i < n && j < n)
        {
            if(left[i] < right[j])
            {
                distance = std::max(j-i, distance);
                ret[0] = i;
                ret[1] = j;
                j = j + 1;
            }
            else
            {
                i = i+ 1;
            }
        }
        return ret;
    }
};

Sunday, February 2, 2014

longest increasing sequence

Link : http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp

 
#include < vector >
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector < int > & a, vector < int > & b)
{
    vector < int > p(a.size());
    int u, v;
    
    if(a.empty()) return;
    
    b.push_back(0);
    
    for(size_t i = 1; i < a.size(); i++)
    {
        // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
        if(a[b.back()] < a[i])
        {
            p[i] = b.back();
            b.push_back(i);
            continue;
        }
        
        // Binary search to find the smallest element referenced by b which is just bigger than a[i]
        // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
        for(u = 0, v = b.size() - 1; u < v;)
        {
            int c = (u + v) / 2;
            if(a[b[c]] < a[i]) u = c + 1;
            else v = c;
        }
        
        // Update b if new value is smaller then previously referenced value
        if(a[i] < a[b[u]])
        {
            if(u > 0) p[i] = b[u - 1];
            b[u] = i;
        }
    }
    
    for(u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include < cstdio >
int main()
{
    int a[] = {
        1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7
    };
    vector < int > seq(a, a + sizeof(a) / sizeof(a[0])); // seq : Input Vector
    vector < int > lis; // lis : Vector containing indexes of longest subsequence
    find_lis(seq, lis);
    
    //Printing actual output
    for(size_t i = 0; i < lis.size(); i++)
    printf("%d ", seq[lis[i]]);
    printf("\n");
    
    return 0;
}

Monday, January 27, 2014

[FW] How to Rock an Algorithms Interview, The Coding Interview

Link by KEVIN SIMLER :
http://www.palantir.com/2011/09/how-to-rock-an-algorithms-interview/
http://www.palantir.com/2011/10/the-coding-interview/#more-1925

Traveling salesman problem comic, originally from http://www.xkcd.com/399/

Comic courtesy of XKCD, via Creative Commons License

We do a lot of interviewing at Palantir, and let me tell you: it’s hard. I don’t mean that we ask tough questions (although we do). I mean that the task of evaluating a candidate is hard.

The problem? Given a whiteboard and one hour, determine whether the person across from you is someone you’d like to work with, in the trenches, for the next n years. A candidate’s performance during an interview is only weakly correlated with his or her true potential, but we’re stuck with the problem of turning the chickenscratch on the whiteboard into an ‘aye’ or ‘nay’. Sometimes it feels like a high-stakes game of reading tea leaves. Believe me we’re doing our best, but we’re often left with the nagging worry that we’re passing up brilliant people who just had a bad day or who didn’t click with a particular problem.

In an effort to improve this situation, we wanted to write up a guide that will help candidates make sense of this process, or at least the part known as an Algorithms Interview. At Palantir we ask questions that test for a lot of different skills — coding, design, systems knowledge, etc. — but one of our staple interviews is to ask you to design an algorithm to solve a particular problem.

It usually starts like this:

Given X, figure out an efficient way to do Y.

First: Make sure you understand the problem. You’re not going to lose points asking for clarifications or talking through the obvious upfront. This will also buy you time if your brain isn’t kicking in right away. Nobody expects you to solve a problem in the first 30 seconds or even the first few minutes.

Once you understand the problem, try to come up with a solution – any solution whatever. As long as it’s valid, it doesn’t matter if your solution is trivial or ugly or extremely inefficient. What matters is that you’ve made progress. This does two things: (1) it forces you to engage with the structure of the problem, priming your brain for improvements you can make later, and (2) it gives you something in the bank, which will in turn give you confidence. If you can achieve a brute force solution to a problem, you’ve cleared a major hurdle to solving it in a more efficient way.

Now comes the hard part. You’ve given an O(n^3) solution and your interviewer asks you to do it faster. You stare at the problem, but nothing’s coming to you. At this point, there are a few different moves you can make, depending on the problem at hand and your own personality. Almost all of these can help on almost any problem:

Start writing on the board. This may sound obvious, but I’ve had dozens of candidates get stuck while staring at a blank wall. Maybe they’re not visual people, but still I think it’s more productive to stare at some examples of the problem than to stare at nothing. If you can think of a picture that might be relevant, draw it. If there’s a medium-sized example you can work through, go for it. (Medium-sized is better than small, because sometimes the solution to a small example won’t generalize.) Or just write down some propositions that you know to be true. Anything is better than nothing.

Talk it through. And don’t worry about sounding stupid. If it makes you feel better, tell your interviewer, “I’m just going to talk out loud. Don’t hold me to any of this.” I know many people prefer to quietly contemplate a problem, but if you’re stuck, talking is one way out of it. Sometimes you’ll say something that clearly communicates to your interviewer that you understand what’s going on. Even though you might not put much stock in it, your interviewer may interrupt you to tell you to pursue that line of thinking. Whatever you do, please DON’T fish for hints. If you need a hint, be honest and ask for one.

Think algorithms. Sometimes it’s useful to mull over the particulars of the problem-at-hand and hope a solution jumps out at you (this would be a bottom-up approach). But you can also think about different algorithms and ask whether each of them applies to the problem in front of you (a top-down approach). Changing your frame of reference in this way can often lead to immediate insight. Here are some algorithmic techniques that can help solve more than half the problems we ask at Palantir:
- Sorting (plus searching / binary search)
- Divide-and-conquer
- Dynamic programming / memoization
- Greediness
- Recursion
- Algorithms associated with a specific data structure (which brings us to our fourth suggestion…)

Think data structures. Did you know that the top 10 data structures account for 99% of all data structure use in the real world? Probably not, because I just made those numbers up — but they’re in the right ballpark. Yes, on occasion we ask a problem whose optimal solution requires a Bloom filter or suffix tree, but even those problems tend to have a near-optimal solution that uses a much more mundane data structure. The data structures that are going to show up most frequently are:
- Array
- Stack / Queue
- Hashset / Hashmap / Hashtable / Dictionary
- Tree / binary tree
- Heap
- Graph
You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) What are the common caveats? (Hashing is tricky, and usually takes O(k) time when k is the size of the object being hashed.) What algorithms tend to go along with each data structure? (Dijkstra’s for a graph.) But when you understand these data structures, sometimes the solution to a problem will pop into your mind as soon as you even think about using the right one.

Think about related problems you’ve seen before and how they were solved. Chances are, the problem you’ve been presented is a problem that you’ve seen before, or at least very similar. Think about those solutions and how they can be adapted to specifics of the problem at hand. Don’t get tripped up by the form that the problem is presented – distil it down to the core task and see if matches something you’ve solved in the past.

Modify the problem by breaking it up into smaller problems. Try to solve a special case or simplified version of the problem. Looking at the corner cases is a good way to bound the complexity and scope of the problem. A reduction of the problem into a subset of the larger problem can give a base to start from and then work your way up to the full scope at hand.
Looking at the problem as a composition of smaller problems may also be helpful. For example, “find a number in a sorted array which has been shifted cyclically by an unknown constant k” can be solved by (1) first figuring out “k” and then (2) figuring out how to perform binary search on a shifted array).

Don’t be afraid to backtrack. If you feel like a particular approach isn’t working, it might be time to try a different approach. Of course you shouldn’t give up too easily. But if you’ve spent a few minutes on an approach that isn’t bearing any fruit and doesn’t feel promising, back up and try something else. I’ve seen more candidates who overcommit than undercommit, which means you should (all else equal) be a little more willing to abandon an unpromising approach.

Incidentally, trying out a few different approaches (rather than sticking with a single approach) tends to work well in interviews, because the problems we choose for an interview usually have many different solutions. Happily, the same is true for the problems we solve on the job =)

Note: this part is part two of our series on doing your best in interviews. Part one: “How to Rock an Algorithms Interview”.

Here at Palantir algorithms are important, but code is our lifeblood. We live and die by the quality of the code we ship. It’s no surprise, then, that coding ability is what we stress the most in our interview process. A candidate can get by with mediocre algorithm skills (depending on the role), but no one can skimp on coding.

Suppose you’re confident in your ability to write great software. Your task in a coding interview (of which there will be several) is to show the interviewers that you in fact do have the programming chops — that you’re an experienced coder who knows how to write solid, production-quality code.

This is easier said than done. After all, coding in your favorite IDE from the comfort of$familiar_place is very different from coding on a whiteboard (on a problem you’re totally unfamiliar with) in a pressure-filled 45-minute interview. We realize that the interview environment is not the real world, and we adjust our expectations accordingly. Nonetheless, there are a number of things you can do to put your best foot forward during the interview.

First, though, we’d like to give you a sense for what we look for during a coding interview. Most important is the ability to write clean and correct code — it’s not enough just to be correct. A lot of people will be interacting with your code once you’re on the job, so it should be readable, maintainable, and extensible where appropriate. If your solution is clean and correct, and you produced it in a reasonable amount of time without a lot of help, you’re in good shape. But even if you stumble a bit, there are other ways to demonstrate your ability. As you work, we also watch for debugging ability, problem-solving and analytical skills, creativity, and an understanding of the ecosystem that surrounds production code.

With our evaluation criteria in mind, here are some suggestions we hope will help you perform at your very best.

Before you start coding

Make sure you understand the problem. Don’t hesitate to ask questions. Specifically, if any of the problem requirements seem loosely defined or otherwise unclear, ask your interviewer to make things more concrete. There is no penalty for asking for clarifications, and you don’t want to miss a key requirement or proceed on unfounded assumptions.
Work through simple examples. This can be useful both before you begin and after you’ve finished coding. Working through simple examples before coding can give you additional clarity on the nature of the problem — it may help you notice additional cases or patterns in the problem that you would otherwise have missed had you been thinking more abstractly.
Make a plan. Be wary of jumping into code without thinking about your program’s high-level structure. You don’t have to work out every last detail (this can be difficult for more meaty problems), but you should give the matter sufficient thought. Without proper planning, you may be forced to waste your limited time reworking significant parts of your program.
Choose a language. At Palantir, we don’t care what languages you know as long as you have a firm grasp on the fundamentals (decomposition, object-oriented design, etc.). That said, you need to be able to communicate with your interviewer, so choose something that both of you can understand. In general, it’s easier for us if you use Java or C++, but we’ll try to accommodate other languages. If all else fails,devise your own pseudo-code. Just make sure it’s precise (i.e. not hand-wavy) and internally consistent, and explain your choices as you go.

While you’re coding

Think out loud. Explain your thought process to your interviewer as you code. This helps you more fully communicate your solution, and gives your interviewer an opportunity to correct misconceptions or otherwise provide high-level guidance.
Break the problem down and define abstractions. One crucial skill we look for is the ability to handle complexity by breaking problems into manageable sub-problems. For anything non-trivial, you’ll want to avoid writing one giant, monolithic function. Feel free to define helper functions, helper classes, and other abstractions to reach a working solution. You can leverage design patterns or other programming idioms as well. Ideally, your solution will be well-factored and as a result easy to read, understand, and prove correct.
Delay the implementation of your helper functions. (this serves a corollary to the previous point) Write out the signature, and make sure you understand the contract your helper will enforce, but don’t implement it right away. This serves a number of purposes: (1) it shows that you’re familiar with abstractions (by treating the method as an API); (2) it allows you to maintain momentum towards the overall solution; (3) it results in fewer context-switches for your brain (you can reason about each level of the call stack separately); and (4) your interviewer may grant you the implementation for free, if he or she considers it trivial.
Don’t get caught up in trivialities. At Palantir we are much more interested in your general problem solving and coding abilities than your recall of library function names or obscure language syntax. If you can’t remember exactly how to do something in your chosen language, make something up and just explain to your interviewer that you would look up the specifics in the documentation. Likewise, if you utilize an abstraction or programming idiom which admits a trivial implementation, don’t be afraid to just write out the interface and omit the implementation so you can concentrate on more important aspects of the problem (e.g., “I’m going to use a circular buffer here with the following interface without writing out the full implementation”).

Once you have a solution

Think about edge cases. Naturally, you should strive for a solution that’s correct in all observable aspects. Sometimes there will be a flaw in the core logic of your solution, but more often your only bugs will be in how you handle edge cases. (This is true of real-world engineering as well.) Make sure your solution works on all edge cases you can think of. One way you can search for edge-case bugs is to…
Step through your code. One of the best ways to check your work is to simulate how your code executes against a sample input. Take one of your earlier examples and make sure your code produces the right result. Huge caveat here: when mentally simulating how your code behaves, your brain will be tempted to project what it wants to happen rather than what actually says happen. Fight this tendency by being as literal as possible. For example, if you’re calculating a string index with code likestr.length()-suffix.length(), don’t just assume you know where that index will land; actually do the math and make sure the value is what you were hoping for.
Explain the shortcuts you took. If you skipped things for reasons of expedience that you would otherwise do in a “real world” scenario, please let us know what you did and why. For example, “If I were writing this for production use, I would check an invariant here.” Since whiteboard coding is an artificial environment, this gives us a sense for how you’ll treat code once you’re actually on the job.

As an addendum, here are a few suggestions for books we like about the art of software construction:

Clean Code: A Handbook of Agile Software Craftsmanship – Robert C. Martin
Code Complete: A Practical Handbook of Software Construction – Steve McConnell
The Practice of Programming – Brian Kernighan, Rob Pike
Design Patterns: Elements of Reusable Object-Oriented Software – Erich Gamma, et al.
Effective Java – Joshua Bloch

[LeetCode] Maximal Rectangle

Link : http://oj.leetcode.com/problems/maximal-rectangle/

More information:
http://dp2.me/blog/?p=482

Thanks for your help. --> 无齿的兔子, 鹿杖客

 
#include <iostream>
#include <vector>

class Solution {
    public:
    int maximalRectangle(std::vector<std::vector<char> > &matrix) {
        int n = matrix.size();
        if(n==0) return 0;
        int m = matrix[0].size();
        if(m==0) return 0;
        std::vector<int> height(m, 0);
        std::vector<int> left(m, 0);
        std::vector<int> right(m, 0);
        int maxArea = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                height[j] = (matrix[i][j]=='1')? height[j]+1 : 0;
                left[j] = j;
                while(left[j]>0 && height[left[j]-1]>=height[j])
                left[j] = left[left[j]-1];
            }
            for(int j=m-1; j>=0; j--)
            {
                right[j] = j;
                while(right[j]<m-1 && height[j]<=height[right[j]+1])
                right[j] = right[right[j]+1];
            }
            for(int j=0; j<m; j++)
            maxArea = std::max(maxArea, (right[j]-left[j]+1)*height[j]);
        }
        return maxArea;
    }
};

Friday, January 24, 2014

[LeetCode] Classification

Sorting is enabled. Please click on the title to sort by specific column

Problem	Classification	Method
Evaluate Reverse Polish Notation	Math	Stack
Max Points on a Line	Count	Map
Sort List	List, BST, Graph	Merge Sort
LRU Cache	Design	Map, List
Binary Tree Postorder Traversal	List, BST, Graph	Stack
Binary Tree Preorder Traversal	List, BST, Graph	Stack
Reorder List	List, BST, Graph	Divide
Linked List Cycle II	List, BST, Graph	Two Pointers
Linked List Cycle	List, BST, Graph	Two Pointers
Word Break II	List, BST, Graph	DP
Word Break	List, BST, Graph	DP
Copy List with Random Pointer	List, BST, Graph	MAP, Copy&Break
Single Number II	Math	Bit
Single Number	Math	Bit
Candy	Math	Stack
Gas Station	Math	DP
Clone Graph	List, BST, Graph	Map
Palindrome Partitioning II	String	DP
Palindrome Partitioning	String	DP
Surrounded Regions	List, BST, Graph	BST
Sum Root to Leaf Numbers	List, BST, Graph	DSF
Longest Consecutive Sequence	Math	Set
Word Ladder II	List, BST, Graph	BST
Word Ladder	List, BST, Graph	BST
Valid Palindrome	String	Two Pointers
Binary Tree Maximum Path Sum	List, BST, Graph	DFS
Best Time to Buy and Sell Stock III	Array	Stack, DP
Best Time to Buy and Sell Stock II	Array
Best Time to Buy and Sell Stock	Array
Triangle	Math	DP
Pascal's Triangle II	Math	DP
Pascal's Triangle	Math	DP
Populating Next Right Pointers in Each Node II	List, BST, Graph	Two Pointers
Populating Next Right Pointers in Each Node	List, BST, Graph	Two Pointers
Distinct Subsequences	String	DP
Flatten Binary Tree to Linked List	List, BST, Graph	DFS, Wrapper
Path Sum II	List, BST, Graph	DFS
Path Sum	List, BST, Graph	DFS
Minimum Depth of Binary Tree	List, BST, Graph	DFS
Balanced Binary Tree	List, BST, Graph	DFS
Convert Sorted List to Binary Search Tree	List, BST, Graph	Divide and Conquer
Convert Sorted Array to Binary Search Tree	List, BST, Graph	Divide and Conquer
Binary Tree Level Order Traversal II	List, BST, Graph	List
Construct Binary Tree from Inorder and Postorder Traversal	List, BST, Graph	Divide and Conquer
Construct Binary Tree from Preorder and Inorder Traversal	List, BST, Graph	Divide and Conquer
Maximum Depth of Binary Tree	List, BST, Graph	DFS
Binary Tree Zigzag Level Order Traversal	List, BST, Graph	BSF, List
Binary Tree Level Order Traversal	List, BST, Graph	BSF, List
Symmetric Tree	List, BST, Graph	DFS, Divide & Conquer
Same Tree	List, BST, Graph	DFS, Divide & Conquer
Recover Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Recover Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Validate Binary Search Tree	List, BST, Graph	DFS, In-Order, Store
Interleaving String	String	DP
Unique Binary Search Trees II	String	DP
Unique Binary Search Trees	String	DFS, Divide & Conquer
Binary Tree Inorder Traversal	String	DFS, Divide & Conquer
Restore IP Addresses	String	DFS
Reverse Linked List II	List, BST, Graph	Two Pointers
Subsets II	List, BST, Graph	DFS
Decode Ways	String, List, BST, Graph	DFS
Gray Code	Math, String, List, BST, Graph	DFS, Math
Merge Sorted Array	Sort	Merge Sort
Scramble String	String, List, BST, Graph	DFS
Partition List	List, BST, Graph	Two Pointers
Maximal Rectangle	List, BST, Graph	DP
Largest Rectangle in Histogram	List, BST, Graph	DP
Remove Duplicates from Sorted List II	List, BST, Graph	Two Pointers
Remove Duplicates from Sorted List	List, BST, Graph	Two Pointers
Search in Rotated Sorted Array II	List, BST, Graph	Divided & Conquer, Binary Search
Remove Duplicates from Sorted Array II	List, BST, Graph	Two Pointers
Word Search	List, BST, Graph	DFS
Subsets	List, BST, Graph	DFS
Combinations	List, BST, Graph	DFS
Minimum Window Substring	String, List, BST, Graph	Count
Sort Colors	Sort, List, BST, Graph	Two Pointers
Search a 2D Matrix	List, BST, Graph	Binary Search, Transformation
Set Matrix Zeroes	other	other
Edit Distance	String, List, BST, Graph	DP
Simplify Path	String, List, BST, Graph	DP, Stack
Climbing Stairs	List, BST, Graph	DP
Sqrt(x)	Math	Binary Search, Bit Manipulation
Text Justification	String	Other
Plus One	Math	Other
Valid Number	String	Other
Merge Two Sorted Lists	List, BST, Graph	Merge Sort
Minimum Path Sum	List, BST, Graph	DFS
Unique Paths II	List, BST, Graph	DP
Unique Paths	List, BST, Graph	DP
Rotate List	List, BST, Graph	Two Pointers
Permutation Sequence	Math	Bit Manipulation
Spiral Matrix II	Other	Other
Length of Last Word	String	Other
Insert Interval	Other	Other
Merge Intervals	Other	Other
Jump Game	List, BST, Graph	DP
Spiral Matrix	Other	Other
Maximum Subarray	List, BST, Graph	DP
N-Queens II	List, BST, Graph	DFS
N-Queens	List, BST, Graph	DFS
Pow(x, n)	Math	Bit Manipulation
Anagrams	String	Count
Rotate Image	Other	Other
Permutations II	Math	Other
Permutations	Math	Other
Jump Game II	List, BST, Graph	DP
Wildcard Matching	String, Pattern	Greedy
Multiply Strings	Math	Other
Trapping Rain Water	Math	DP
First Missing Positive	Math	Two Pointers
Combination Sum II	Math	DP
Combination Sum	Math	DP
Count and Say	String	DP
Sudoku Solver	List, BST, Graph	Other
Valid Sudoku	List, BST, Graph	DFS
Search Insert Position	List, BST, Graph	Binary Search
Search for a Range	List, BST, Graph	Binary Search
Search in Rotated Sorted Array	List, BST, Graph	Binary Search
Longest Valid Parentheses	String, List, BST, Graph	DP
Next Permutation	Math	Other
Substring with Concatenation of All Words	String, List, BST, Graph	DFS
Divide Two Integers	Math	Bit Manipulation
Implement strStr()	String, Pattern	Brute Force, KMP
Remove Element	List, BST, Graph	Two Pointers
Remove Duplicates from Sorted Array	List, BST, Graph	Two Pointers
Reverse Nodes in k-Group	List, BST, Graph	Two Pointers
Swap Nodes in Pairs	List, BST, Graph	Two Pointers
Merge k Sorted Lists	List, BST, Graph	Heap, Compare
Generate Parentheses	String, List, BST, Graph	DP
Valid Parentheses	String, List, BST, Graph	Stack
Remove Nth Node From End of List	List, BST, Graph	Two Pointers
Letter Combinations of a Phone Number	String, List, BST, Graph	DFS, Backtrace
Letter Combinations of a Phone Number	String, List, BST, Graph	DFS, Backtrace
4 Sum	Math, Combination	Two Pointers
3 Sum Closest	Math, Combination	Two Pointers
3 Sum	Math, Combination	Two Pointers
Longest Common Prefix	String, List, BST, Graph
Roman to Integer	String	Other, Pattern
Integer to Roman	String	Other, Pattern
Container With Most Water	List, BST, Graph	Two Pointers, Other
Regular Expression Matching	String, List, BST, Graph	DFS, Greedy
Palindrome Number	String, List, BST, Graph	Two Pointers
String to Integer (atoi)	String	Other
Reverse Integer	Math	Overflow
ZigZag Conversion	Other	Other
Longest Palindromic Substring	String	DP, Manacher's Algorithm
Add Two Numbers	Other	Other
Longest Substring Without Repeating Characters	String	Two Pointers
Median of Two Sorted Arrays	Math	Divide & Conquer
2 Sum	Math	Two Pointers

West Pavilion