Tuesday, March 31, 2015

Median

Given a unsorted array with integers, find the median of it.

A median is the middle number of the array after it is sorted.

If there are even numbers in the array, return the N/2-th number after sorted.

Example

Given [4, 5, 1, 2, 3], return 3

Given [7, 9, 4, 5], return 5

Challenge

O(n) time.

---------------------------- thinking -----------------------------------
quick sort idea
http://codeanytime.blogspot.com/2014/12/median.html
http://www.shuati.info/blog/2014/07/01/Median-in-stream-of-integers/
http://algs4.cs.princeton.edu/23quicksort/
---------------------------- codes ------------------------------------
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
int median(vector<int> &nums) {
// write your code here
int kth = (1 + nums.size()) / 2 - 1;
return medianHelper(nums, 0, nums.size()-1, kth);
}
void swap(vector<int> &nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
int medianHelper(vector<int> &nums, int start, int end, int kth) {
int s = start + 1;
int e = end;
while (s <= e) {
if (nums[s] < nums[start]) {
s++;
} else if (nums[e] > nums[start]) {
e--;
} else {
swap(nums, s, e);
s++;
e--;
}
}
swap(nums, start, e);
if (e == kth) {
return nums[e];
} else if (e < kth) {
//BUG here, the start val should be e+1 instead of e -> the same reason as binary search
return medianHelper(nums, e+1, end, kth);
} else {
return medianHelper(nums, start, e-1, kth);
}
}
};

Majority Number III

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array. Find it.

Note

There is only one majority number in the array.

Example

For [3,1,2,3,2,3,3,4,4,4] and k = 3, return 3

Challenge

O(n) time and O(k) extra space

----------------------------- thinking -------------------------------------
http://codeanytime.blogspot.com/2014/12/majority-number-iii.html
http://www.cnblogs.com/lishiblog/p/4189468.html
----------------------------- codes ---------------------------------------
class Solution {
public:
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
int majorityNumber(vector<int> nums, int k) {
// write your code here
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
if (map.find(nums[i]) == map.end()) {
if (map.size() < k) {
map[nums[i]] = 1;
} else {
vector<int> zero_keys;
for (auto it = map.begin(); it != map.end(); ++it) {
it->second--;
if (it->second == 0) {
zero_keys.push_back(it->first);
}
}
for (int k = 0; k < zero_keys.size(); k++) {
map.erase(zero_keys[k]);
}
}
} else {
map[nums[i]] = map[nums[i]] + 1;
}
}
int res = map.begin()->first;
int val = map.begin()->second;
for (auto it = map.begin(); it != map.end(); ++it) {
if (it->second > val) {
res = it->first;
val = it->second;
}
}
return res;
}
};

Monday, March 30, 2015

Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

------------------- thinking ---------------------------

BUGs -> pay attention to the comparison -> bigger or smaller

http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html

------------------- codes -----------------------------

