b***m
发帖数: 5987 | 1 十点半开始，又得起大早进城。不求bless，当M家练手吧。去Seattle上班太麻烦了…
… |
l*****a
发帖数: 14598 | 2 你拿个Sr position
package肯定比M的强
【在 b***m 的大作中提到】
: 十点半开始，又得起大早进城。不求bless，当M家练手吧。去Seattle上班太麻烦了…
: …
|
f********4
发帖数: 988 | 3 bless 大牛。。
我去A家面之前也这么想。。结果。。去了以后很容易就变节了。。
主要是他们说自己的group size很小，然后换组很平常。。还有我发现好多人带宠物上
班。。看起来好自由啊。。 |
p*****2
发帖数: 21240 | |
b***m
发帖数: 5987 | 5
Seller Service……我现在都不知道具体是什么。
【在 p*****2 的大作中提到】
: 什么组呀？AWS吗？
|
p*****2
发帖数: 21240 | 6
hiring manager是老中吗？
【在 b***m 的大作中提到】
:
: Seller Service……我现在都不知道具体是什么。
|
y***u
发帖数: 37 | 7 A家Senior的职位底薪大概多少? 15-20万吗? 有人知道吗? 谢谢! |
g**e
发帖数: 6127 | 8 seattle? 13起，20 base是不可能的.
【在 y***u 的大作中提到】
: A家Senior的职位底薪大概多少? 15-20万吗? 有人知道吗? 谢谢!
|
b***m
发帖数: 5987 | 9
目前神马都不知道。recruiter找上来，一轮电面后就直接onsite了。
【在 p*****2 的大作中提到】
:
: hiring manager是老中吗？
|
p*****2
发帖数: 21240 | 10
不可能吧？2都14万起了。
【在 g**e 的大作中提到】
: seattle? 13起，20 base是不可能的.
|
|
|
F********9
发帖数: 44 | 11 俺是明天A家多伦多的电面。
网上查了查面试官， 是 Customer Service Technology。
A在多伦多的分舵主要干啥呀？
Bless， 也 bless 自己。哈哈。 |
F********9
发帖数: 44 | |
b***m
发帖数: 5987 | 13 面完了，正在回家路上，晚上上面经。
【在 F********9 的大作中提到】
: 求大牛面经
|
h****n
发帖数: 1093 | |
l*****a
发帖数: 14598 | 15 deng!!!!!
【在 b***m 的大作中提到】
: 面完了，正在回家路上，晚上上面经。
|
s*****2
发帖数: 68 | |
b***m
发帖数: 5987 | 17 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
上面经（题都很传统）：
第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
test case。
第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
楼去附近的一家意大利店，一人买了一个三明治、一瓶可乐，然后回来在会议室边吃边
聊。基本行为问题居多，出了一个brainstorm题：用户在客户端浏览订单信息，页面狂
慢，怎么分析可能的原因？基本架构是：浏览器连load balancer（LB），LB连
application server（AS），AS连Database（DB）。更具体的，如果问题是在AS中，如
何定位可能的原因？
第四轮又是一个印度女孩儿，除了一道貌似简单的题：写一个函数，输入是整数数组，
输出是一对一对数值，表示该整数数组中连续数列的起始和终止值。比如数组是3，4，
5，7，8，14，15，20，那么输出是(3,5)(7,8)(14,15)(20,20)。数组可能是无序的，
允许in place排序。题解法思路并不难，但是corner case比较多。
第五轮是一个白人，senior manager，先让我design一个data structure，功能类似双
向queue，可以从front和end两端add、peek元素，以及用index i来随机访问队列中元
素，所有操作都必须是O(1)。要求设计、实现该data structure的主要结构、成员变量
、接口。这题完了之后，又做一道，提供一个二维boolean值的数组，如何找出连在一
起的true值的block数量。所谓连在一起，是某个cell跟另外一个cell上、下、左、右
相连，对角相连不算。比如下面这个数组，返回值为3：
000000000000000
111011110000001
010111000000000
000000000000000
最后是HR聊天，问了大致的个人情况，有否绿卡，什么时候可以开始上班，个人发展方
向和兴趣，有没有别的面试，期望多少薪水等等。说下周一告知是否有offer，如果有
offer，需要3、4天发出正式offer。
总体面试感觉不难，不知道会不会发offer。 |
b***m
发帖数: 5987 | 18 明天一早八点半去州政府定点单位接受下岗再就业培训！！ |
p*****s
发帖数: 57 | 19 haha
【在 b***m 的大作中提到】
: 明天一早八点半去州政府定点单位接受下岗再就业培训！！
|
b***m
发帖数: 5987 | 20
不培训不给发失业金…… ;-)
【在 p*****s 的大作中提到】
: haha
|
|
|
l*****a
发帖数: 14598 | 21 存下了
有时间再看
另外不是给20W也不去吗？
【在 b***m 的大作中提到】
: 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
: 上面经（题都很传统）：
: 第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
: 输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
: ()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
: test case。
: 第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
: 看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
: ，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
: 第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
|
b***m
发帖数: 5987 | 22
拿着A的offer才好抬M的啊。
【在 l*****a 的大作中提到】
: 存下了
: 有时间再看
: 另外不是给20W也不去吗？
|
p*****2
发帖数: 21240 | 23 牛。
那个queue你怎么做的？循环array可以吧？ |
e****e
发帖数: 418 | 24 Thanks for sharing. Big bless. |
t*******2
发帖数: 292 | 25 没老中啊，
【在 b***m 的大作中提到】
: 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
: 上面经（题都很传统）：
: 第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
: 输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
: ()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
: test case。
: 第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
: 看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
: ，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
: 第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
|
b***m
发帖数: 5987 | 26
没。除了白人就是烙印。
【在 t*******2 的大作中提到】
: 没老中啊，
|
b***m
发帖数: 5987 | 27
我用的hashmap。你的循环数组怎么做？
【在 p*****2 的大作中提到】
: 牛。
: 那个queue你怎么做的？循环array可以吧？
|
z********i
发帖数: 568 | 28 都要写程序吗？
第一个是只有一个符号，还是有任意多个不同符号？
第三个？
第四个：排序后，不久扫描一遍？
第五个：A）要求worst case O（1）还是average? If average, 不就是vector？
【在 b***m 的大作中提到】
: 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
: 上面经（题都很传统）：
: 第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
: 输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
: ()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
: test case。
: 第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
: 看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
: ，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
: 第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
|
z********i
发帖数: 568 | 29 牛啊！M投了好几个，一点消息都没有。是不是需要内部refer?
【在 b***m 的大作中提到】
:
: 我用的hashmap。你的循环数组怎么做？
|
b***m
发帖数: 5987 | 30
第一个是任意对符合，允许自定义。
第四个比较简单，但是code要考虑细节。
第五个用vector你在前面插入一个的代价是O(n)。
【在 z********i 的大作中提到】
: 都要写程序吗？
: 第一个是只有一个符号，还是有任意多个不同符号？
: 第三个？
: 第四个：排序后，不久扫描一遍？
: 第五个：A）要求worst case O（1）还是average? If average, 不就是vector？
|
|
|
b***m
发帖数: 5987 | 31
网投没用。refer最好。
【在 z********i 的大作中提到】
: 牛啊！M投了好几个，一点消息都没有。是不是需要内部refer?
|
e****e
发帖数: 418 | 32 Q5. Array.
1. Two indexes keep track of front and end.
2. Insert the first element in the middle of the array.
3. The following insertion(addFront and addEnd) expands towards the two ends
of array.
4. The retrieval is
get(int i) { return A[frontIndex + i]; }
4. When reach the 0, or A.length()-1, create a new array with doubling the
size of original one and copy the elements into the middle of the new array. |
b***m
发帖数: 5987 | 33
ends
array.
这也是方法之一。
【在 e****e 的大作中提到】
: Q5. Array.
: 1. Two indexes keep track of front and end.
: 2. Insert the first element in the middle of the array.
: 3. The following insertion(addFront and addEnd) expands towards the two ends
: of array.
: 4. The retrieval is
: get(int i) { return A[frontIndex + i]; }
: 4. When reach the 0, or A.length()-1, create a new array with doubling the
: size of original one and copy the elements into the middle of the new array.
|
l*********8
发帖数: 4642 | 34 谢谢分享！
【在 b***m 的大作中提到】
: 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
: 上面经（题都很传统）：
: 第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
: 输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
: ()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
: test case。
: 第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
: 看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
: ，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
: 第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
|
z********i
发帖数: 568 | 35 等A onsite后，有offer就从了，没消息再找人refer M 吧。
【在 b***m 的大作中提到】
:
: ends
: array.
: 这也是方法之一。
|
b***m
发帖数: 5987 | 36
A家offer应该能好些，对于我来说，只是上班不那么方便。
【在 z********i 的大作中提到】
: 等A onsite后，有offer就从了，没消息再找人refer M 吧。
|
b***m
发帖数: 5987 | 37 对了，第四个女烙印还考了一道找BST的next successor。 |
t*********n
发帖数: 89 | 38
hashmap的话应该是类似与LRU cache的结构。key 为index, 值为double linked list
node，记录队头队尾的index,如果从前面插入就是将队头的index_front-1,更新队头。
从后面插入就是index_end+1。随机取的话就是取key 为index_frount + i 那个。
感觉这样可以避免循环数组的超出空间的问题。
是这样吗？
【在 b***m 的大作中提到】
: 对了，第四个女烙印还考了一道找BST的next successor。
|
t*********n
发帖数: 89 | |
b***m
发帖数: 5987 | 40
list
我就是这么做的。
【在 t*********n 的大作中提到】
: 祝lz好运！
|
|
|
z********i
发帖数: 568 | 41 祝那个大offer!
【在 b***m 的大作中提到】
:
: list
: 我就是这么做的。
|
i****y
发帖数: 58 | |
c******t
发帖数: 391 | 43 感谢分享！
第一轮算括号的题，想到两种解法，用counter算左右括号数，以及压栈比较。
//For '(,)' only, use counter, left and right are half of length, e.g. for "
(())", the call
is validParen(2,2,"(())",0).
public static boolean validParen(int left, int right, String str, int
index){
if(left==0&&right==0)return true; //base case
if(str.length()%2==1)return false; //length must be even
if(left>right)return false;
if(left<0||right<0)return false;
if(str.charAt(index)=='(') return validParen(left-1,right, str,index
+1);
if(str.charAt(index)==')') return validParen(left,right-1, str,index
+1);
return true;
}
//or use stack
public static boolean validParen2(String str){
Stack stack = new Stack();
for(int i = 0; i
if(str.charAt(i)=='{'||str.charAt(i)=='['||str.charAt(i)=='('){
stack.push(str.charAt(i));
}
else{
if(str.charAt(i)=='}'){
if(stack.pop()!='{')
return false;
}
if(str.charAt(i)==']'){
if(stack.pop()!='[')
return false;
}
if(str.charAt(i)==')'){
if(stack.pop()!='(')
return false;
}
}
}
return true;
}
不知道思路对不对，请大牛指教！ |
b***m
发帖数: 5987 | 44
"
用栈就对了，连counter都不需要。
【在 c******t 的大作中提到】
: 感谢分享！
: 第一轮算括号的题，想到两种解法，用counter算左右括号数，以及压栈比较。
: //For '(,)' only, use counter, left and right are half of length, e.g. for "
: (())", the call
: is validParen(2,2,"(())",0).
: public static boolean validParen(int left, int right, String str, int
: index){
: if(left==0&&right==0)return true; //base case
: if(str.length()%2==1)return false; //length must be even
: if(left>right)return false;
|
r*******e
发帖数: 36 | |
e****e
发帖数: 418 | 46 有没有parent pointer?
【在 b***m 的大作中提到】
: 对了，第四个女烙印还考了一道找BST的next successor。
|
b***m
发帖数: 5987 | 47
这题比较open，我把有parent和没parent的情况都分析了一遍。
另外，这个面试官夸我whiteboard写得是她见过的candidate里面最漂亮的。;-)
【在 e****e 的大作中提到】
: 有没有parent pointer?
|
O******i
发帖数: 269 | 48 有哪些可能的原因？
出了一个brainstorm题：用户在客户端浏览订单信息，页面狂慢，怎么分析可能的原因
？基本架构是：浏览器连load balancer（LB），LB连application server（AS），AS
连Database（DB）。更具体的，如果问题是在AS中，如何定位可能的原因？
【在 b***m 的大作中提到】
:
: 这题比较open，我把有parent和没parent的情况都分析了一遍。
: 另外，这个面试官夸我whiteboard写得是她见过的candidate里面最漂亮的。;-)
|
b***m
发帖数: 5987 | 49
AS
这个也没有特别固定的答案吧，就看你分析的思路了。能否找出原因不是关键，你怎么
分析才最重要。
【在 O******i 的大作中提到】
: 有哪些可能的原因？
:
: 出了一个brainstorm题：用户在客户端浏览订单信息，页面狂慢，怎么分析可能的原因
: ？基本架构是：浏览器连load balancer（LB），LB连application server（AS），AS
: 连Database（DB）。更具体的，如果问题是在AS中，如何定位可能的原因？
|
O******i
发帖数: 269 | 50 给点思路和你说的例子吧，这种题我没啥头绪。
【在 b***m 的大作中提到】
:
: AS
: 这个也没有特别固定的答案吧，就看你分析的思路了。能否找出原因不是关键，你怎么
: 分析才最重要。
|
|
|
b***m
发帖数: 5987 | 51
其实考察的就是你的problem solving和troubleshooting。抛开客户端不谈，无非就是
如下因素：网络问题，看看是否有大量异常traffic；LB是否有过载，内存、交换文件
的使用是否异常；AS是否异常；DB是否异常。具体到几个service，LB的HTTP
connection pool是否使用过度，balance算法是否出现了超出设计预期；DB的
connection pool是否使用过度，是否有table被长期锁死，或者某些query超出可容忍
时长，数据库硬盘是否已满，内存临时表是否过大；AS是否有异常application，具体
到刷新订单出问题，order.java程序是否内部有死循环，从LB接收的数据是否有
corruption，发送到DB的数据是否正确，从DB接收的数据是否有问题，发往LB的数据是
否完整……具体到我熟悉的Linux+Apache+Perl+MySQL架构，在针对这个架构谈谈可能
出现的问题。基本意思就这样，我也是乱说。
【在 O******i 的大作中提到】
: 给点思路和你说的例子吧，这种题我没啥头绪。
|
F********9
发帖数: 44 | 52 design一个data structure，功能类似双
向queue，可以从front和end两端add、peek元素，以及用index i来随机访问队列中元
素，所有操作都必须是O(1)。
这个是要构造一个环来实现么？ |
O******i
发帖数: 269 | 53 多谢，我是想不到这么多，这要问我肯定挂。看来老同志多年累积的经验真不是盖的
【在 b***m 的大作中提到】
:
: 其实考察的就是你的problem solving和troubleshooting。抛开客户端不谈，无非就是
: 如下因素：网络问题，看看是否有大量异常traffic；LB是否有过载，内存、交换文件
: 的使用是否异常；AS是否异常；DB是否异常。具体到几个service，LB的HTTP
: connection pool是否使用过度，balance算法是否出现了超出设计预期；DB的
: connection pool是否使用过度，是否有table被长期锁死，或者某些query超出可容忍
: 时长，数据库硬盘是否已满，内存临时表是否过大；AS是否有异常application，具体
: 到刷新订单出问题，order.java程序是否内部有死循环，从LB接收的数据是否有
: corruption，发送到DB的数据是否正确，从DB接收的数据是否有问题，发往LB的数据是
: 否完整……具体到我熟悉的Linux+Apache+Perl+MySQL架构，在针对这个架构谈谈可能
|
b***m
发帖数: 5987 | 54
没有固定答案，目前用动态数组和hashmap都能实现。你的环怎么讲？
【在 F********9 的大作中提到】
: design一个data structure，功能类似双
: 向queue，可以从front和end两端add、peek元素，以及用index i来随机访问队列中元
: 素，所有操作都必须是O(1)。
: 这个是要构造一个环来实现么？
|
e****e
发帖数: 418 | 55 如果用hashmap 如何用index i来随机访问队列中元素？
比如AddFront(10); AddFront(20); AddFront(30), AddEnd(90), AddEnd(80), Queue
的示意图如下：
30 | 20 | 10 | 90 | 80,
这个时候怎末知道hashtable里key = 3所指向的是Node 30？ 也就是如何更新
hashtable 里的index随着AddFront and AddEnd? 或者有其它方法？
list
【在 t*********n 的大作中提到】
: 祝lz好运！
|
O******i
发帖数: 269 | 56 STL中的deque貌似是用多级vector实现的，所以可以随机访问，STL的那个实现符合要
求么？
【在 b***m 的大作中提到】
:
: 没有固定答案，目前用动态数组和hashmap都能实现。你的环怎么讲？
|
b***m
发帖数: 5987 | 57
Queue
因为只能从front和end添加和提取元素，比如0号被取走后，新的1号就变成了0号，内
部设一个变量记录起始元素的编号。
【在 e****e 的大作中提到】
: 如果用hashmap 如何用index i来随机访问队列中元素？
: 比如AddFront(10); AddFront(20); AddFront(30), AddEnd(90), AddEnd(80), Queue
: 的示意图如下：
: 30 | 20 | 10 | 90 | 80,
: 这个时候怎末知道hashtable里key = 3所指向的是Node 30？ 也就是如何更新
: hashtable 里的index随着AddFront and AddEnd? 或者有其它方法？
:
: list
|
b***m
发帖数: 5987 | 58
我对STL的那个container不是很熟悉啊。
【在 O******i 的大作中提到】
: STL中的deque貌似是用多级vector实现的，所以可以随机访问，STL的那个实现符合要
: 求么？
|
l*****a
发帖数: 14598 | 59 我也觉得你乱说，haha
【在 b***m 的大作中提到】
:
: 我对STL的那个container不是很熟悉啊。
|
b***m
发帖数: 5987 | 60
其实就是乱说。我说之前跟那面试官说了：我对这个基本不懂，我就乱说一些吧，说得
不对希望不要影响你对我面试的印象。;-)
【在 l*****a 的大作中提到】
: 我也觉得你乱说，haha
|
|
|
h**6
发帖数: 4160 | 61 今年夏天我们组专门招了个实习妹妹来写这个队列，那程序连测试好几千行。她那水平
是响当当的，return offer也不屑一顾，又接着投身于phd大业去了。 |
b***m
发帖数: 5987 | 62
那MM有追求，赞一个。
【在 h**6 的大作中提到】
: 今年夏天我们组专门招了个实习妹妹来写这个队列，那程序连测试好几千行。她那水平
: 是响当当的，return offer也不屑一顾，又接着投身于phd大业去了。
|
e****e
发帖数: 418 | 63 我是不明白如何<<"用index i来随机访问队列中元素，所有操作都必须是O(1)">>, 我
想也就是怎么更新hashtable 里的key值？比如我上面的例子，
30 | 20 | 10 | 90 | 80,
hashtable 里 key 1 指向 node 30, key 2指向node 20， key 3指向node 10,... 当
AddFront(100),之后，queue变成：
100 | 30 | 20 | 10 | 90 | 80,
这时， 我想是要更新hashtable里的key的值，key 1指向 node 100, key 2指向node
30,...
?
【在 b***m 的大作中提到】
:
: 那MM有追求，赞一个。
|
h****n
发帖数: 1093 | 64 收藏了，以后别人问我就背诵给对方听，感谢大牛哈哈
【在 b***m 的大作中提到】
:
: 那MM有追求，赞一个。
|
b***m
发帖数: 5987 | 65
key值不动。看下面的情况：
key 1 2 3 4
value A B C D
AddFront之后：
key 0 1 2 3 4
value Z A B C D
这时原来的第一个元素变成了第二个，内部用一个idStart来offset一下起始坐标就好
了。
【在 e****e 的大作中提到】
: 我是不明白如何<<"用index i来随机访问队列中元素，所有操作都必须是O(1)">>, 我
: 想也就是怎么更新hashtable 里的key值？比如我上面的例子，
: 30 | 20 | 10 | 90 | 80,
: hashtable 里 key 1 指向 node 30, key 2指向node 20， key 3指向node 10,... 当
: AddFront(100),之后，queue变成：
: 100 | 30 | 20 | 10 | 90 | 80,
: 这时， 我想是要更新hashtable里的key的值，key 1指向 node 100, key 2指向node
: 30,...
: ?
|
h****n
发帖数: 1093 | 66 我感觉他的意思是
当你insert一个数在front之后，有一个计数器就+1了，如果想找2的，你就应该用2-计
数器的那个key作为查找值
不过我感觉这个设计还是不够straight forward，没有数组那个方法好理解
【在 e****e 的大作中提到】
: 我是不明白如何<<"用index i来随机访问队列中元素，所有操作都必须是O(1)">>, 我
: 想也就是怎么更新hashtable 里的key值？比如我上面的例子，
: 30 | 20 | 10 | 90 | 80,
: hashtable 里 key 1 指向 node 30, key 2指向node 20， key 3指向node 10,... 当
: AddFront(100),之后，queue变成：
: 100 | 30 | 20 | 10 | 90 | 80,
: 这时， 我想是要更新hashtable里的key的值，key 1指向 node 100, key 2指向node
: 30,...
: ?
|
b***m
发帖数: 5987 | 67
嗯。不过面试官看懂了，也认可这个方法。这就够了。
【在 h****n 的大作中提到】
: 我感觉他的意思是
: 当你insert一个数在front之后，有一个计数器就+1了，如果想找2的，你就应该用2-计
: 数器的那个key作为查找值
: 不过我感觉这个设计还是不够straight forward，没有数组那个方法好理解
|
h****n
发帖数: 1093 | 68 最后数组那个题，我只能想到DFS+访问标记的办法，貌似效率有点低，大牛有啥好办法 |
b***m
发帖数: 5987 | 69
没啥好办法。你总得遍历一遍吧。
【在 h****n 的大作中提到】
: 最后数组那个题，我只能想到DFS+访问标记的办法，貌似效率有点低，大牛有啥好办法
|
e****e
发帖数: 418 | 70 明白了，多谢好猫!
【在 b***m 的大作中提到】
:
: 没啥好办法。你总得遍历一遍吧。
|
|
|
e****e
发帖数: 418 | 71 数组的缺点是size是fixed, 扩容的时候耗时。
【在 h****n 的大作中提到】
: 我感觉他的意思是
: 当你insert一个数在front之后，有一个计数器就+1了，如果想找2的，你就应该用2-计
: 数器的那个key作为查找值
: 不过我感觉这个设计还是不够straight forward，没有数组那个方法好理解
|
h****n
发帖数: 1093 | 72 写了最后那个，没测，大牛测测
void helper(vector > &Input, int i, int j, int n, int m)
{
if(i<0||i>n-1||j<0||j>m-1)
return;
Input[i][j] = -1;
if(i>0&&Input[i-1][j]==1)
helper(Input, i-1, j, n, m);
if(i
helper(Input, i+1, j, n, m);
if(j>0&&Input[i][j-1]==1)
helper(Input, i, j-1, n, m);
if(j
helper(Input, i, j+1, n, m);
return;
}
int GetAdjArea(vector > input)
{
int i,j;
int res = 0;
if(input.size()<1) return 0;
int n = input.size();
int m = input[0].size();
vector > copyInput(input);
for(i=0;i
for(j=0;j
if(copyInput[i][j]==1)
{
res++;
helper(copyInput, i, j, n, m);
}
return res;
}
int main()
{
vector > input;
int l1[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
vector v1(l1, l1+15);
int l2[] = {1,1,1,0,1,1,1,1,0,0,0,0,0,0,1};
vector v2(l2, l2+15);
int l3[] = {0,1,0,1,1,1,0,0,0,0,0,0,0,0,0};
vector v3(l3, l3+15);
int l4[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
vector v4(l4, l4+15);
input.push_back(v1);
input.push_back(v2);
input.push_back(v3);
input.push_back(v4);
cout<
} |
r**d
发帖数: 90 | 73 Cool + blessing!
问一下匹配题，估计你会用stack做，我在面google的时候也面的这道，不过却栽在这
，答完后问，有一种情况不work，后来说unicode 怎么办？没答后fail了
【在 b***m 的大作中提到】
: 一点儿也不传奇。就是一普通面试。如果面的是CEO职位估计能传奇点儿。废话少说，
: 上面经（题都很传统）：
: 第一轮面试是俩人，一个白人小伙子，一个印度女孩儿。写一个函数，输入是字符串，
: 输出是布尔值，判断字符串中括号的匹配，比如“()()()”、“((()))”是匹配的，“
: ()))”是不匹配的。扩展开，可以接受{}和[]，甚至任何自定义符号。写完函数后提供
: test case。
: 第二轮是个中年白人，明显是抓壮丁来的，没有技术面试，纯粹瞎扯，扯的过程中不断
: 看钟，口中念念有词这45分钟怎么打法。由于我做过10年游戏，于是跟他狂侃游戏开发
: ，包括怎么做到让游戏不crash，如何让游戏跑得更快、用更少的硬件资源。
: 第三轮是个development manager，印度人，不是HM，但是负责带我去吃中饭。我俩下
|
e****e
发帖数: 418 | 74 没看懂，说说思路先。
【在 h****n 的大作中提到】
: 写了最后那个，没测，大牛测测
: void helper(vector > &Input, int i, int j, int n, int m)
: {
: if(i<0||i>n-1||j<0||j>m-1)
: return;
:
: Input[i][j] = -1;
:
: if(i>0&&Input[i-1][j]==1)
: helper(Input, i-1, j, n, m);
|
c******t
发帖数: 391 | 75 这周五也要去onsite他家，面seller experience和MWS组，貌似和你面的是一个部门啊
。不知道能不能在面试准备上给点建议呢？
多谢！
Seller Service……我现在都不知道具体是什么。
★ Sent from iPhone App: iReader Mitbbs 7.51 - iPad Lite
【在 b***m 的大作中提到】
:
: 没啥好办法。你总得遍历一遍吧。
|
h****n
发帖数: 1093 | 76 就是DFS+访问标记
我测过了，没问题
不知道有没有不需要DFS的办法
【在 e****e 的大作中提到】
: 没看懂，说说思路先。
|
p*****2
发帖数: 21240 | 77
BFS
【在 h****n 的大作中提到】
: 就是DFS+访问标记
: 我测过了，没问题
: 不知道有没有不需要DFS的办法
|
e****e
发帖数: 418 | 78 第五题，网页上手打，没测，破转引玉。
int getNumOfAdjArea(int[][] m) {
ArrayList> list = new ArrayList>();
for ( int i = 0; i < m.length; i++ ) {
for ( int j = 0; j < m[0].length; j++ ) {
if ( m[i][j] == 1 ) {
Point point = new Point(i, j);
HashSet hashSet = containsAndMerge( list, point );
if ( hashSet != null )
hashSet.add( point );
else {
hashSet = new HashSet();
hashSet.add( point );
list.add( hashSet );
}
}
}
}
return list.size();
}
HashSet containsAndMerge( ArrayList> list, Point point ){
List foundIntersectSets = new ArrayList();
for ( HashSet hashSet : list ) {
if ( hashSet.contains( point ) )
foundIntersectSets.add(hashSet);
}
if ( foundIntersectSets.size() == 0 )
return null;
else {
list.removeAll(foundIntersectSets);
HashSet mergedSet = new HashSet();
for ( HashSet hashSet : foundIntersectSets) {
for ( Point p : hashSet )
mergedSet.add( p );
}
list.add( mergedSet);
return mergedSet;
}
}
class Point{
int i;
int j;
public Point(int i, int j) {this.i = i; this.j = j;}
public boolean equals(Point p) {
if (p.i - 1 == this.i && p.j = this.j )
return true;
if (p.i + 1 == this.i && p.j = this.j )
return true;
if (p.i == this.i && p.j - 1 = this.j )
return true;
if (p.i == this.i && p.j + 1 = this.j )
return true;
return false;
}
public boolean hashcode()...
} |
e****e
发帖数: 418 | 79 还是 BFS+标记 简单明了，写起来也不容易出错。 |
b***m
发帖数: 5987 | 80 地址是2201 Westlake Ave吗？具体该怎么准备我也说不好，个人感觉沟通的有效性和
愉快性比题做的好坏更重要吧。
【在 c******t 的大作中提到】
: 这周五也要去onsite他家，面seller experience和MWS组，貌似和你面的是一个部门啊
: 。不知道能不能在面试准备上给点建议呢？
: 多谢！
:
: Seller Service……我现在都不知道具体是什么。
: ★ Sent from iPhone App: iReader Mitbbs 7.51 - iPad Lite
|
|
|
b***m
发帖数: 5987 | 81 Unicode能有多大区别？不太明白为什么会fail？
【在 r**d 的大作中提到】
: Cool + blessing!
: 问一下匹配题，估计你会用stack做，我在面google的时候也面的这道，不过却栽在这
: ，答完后问，有一种情况不work，后来说unicode 怎么办？没答后fail了
|
b***m
发帖数: 5987 | 82 对，越到后面越耗时，所以我用hashmap。
【在 e****e 的大作中提到】
: 数组的缺点是size是fixed, 扩容的时候耗时。
|
r**d
发帖数: 90 | 83 如果不是Unicode
for(int i=0; i
{
if (str[i] == "{" || ...)stack.push(str[i]);
else ...
}
如果是Unicode,不清楚是不是two byte去存“{", 反正对方说不行
【在 b***m 的大作中提到】
: Unicode能有多大区别？不太明白为什么会fail？
|
y***u
发帖数: 174 | 84 直接上java的doubly linked hashmap吧。
【在 b***m 的大作中提到】
: 对，越到后面越耗时，所以我用hashmap。
|
y***u
发帖数: 174 | 85 面过类似的，我倒是没考虑到LB会过载的情况，不愧是老同志了。不过要考虑可能LB的
vip出错。
balance算法没啥好说的吧，出错可能性不大。
AS那边可以考虑用strace来profile一下，看看哪个API耗时最多。另外apache有个ab命
令可以查request/sec, response time之类的，挺好的，可以用来investigate。
我当时说的其他可能的几个corner case是，一个是有没有用cache。如果某个新的
cache server上线，去这个server的request会有大量的cache miss。
另外还扯了一点怎么增速，比如说把动态内容变成静态啊，用memcache啊，或者利用
cache避免重复编译什么的。其他想不到了。。
【在 b***m 的大作中提到】
: 对，越到后面越耗时，所以我用hashmap。
|
y***u
发帖数: 174 | 86 写了一下next successor: O(1) space, O(lgN) time。
Node getNextSuccessor(Node root, Node node){
if(root==null || node == null){
return null;
}
Node pre = null;
while(root!=null && root!=node){
if(root.val > node.val){
// go left
pre = root;
root = root.left;
}else if(root.val < node.val){
// right
root = root.right;
}else{
//found
if(node.right!=null){
node = node.right;
while(node.left!=null){
node = node.left;
}
return node;
}else{
return pre;
}
}
}
// node not found
return null;
}
【在 b***m 的大作中提到】
: 对了，第四个女烙印还考了一道找BST的next successor。
|
z********i
发帖数: 568 | 87 只用一个counter保存尚未匹配的‘（'，也行吧？
例子： （ （ （ ） （ ） ） ）
counter 1 2 3 2 3 2 1 0
"
【在 c******t 的大作中提到】
: 感谢分享！
: 第一轮算括号的题，想到两种解法，用counter算左右括号数，以及压栈比较。
: //For '(,)' only, use counter, left and right are half of length, e.g. for "
: (())", the call
: is validParen(2,2,"(())",0).
: public static boolean validParen(int left, int right, String str, int
: index){
: if(left==0&&right==0)return true; //base case
: if(str.length()%2==1)return false; //length must be even
: if(left>right)return false;
|
b***m
发帖数: 5987 | 88 可，但是只能用于单一类型括号。
【在 z********i 的大作中提到】
: 只用一个counter保存尚未匹配的‘（'，也行吧？
: 例子： （ （ （ ） （ ） ） ）
: counter 1 2 3 2 3 2 1 0
:
: "
|
c******t
发帖数: 391 | 89 对啊，是在那啥Vaezer Office的五楼。看schedule上写的，半数interviewer都是烙印
，很紧张啊……
【在 b***m 的大作中提到】
: 地址是2201 Westlake Ave吗？具体该怎么准备我也说不好，个人感觉沟通的有效性和
: 愉快性比题做的好坏更重要吧。
|
b***m
发帖数: 5987 | 90
紧张就该坏菜了。昨天面我的人，半数白人半数烙印，感觉烙印还比较友善。是不是夸
夸他们，总会有点儿用的。
【在 c******t 的大作中提到】
: 对啊，是在那啥Vaezer Office的五楼。看schedule上写的，半数interviewer都是烙印
: ，很紧张啊……
|
