g**e
发帖数: 6127 | 1 As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
我要啊，哈哈。
早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
们穿着拖鞋就来了，一看就是很nb的geek。
1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
抛出。还有在
写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
么时候返回null，什么时候throw exception之类。
1. hr
被HR轰炸了一个小时，问了我各种你们能想到的behavior问题。好些如果没工作经验，
真的很难回答，背答案是没用的。比如问你在有些情况下，你需要绕过公司的一些规定
和policy来完成一些工作，你会怎么办。比如如何控制risk，当你做了个错误的决定，
如何反应。当你screw up了一个project，你怎么办等等。都要举出工作中的例子来回
答。非常难缠。
2. design a library. 详细到每个class， interface和内部的方法。这个如果设计过
ecom网站的话，非常容易，稍微改改就是了。另外问到查询的时候如何根据当前的
input给出suggestion，版上经常见的。我说用trie，然后让介绍了一下trie map是怎
么回事，每个节点存怎样的数据，给出了两种方案，各自优缺点。
这个说了整整一个小时。
3. HM,solve boggle puzzle. 给定一个5x5方格，每格一个随机生成的字母。要求给出
这个
board里面所有可以组成的单词。每格方格最多可以有8个方向，当然四条边上的方格只
能有
3个或者5个可移动的方向。以及使用的方格不能再用。要求写出95％以上complete代码
，40分钟时间。
直接上了递归，从每个格子开始，用一个hashset保存已走过的path。每次检查当前的
选择，并去掉已经访问过的。这个getNextAvailableMove方法写了好长，因为要考虑边
界。最后
还是40分钟内写完了，基本work。
然后又上了15分钟的behavior questions...
4. 午饭，约旦mm没让我吃两口，一直在问我过去做的project，穿插一堆behavior
question。 coding是一个简单的anagram题。给定一个string array， return all
groups of strings that are anagrams. 俺用了个int[26]做signature，一个HashMap
>。穿插解释java hashmap的实现，什么是open/close hashing
。代码一次性写完通过。
最后10分钟问了个设计题。如何设计一个类似facebook这样的framework，可以让不同
的developer来开发不同的小游戏之类的程序，你重点要考虑哪些内容。这个我就根据
自己平时的
经验说了一下，看起来人家挺满意。
5.最后一个很pp但是很凶的mm，说话象机关枪。上来又问了一堆behavior， how do
you make tough decisions, what if the project went south, how do you make
your clients happy even if they have some ridiculous requests, etc etc. 经常
没等我说完就打断
。
然后来了个题： given an array of int, each int appears exactly TWICE in the
array. find and return the int such that this pair of int has the max
distance between each other in this array.
e.g. [2, 1, 1, 3, 2, 3]
2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2
似乎bar raiser终于来了。给了个用hashmap的，让写100％ compilable代码。写完问
我空间复杂度，然后如何改进。我问你的意思是可以O(n)时间，O(1)空间？她不置可否
。想了一下DP没想出来，就给了个简单的O(n^2)时间的，没想到这就是她要的，ft。
这个题目请大牛告诉我，可不可以O(n) time O(1) space？
基本就是这样。他们纽约分店似乎刚开张，office很小。面试的人都是从总部飞来的。
总体感觉还可以，比想象的简单多了。除非给我一个无法拒绝的offer，否则我今天就
是来打酱油的了。他们昨天今天似乎一共面了14个人，但是要招4-6个，成功率应该还
是很高的，呵呵。
跳槽终于告一段落，新的生活即将开始。
希望对大家有用，也祝福大家各自找到心满意足的工作。 | l****n
发帖数: 274 | | w**********n
发帖数: 29 | | C*Y
发帖数: 679 | 4 niu
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| s*****y
发帖数: 897 | 5 最后究竟她想要
o(n^2) time o(1) space
还是o(n) time o(1) space 阿
还有其他条件吗？
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| w*****3
发帖数: 101 | | g**e
发帖数: 6127 | 7 我给了个O(n^2) time O(1) space她就满意了，也不知道是不是真满意，呵呵
有啥思路？
【在 s*****y 的大作中提到】
: 最后究竟她想要
: o(n^2) time o(1) space
: 还是o(n) time o(1) space 阿
: 还有其他条件吗？
| g**e
发帖数: 6127 | 8 收到offer email了。。。
【在 g**e 的大作中提到】
: 我给了个O(n^2) time O(1) space她就满意了，也不知道是不是真满意，呵呵
: 有啥思路？
| m********l
发帖数: 4394 | 9 总部在Vegas?
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| g**e
发帖数: 6127 | 10 总部在西雅图
【在 m********l 的大作中提到】
: 总部在Vegas?
| | | s*****n
发帖数: 5488 | 11 第三题怎么做?
看上去可以转化为一个graph.然后每个节点开始，做25次bfs.每走到一个节点，查字典
是不是一个单词？
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| s*****n
发帖数: 5488 | 12 Nordstorm这莫变态？
【在 g**e 的大作中提到】
: 总部在西雅图
| g**e
发帖数: 6127 | 13 为啥会是nordstorm... 是版上喜闻乐见的某A公司，呵呵
【在 s*****n 的大作中提到】
: Nordstorm这莫变态？
| s*****n
发帖数: 5488 | 14 因为著名的卖鞋的总部在西雅图就是NordStrom. 家里有个败家的媳妇就明白了。
【在 g**e 的大作中提到】
: 为啥会是nordstorm... 是版上喜闻乐见的某A公司，呵呵
| s*******d
发帖数: 4135 | 15 非常强，boggle那道题能多说说么？
【在 g**e 的大作中提到】
: 收到offer email了。。。
| m********l
发帖数: 4394 | 16 果然是.
就是那中国人当老板的那个?
俺面过SQL/.NET programmer那职
不过他们是个Java/C++ Shop
【在 g**e 的大作中提到】
: 为啥会是nordstorm... 是版上喜闻乐见的某A公司，呵呵
| g**e
发帖数: 6127 | 17 另外一个heads up，今天猎头告诉我，A的recruitor分两种，工作经验在0-2yr exp的
，都是走的campus recruitor，2 yr以上的是exp hire。感觉面试的侧重点很不同，我
没有遇到任何很难的DP题目
人找
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| G****2
发帖数: 37 | 18 cong and zan！
准备从这个OFFER了？ | h*********n
发帖数: 46 | 19 楼主牛逼啊。我觉得O(n)time, O(1) space的算法没有吧。
人找
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| a*****a
发帖数: 46 | 20 排序呢？O(nlogn) time, O(1) space.
typedef pair ids;
bool cmpIds(ids a1, ids a2) {
return (a1.first < a2.first);
}
int maxDistance(int a[], int n) {
vector numid;
for(int i=0; i
numid.push_back( make_pair(a[i], i) );
sort( numid.begin(), numid.end(), cmpIds );
int maxd=0;
for(int i=1; i
int d = numid[i].second - numid[i-1].first;
if (d<0) d*=-1;
if (d>maxd) maxd = d;
}
return maxd;
} | | | a*****a
发帖数: 46 | 21 boggle puzzle那道题能详细说一下么？是每行/列/斜线组成一个词 还是 整个表组一
个词？ | s*****y
发帖数: 897 | 22 you use stl vector which is already not o(1) space.
【在 a*****a 的大作中提到】
: 排序呢？O(nlogn) time, O(1) space.
: typedef pair ids;
: bool cmpIds(ids a1, ids a2) {
: return (a1.first < a2.first);
: }
: int maxDistance(int a[], int n) {
: vector numid;
: for(int i=0; i: numid.push_back( make_pair(a[i], i) );
: sort( numid.begin(), numid.end(), cmpIds );
| a*****a
发帖数: 46 | 23 呀，是的啊，丢人了。。。
【在 s*****y 的大作中提到】
: you use stl vector which is already not o(1) space.
| f**********7
发帖数: 1139 | | f**********7
发帖数: 1139 | | i**********e
发帖数: 1145 | 26 我写的 boggle 游戏算法，DFS + trie.
一秒以内给出所有 5x5 的答案。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Trie {
bool end;
Trie *children[26];
Trie() {
end = false;
memset(children, NULL, sizeof(children));
}
void insert(const char *word) {
const char *s = word;
Trie *p = this;
while (*s) {
int j = *s-'A';
assert(0 <= j && j < 26);
if (!p->children[j])
p->children[j] = new Trie();
p = p->children[j];
s++;
}
p->end = true;
}
};
const int MAX_ROWS = 5;
const int MAX_COLS = 5;
void dfs(int row, int col,
char *grid[],
int nRows, int nCols,
const Trie *prefix,
string currentWord,
bool visited[][MAX_COLS],
hash_set &answer) {
if (row < 0 || row > nRows-1 || col < 0 || col > nCols-1) return;
if (visited[row][col]) return;
currentWord += grid[row][col];
int idx = currentWord.back()-'A';
if (!prefix->children[idx]) return;
prefix = prefix->children[idx];
visited[row][col] = true;
if (currentWord.length() >= 3 &&
prefix->end &&
answer.find(currentWord) == answer.end()) {
answer.insert(currentWord);
}
dfs(row, col+1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row, col-1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row+1, col, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row-1, col, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row+1, col+1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row+1, col-1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row-1, col+1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
dfs(row-1, col-1, grid, nRows, nCols, prefix, currentWord, visited,
answer);
visited[row][col] = false;
}
vector findBoggle(char *grid[],
int nRows, int nCols,
const Trie *dictionary) {
hash_set answer;
for (int row = 0; row < nRows; row++) {
for (int col = 0; col < nCols; col++) {
//cout << "DFS at: " << row << ", " << col << endl;
bool visited[MAX_ROWS][MAX_COLS] = { false };
dfs(row, col, grid, nRows, nCols, dictionary, "", visited,
answer);
}
}
vector sortedAnswer;
for (hash_set::iterator iter = answer.begin();
iter != answer.end();
++iter) {
sortedAnswer.push_back(*iter);
}
sort(sortedAnswer.begin(), sortedAnswer.end());
return sortedAnswer;
}
Trie *readDictionary(string fileName) {
ifstream fin(fileName);
Trie *dictionary = new Trie();
char word[256];
while (fin >> word) {
dictionary->insert(word);
}
fin.close();
return dictionary;
}
int main() {
Trie *dictionary = readDictionary("dict.txt");
char *grid[MAX_ROWS] = {
"IKNOA",
"TWYZB",
"ORNTC",
"AEOSE",
"THRSE"
};
int nRows = 5, nCols = 5;
vector answers = findBoggle(grid, nRows, nCols, dictionary);
int nAnswers = answers.size();
cout << "Found " << nAnswers << " Solutions!\n";
for (int i = 0; i < nAnswers; i++) {
cout << answers[i] << endl;
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*******d 的大作中提到】
: 非常强，boggle那道题能多说说么？
| d*******r
发帖数: 208 | 27 Thanks for sharing and congrats!
for 3.
How about use a simple recursion?
int maxdistance(int a[], int i, int j) {
if (i>=j) { return 0; }
if (a[i] == a[j]) { return j-i; }
else { return std::max(maxdistance(a, i+1, j),
maxdistance(a, i, j-1)); }
}
人找
【在 g**e 的大作中提到】
: As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
: 我要啊，哈哈。
: 早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
: 们穿着拖鞋就来了，一看就是很nb的geek。
: 1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
: 根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
: 的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
: 抛出。还有在
: 写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
: 么时候返回null，什么时候throw exception之类。
| s*****y
发帖数: 897 | 28 recursion is not o(1) space.
【在 d*******r 的大作中提到】
: Thanks for sharing and congrats!
: for 3.
: How about use a simple recursion?
: int maxdistance(int a[], int i, int j) {
: if (i>=j) { return 0; }
: if (a[i] == a[j]) { return j-i; }
: else { return std::max(maxdistance(a, i+1, j),
: maxdistance(a, i, j-1)); }
: }
:
| g***3
发帖数: 2304 | | d*******r
发帖数: 208 | 30 yes. it uses lots of stack frame. maybe can do better by memorization, like
fibnacci
【在 s*****y 的大作中提到】
: recursion is not o(1) space.
| | | z*******y
发帖数: 578 | 31 楼主很厉害 应该是准备的相当充分了
四个字 “行云流水”
恭喜了 | h**********8
发帖数: 267 | |
|