/**

* Definition of Interval:

* classs Interval {

* int start, end;

* Interval(int start, int end) {

* this->start = start;

* this->end = end;

* }

class Solution {

public:

/**

* Insert newInterval into intervals.

* @param intervals: Sorted interval list.

* @param newInterval: new interval.

* @return: A new interval list.

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {

// write your code here

vector<Interval> result;

int i = 0;

while (i < intervals.size()) {

if (newInterval.start > intervals[i].end) {

result.push_back(intervals[i]);

} else if (newInterval.end < intervals[i].start) {

break;

} else {

newInterval.start = newInterval.start<intervals[i].start?newInterval.start:intervals[i].start;

newInterval.end = newInterval.end>intervals[i].end?newInterval.end:intervals[i].end;

}

i++;

}

result.push_back(newInterval);

for (int k = i; k < intervals.size(); k++) {

result.push_back(intervals[k]);

}

return result;

}

};

Sunday, March 29, 2015

Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A-->B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Note

You can assume that there is at least one topological order in the graph.

Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]

[0, 2, 3, 1, 5, 4]

....

---------------------- thinking ------------------------------
https://hellosmallworld123.wordpress.com/2014/04/17/topological-sort/
http://www.cnblogs.com/lishiblog/p/4187867.html
---------------------- codes ---------------------------------
/**
* Definition for Directed graph.
* struct DirectedGraphNode {
* int label;
* vector<DirectedGraphNode *> neighbors;
* DirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
/**
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
// write your code here
vector<DirectedGraphNode*> result;
vector<DirectedGraphNode*>roots = findRoot(graph);
stack<DirectedGraphNode*> stack;
unordered_set<DirectedGraphNode*> visited;
for (int i = 0; i < roots.size(); i++) {
stack.push(roots[i]);
visited.insert(roots[i]);
}
while (!stack.empty()) {
DirectedGraphNode* cur = stack.top();
bool all_visited = true;
for (int i = 0; i < cur->neighbors.size(); i++) {
if (visited.find(cur->neighbors[i]) == visited.end()) {
all_visited = false;
visited.insert(cur->neighbors[i]);
stack.push(cur->neighbors[i]);
//bug here : only push one child at a time
break;
}
}
if (all_visited) {
result.insert(result.begin(), cur);
stack.pop();
}
}
return result;
}
//bug here: a DAG might have multiple root nodes to start
vector<DirectedGraphNode*> findRoot(vector<DirectedGraphNode*> &graph) {
unordered_set<DirectedGraphNode*> set;
for (int i = 0; i < graph.size(); i++) {
for (int k = 0; k < graph[i]->neighbors.size(); k++) {
if (set.find(graph[i]->neighbors[k]) == set.end()) {
set.insert(graph[i]->neighbors[k]);
}
}
}
vector<DirectedGraphNode*> result;
for (int i = 0; i < graph.size(); i++) {
if (set.find(graph[i]) == set.end()) {
result.push_back(graph[i]);
}
}
return result;
}
};

Saturday, March 28, 2015

Remove Node in Binary Search Tree Show result

Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

/ \

3 6

/ \

2 4

Remove 3, you can either return:

/ \

2 6

or :

/ \

4 6

--------------- thinking -------------------------
BUG: remember to update parent info of a deleting node

A better solution here:
http://www.dailyfreecode.com/code/insert-delete-node-binary-search-tree-2843.aspx
--------------- codes --------------------------
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param value: Remove the node with given value.
* @return: The root of the binary search tree after removal.
*/
TreeNode* removeNode(TreeNode* root, int value) {
// write your code here
//find the node
if (root == NULL) return root;
TreeNode *parent = NULL;
TreeNode *target = finder(root, value, parent);
if (target == root && root->left == NULL && root->right == NULL) return NULL;
if (target == NULL) return root;
if (target->left == NULL && target->right == NULL) {
if (parent->left == target) {
parent->left = NULL;
} else {
parent->right = NULL;
}
return root;
}
remover(target, parent);
return root;
}
TreeNode* finder(TreeNode* root, int value, TreeNode* &parent) {
TreeNode *cur = root;
parent = root;
while (cur) {
if (cur->val == value) {
return cur;
} else if (cur->val > value) {
parent = cur;
cur = cur->left;
} else if (cur->val < value) {
parent = cur;
cur = cur->right;
}
}
return NULL;
}
void remover(TreeNode* root, TreeNode* &parent) {
if (root->left == NULL && root->right == NULL) {
if (parent->left == root) {
parent->left = NULL;
} else {
parent->right = NULL;
}
return;
}
parent = root;
if (root->left) {
TreeNode *rightmost = root->left;
while (rightmost->right) {
parent = rightmost;
rightmost = rightmost->right;
}
root->val = rightmost->val;
if (rightmost->left == NULL) {
if (parent->left == rightmost) {
parent->left = NULL;
} else {
parent->right = NULL;
}
return;
} else {
remover(rightmost, parent);
}
} else {
TreeNode *leftmost = root->right;
while (leftmost->left) {
parent = leftmost;
leftmost = leftmost->left;
}
root->val = leftmost->val;
if (leftmost->right == NULL) {
if (parent->left == leftmost) {
parent->left = NULL;
} else {
parent->right = NULL;
}
return;
} else {
remover(leftmost, parent);
}
}
}
};

Friday, March 27, 2015

Median II

Numbers keep coming, return the median of numbers at every time a new number added.

Example

For numbers coming list: [1, 2, 3, 4, 5], return [1, 1, 2, 2, 3]

For numbers coming list: [4, 5, 1, 3, 2, 6, 0], return [4, 4, 4, 3, 3, 3, 3]

For numbers coming list: [2, 20, 100], return [2, 2, 20]

Challenge

O(nlogn) time

Clarification

What's the definition of Median?

Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is A[(n-1)/2].
For example, if A=[1,2,3], median is 2. If A=[1,19], median is 1.

----------------------------- thinking ----------------------------------
Bug -> we need to consider the equal numbers in the codes

Attention!!!! the usage of priority queue in this question

http://blog.csdn.net/nicaishibiantai/article/details/43634367
------------------------------- codes ---------------------------------------
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of numbers
*/
vector<int> medianII(vector<int> &nums) {
// write your code here
priority_queue<int, vector<int>, greater<int>> minheap;
priority_queue<int> maxheap;
vector<int> result(nums.size());
for (int i = 0; i < nums.size(); i++) {
if (minheap.size() == maxheap.size()) {
if (minheap.size() == 0) {
result[i] = nums[i];
maxheap.push(nums[i]);
} else {
if (nums[i] >= maxheap.top() && nums[i] <= minheap.top()) {
result[i] = nums[i];
maxheap.push(nums[i]);
} else if (nums[i] < maxheap.top()) {
result[i] = maxheap.top();
maxheap.push(nums[i]);
} else {
result[i] = minheap.top();
maxheap.push(minheap.top());
minheap.pop();
minheap.push(nums[i]);
}
}
} else {
if (nums[i] >= maxheap.top()) {
result[i] = maxheap.top();
minheap.push(nums[i]);
} else {
maxheap.push(nums[i]);
minheap.push(maxheap.top());
maxheap.pop();
result[i] = maxheap.top();
}
}
}
return result;
}
};

Thursday, March 26, 2015

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What's the definition of longest increasing subsequence?

* The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

* https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

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

-------------------------- codes ----------------------------------
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.size() == 0) return 0;
// write your code here
vector<int> sub_max(nums.size(), 1);
for (int j = 1; j < nums.size(); j++) {
int index = j - 1;
while (index>=0) {
if (nums[index] <= nums[j] && (sub_max[index] + 1 > sub_max[j])) {
sub_max[j] = sub_max[index] + 1;
}
index--;
}
}
int max = 1;
for (int i = 1; i < sub_max.size(); i++) {
if (sub_max[i] > max) {
max = sub_max[i];
}
}
return max;
}
};

Subset II

Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

------------------------- thinking --------------------------
http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html
------------------------ codes -----------------------------
class Solution:
# @param num, a list of integer
# @return a list of lists of integer
def subsetsWithDup(self, S):
if len(S) == 0:
return [[]]
S.sort()
outs = [[]]
start = 0
next = 0
#bug here, pay attention
while start < len(S):
if next < len(S) and S[next] == S[start]:
next += 1
continue

insrt_eles = []
new_outs = []
for i in range(start, next):
insrt_eles.append(S[start])
for j in outs:
new_out = j + insrt_eles
new_outs.append(new_out)
start = next
outs = outs + new_outs
return outs

Tuesday, March 24, 2015

Useful websites

http://bangbingsyb.blogspot.com/
https://codesolutiony.wordpress.com/category/lintcode/
http://isocpp.org/wiki/faq/how-to-learn-cpp#design-books

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

http://nlp.stanford.edu/IR-book/html/htmledition/web-crawling-and-indexes-1.html
http://www.linuxfromscratch.org/

https://hellosmallworld123.wordpress.com/category/interview-questions/facebook/

http://www.codeproject.com/Articles/96942/Singleton-Design-Pattern-and-Thread-Safety

http://www.ocoudert.com/blog/2010/07/07/how-to-write-abstract-iterators-in-c/

http://www.fgdsb.com/archives/

Max Tree

Given an integer array with no duplicates. A max tree building on this array is defined as follow:

The root is the maximum number in the array
The left subtree and right subtree are the max trees of the subarray divided by the root number.
Construct the max tree by the given array.
还是用到了ordered stack。对于每个数，他的左右右节点是在他与第一个比他大的数之间，比他小的最大数，因此维护一个递减stack就可以得到。

----------------------- thinking----------------------------
https://codesolutiony.wordpress.com/2015/01/28/lintcode-max-tree/
---------------------- codes ----------------------------------
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param A: Given an integer array with no duplicates.
* @return: The root of max tree.
*/
TreeNode* maxTree(vector<int> A) {
// write your code here
stack<TreeNode*> stack;
for (int i = 0; i < A.size(); i++) {
TreeNode * pre = NULL;
TreeNode * ele = new TreeNode(A[i]);
while (!stack.empty() && stack.top()->val < A[i]) {
TreeNode *cur = stack.top();
stack.pop();
cur->right = pre;
pre = cur;
ele->left = cur;
}
stack.push(ele);
}
TreeNode * pre = NULL;
while (!stack.empty()) {
TreeNode * cur = stack.top();
stack.pop();
cur->right = pre;
pre = cur;
}
return pre;
}
};

【转贴】面试中的clarifying questions

【转载】http://bangbingsyb.blogspot.com/2014/11/leetcode-read-n-characters-given-read4.htmle-read-n-characters-given-read4.html

Sunday, November 30, 2014

面试中的clarifying questions

面试题经常有意无意字面上很含糊，这个时候一定需要和面世官交流搞清楚确切的意思。总结一下每个topic需要澄清的地方：

1. Array:

(1) Sorted or not?

(2) How many elements?

(3) Element type? Int, float, double?

(4) What's the range of those numbers? Positive or negative?

(5) Contain duplicates or not?

(6) Subsequence: adjacent or not?

2. Binary tree:

(1) Binary search tree or normal binary tree?

(2) Balanced or not?

(3) Complete or not?

(4) Has parent pointer or not?

3. Linked list:

(1) Singly or doubly linked list?

(2) Has duplicated nodal value or not?

4. String:

(1) Need to remove white spaces? Tab and newline?

(2) Only has digits? English letters? Upper or lower case?

5. Graph:

(1) How many nodes and edges?

(2) Directed or undirected?

(3) Edges have weights? If so, what's the range?

(4) Has loops? Negative sum loops?

6. Return value:
(1) What should my method return?
(2) If there are multiple solutions to the problem, which one should be returned?
(3) If it should return multiple values, do you have any preference on what to return?
(4) What should I do/return if the input is invalid / does not match the constraints?

Monday, March 23, 2015

美国CS面试经验分享【转帖】

7094182

分类：互联网2011-12-22 09:33 924人阅读评论(0) 收藏举报

面试google数据结构algorithmdecoratorrecursion

目录(?)[+]

美国CS面试经验分享

过去的一年多里，参加了一些面试，虽然面过的公司不多，但都从头一直走到尾。毕竟自己也是花了大量的时间和精力在这一场场的面试里。所以，就絮叨下自己的一些经验，希望能给在美国找实习找工作的同学们提供一点点帮助。

开始前的一些说明：

1. 笔者只是一介小本科，虽然留了学，但是留了级，学识浅薄，目光短浅，文章若有不恰之处，恳请各位大牛不吝指正！

2. 笔者面试的岗位均为Software Engineer，俗称“程序猿”。如果读者是非CS专业或没有找此类工作的需求，请ctrl + w。本文更多的倾向于CS技术层面，关于面试仪表妆容礼仪等等的其他问题，请出门右拐。

3. 鉴于保密协议，本文只谈面试准备材料和方法，不涉及任何具体面试题。（当然，你如果单独请笔者吃饭，可以考虑）

4. 本文涉及的内容更多地适用于在美国本土的技术面试。美国的面试更加正式规范，国内同学可做适当参考。

5. 个人认为，面试的成功 = 60%的平时积累 + 30%的考前准备 + 10%的其他因素（如自信、谈吐）。所以，面试的准备对于我们这类凡人来说，异常重要；靠平时积累就能虐了面试官的大牛，不在本文考虑之列。

我面过的公司：

公司	时间	岗位	地点	过程
百度	2010年	实习	中关村总部	3轮onsite
Microsoft	2011上半年	实习	西雅图总部	1轮on-campus + 4轮onsite
Bloomberg	2011上半年	实习	纽约总部	1轮网上答题 + 1轮电话面试 + 3轮onsite
Google	2011下半年	全职	硅谷总部	2轮电话面试 + 5轮onsite

笔者运气较好，除了在微软败在了最后一轮大manager的石榴裙下，其他三家都顺利拿到了offer：先后在百度和Bloomberg实习，并将于明年正式加入Google工作。

下面将分Behavior Question和Technical Question分别介绍个人的面试准备技巧：

I. Behavior Question

这类问题的特点是，易准备，好回答，必出现。所以一定要花几个小时好好准备，写写提纲，面试前对着镜子说几次。

a. HR Question

最无聊的一类问题，比如“why Microsoft？”、“what’s your plan in 5 years? ” 一般为HR所喜欢。

推荐准备材料：http://hrinterviews.blogspot.com/。把这64道题刷一下，所有的HR问题都不会是问题了。准备的方法类似于托福口语，准备几个段子，反复用，就很充分了。

另外，回答一定要真诚。比如，如果被问到“what’s your weakness?”，你如果回答：我太追求完美太热爱工作巴拉巴拉——太过时太恶心人了吧，亲！

b. Talk about your project

一般会在面试的开始被问及，必然会被问到的题目之一。把简历上的项目好好地阐述，辅以画图更佳。一些经典的Follow up是：What is the most challenging part? What will you do if you have opportunities to improve it?

百分一万的准备好这些问题！面试官通常会刨根问底。答的吭吭哧哧，几乎是不诚信的表现。

c. Question for interviewer

一般会在面试的最后十分钟里，面试官会请你提出问题。这是你展现对公司的激情、个人的兴趣、和面试官套近乎等等等等的大好机会。不要说“no”或者仅仅问“啥时知道结果啊，哥们”这类的问题。至少准备五个有深度的问题。

个人经验来说，最好的方法还是随机应变，根据之前面试的情况来合理提问。比如，我在Google的一次面试里，面试官无意间提及他在设计一门新的编程语言。面试最后，我就满脸好奇地说：“talk about your language, please”。然后我和他就编程语言的设计各方面进行了一些小讨论，他最后离开时万分兴奋。就这样，对面试官的尊重，自身兴趣和能力的展现，对技术的激情——一脉相承，水到渠成。

II. Technical Question

技术面试的最核心部分。

下面是一些笔者使用过的材料（请适当支持正版）：

Programming Interviews Exposed

入门级书籍，可以了解一些基本概念。

Cracking the Coding Interview

中级书籍，经典必备教材，重点推荐，重中之重！从头到尾我做过五次。

Hacking a Google Interview

MIT的一门课程，教学Handout可作为中级题目练习。

mitbbs的JobHunt板块

资料很多，水帖更多，可以寻找到很多战友和第一手的面经。可以重点学习里面的精华贴。

http://www.sureinterview.com/

中高级的算法题。

http://www.leetcode.com/

高级算法题，难度偏难，可做适当了解。个人认为，如果不是面Google，里面的题目被面到的可能性不高。

Topcoder

知名的编程练习网站，有一些相关的材料和教材很经典。

面经来源：

mitbbs的JobHunt板块，Glassdoor，CareerCup

C++ FAQ

非常有名的高级C++语言学习网站。啃下来会很有帮助。主要的目的是为了应付关于Object-Oriented的相关题目。

如果你准备用Java，也请至少把语言使用能力达到中阶。

Object Oriented Analysis and Design （Oreilly Head First.）和

Design Patterns Oct.2004（Oreilly Head First）

两本OOP的经典教材。据说Design Pattern挺重要，但个人从未遇到过相关题目。但是大致了解一下，总不会错。

Wikipedia/Google

仔细查阅每一个你所不知道的算法、数据结构和概念，做好笔记。等你在面试时发现一个名词你见过却不知道是什么，你会把肠子悔青的。

每个公司所关注的技术

这一点非常重要。比如面Google，就要把Distributed System和Information Retrieval的相关技术了解下，好好看看他家的经典Paper：Map-Reduce和Google File System；比如面Bloomberg，对C++的了解和使用一定要啃到一定级别；比如面Amazon，要准备好OOP。

相信我，花六个月的时间，把上述的所有材料搞定，世界上没有哪个技术公司你进不去的。(You know I’m kidding… But it’s basically the fact. )

你可能会问，那如果我只有一周，或者两天，甚至更短的时间去准备一场面试，该怎么办？

我的回答是：第一，如果它是phone interview或者on-campus interview，那只是初级的筛选，难度不会很高，just relax；第二，拿下上述材料中的初级和中级部分（再次强调Cracking the Coding Interview这本书），然后根据公司来决定学习重点，这样就应该有不错的发挥了。毕竟个人积累不同，尽力而为吧。

当你拿到on-site的邀请时，不要去炫耀你的成就了，赶紧去准备之后的面试吧。On-site的难度深度都会有很大的提高。那才是真正的战斗！过不了on-site，你什么也都不是！

下面我会分topic介绍一下准备重点。在你准备面试的过程中，你也应该有一份这样类似的word文档，记录你每天学习到的所有东西。

面试准备绝不是背诵和题海战术，而是能帮助你对CS知识的理解和运用提升到新高度的过程。

1.) Time Complexity分析

基础中的基础。绝大部分情况下，算法的时间复杂度能一眼看出来。

如果是面Google，需要掌握一些严密的时间复杂度的数学推导，有些算法不是一眼能看出时间复杂度的。

2.) Coding

废话！

但是需要练习的是在纸上和在白板上写code。（不要小看这件事！关掉愚蠢的Eclipse和VC吧）

更关键的是，写的代码要一次成型，bug-free，即使多花点时间。如果你平时有写完代码再慢慢debug的习惯，是很不利的。被面试官找出bug来，你的分数会被大扣分！

语言选择上，C++和Java，抑或 C#，都是无可挑剔的选择——好比，孙权刘备曹操主；

Python，Ruby，Perl啥的也还行，在字符串处理上有奇效，但面试官未必买账，因为有些问题他需要你从底层实现起——貂蝉诸葛主；

啥，你说汇编？——黄盖主！还是开局鞭挞至一血的！

3.) Data Structure

题目类型大多是：给定一些实际需求，来设计相应的数据结构。所以，对每一种数据结构的特点、时间复杂度要非常熟悉，而且要有很敏锐的第一感。

a. Hashtables

可以说是人类发明的最重要的数据结构之一了。面试时的出现率极高！

保证你玩得转Collision strategies和hash function。如果深入到如何设计具体的hash function，题目的难度也会是很大的。

b. Trees

BST，BFS，DFS，trie，Kruskal’s Algorithm ，Prim’s Algorithm

Balanced tree就没什么研究必要了。

c. Graphs:

图的几种储存形式，BFS/DFS，Dijkstra，A* algorithm

d. Linked List/Queue/Stack/Heap

相应操作的时间复杂度要了如指掌。保证你能轻松写出C++ STL或Java Library对应类库的API。

4.) Algorithm

重中之重的重中之重！

Sort，Recursion，Binary Search，Greedy Strategy等等等等要全面准备到。

Dynamic Programming的一些经典题也要会。如果面Google，可能要准备一下DP的高级题目。

笔者认为，准备这类题目毫无捷径，只有不断刷题，总结，刷题，总结。要培养出对题目的直觉，这是一个漫长的训练过程。

在面试的时候，一般来说，要先给面试官提供一个暴力搜索的方法，然后计算复杂度。然后再慢慢做优化。面试时一定要keep talking，提出自己的想法，展现自己的思路。如果你get stuck，面试官也会给出相应的hint（当然这是会被扣分的）。

5.) System Design

常见形式是：给定大数据量和N台机器，解决一个特定的问题。较开放的题目。在网络公司的面试中经常出现。

解法有固定套路，可以参考Cracking the Coding Interview 相关章节，并自己做一些总结和应用。这类题目看起来很难，掌握方法后，实际难度并不算很高，而且容易展现自身的分析能力，容易出彩。当然，面试官很可能会做适当的延伸，涉及到具体的技术，这就靠自身平时的积累见招拆招了。

Web Crawler (http://nlp.stanford.edu/IR-book/html/htmledition/web-crawling-and-indexes-1.html)

Google MapReduce (http://labs.google.com/papers/mapreduce.html)

Google File System (http://labs.google.com/papers/gfs.html)

6.) Mathematics

重点在于组合数学和概率论。会有一些这类的变体出现。稍微准备准备就可以了，相信国人的数学水平，绝对凌驾于世界巅峰，不管他面试官是阿三还是老美还是欧洲人。

7.) Operating Systems

Processes vs. Threads

Locks, mutexes and semaphores

Deadlock and livelock

Scheduling: FIFO, priority, shortest remaining time, round robin, and multi level.

不算特别重要。至少笔者从未遇过相关题目。

8.) Bit manipulation

两个目的：应付该类面试题（出现率不高，但是Google喜欢问）；

用于自己的编程技巧——尽管有些silly，但是在代码中整一点bit manipulation，是很geek的事。

9.) Design Pattern

了解这些：Observer Pattern, Decorator pattern, Factory Pattern, Singleton Pattern

面试是一个很吃经验的考试。不要顾忌前几次的失败，那都是必要的练级。

最后，送上我笃信的一句话："Success is just like being pregnant. Everybody congratulates you but nobody knows how many times you were fucked"。

谨以此祝愿所有的童鞋都能获得自己Dream Company的offer！

Tuesday, March 31, 2015

Median

Majority Number III

Monday, March 30, 2015

Insert Interval

Sunday, March 29, 2015

Topological Sorting

Saturday, March 28, 2015

Friday, March 27, 2015

Median II

Thursday, March 26, 2015

Longest Increasing Subsequence

Subsets II

Tuesday, March 24, 2015

Sunday, November 30, 2014

面试中的clarifying questions

Monday, March 23, 2015

美国CS面试经验分享 【转帖】

美国CS面试经验分享

美国CS面试经验分享【转帖】